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

Are you saying on the basis of cases possible,since it is OR?

For example : {(1,2),(2,1)} belongs to R then {(2,1),(1,2)} also belongs to R, so for this case it is coming symmetric pair and hence not Antisymmetric

---

……………………………

---

If here condition was $AND$ then it will Satisfy transitive property too.(Correct me if i am wrong)

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

Here, they have taken OR property.

so, Either one of the condition satisfies it will true. in the example 4<1 or 2<4 either one condition holds good.

Good example..

---

Why we can't say symmetric ?

Because (a,b)R(b,a) always true.

Ex- (6,7)R(7,6)

    6<=7

---

 

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

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.

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.