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.5k points)   | 173 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.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 
(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.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.


Related questions

Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1630 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Devshree Dubey

    1246 Points

  6. Angkit

    1044 Points

  7. Debashish Deka

    1022 Points

  8. Bikram

    972 Points

  9. LeenSharma

    820 Points

  10. Prashant.

    692 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    256 Points

  2. Ahwan

    232 Points

  3. jjayantamahata

    114 Points

  4. joshi_nitish

    114 Points

  5. Arnab Bhadra

    94 Points

22,731 questions
29,061 answers
27,625 users