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.

  • $\begingroup$ 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$. $\endgroup$ – BrianO Apr 11 '16 at 2:52

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.

  • $\begingroup$ 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. $\endgroup$ – billyredface88 Apr 11 '16 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.