Let S = {0,1,2,4,6}. Find the reflexive closure, symmetric closure, and transiti

Question

Let S = {0,1,2,4,6}. Find the reflexive closure, symmetric closure, and transitive closure of the following binary relation R: R={(0,1),(1,0),(2,4),(4,2),(4,6),(6,4)}

For Reflexive closue I have: R = {(0,0),(0,1),(1,0),(2,2),(2,4),(4,2),(4,4),(4,6),(6,4),(6,6)}
For Symmetric closure I have: Binary relation R is symmetric
For Transitive closure I have: R = {(0,0),(0,1),(1,0),(2,2),(2,4),(4,2),(4,4),(4,6),(6,4),(6,6)}

I believe I am reight for the reflexive and symmetric closures but am unsure about the transitive closure.

Please help :)

Explanation / Answer

Well I see, you are right about only symmetric closure, but not in terms of reflexive and transitive ones yet very close.

Given S = {0,1,2,4,6} and the binary relation R={(0,1),(1,0),(2,4),(4,2),(4,6),(6,4)}

Now, let us find the three closures for the relation one by one.

1) Reflexive closure: It’s the easiest one. For each element in the set, just add a self loop in the relation if not present already.

So, for reflexive closure, you will have R’ = R U {(0, 0), (1, 1), (2, 2), (4, 4), (6, 6)}

Or as you have written it R’ ={0, 0), (0,1), (1,0), (1,1), (2,2), (2,4), (4,2), (4,4), (4,6), (6,4), (6,6)}

So you see, you were close, you just missed (1, 1).

2) Symmetric Closure: Well, it’s also easy. What you have to do is, for each arc in the relation, you have to put a reverse arc, if not present already.

e.g. if (1,2) is there in a relation, there must be a (2,1) also.

Now the given relation R satisfies this closure, so you are absolutely correct there.

3) Transitive Closure: It’s also not difficult, just a little tricky. You can do draw a directed graph from the given relation. I have drawn one for your reference. The solid lines represent the arcs given in the relation. The dotted lines represent the arcs for transitive closure.

If a node can be reached from another node through an indirect path, draw a direct arc there.

i.e. if (x, y) and (y, z) is there, then you put (x, z) also there to make it transitive.

So, R’ = R U {(0, 0), (1, 1), (2, 2), (2, 6), (4, 4), (6, 2), (6, 6)}

Or R’ = {(0, 0), (0,1), (1,0), (1,1), (2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6)}

So you had missed (1, 1), (2,6) and (6,2) there.

You need to put (2, 6) there because 2->4 is there and 4->6 is there, so 6 can be reached from 2. Similarly for (6, 2)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.