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 Answer 1

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$
6
  • $\begingroup$ so what is necessary to change in my proof? $\endgroup$ Apr 6, 2017 at 23:49
  • $\begingroup$ you are saying that i am missing (4,2)? $\endgroup$ Apr 6, 2017 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$ Apr 6, 2017 at 23:50
  • $\begingroup$ no clue on how you got (4,2) $\endgroup$ Apr 6, 2017 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$ Apr 6, 2017 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.