Consider the binary relation: S = {(x,y) | y = x+1 and y in {0,1,2}}. The reflexive closure is S. The reflexive transiti...

Question

Consider the binary relation: S = {(x,y) | y = x+1 and y in {0,1,2}}. The reflexive closure is S. The reflexive transitive closure of S is A. {(x,y) | y > x and y in {0,1,2}} B. {(x,y) | y >= x and y in {0,1,2}} C. {(x,y) | y < x and y in {0,1,2}} D. {(x,y) | y <= x and y in {0,1,2}}

Accepted Answer

B. {(x,y) | y >= x and y in {0,1,2}} The relation S contains pairs where y is exactly one more than x, restricted to y in {0,1,2}. So S = {(-1,0),(0,1),(1,2)}. The reflexive transitive closure (R*) first adds all reflexive pairs (z,z) for z in the universe, then closes under transitivity. Since y is restricted to {0,1,2}, the universe contains {0,1,2} plus x-values {-1,0,1}. Adding reflexive pairs (0,0),(1,1),(2,2) and computing all transitive compositions gives exactly all pairs (x,y) where y >= x and y in {0,1,2}.