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$.)