Question

The transitive closure of the relation {(0,1), (1,2), (2,2), (3,4), (5,3), (5,4)}  on the set {1, 2, 3, 4, 5}        is _______

(a) {(0,1), (1,2), (2,2), (3,4)}

(b) {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}

(c) {(0,1), (1,1), (2,2), (5,3), (5,4)}

(d) {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}

This question was addressed to me in exam.

My doubt is from Closure on Relations topic in division Relations of Discrete Mathematics

Answer 1

Correct choice is (d) {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}

Easiest explanation: Let R be a relation on a set A. The connectivity relation on R* consists of pairs (a,b) such that there is a path of length at least one from a to b in R. Mathematically, R* = R^1  ∪ R^2  ∪ R^3 ∪ … ∪ R^n. Hence the answer is {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}.