187 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.
It is well ordered. option (c) is correct.
you are correct !

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://en.wikipedia.org/wiki/Well-order#Examples_and_counterexamples

How does it not have infinite descending chain?

@Akash  how can you say (0,0) is the least element . (-1,-2)R(-1,-1) is also satisfying the relation . so a/c to me its not well ordered . so  option b should be the answer a/c to me.

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

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.