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

thankyou @neel19

---

Stop putting big random gpt answers here. Nobody wants AI answers here.

---

relax dude. stop ruining your reputation by being labelled as the ai answers guy.

i appreciate your efforts

Answer 1

Option $b$. Transitive means, $x$ is related to all greater $y$ (as every $x$ is related to $x + 1$) and reflexive means $x$ is related to $x$.

Comments

Reflexive closure is easy, x should relate to itself, therefore along with y=x+1, we should put y=x also.
Option B and D left.

For transitive closure, u see in original relation O is related to 1, 1 is related to 2, 2 is related to 3, ..and so on.
Now in transitive closure, O should relate to 2, and the moment i add (O, 2), i also have to add (O,3) because 2 is already related to 3.
basically i have to add all pairs which are greater than O. and that applies to all numbers. To make transitive closure, i have to add rule $y>x$

Now it boils down to 3 rules in total
y=x+1 (given)
y=x (reflexive closure)
y>x (transitive closure)

3rd condition already includes 1st one, therefore first con^d is redundant.

 $\left.\begin{aligned}
  y>x\\
  y=x
\end{aligned}\right\} \implies y\geqslant    x$

---

Since, set is small, better we draw the digraph of the relation and then solve

The red arrows indicate our original relation R.

The reflexive closure would add self-loops to all nodes by blue edges. (x=x)

(0,0),(1,1),(2,2) would be added. This eliminates option A and C.

 

Transitive closure of R would contain all ordered pairs of {0,1,2} that now have a path between them in the reflexive closure of R. Like (0,2) would be included in the Transitive closure of R because we have a path from 0 to 2.

So, under transitive closure, only pair added is (0,2)

So our R becomes

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

Only option B satisfies.

---

@ayush since 

Transitive = { (0,1) (1,2) (0,2) }because of original relation

After Reflexive ={ (0,1) (1,2) (0,2) (0,0) (1,1) (2,2) }

then why you add the symmetric pairs too,To make transitive closure,  rule should be y>x

---

Why not D option , {  (3,2) (2,1) (3,1)  } here is y<=x this is also transitive relation. please correct me

---

@Prince-Made changes. Thank you so much :)

---

option D is wrong. As all elements of original relation not present in y<=x relation.

---

@VIDYADHAR SHELKE 1 y=x+1 means y must be greater than 1 is mentioned in the question itself.

Therefore S={(0,1),(1,2)} and its transitive closure would be {(0,1),(1,2),(0,2)}.

---

Thank you @Harshada & @Dushyant Raut 4

If anyone still did understand, its just that option D won't able to produce transitive closure of set in original set (set S).

Set s has {(0,1)(1,2)} so transitive relation should produce (0,2) from this but relation D won't able to, So option B.

---

using option D we can ensure summetricity and reflexivity

Answer 2

Relation contains = { (0,1) , (1,2) }

When said Reflexive Transitive then apply first Transitive closure and then Reflexive closure.

After Transitive = { (0,1) (1,2) (0,2) }

After Reflexive ={ (0,1) (1,2) (0,2) (0,0) (1,1) (2,2) }

So B is ans.

Some Important Note: Wiki

The transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive.

For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R⁺such that x R⁺ y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.

More formally, the transitive closure of a binary relation R on a set X is the transitive relation R⁺ on set X such that R⁺ contains R and R⁺ is minimal . If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation.

Comments

@Gabbar  Best one :)

Thank u for explaing

---

good

---

This one should be marked as the best answer.

---

thank you

Answer 3

Reflexive closure of a relation R on set S is the smallest reflexive relation which contains R.
If S = {(0, 1), (1, 2)} , we make it reflexive by taking its union with set {(0, 0), (1, 1), (2, 2)}. 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.
We check where does it violate property of transitivity then add appropriate pair. We have (0, 1) and (1, 2) but not (0, 2). So, S = {(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)} now.
 
Thus, option (B) matches the final set S.

Answer 4

y=x+1  include { (0,1),(1,2) }  order set
it is reflexive too so order set become { (0,1),(1,2),(0,0),(1,1),(2,2) } 
it is transitive too so it become { (0,1),(1,2),(0,0),(1,1),(2,2),(0,2) } 

from options only B satisfiled Hence ans is B
 

Answer 5

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 6

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

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