If $X,Y$ are equivalence relations, so is $X \times Y$

Question

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$.

I am trying to self learn these topics. I do know what an equivalence relation is. I wanted to know how would someone prove that $X\times Y$ be an equivalence relation?

Answer 1

I will assume that $X$ is an equivalence relation on some set $A$, and $Y$ is an equivalence relation on some set $B$. It appears, then, that we’re being asked to prove that $X\times Y$ is an equivalence relation on $A\times B$.

Technically this isn’t actually true: a relation on $A\times B$ is a subset of $(A\times B)\times(A\times B)$, while $X\times Y$ is a subset of $(A\times A)\times(B\times B)$, and

$$(A\times B)\times(A\times B)\tag{1}$$

and

$$(A\times A)\times(B\times B)\tag{2}$$

are not the same set. Elements of $(1)$ have the form $\big\langle\langle a_1,b_1\rangle,\langle a_2,b_2\rangle\big\rangle$, where $a_1,a_2\in A$ and $b_1,b_2\in B$, while elements of $(2)$ have the form $\big\langle\langle a_1,a_2\rangle,\langle b_1,b_2\rangle\big\rangle$, where again $a_1,a_2\in A$ and $b_1,b_2\in B$. However, there is a natural correspondence between the sets $(1)$ and $(2)$, the one that matches the element

$$\big\langle\langle a_1,b_1\rangle,\langle a_2,b_2\rangle\big\rangle\in(A\times B)\times(A\times B)$$

with the element

$$\big\langle\langle a_1,a_2\rangle,\langle b_1,b_2\rangle\big\rangle\in(A\times A)\times(B\times B)\;;$$

if this theorem is taken from a book or set of notes, I imagine that the author is silently (and sloppily) expecting us to use this correspondence to treat $(1)$ and $(2)$ as if they were the same set. (If that’s not the case, then the question simply does not make sense at all.) I will use the equivalence explicitly.

To be precise, let

$$R=\left\{\big\langle\langle a_1,b_1\rangle,\langle a_2,b_2\rangle\big\rangle:\big\langle\langle a_1,a_2\rangle,\langle b_1,b_2\rangle\big\rangle\in X\times Y\right\}\;;\tag{3}$$

we want to show that $R$ is an equivalence relation on $A\times B$, i.e., that $R$ is reflexive, symmetric, and transitive.

Reflexivity: We must show that for each $\langle a,b\rangle\in A\times B$, $\big\langle\langle a,b\rangle,\langle a,b\rangle\big\rangle\in R$.

Let $\langle a,b\rangle\in A\times B$. Then $a\in A$, and $X$ is reflexive, so $\langle a,a\rangle\in X$. Similarly, $b\in B$, and $Y$ is reflexive, so $\langle b,b\rangle\in Y$. But then $\big\langle\langle a,\color{brown}a\rangle,\langle\color{green}b,\color{purple}b\rangle\big\rangle\in X\times Y$, and therefore

$$\big\langle\langle a,\color{green}b\rangle,\langle\color{brown}a,\color{purple}b\rangle\big\rangle\in R$$

by $(3)$.

Symmetry: Suppose that $\big\langle\langle a_1,b_1\rangle,\langle a_2,b_2\rangle\big\rangle\in R$: we need to show that $\big\langle\langle a_2,b_2\rangle,\langle a_1,b_1\rangle\big\rangle\in R$ as well.

Since $\big\langle\langle a_1,b_1\rangle,\langle a_2,b_2\rangle\big\rangle\in R$, $(3)$ tells us that $\big\langle\langle a_1,a_2\rangle,\langle b_1,b_2\rangle\big\rangle\in X\times Y$ and hence that $\langle a_1,a_2\rangle\in X$ and $\langle b_1,b_2\rangle\in Y$. But $X$ and $Y$, being equivalence relations, are symmetric by hypothesis, so $\langle a_2,a_1\rangle\in X$ and $\langle b_2,b_1\rangle\in Y$. Thus, $\big\langle\langle a_2,a_1\rangle,\langle b_2,b_1\rangle\big\rangle\in X\times Y$, and by applying $(3)$ again we see that

$$\big\langle\langle a_2,b_2\rangle,\langle a_1,b_1\rangle\big\rangle\in R\;,$$

as desired.

Transitivity: Suppose that $\big\langle\langle a_1,b_1\rangle,\langle a_2,b_2\rangle\big\rangle\in R$ and $\big\langle\langle a_2,b_2\rangle,\langle a_3,b_3\rangle\big\rangle\in R$; we want to show that $\big\langle\langle a_1,b_1\rangle,\langle a_3,b_3\rangle\big\rangle\in R$.

As before, we know from $(3)$ that $\langle a_1,a_2\rangle\in X$ and $\langle b_1,b_2\rangle\in Y$. Similarly, applying $(3)$ to the hypothesis that $\big\langle\langle a_2,b_2\rangle,\langle a_3,b_3\rangle\big\rangle\in R$, we find that $\langle a_2,a_3\rangle\in X$ and $\langle b_2,b_3\rangle\in Y$. Being an equivalence relation, $X$ is transitive, and we have $\langle a_1,a_2\rangle\in X$ and $\langle a_2,a_3\rangle\in X$, so $\langle a_1,a_3\rangle\in X$. $Y$ is also transitive, so a completely similar argument shows that $\langle b_1,b_3\rangle\in Y$. Thus, $\big\langle\langle a_1,a_3\rangle,\langle a_3,b_3\rangle\big\rangle\in X\times Y$, and $(3)$ tells us that

$$\big\langle\langle a_1,b_1\rangle,\langle a_3,b_3\rangle\big\rangle\in R\;,$$

just as we wanted.

Since $R$ is a reflexive, symmetric, and transitive relation on $A\times B$, it is by definition an equivalence relation on $A\times B$. And as we saw above, there is a natural equivalence — technically, a bijection — between $R$ and $X\times Y$; if we (sloppily) pretend that the equivalence is actually an identity, we can say that $X\times Y$ is an equivalence relation on $A\times B$. (I myself would not do so, especially in an introductory course: that kind of sloppiness is more confusing than helpful until one really understands the basics of set theory.)