edited by
14,453 views
50 votes
50 votes

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?

  1. Both $P$ and $Q$ are true.
  2. $P$ is true and $Q$ is false.
  3. $P$ is false and $Q$ is true.
  4. Both $P$ and $Q$ are false.
edited by

8 Answers

1 votes
1 votes

(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

1 votes
1 votes

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 1st term is true, it would mean a<=e which would make our claim to transitivity , true, similarly for 4th term. But 1st/4th term need not be true, even if 2nd/3rd term is true that also makes the expression true, and 2nd/3rd 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.

0 votes
0 votes
(a,b)R(a,b) is true for every (a,b) belonging to R. as a<=a is true or b<b is true .So it is reflexive.

Now , if (a,b)R(c,d) [ which means a<=c or b<=d ]and (c,d)R(x,y) [ which means c<=x or d<=y ]

then (a,b)R(x,y) is true as a<=x or b<=y [ transitive property of inequalities]

So P and Q both are true.
0 votes
0 votes

here, it is given that:

(a, b)R(c, d)

if a ≤ c or b ≤ d

Statement P: R is reflexive → TRUE

For R to be reflexive (a, b) R (a, b) should hold true.

Here, a ≤ a or b ≤ b So, (a, b) R (a, b) holds true.

R is reflexive.

 

Statement Q: R is transitive → FALSE

Consider the elements as (4, 5), (5, 1), (1, 1) As, (4, 5) R (5, 1)

so, 4 ≤ 5 or 5 ≤ 1 And (5, 1) R (1, 1)

so, 1 ≤ 1 But here, (4, 5) R (1, 1)

where, 4 ≥ 1 and 5 ≥ 1

For this, relation doesn’t hold true,

So, Relation R is not transitive.

Answer:

Related questions

43 votes
43 votes
7 answers
3