0

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!

Elena
  • 11
  • 1
    You are asked to prove that it is a well ordering, right? – blueInk Mar 24 '18 at 11:35
  • 1
    @blueInk, I'm asked to prove usual lexicographic ordering R on X is not a well-ordering. – Elena Mar 24 '18 at 11:36
  • 1
    Can you include your definition of 'usual lexicographic ordering'? The one I am used to is a well ordering. – blueInk Mar 24 '18 at 11:37
  • @blueInk I think lexicographic ordering is well-ordering as well. I think the question is usual lexicographic ordering R on X set which is fulfilled with words on the usual English alphabet order. – Elena Mar 24 '18 at 11:41
  • 1
    What about the words $b, ab, aab, aaab,\ldots$? – Bob Jones Mar 24 '18 at 11:43
  • For this definition: Given a non-empty set of words, look at the words with minimal length. This minimal length exists because the narural numbers are well ordered. Then among those words of minimal length there are some that have the first letter closest to the beginning of the alphabet. This is because the alphabet is also well-ordered. Then among those there are some that have the second letter closest to the beginning of the alphabet, and so on. The process ends because the length of the words was finite. ... – blueInk Mar 24 '18 at 11:43
  • @BobJones shorter words are smaller in the lexicographic order. $b$ is the first element. – blueInk Mar 24 '18 at 11:44
  • ... Finally, I claim that the set of words resulting when the process ends is only one word. Clarly, if there were two words left, then they would have the same length and each of their letters would be the same, because each letter would be the smallest in the alphabet among the words in the set, therefore the words are the same. – blueInk Mar 24 '18 at 11:45
  • 1
    In my usual lexicographic ordering, $ab$ comes before $b$, in the dictionary for example...? – Bob Jones Mar 24 '18 at 11:47
  • @BobJones In that variation your example is still wrong. Because you should have put the $b$ after all the sequence of the other words. The first element would be $ab$. The order would be $ab,aab,aaab,...,b$. – blueInk Mar 24 '18 at 11:51
  • @BobJones In case it is not clear to you. That 'dictionary order' is also a well-ordering. – blueInk Mar 24 '18 at 12:17
  • 1
    @blueink what are you talking about? $aab$ certainly comes before $ab$ in the dictionary. And $aaaaaab$ comes before $b$ and $ab$ and $aab$ and ... and $aaaaab$. Every word I wrote comes before every word I wrote before it. – Bob Jones Mar 24 '18 at 12:27
  • @BobJones Never. But if you want that order, be happy. Not the lexicographic, nor the dictionary order, though. – blueInk Mar 24 '18 at 12:29
  • 1
    @blueink I am still confused. Do you believe that "aardvark" comes after "ab" in the dictionary? And the original question is that the lexicographic order is not well-ordered, why are you arguing so hard against the statement? – Bob Jones Mar 24 '18 at 12:39
  • @BobJones Because, to begin with, the lexicographic order is a well-order. Whatever you define there that is not a well-order is not the lexicographic order. – blueInk Mar 24 '18 at 12:41

1 Answers1

3

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

Malcolm
  • 1,055