The Gateway to Computer Science Excellence
+33 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.
in Set Theory & Algebra by Boss (42.1k points)
edited by | 5.1k views

1)   (a,b)R(c,d) if a≤c or b≤d.

     Reflexive, but not transitive

2)  (a,b)R(c,d) if a≤c and  b≤d



6 Answers

+62 votes
Best answer

$(B)$ Reflexive, but not transitive.

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

"$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)$

by Active (1.5k points)
edited by
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 :)
+18 votes

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.

by Loyal (8.1k points)
Read question carefully  case of or

Ram Swaroop Read question carefully  case of or ,It is always Refexive.

Please help me I have a doubt??!

In example you are taking a>c but it is given that a<=c??
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 votes

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.

by Boss (10.2k points)
+1 vote
$(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.
by Loyal (5.9k points)
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.
by Junior (657 points)
but consider the case when (a,b) = (4,9) ; (c,d)=(6,5)

Now (a,b)R(c,d) is true if a<=c or b<=d

Here 4<6 , hence it is true.

Let (x,y) = (3,8)

(c,d)R(x,y) since 5<8

But in this case (a,b) is not related to (x,y)

Hence it is not transitive .

Please verify if the above is correct.
i too think its not transitive
Yes it is not transitive.

take case

(1, 4)R(2, 1) and (2, 1)R(0, 2)

BUT (1, 4)R(0, 2) is not true. hence not transitive.
It is not Symmetric too, take case (1,2)R(3,4) but not (3,4) R(1,2).
0 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

by (303 points)

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
50,834 questions
57,838 answers
108,337 users