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$ Commented Apr 6, 2017 at 23:49
  • $\begingroup$ you are saying that i am missing (4,2)? $\endgroup$ Commented 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$ Commented Apr 6, 2017 at 23:50
  • $\begingroup$ no clue on how you got (4,2) $\endgroup$ Commented 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$ Commented Apr 6, 2017 at 23:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .