0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ OK, I got (1-9-4), (2-5-8-6) and (3-7) from the first Q. Why am I doing Q2? Based on my study materials, I should carry on up to Q4. Why do I need to do that? $\endgroup$ – imre Dec 16 '13 at 16:54
  • $\begingroup$ uhm, Just look at the natural cycles that are formed. Once you extend them you will get that the relation inside those cycles is complete except for the reflexive cases. $\endgroup$ – Jorge Fernández Hidalgo Dec 16 '13 at 16:56
  • $\begingroup$ I extended my question with the solution from my materials. Could you please take a look? $\endgroup$ – imre Dec 16 '13 at 17:02
  • $\begingroup$ Thanks, I'm gonna read this a few more times to actually get it. Thanks :) $\endgroup$ – imre Dec 16 '13 at 17:29
  • $\begingroup$ You can think of any relation as a directed graph where the edge (a,b) is an edge on the graph if (a,b) is an element in the relation. Then the transitive closure of the same vertex looks like the graph where (x,y) is connected if and only if (x,y) are connected, also (x,x) is an element if and only if x is inside a directed cycle inside the graph. $\endgroup$ – Jorge Fernández Hidalgo Dec 16 '13 at 17:33

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.