Consider the binary relation: S = {(x, y) | y = x+1 and x, y ∈ {0, 1, 2, ...}}…
2004
Consider the binary relation:
S = {(x, y) | y = x+1 and x, y ∈ {0, 1, 2, ...}}The reflexive transitive closure of S is
- A.
{(x, y) | y > x and x, y ∈ {0, 1, 2, ... }}
- B.
{(x, y) | y ≥ x and x, y ∈ {0, 1, 2, ... }}
- C.
{(x, y) | y < x and x, y ∈ {0, 1, 2, ... }}
- D.
{(x, y) | y ≤ x and x, y ∈ {0, 1, 2, ... }}
Attempted by 231 students.
Show answer & explanation
Correct answer: B
Correct relation: {(x, y) | y ≥ x and x, y ∈ {0, 1, 2, ...}}
Reason:
The given relation contains exactly pairs of the form (x, x+1).
By transitivity, composing n such steps yields pairs (x, x+n) for any positive integer n.
Adding reflexivity includes the case n = 0, i.e., the pairs (x, x).
Therefore the reflexive transitive closure contains exactly those pairs where y = x + n for some integer n ≥ 0, which is equivalent to y ≥ x.
Example: (0,3) is in the closure via (0,1),(1,2),(2,3); (2,2) is included by reflexivity.