I´ve come across a problem regarding relation composition. The task is to show, whether a composition of two equivalence relations on a set X is again an equivalence on the set X.

I´ve tried some graphical solutions for some examples but I am not sure how to show this generally.
We know an equivalence must be symmetric, transitive and reflexive but how can I prove that it all applies in this situation? I believe I can manage to show this for a relation intersection but for the composition I donť know how.

I don´t really need a formal proof whether it is true or not, some graphical illustration of the general principle would suffice as I am just trying to understand this.

Thank you.


There isn't really a general principle, because the general statement is false, although for some equivalence relations the composition is an equivalence relation (e.g. if both are the identity). What you need is a counterexample to show that the statement isn't always true.

Consider two equivalence relations on $\{1,2,3\}$ given by their partitions as follows: $$ A/R = \{\{1,2\}, \{3\}\} \\ A/S = \{\{1\}, \{2,3\}\} $$ Then $S\circ R$ is not symmetric: $1(S\circ R)3$ because $1R2$ and $2S3$, but not $3(S\circ R)1$. (If $3(S\circ R)1$, there would be some $x$ such that $3Rx$ and $xS1$. But $xS1$ implies $x=1$; however, not $3R1$. So there's no such $x$.)

For an example where the composition fails to be transitive: Consider $A = \{1,2,3,4\}$, and let the two equivalence relations $R,S$ be given by their partitions: $$ A/R = \{\{1,2\}, \{3,4\}\} \\ A/S = \{\{1,2,3\}, \{4\}\} \\ $$ Then $(S\circ R)$ isn't transitive: $1(S\circ R)3$ because $1R1$ and $1S3$, and $3 (S\circ R) 4$ because $3R4$ and $4S4$; but $(1,4) \notin (S\circ R)$. (If it were, there would be some $x$ such that $1Rx$ and $xS4$, but by inspection there's no such $x$.)


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.