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

Question

Accepted Answer

The transitive closure is {(i,j) : 1 <= i < j <= 5} = {(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}, a set of 10 pairs. The given relation forms a directed chain 1 -> 2 -> 3 -> 4 -> 5. The transitive closure adds all pairs (i,j) that are reachable by following the chain: you can go from 1 to 2, 3, 4, or 5; from 2 to 3, 4, or 5; etc. This gives all pairs (i,j) with i < j. There are C(5,2) = 10 such pairs.