well ordered set on dictionary order

658 Views Asked by At

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.

  1. Between $``aa"$ and $``az"$ there are only $24$ words.
  2. Between $``aa"$ and $``az"$ there are only $2^{24}$ words.
  3. $W$ is not a partial order.
  4. $W$ is a partial order but not a well order.
  5. $W$ is a well order.

This Question was asked in one of the entrance examination.I found this question interesting , so i tried solving this but got stuck.

My Approach

Partial order set or POSET is a binary relation having following properties-:

  1. Reflexive
  2. Antisymmetric
  3. Transitive

Now coming to option , it can be easily predicted that there are infinitely many words between $aa$ and $az$. so option $1$,2$ gets eliminated.

dictionary order are POSET see this.

Now i have doubt in option $4$ and $5$
Some says that answer will be $5$ because well order is POSET here

but from the question i think it will be $4$ because there are infinite chains in lexicographic(dictionary) order. so it will not be well order(according to definition in question)

Please help

1

There are 1 best solutions below

3
On BEST ANSWER

Every well order is a total, hence partial order, but the converse does not hold. $(W,\ll)$ is a counterexample, just like you suspected.

And yes, we have infinite chains. We start at some specific, finite word. For example "aab". We could go on with "aaba", "aabaa" etc. but that would mean $x_i \ll x_{i+1}$. However, if we take "aaab", "aaaab" etc. we can see that $x_{i+1} \ll x_i$.

Note that you can use either of these two sequences to show (1) and (2) are false, since all words of both sequences are between "aa" and "az".