TIFR CSE 2013 | Part B | Question: 4

Question

A set $S$ together with partial order $\ll$ is called a well order if it has no infinite descending chains, i.e. there is no infinite sequence $x_1, x_2,\ldots$ of elements from $S$ such that $x_{i+1} \ll x_i$ and $x_{i+1} \neq x_i$ for all $i$.

Consider the set of all words (finite sequence of letters $a - z$), denoted by $W$, in dictionary order.

• A. Between $``aa"$ and $``az"$ there are only $24$ words.
• B. Between $``aa"$ and $``az"$ there are only $2^{24}$ words.
• C. $W$ is not a partial order.
• D. $W$ is a partial order but not a well order.
• E. $W$ is a well order.

Comments

But if we pick random word like ab, it has infinite descendants like aa, aaa, aaaaaa, .....

This is Not a descending sequence.. This is ascending sequence. And for this Subset we have least element $aa$..So, This sequence can't be used as a counter example for showing that it is not well ordered set.

---

it stops there right...so it isnt infinite

It indeed is Infinite. But Not descending infinite.  

---

Indeed a nice exolexplana dee. But anyone if doesn't get something , even a little.. i highly recommend to go for K.H Rosen (P-619)

Answer 1

For W to be a well order

It has to be a connix relation on a total order

a connex relation forces your element to have atleast one lower bound for all elements belonging to A

Hence D is correct

iT is a partial order but not a well order