First time here? Checkout the FAQ!
+1 vote

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 (29.1k points)   | 165 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 :-


answered by Veteran (41.3k 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 
(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
so it is Transitive 

Hence it is Poset 

 For well ordered for all xi+1Rxi and xi≠xi+1
(i1j1⊑ (i2j2 given i1<i2 
 ⊑ (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.3k 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.


Related questions

Top Users Mar 2017
  1. rude

    5156 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2732 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1386 Points

  9. Bikram

    1354 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,537 questions
26,871 answers
23,222 users