GATE CSE 2016 | Set 2 | Question: 26

Question

A binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ is defined as follows: $(a, b) R(c, d)$ if $a \leq c$ or $b \leq d$. Consider the following propositions:

• $P:$ $R$ is reflexive.
• $Q:$ $R$ is transitive.

Which one of the following statements is TRUE?

• A. Both $P$ and $Q$ are true.
• B. $P$ is true and $Q$ is false.
• C. $P$ is false and $Q$ is true.
• D. Both $P$ and $Q$ are false.

Comments

hope it helps

---

Ans

---

Let the relation $R$ defined on $\mathbb{N} \times \mathbb{N}$ be:

$$(a,b) \, R \, (c,d) \iff a \le c \quad \text{or} \quad b \le d$$

1. Reflexive

A relation is reflexive if every element is related to itself:

$$xRx \quad \text{for all } x$$

 Take any arbitrary pair $(a,b) \in \mathbb{N} \times \mathbb{N}$. Checking its relation to itself:

$$(a,b) \, R \, (a,b) \iff a \le a \quad \text{or} \quad b \le b$$

• Analysis: Since both statements $a \le a$ and $b \le b$ are individually true, the logical "or" statement evaluates to true for every element in the domain.

$\boxed{\text{Result: } R \text{ is reflexive}}$

2. Irreflexive

A relation is irreflexive if no element is related to itself:

$$\neg(xRx) \quad \text{for all } x$$

• Analysis: We just proved that $(a,b) \, R \, (a,b)$ is always true for every single ordered pair in the set.

$\boxed{\text{Result: } R \text{ is not irreflexive}}$

3. Symmetric

A relation is symmetric if:

$$xRy \implies yRx$$

We need to test whether:

$$(a,b) \, R \, (c,d) \implies (c,d) \, R \, (a,b)$$

• Analysis:  To disprove it, we need the forward direction to be true and the reverse direction to be false.

• Counterexample: Choose $x = (1,1)$ and $y = (2,2)$.

  • Forward check ($xRy$): $(1,1) \, R \, (2,2) \iff 1 \le 2 \text{ or } 1 \le 2 \quad \text{(True)}$

  • Reverse check ($yRx$): $(2,2) \, R \, (1,1) \iff 2 \le 1 \text{ or } 2 \le 1 \quad \text{(False)}$

$\boxed{\text{Result: } R \text{ is not symmetric}}$

4. Antisymmetric

A relation is antisymmetric if:

$$xRy \text{ and } yRx \implies x = y$$

• Analysis: We can disprove this by finding two distinct, non-identical pairs that relate to each other in both directions.

• Counterexample: Take the distinct pairs $(1,2)$ and $(2,1)$.

  • $(1,2) \, R \, (2,1)$ is true because $1 \le 2$.

  • $(2,1) \, R \, (1,2)$ is true because $1 \le 2$.

• Even though both directional relations hold true, $(1,2) \neq (2,1)$.

$\boxed{\text{Result: } R \text{ is not antisymmetric}}$

5. Asymmetric

A relation is asymmetric if:

$$xRy \implies \neg(yRx)$$

• Analysis: Since this relation has already been proven to be reflexive, it cannot be asymmetric. Additionally, our previous counterexample showed pairs like $(1,2)$ and $(2,1)$ where both directions hold simultaneously.

$\boxed{\text{Result: } R \text{ is not asymmetric}}$

6. Transitive

A relation is transitive if:

$$xRy \text{ and } yRz \implies xRz$$

• Counterexample: Let $x = (2,10)$, $y = (3,1)$, and $z = (1,2)$.

  • Step 1 ($xRy$): $(2,10) \, R \, (3,1)$ is true because $2 \le 3$.

  • Step 2 ($yRz$): $(3,1) \, R \, (1,2)$ is true because $1 \le 2$.

  • Step 3 ($xRz$): Now we check $(2,10) \, R \, (1,2)$:

    $$(2,10) \, R \, (1,2) \iff 2 \le 1 \quad \text{or} \quad 10 \le 2 \quad \text{(Both are False)}$$

• Analysis: Both $xRy$ and $yRz$ hold true, but the direct path $xRz$ fails.

$\boxed{\text{Result: } R \text{ is not transitive}}$

7. Equivalence Relation

An equivalence relation must simultaneously satisfy three structural properties: Reflexive, Symmetric, and Transitive.

• Analysis: While this relation satisfies reflexivity, it completely fails both symmetry and transitivity. Therefore, it cannot be classified as an equivalence relation.

$\boxed{\text{Result: } R \text{ is not an equivalence relation}}$

Answer 1

$(B)$ Reflexive, but not transitive.

it is "$a \leq c$ OR $b \leq d$",

NOT
"$a \leq c$ AND $b \leq d$"

$(2,5) R (6, 3), \quad (6,3)R (1, 4),$ but $(2,5) \not R (1, 4)$

Comments

You know, you are allowed to edit answers too :) No need to give another answer just to give more information ! There is edit button on interface :)

---

If Q : R can be transitive Then answe would be (a) because (1,2) R(3,4) and (3,4) R(6,5) (1,2)R(6,5) exists.     Correct me if I am worng???

---

ashishroushan4  It has to be true for all the transitive pairs. One counter-example means not transitive.

Suppose you have written a code for a problem if it does not produce the correct result for even a single valid input, then your code is wrong.

---

Can you solve for Transitivity without counter example by som proof or by proof by contradiction?

Answer 2

Given relation  (a,b)R(c,d) if a≤c or b≤d is satifies ,

            1.Reflexive property :YES ,bcoz (a,b)R(a,b)

            2.Transitive property :NO  ,counter example  (4,2)R(1,4) and (1,4)R(3,1) but not (4,2)R(3,1).

            3.Symmetric property:NO ,counter eg (1,2)R(3,4) but not (3,4)R(1,2)

Correct ans is,(B) P is true and Q is false.

Comments

 

2.Transitive property :NO  ,counter example  (4,2)R(1,4) and (1,4)R(3,1) but not (4,2)R(3,1).

how a=4 can be greater than c=1.

a≤c or b≤d 

wrong explanation

---

i was thinking the same first but read carefully it "or" i,e in (4,2) R (1,2) we have 2<= 2 thus its valid as question says:

see there is an 'or"

---

Symmetric doesnt mean(a,b )R(b,a), it means for all element a,b,c,d if (a,b)R(c,d) then there must be (c,d)R(a,b) here relation is from 2 elemnet order pair to 2 element order pair.

Answer 3

It is obvious that it will be it will be reflexive by definition bcz if a relation "<=" then such relation must be reflexive and when we read about the definition about Transititve we found that "A relation "< || > || subset || superset || \" always be transitive so P true and Q is false.

Above is by Theory.

Now in transitive relation it is always given that if a<b,b<c then a<c but there is no such condition is reflecting in above.

Comments

Which book do you study for relations?

Answer 4

$(a,b)R(a,b)$ is always true , since $a<=a \ and\  b <= b$ is always true , thus the relation is reflexive for sure.

According to the definition of transitivity :-

$If \ (a,b)R(c,d) \ and \ (c,d)R(e,f) \ then (a,b)R(e,f) \ must \ also \ hold \ true.$

Here , the statement is in the form of an implication ,

If A then B.

Thus ,

$(\ (a,b)R(c,d) \ and \ (c,d)R(e,f) )\ => (a,b)R(e,f) $

If the RHS can be proved to be false and LHS can be proved to be true at the same point of time we can surely say that the statement is invalid and thus the relation in not transitive.

Let RHS is false.

Thus , $((a,b),(e,f)) \notin R => a>e \ and \ b>f.$

Let's reverse engineer this .

Let $a = 4 , b=5 ,e=3 \ and \ f=3$.

It can be easily shown that:-

$(4,5)R(3,6) \ holds \ and \ (3,6)R(3,3) \ holds \ but \ (4,5)R(3,3) \ doesn't \ hold. $

Thus we can show that the LHS of the implication is true , and RHS is false at the same point of time , thus the statement is invalid.

Thus , the relation is not following the property of transitivity.

Answer 5

Some might erroneously conclude that R is transitive using following proof:

Let (a,b)R(c,d) implies a<=c OR b<=d

Let (c,d)R(e,f) implies c<=e OR d<=f

For R to be transitive we have to show (a,b)R(e,f) implies a<=e OR b<=f

Now since we have assumed both (a,b)R(c,d) AND (c,d)R(e,f) 
Therefore (a<=c OR b<=d) AND (c<=e OR d<=f)

=>  (a<=c AND c<=e) OR (a<=c AND d<=f) OR (b<=d AND c<=e) OR (b<=d AND d<=f)

From our assumptions the above expression is True. If any one of the 4 terms above is true, the expression becomes true. Now if 1^st term is true, it would mean a<=e which would make our claim to transitivity , true, similarly for 4^th term. But 1^st/4^th term need not be true, even if 2^nd/3^rd term is true that also makes the expression true, and 2^nd/3^rd term don’t give us enough proof to claim that R is transitive i.e. counter examples exist to our claim of R being transitive, some of which are mentioned in the above answers. 

NOTE : Even one counterexample is enough to make a claim false, but some might try the proof route and might end up doing what I am doing above.

Answer 6

(a,b) R (c,d) exists if a<=c or b<=d

 

Reflexive definition: a R a exists if a R a exists (in reverse).

=> (a,b) R (a,b) and (a,b) R (a,b) in reverse both exists => Reflexive

 

Transitive definition: if a R b and b R c exists then a R c also exists.

=> Take an example that could contradict, for example

=> (5,6) R (6,5)

=> (6,5) R (4,5) 

=> then (5,6) R (4,5) must also exist but it doesn't. Not Transitive

 

Ans : B