The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 votes

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

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

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

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

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

asked in Set Theory & Algebra by Veteran (52k points)
retagged by | 2k views
@Habibkhan, can u explain this problem in detail. Thanks in advance.
Reflexive closure is taken to add the reflexive property and same for transitive as well..

Now for reflexivity we should have (x,x) ordered pair..which is not possible if y = x + 1..So the modification required is y = x need also be added..

For transitive property we require here if y >= x and z >= y implies z >= x as original condition is not transitive clearly bcoz if y = x + 1 and z = y + 1 this does not imply z = x + 1 as z = x + 2..So we need to redefine it as y > x instead of y = x + 1 and for reflexitvity y = x is also to be mentioned..

So y >= x is the appropriate closure..Hence B) option is correct.
What is asked to do in question..??
simple, just take the reflexive closure by adding the diagonal elements and then take the transitive closure and verify with the options.


reflexive closure of S={(0,0), (1,1), (2,2,) ,(0,1),(1,2)}

Now take transitive closure={(0,0), (1,1), (2,2,) ,(0,1),(1,2),(0,2)}

clearly x<=y.
S = {(0,1), (1,2)}

Then Relation set on S = S X S = [ {(0, 1), (0, 1)}, {(1, 2), (1, 2)}, {(0, 1), (1, 2)}, {(1, 2), (0, 1)}]

How could we compare x < = y in this?
Just look at every pair you can clearly see x < y but not x <= y.

5 Answers

+12 votes
Best answer
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$.
answered by Active (3.3k points)
edited by

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 cond is redundant.

\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)}.

+19 votes

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.

answered by Boss (25.3k points)
edited by
@Gabbar  Best one :)

Thank u for explaing
+4 votes
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.
answered by Loyal (9.3k points)
+3 votes

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

answered by Active (2.6k points)
0 votes

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



answered by Active (2.4k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,034 users