GATE CSE 2004 | Question: 24

Question

Consider the binary relation:

$S= \left\{\left(x, y\right) \mid y=x+1 \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$

The reflexive transitive closure is $S$ is

• A. $\left\{\left(x, y\right) \mid y >x \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$ 

• B. $\left\{\left(x, y\right) \mid y \geq x \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$ 

• C. $\left\{\left(x, y\right) \mid y < x \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$ 

• D. $\left\{\left(x, y\right) \mid y \leq x \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$

Comments

Question says that  " modify S such that it become reflexive transitive closure?"

So , y=x+1 in S will be changed to y>=x.

---

16:57

https://www.youtube.com/watch?v=mnOHvCZJu9g

---

thankyou @neel19

Answer 1

S={ (0,1) , (1,2) }

the reflexive closure of a binary relation R on a set X is the smallest reflexive relation on X that contains R.(Source - Wikipedia)

Hence ,reflexive closure of S (Lets call it R) ={ (0,1) , (1,2) , (0,0) ,(1,1) , (2,2) }

Now R is not transitive  since (0,1) , (1,2) are in R but  (0,2) is not in R .

the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive.(Source - Wikipedia)

If we only add (0,2) to R then R will be transitive as well. Lets call this set as RT.

RT ={ (0,1) , (1,2) , (0,0), ,(1,1) , (2,2) , (0,2) }

No proper subset of RT can contain R as well as at the same time being transitive.Hence, RT is the smallest relation  that contains R and also transitive. So, RT is transitive closure of R.

Now , RT is the smallest set that contains S and reflexive as well as transitive.So, RT is reflexive transitive closure of S.

RT contains (x,y) iff x∈{0,1,2} and y∈{0,1,2} and y>=x   .  Hence answer B

 

 

Comments

In the case of reflexive closure, the relation given in the question does not follow as (1,1) ≠ (x, x+1). So, we cannot find any reflexive closure in this case. Please correct me if I am missing anything.

---

Someone Please answer this doubt of mine,  when they said that S={x,y}| y=x+1

wouldn't that mean that every pair you take should satisfy this property. I don’t understand that how come it {x,x} would satisfy the property it’s like x=x+1. how is that possible?

Answer 2

S = {(x, y) | y = x+1 and x, y ∈ {0, 1, 2, ...}}

If S = {(0, 1), (1, 2)} , we make it reflexive by taking its union with set {(0, 0), (1, 1), (2, 2)}.

Reflexive closure of a relation R on set S is the smallest reflexive relation which contains R.
Thus, reflexive closure of S = {(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)}.

Now transitive closure is defined as smallest transitive relation which contains S.

So, S = {(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)} now.

 
Thus, option (B) is correct

😊😊😊😊😊😊😊😊😊😊😊😊