# equivalence relation and sets

The question:

Let $X$ and $Y$ be two sets, and let $S$ be an equivalence relation on set $X$ and $T$ be an equivalence relation on set $Y$. Define a relation $R$ on $X ×Y$ by $(a,b)R(c,d)$ if and only if $aSc$ and $bTd$.

Prove that $R$ is an equivalence relation on $X × Y$

The confusion:

I understand that I need to show that: reflexive, symmetric, and transitive properties hold in order for this to be an equivalence relation, but I don't understand what is in the two sets which from what I gather is the hard point of the problem. Then again even if I did know what was in each set, likely I still would need help showing the 3 properties hold. Then again this is my first problem of this sort so... Anyhow, would $X$={a,b} and $Y$={c,d}? That's about as far as I can go which likely is also wrong. Any help greatly appreciated. Thanks.

• Hint: the equivalence classes of the induced relation on $X\times Y$ will be all sets $[x]_S \times [y]_T$ for $x\in X, y\in Y$, i.e. all products of equivalence classes in $X/S$ and $Y/T$. – BrianO Apr 11 '16 at 2:52

## 1 Answer

Reflexive: Take $(x,y)\in X \times Y$, since S and T are reflexive $xSx$ and $yTy$, therefore $(x,y)R(x,y)$.

Transitive: Let $(x_1,y_1)R(x_2,y_2)$ and $(x_2,y_2)R(x_3,y_3)$. Then by definition of R we have $x_1 S x_2$, $x_2 S x_3$, $y_1 T y_2$ and $y_2 T y_3$. But since S and T are transitive we have $x_1 S x_3$ and $y_1 T y_3$. Therefore $(x_1,y_1)R(x_3,y_3)$, hence R is transitive.

Symmetric: Let $(x_1,y_1)R(x_2,y_2)$, then by definition of R we have $x_1 S x_2$, $y_1 T y_2$. Since S and T are symmetric we have $x_2 S x_1$, and $y_2 T y_1$. Therefore we have $(x_2,y_2)R(x_1,y_1)$, hence it is symmetric.

• Thank you so much! Now this makes so much more sense. I was really confused by how this is written to express what R is really representing. The way you made transitivity work is super awesome. I would not have known to do that. It helped to really look at and understand the other 2 properties and then get the transitive one. – billyredface88 Apr 11 '16 at 3:20