Let $R$ be an equivalence relation on $A$ and let $S$ be an equivalence relation on $B$. Define a $T$ on $ A \times B$ by $((a_1,b_1),(a_2,b_2)) \in T \leftrightarrow (a_1,a_2) \in R$ and $(b_1,b_2) \in S$. Prove that $T$ is an equivalence relation.

My attempt:

We need to prove that $T$ is an equivalence relation.

Definition 6.2.3 states that $R$ is an equivalence relation if $R$ is reflexive, symmetric, and transitive.

R is reflexive if $(\forall x \in S)(x,x) \in R]$

R is symmetric if $(\forall x,y \in S)[(x,y) \in R \rightarrow (y,x) \in R]$

R is transitive if $(\forall x, y, z \in S)[((x,y) \in R \land (y,z) \in R) \rightarrow (x,z) \in R]$

What if we let $x = (a_1,b_1), y = (a_2,b_2),$ and $z=(a_3,b_3)$?

For $T$ to be reflexive, we need $(\forall (a_1),(b_1) \in S)[((a_1,b_1),(a_1,b_1)) \in T $

For all $T$ to be symmetric, we need $(\forall (a_1,b_1),(a_2,b_2) \in S)[(a_1,b_1),(a_2,b_2) \in T \rightarrow (a_2,b_2),(a_1,b_1) \in T$

For all $T$ to be transitive, we need $(\forall (a_1,b_1),(a_2,b_2),(a_3,b_3) \in S]((a_1,b_1),(a_2,b_2) \in T \land ((a_2,b_2),(a_3,b_3)) \in T \rightarrow ((a_1,b_1), (a_3,b_3)) \in T$

We have proven that $T$ is an equivalence relation.

I'm not sure if I did this correctly, but the problem did ask to prove that $T$ is an equivalence relation and the definition fits perfectly. I don't know if there's some other fancy thing that I need to do or is that it?


1 Answer 1


I think you may need some further justification -- that is, it seems as though you're stating what you need to be true and not why it is true. (Of course, this may also be me misunderstanding your notation.)

For example:

Let $\sim_{T}, \sim_{R}, \sim_{S}$ denote relation by $T,R$ and $S$, respectively.

To show $T$ is reflexive, we must have $(a,b) \sim_{T} (a,b)$ for all $(a,b) \in A \times B$. Because $R$ and $S$ are both equivalence relations [hence reflexive], we have that $a \sim_{R} a$ for all $a \in A$ and $b \sim_{S} b$ for all $b \in B$. Then $(a,b) \sim_{T} (a,b)$ for all $(a,b) \in A \times B$.

Now, suppose that $(a_{1},b_{1}) \sim_{T} (a_{2},b_{2})$. Because $R$ is symmetric, $a_{1} \sim_{R} a_{2}$ implies $a_{2} \sim_{R} a_{1}$ for all $a_{1},a_{2} \in A$. Likewise, $b_{1} \sim_{S} b_{2}$ implies $b_{2} \sim_{S} b_{1}$ for all $b_{1},b_{2} \in B$. Hence $(a_{2},b_{2}) \sim_{T} (a_{1},b_{1})$ and $T$ is symmetric.

Finally, suppose that $(a_{1},b_{1}) \sim_{T} (a_{2},b_{2})$ and $(a_{2},b_{2}) \sim_{T} (a_{3},b_{3})$. By transitivity of $R$, $a_{1} \sim_{R} a_{2}$ and $a_{2} \sim_{R} a_{3}$ implies $a_{1} \sim_{R} a_{3}$ for all $a_{1},a_{2},a_{3} \in A$. Similarly, due to transitivity of $S$ we have that $b_{1} \sim_{S} b_{2}$ and $b_{2} \sim_{S} b_{3}$ implies $b_{1} \sim_{S} b_{3}$ for all $b_{1},b_{2},b_{3} \in B$. Thus $(a_{1},b_{1}) \sim_{T} (a_{3},b_{3})$ and $T$ is transitive, hence an equivalence relation on $A \times B$.

There isn't anything fancy, as you said, but it's a matter of unpacking definitions. I'm not sure if the above is the sort of format you're looking for, but I thought I'd write things out explicitly with words rather than symbols.

  • $\begingroup$ yes this helps a lot... I should've expanded on top of what I've written. $\endgroup$
    – usukidoll
    Feb 24, 2014 at 3:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .