lexicographic ordering is not a well ordering

Question

I'm new to discrete mathematics, here is the question I need to proof: Let X be the set of all possible words on the usual English alphabet (the words are just finite strings of letters and need not correspond to actual words). Show that the usual lexicographic ordering R on X is not a well-ordering. My idea is to prove whether lexicographic ordering meets the properties of well-ordering? (but I get struggled with how to start) Please give me some hints, many thanks!

Answer 1

Working with the definition given on Wikipedia:

Consider a finite set $A$, often called alphabet, which is totally ordered. In dictionaries, this is the common alphabet, ordered by the alphabetical order. In book indexes, the alphabet is generally extended to all alphanumeric characters; it is the object of a specific convention whether a digit is considered as smaller or larger than a letter. The lexicographic order is a total order on the sequences of elements of $A$, often called words on $A$, which is defined as follows.

Given two different sequences of the same length, $a_1, a_2,\cdots, a_k$ and $b_1, b_2,\cdots ,b_k$, the first one is smaller than the second one for the lexicographical order, if $a_i<b_i$ (for the order of $A$), for the first $i$ where $a_i$ and $b_i$ differ.

To compare sequences of different lengths, the shorter sequence is usually padded at the end with enough "blanks" (a special symbol that is treated as smaller than every element of $A$). This way of comparing sequences of different lengths is always used in dictionaries.

Then using Bob Jones' counter-example mentioned in the comments, define $$ w_n = \underbrace{aa\dots a}_{n\ a\text{'s}}b \quad n = 0, 1, \cdots $$ $w_n$ is $n$ $a$'s followed by $b$. The subset $$ Y = \{w_n|n\geq 0\} = \{ b, ab, aab, aaab, \cdots \} $$ is a non-empty subset of $X$, but $Y$ has no least element.

To compare $w_m$ to $w_n$ for $0<m<n$, $(w_m)_i = a = (w_n)_i$ for $0\leq i \leq m$, but $(w_m)_{m+1} = b$ which follows $(w_n)_{m+1} = a$ so $w_n$ precedes $w_m$.

$Y$ has no first element so the usual lexicographic ordering on $X$ is not a well-ordering.

As noted in the Wikipedia article this "failure" can be addressed by using a variant of the lexicographic called the shortlex order where words are first sorted by length (shorter words preceding longer words).