GATE CSE 2006 | Question: 4

Question

A relation $R$ is defined on ordered pairs of integers as follows: $$(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$$ Then $R$ is:

• A.    Neither a Partial Order nor an Equivalence Relation
• B.    A Partial Order but not a Total Order
• C.    A total Order
• D.    An Equivalence Relation

Comments

Detailed Video Solution: Complete Analysis & Variations (Click HERE)

---

Sir, In the question there is if  : (x,y)R(u,v) if x<u and y>v instead of iff . So it is like Q if P = [ P → Q].

  Q = (x,y)R(u,v) ; P = x<u and y>v

• For Reflexive, the Proposition P {Premise } ≡ ( a < a ∧ b > b ) is False hence the [ P → Q] is True but Q(Conclusion) ≡ { (a,b)R(a,b)} can't be uniquely determined whether it is true or False . "So Sir, how can we comment on  Reflexivity?
• For Symmetry, if (a,b)R(c,d) is True ≡ Q(Conclusion) hence [ P → Q] is True. "So Sir we cannot comment on  P {Premise } ≡ ( a < c ∧ b > d ) that it is always true , it can be false also , since P {Premise } ≡ ( a < c ∧ b > d )  cannot be uniquely determined ( T or F)  so we can't comment on (c,d)R(a,b) whether true or False? 
• Please Sir  check once , I got answer according to options but there is doubt ​​​​​​​

---

R is Antisymmetric and Transitive

Answer 1

Answer is $(A)$. Because the relation is not reflexive which is a necessary condition for both partial order and equivalence relation..!!

PS: For a relation to be reflexive $R(a,a)$ must hold for all possible $a$.

Comments

not reflexive in all cases

---

For reflexivity, (X,Y) R (X,Y) , which here requires x<x and y<y and this is not possible in this relation.

This relations is Not Symmetric as

$(x,y)R(u,v)$ iff x<u and y>v

$(u,v)R(x,y)$ iff u<x and v>y completly opposite conditions!!

Since, reflexive and symmetric pairs are not allowed, the matrix of this relation would contain only either lower triangular or upper triangular elements as 1.

So this relation is Anti-Symmetric.

This relation is Irreflexive as not even a single case of reflexivity is possible.

Since the relation is Irreflexive and Anti-Symmetric, it is Asymmetric.

This relation is also transitive as

$(x,y)R(u,v)$ iff x<u and y>v

$(u,v)R(a,b)$ iff u<a and v>b

both imply

x<u<a and y>v>b

implies

x<a and y>b which makes (x,y)R(a,b)

Hence, transitive.

Answer 2

Just take an eg. of 3 elements. Let set A={0,1,2}

Find out the relation set according to qs.

Relation R ={  ((0,1),(1,0))  ,   ((1,2),(2,1))   ,  ((0,1),(2,0))  ,   ((0,2),(1,0))  ,  ((0,2),(1,1))  ,   ((0,2),(2,1))  , ((1,2),(2,0))  , ((1,2),(2,1)) }

Check properties of relation R :

                                               1.Reflexive    =  NO

                                               2.Symmetric  = NO

                                               3.Transitivity  = YES

                                               4.Antisymmetric = Yes

  So according to properties of POR and Equivalence relation it is neither POR nor Equivalence relation.

The correct answer is (A) Neither a Partial Order nor an Equivalence Relation

Comments

how to check transitivity in this relation?

Answer 3

An equivalence relation on a set x is a subset of x*x, i.e., a collection R of ordered pairs of elements of x, satisfying certain properties. Write “x R y” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are
1. Reflexive: a R a for all a Є R,
2. Symmetric: a R b implies that b R a for all a,b Є R
3. Transitive: a R b and b R c imply a R c for all a,b,c Є R.

An partial order relation on a set x is a subset of x*x, i.e., a collection R of ordered pairs of elements of x, satisfying certain properties. Write “x R y” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are

1. Reflexive: a R a for all a Є R,
2. Anti-Symmetric: a R b and b R a implies that for all a,b Є R
3. Transitive: a R b and b R c imply a R c for all a,b,c Є R.

An total order relation a set x is a subset of x*x, i.e., a collection R of ordered pairs of elements of x, satisfying certain properties. Write “x R y” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are

1. Reflexive: a R a for all a Є R,
2. Anti-Symmetric: a R b and b R a implies that for all a,b Є R
3. Transitive: a R b and b R c imply a R c for all a,b,c Є R.
4. Comparability : either a R b or b R a for all a,b Є R.

As given in question, a relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v , reflexive property is not satisfied here , because there is > or < relationship between (x ,y) pair set and (u,v) pair set . Other way , if there would have been x <= u and y>= v (or x=u and y=v) kind of relation amongs elements of sets then reflexive property could have been satisfied. Since reflexive property in not satisfied here , so given realtion can not be equivalence ,partial order or total order relation.So ,Answer (A) is true

Comments

Small Correction: For total order, antisymmetry needs to hold and not symmetry.

---

Excellent explanation

---

but one thing you should notice even if u allow reflexivity it is not total order .

when u allow reflexivity it will become (x,y) R (u,v) if x<= u & y>=v.

take this example   (1,2) R (3,1)      and (1,2) R (2,2)     but (3,1) is not related to (2,2) so you will not get a chain for this toset.

Answer 4

For a relation to be partial order or equivalence relation it must be reflexive.
i.e. (x,y) is some element of the set then (x,y)R(x,y), but this doesn't satisfy the given condition of x<x, y>y

Option A

Comments

Can anyone explain the option c

Answer 5

equivalence relation - a collection R of ordered pairs of elements of x, satisfying certain properties. Write “x R y” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are:

1. Reflexive: a R a for all a Є R,

2. Symmetric: a R b implies that b R a for all a,b Є R

3. Transitive: a R b and b R c imply a R c for all a,b,c Є R.

---------------------------------------------------------------

partial order-  a collection R of ordered pairs of elements of x, satisfying certain properties. Write “x R y” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are:

1. Reflexive: a R a for all a Є R,

2. Anti-Symmetric: a R b and b R a implies that for all a,b Є R

3. Transitive: a R b and b R c imply a R c for all a,b,c Є R.

--------------------------------------------------------------------

total order - a collection R of ordered pairs of elements of x, satisfying certain properties. Write “x R y” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are:

1. Reflexive: a R a for all a Є R,

2. Symmetric: a R b implies that b R a for all a,b Є R

3. Transitive: a R b and b R c imply a R c for all a,b,c Є R.

4. Comparability : either a R b or b R a for all a,b Є R.

 

so correct option is A
So R is not reflexive.
∴R is neither a partial order, nor an equivalent relation.