1
$\begingroup$

Transitive closure given by relation $A$ is?

$A = \{ (1,2) , (2,3) , (3,4) , (3,1), (4,3)\}$

My answer:

We have $(1,2)$ and $(2,3)$ gives $(1,3)$

moreover, $(1,3)$ and $(3,1)$ gives $(1,1)$,

$(1,3)$ and $(3,4)$ gives $(1,4)$

We have $(2,3)$ and $(3,4)$ gives $(2,4)$, $(2,4)$ and $(4,3)$ gives $(2,3)$

We have $(2,3)$ and $(3,1)$ gives $(2,1)$

$(2,1)$ and $(1,2)$ gives $(2,2)$

We have $(3,4)$ and $(4,3)$ gives $(3,3)$

We have $(3,1)$ and $(1,2)$ gives $(3,2)$

We have $(4,3)$ and $(3,1)$ gives $(4,1)$

We have $(4,3)$ and $(3,4)$ gives $(4,4)$ ,

So Transitive closure given by relation $A$ is given by

$\{ (1,1),(1,2) ,(1,3),(1,4) ,(2,1),(2,2),(2,3) ,(2,4), (3,1) , (3,2),(3,3),(3,4), (4,1),(4,2),(4,3),(4,4)\}$

Now my question is, am I correct? My friend said I was incorrect but I do not know what is wrong with my answer. If anyone can point out why I'm wrong, it would be appreciated.

$\endgroup$
1
$\begingroup$

Your conclusion is correct, but your proof is not.

You showed that $(2,3)$ is an element of the transitive closure of $A,$ but this is not necessary, since $(2,3)\in A.$ You didn't show that $(4,2)$ is an element of the transitive closure of $A,$ but it is.

$\endgroup$
  • $\begingroup$ so what is necessary to change in my proof? $\endgroup$ – Robert Miller Apr 6 '17 at 23:49
  • $\begingroup$ you are saying that i am missing (4,2)? $\endgroup$ – Robert Miller Apr 6 '17 at 23:49
  • $\begingroup$ Yes. Remove the redundant justification, and add the missing justification. Can you see why $(4,2)$ is in the transitive closure of $A$? $\endgroup$ – Cameron Buie Apr 6 '17 at 23:50
  • $\begingroup$ no clue on how you got (4,2) $\endgroup$ – Robert Miller Apr 6 '17 at 23:52
  • $\begingroup$ Just keep doing the same kind of thing you've been doing. There are multiple ways to get there. There are $3$ ways, to be exact. $\endgroup$ – Cameron Buie Apr 6 '17 at 23:55

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.