Question

Consider the binary relation:
$S=\left\{\right(x,y)|y=x+1\text{and}x,yϵ\{0,1,2,\dots \dots \left\}\right\}$
The reflexive transitive closure of $S$ is

• A. $\left\{\right(x,y)|y>x\text{and}x,yϵ\{0,1,2\left\}\right\}$
• B. $\left\{\right(x,y)|y\ge x\text{and}x,yϵ\{0,1,2\left\}\right\}$
• C. $\left\{\right(x,y)|y<x\text{and}x,yϵ\{0,1,2\left\}\right\}$
• D. $\left\{\right(x,y)|y\le x\text{and}x,yϵ\{0,1,2\left\}\right\}$

Answer 1

The correct option is B $\left\{\right(x,y)|y\ge x\text{and}x,yϵ\{0,1,2\left\}\right\}$

$S=(x,y)|y=x+1$, and $x,yϵ\{0,1,2,\dots \dots \}\}$
$=\left\{\right(0,1),(1,2),(2,3),(3,4),\dots \dots \}$
Now let $T_1$ be the reflexive closure of $S$
$T_1=\left\{\right(0,0),(1,1),(2,2),(3,3)\dots \dots \}\cup$
$\left\{\right(0,1),(1,2),(2,3),(3,4)\dots \dots \}$
$=\left\{\right(0,0),(0,1),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)\dots \dots \}$
Let $T_2$ be the transitive closure of $S$
$(0,1),(1,2)ϵS\Rightarrow (0,2)ϵT_2$
$(0,2),(2,3)ϵS\Rightarrow (0,3)ϵT_2$
$(0,3),(3,4)ϵS\Rightarrow (0,4)ϵT_2$
and so on....
Also $(1,2),(2,3)ϵS\Rightarrow (1,3)ϵT_2$
$(1,3),(3,4)ϵS\Rightarrow (1,4)ϵT_2$
$(1,4),(4,5)ϵS\Rightarrow (1,5)ϵT_2$
and so on....
$\therefore T_2=\left\{\right(0,1),(0,2),(0,3),\dots \dots (1,2),(1,3),(1,4),\dots \dots \}$
Now the reflexive, transitive closure of $S$ will be $T_3=T_1\cup T_2=\left\{\right(0,0),(0,1),(0,2),\dots \dots (1,1),(1,2),(1,3)\dots \dots (2,2),(2,3),(2,4\left)\right\}$.
Option (b) is correct.