GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
175 views

Let $R$ be a binary relation over a set $S$. The binary relation $R$ is called an equivalence relation if it is reflexive transitive and symmetric. The relation is called partial order if it is reflexive, transitive and anti symmetric. (Notation: Let $aRb$ denote that order pair $(a, b) ∈ R.$) The relation $R$ is called a well-order if $R$ is a partial order and there does not exist an infinite descending chain (with respect to $R$) within $S$. An infinite sequence $x_{1}, x_{2}...$ of elements of $S$ is called an infinite descending chain if for all $i$ we have $x_{i+1}Rx_{i}$ and $x_{i}\neq x_{i+1}$.

Take $S=\aleph \times \aleph$ and let the binary relation $\sqsubseteq$ over $S$ be such that $\left ( i_{1}, j_{1}\right )\sqsubseteq \left ( i_{2}, j_{2} \right )$ if and only if either $\left ( i_{1}< i_{2} \right )$ or $\left ( \left ( i_{1}= i_{2}\right )\wedge \left ( j_{1}\leq j_{2} \right ) \right )$. Which statement is true of $\sqsubseteq $?

  1. $\sqsubseteq $ is an equivalence relation but not a well order.
  2. $\sqsubseteq $ is a partial order but not a well order.
  3. $\sqsubseteq $ is a partial order and a well order.
  4. $\sqsubseteq $ is an equivalence relation and a well order.
  5. $\sqsubseteq $ is neither a partial order nor an equivalence relation.
asked in Set Theory & Algebra by Veteran (30k points)   | 175 views
It is well ordered. option (c) is correct.
you are correct !

2 Answers

+1 vote

Answer -> C

S = (i1j1) ⊑ (i2j2)  iff  (i1<i2) or ((i1=i2)∧(j1≤j2))

1. (m,n) R (m,n) ?

yes, here m !< n , so we go at second criteria.

Now m=n & n =n. So This is reflexive.

2. Antisymmetric

(1,2) R (2,3)

Is (2,3) R (1,2) ? No as 2 < 1.

If you see the defination, it is clear that other than diagonal element no other element is related to itself. So antisymmetric.

3. Transitive ->
(1,2) R (2,3)  & (2,3) R (2,4) (It is easy to prove)

(1,2) R (2,4) ? Yes. It can be seen easily from following property

S = (i1j1) ⊑ (i2j2)  iff  (i1<i2) or ((i1=i2)∧(j1≤j2)).

Not going to prove this formally.

4. It is Not reflexive (1,2) R (2,3) but (2,3 ) ~R ( 3,2)

5. This is well ordered. We do not had infinite descending chain. As we have least element (0,0) we our chain stops there.

Ref :-

https://en.wikipedia.org/wiki/Infinite_descending_chain

https://books.google.co.in/books?id=OR5KAAAAQBAJ&pg=PA17&lpg=PA17&dq=does+natural+no+have+infinite+descending+chain&source=bl&ots=dDJdZ26vWP&sig=WMJUx-35YMNbgkR5twmKDMwL2bo&hl=en&sa=X&ved=0ahUKEwje9of1-rfJAhUSC44KHRqGDI4Q6AEIKjAC#v=onepage&q=does%20natural%20no%20have%20infinite%20descending%20chain&f=false

https://en.wikipedia.org/wiki/Well-order#Examples_and_counterexamples

 

answered by Veteran (41.5k points)  
How does it not have infinite descending chain?
0 votes

S = (i1j1⊑ (i2j2)  iff  (i1<i2) or ((i1=i2)∧(j1≤j2))
for reflexive 
aRb where a=b here (i1j1⊑ (i2j2
if we take any value which satisfy the reflexive property and exist in set it will also satisfy the given condition
e.g (12) 
⊑ (12)  here  ((i1=i2)∧(j1≤j2)) so its a Reflexive

for anti-symetric 
aRb -> bNRa unless a=b 
here if we take any set like i1<i2 surely it i2≨i1
                                       if i1=i2 and j1≤j2 then surely j2≨j1 
e.g.
(12) ⊑ (23)   exist in S but (23) ⊑ (12) doesn't exist since i1 ≨i2 and j1≨j2 
      
(32) ⊑ (36) exist in S  but   (36) ⊑ (32) doesn't exist  i1=i2 but   j1≨j2
so it is Anti-symmetric 


for Transitive 
aRb & bRc then aRc 
here (i1j1⊑ (i2j2(i2j2⊑ (i3j3) then (i1j1⊑ (i3j3
if i1<i2 & i2<i3 then surely i1<i3 
if i1=i2 & j1≤j2 && i2=i3 &  j2≤j3 then surely i1=i3 & j1
≤j3
so it is Transitive 

Hence it is Poset 

 For well ordered for all xi+1Rxi and xi≠xi+1
(i1j1⊑ (i2j2 given i1<i2 
(21)
 ⊑ (14) is well ordered pair but it doesnt exist in set  S. i1≨i2 && i1 ≠ i2

so i think option B


 

 

answered by Veteran (14.4k points)  

it is well order also , as there is least element (0,0)     [ if N = 0,1,2,... ]

the given sequence is infinite ascending chain. not descending chain. 

a well-order if R is a partial order and there does not exist an infinite descending chain (with respect to R) within S

by default well order is partial order , which is reflexive.

 



Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1132 Points

  8. Debashish Deka

    994 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,355 questions
30,066 answers
67,371 comments
28,382 users