0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ You are asked to prove that it is a well ordering, right? $\endgroup$ – blueInk Mar 24 '18 at 11:35
  • 1
    $\begingroup$ @blueInk, I'm asked to prove usual lexicographic ordering R on X is not a well-ordering. $\endgroup$ – Elena Mar 24 '18 at 11:36
  • 1
    $\begingroup$ Can you include your definition of 'usual lexicographic ordering'? The one I am used to is a well ordering. $\endgroup$ – blueInk Mar 24 '18 at 11:37
  • 1
    $\begingroup$ What about the words $b, ab, aab, aaab,\ldots$? $\endgroup$ – Bob Jones Mar 24 '18 at 11:43
  • 1
    $\begingroup$ In my usual lexicographic ordering, $ab$ comes before $b$, in the dictionary for example...? $\endgroup$ – Bob Jones Mar 24 '18 at 11:47
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ thanks so much! $\endgroup$ – Elena Mar 27 '18 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.