Am I correct about the transitive closure of this relation?

250 Views Asked by At

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.

1

There are 1 best solutions below

6
On

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.