Let R = {(1,2), (2,3), (3,4)} on the set {1,2,3,4}. Which set of new pairs must be added to R to form its transitive closure R⁺?
AOnly (1,3) — one level of transitivity is sufficient
BOnly (2,4) — only the last indirect pair is missing
C(1,3), (2,4), and (1,4) — all pairs reachable by a directed path
DNo new pairs — R is already transitive
The transitive closure adds every pair (a,b) for which there is a directed path of any length from a to b. From 1 you can reach 3 via 2 (path length 2), reach 4 via 2→3 (length 3). From 2 you can reach 4 via 3 (length 2). So (1,3), (1,4), and (2,4) are all added. The common error in option A is stopping after one application of transitivity — you must follow all possible paths, not just length-2 ones.
Question 2 Multiple Choice
Which statement best describes what it means for (a, b) to be in the transitive closure R⁺?
A(a, b) is already in R
BThere exists a single intermediate element c such that (a,c) ∈ R and (c,b) ∈ R
CThere exists a directed path of one or more edges from a to b in the directed graph of R
DThere exists a directed path of exactly two edges from a to b in the directed graph of R
(a,b) ∈ R⁺ means you can get from a to b by following edges of R in one or more steps — a path of any positive length. Option B only captures paths of length exactly 2; option D says exactly 2 edges. Both miss longer paths. The transitive closure captures all reachable pairs, not just those with a single common intermediate.
Question 3 True / False
If (a,b) ∈ R and (b,c) ∈ R and (c,d) ∈ R, then (a,d) is in the transitive closure R⁺.
TTrue
FFalse
Answer: True
The path a→b→c→d has length 3, meaning there is a directed path from a to d in the graph of R. Therefore (a,d) ∈ R⁺ by definition — the transitive closure includes all pairs reachable by any path of any length, not just length 2.
Question 4 True / False
The transitive closure R⁺ of a relation R typically contains strictly more pairs than R itself.
TTrue
FFalse
Answer: False
If R is already transitive, then R⁺ = R — no new pairs need to be added. For example, R = {(1,1), (2,2)} is transitive (no pairs of the form (a,b),(b,c) exist to require a new (a,c)), so its transitive closure equals R itself. R⁺ contains *at least* the pairs in R, but may add nothing if R is already transitive.
Question 5 Short Answer
Explain why computing the transitive closure of a relation is equivalent to solving the reachability problem in a directed graph.
Think about your answer, then reveal below.
Model answer: Represent the relation R as a directed graph: nodes are elements of the set, and draw an edge from a to b for each (a,b) ∈ R. Then (a,b) ∈ R⁺ if and only if b is reachable from a by following directed edges. The transitive closure is exactly the set of all reachable pairs — so any algorithm that computes reachability (DFS/BFS from each node, or Warshall's algorithm via matrix operations) computes the transitive closure.
The graph interpretation transforms an abstract algebraic operation into a concrete path-finding problem. DFS from a node a visits all nodes reachable from a; the resulting pairs (a, visited_node) are exactly the transitive closure entries involving a as the first element.