On the set X = {1,2,3,4,5,6,7,8,9}, there is binary relation Q = {(1,9),(2,5),(3,7),(4,1),(5,8),(6,2),(7,3),(8,6),(9,4)}. Make a transitive closure T of the relation Q. Decide and prove whether the relation T is an equivalence on X.
If yes, write out the partition belonging to this equivalence. If not, find the partition belonging to the least equivalence which contains the relation T. Also state how many classes does the partition have.
Could you please help me understand the way this is solved?
This is the solution I have in my study materials:
Q = {(1,9),(9,4),(4,1),(2,5),(5,8),(8,6),(6,2),(3,7),(7,3)}
Q2 = {(1,4),(9,1),(4,9),(2,8),(5,6),(8,2),(6,5),(3,3),(7,7)}
Q3 = {(1,1),(4,4),(9,4),(6,8),(2,6),(5,2),(8,5),(3,7),(7,3)}
Q4 = {(1,9),(9,4),(4,1),(2,2),(5,5),(6,6),(8,8),(3,3),(7,7)}
T = {(1,1),(4,4),(4,9),(1,4),(1,9),(4,1),(4,9),(9,1),(9,4),(2,2),(5,5),(6,6),(8,8),(2,8),(2,5),(2,6),(5,2),(5,6),(5,8),(6,2),(6,5),(6,8),(8,2),(8,5),(8,6),(3,3),(7,7),(3,7),(7,3)} = T-1
Which means T is symmetric and reflexive, because X = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9)}. As a transitive closure T is transitive -> therefore it is an equivalence.
I don't like how it is written in your solution, it seems kind of tedious. I propose the following. First identify we have
$(1,9),(9,4),(4,1)$. We also have $(2,5),(5,8),(8,6),(6,2)$. And finally $(3,7),(7,3)$
Now the transitive closure of the relation Q is the minimal relation that contains all of the pairs in Q but also satisfies transitivity.
We are going to prove that this closure is precisely the relation where (x,y) are related if and only if ${x,y}$ is a subset of $\{ 1,9,4 \}$,$\{2,5,8,6\}$ or $\{3,7\}$.
To prove this it suffices to prove that the relations of this subset are required for transitivity to occur.
To see why think of the relations within your cycle as a directed cycle. Now see that directed cycles are strongly connected components and that they have a path from $y$ to $y$ for any vertex $y$. (which also satisfies reflexivity).
Therefore what you have is an equivalence relation.