The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
809 views

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:

  1.    Neither a Partial Order nor an Equivalence Relation
  2.    A Partial Order but not a Total Order
  3.    A total Order
  4.    An Equivalence Relation
asked in Set Theory & Algebra by Loyal (4.3k points)
edited by | 809 views
Is the relation irreflexive?
Hello Tuhin

yes! it is.Self loop can't possible.

4 Answers

+20 votes
Best answer
ans is (A).. because the relation is not reflexive.. which is a necessary condition for both partial order and equivalence realtion..!!
answered by Boss (5.2k points)
selected by
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.
+8 votes

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

 

answered by Veteran (16.3k points)
+5 votes
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
answered by Active (2.2k points)
Can anyone explain the option c
+5 votes

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

answered by Boss (8.4k points)
edited by

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



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

33,646 questions
40,193 answers
114,179 comments
38,666 users