retagged by
9,715 views
34 votes
34 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\}$

retagged by

6 Answers

Best answer
20 votes
20 votes
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$.
edited by
32 votes
32 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.

edited by
4 votes
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.
4 votes
4 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
 

Answer:

Related questions

40 votes
40 votes
4 answers
2
Kathleen asked Sep 18, 2014
6,657 views
The following is the incomplete operation table of a $4-$element group.$$\begin{array}{|l|l|l|l|l|} \hline \textbf{*} & \textbf{e}& \textbf{a} &\textbf{b} & \textbf{c}\\\...
38 votes
38 votes
4 answers
3
Kathleen asked Sep 18, 2014
8,310 views
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$odd and evene...
37 votes
37 votes
7 answers
4
Kathleen asked Sep 18, 2014
12,554 views
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$