I'm given two equivalence relations $E_1$ and $E_2$ over a set A and need to show whether the composition $E_1 \circ E_2$ is reflexive, symmetric and transitive.

I only managed to show that $E_1 \circ E_2$ is reflexive, but I'm struggling with symmetry and transitivity.

Let $(x,z)\in E_1 \circ E_2$ be arbitrary. Then it follows that $\exists y\in A : xE_1y \wedge yE_2z$.

Since $E_1$ and $E_2$ are reflexive: $xE_1x$ and $zE_2z$. Then $y=x$, so that $xE_1x$ and $y=z$, so that $zE_2z$, leads to $x=z$ and therefore $E_1 \circ E_2$ is reflexive.

For the symmetry property, I would need: $xE_1\circ E_2y => yE_1\circ E_2x$.

Let $(x,y) \in E_1\circ E_2$ be arbitrary. It follows $\exists z \in A : xE_1z \wedge zE_2y$. But now I was unable to find a way to show that $yE_1\circ E_2x$ by applying the properties of $E_1$ and $E_2$, but also couldn't show that it was not symmetric.

I had the same problem with the transitive property.

  • $\begingroup$ What do you mean by $E_1 \circ E_2$? $\endgroup$ – Babai Dec 30 '13 at 13:10
  • $\begingroup$ It's the composition of the relations $E_1$ and $E_2$. $\endgroup$ – eager2learn Dec 30 '13 at 13:15
  • $\begingroup$ Conceptually, a useful way of understanding equivalence relations, is that it categorizes a set according to some "property". For example, if you have a set of toys sorting them according to their color could be seen as an equivalence relation. Now, after you have sorted the toys according to color, you could sort each set of similarly colored toys according to material (wood, plastic, metal); so the end result is then that the toys are sorted into subsets where toys of the same color AND material comprise a particular subset. The composition results in a "sorting" by two characteristics. $\endgroup$ – Christiaan Hattingh Dec 30 '13 at 13:34
  • $\begingroup$ @ChristiaanHattingh That would be the intersection of two equivalence relations, not their composition. $\endgroup$ – Arnaud D. Dec 13 '17 at 9:19

$E_1\circ E_2$ is not necessarily an equivalence relation. Let $A = \{x,y,z\}$, $E_1$ be given by the equivalence classes $\{x,y\}$ and $\{z\}$ and $E_2$ be given by the equivalence classes $\{x\}$ and $\{y,z\}$.

Then $(x,z) \in E_1\circ E_2$, since $(x,y)\in E_1$ and $(y,z)\in E_2$. However, $z$ is connected in $E_1$ only to itself, and $x$ is connected in $E_2$ only to itself. Hence you won't be able to find some $y$ such that both $(z,y)\in E_1$ and $(y,x)\in E_2$.

Moreover, your writing of the reflexivity proof isn't correct. You shouldn't "pick $(x,z)\in E_1\circ E_2$ arbitrary", because you cannot deduce what is $y$ as you did once it is given. It is indeed reflexive, but the way of proving it is to state that taking $y:=x$ indeed statisfies the defining formula of $E_1\circ E_2$.

  • $\begingroup$ Thanks for your answer. I don't understand the last part though. If I take $y := x$, I would get $xE_1x \wedge xE_2z$, how can this be used to show that $x=z$? $\endgroup$ – eager2learn Dec 30 '13 at 13:18
  • $\begingroup$ Nevermind, I think by using $zE_2x$, we can imply that $x=z$. $\endgroup$ – eager2learn Dec 30 '13 at 13:20
  • 1
    $\begingroup$ You cannot imply that $x=z$, because that would mean that $x(E_1\circ E_2)z \Rightarrow x=z$, which is false. Don't overthink it, simply the fact that $xE_1 x$ and $xE_2 x$ implies $x(E_1\circ E_2)x$, there's no $z$ in that story. $\endgroup$ – zarathustra Dec 30 '13 at 13:41

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.