Lexicographic order

These notes are about an example that isn’t directly relevant to the material in Rudin, but which seems to me to shed some light on the “least upper bound” property of the real numbers. You might read it as a “lite” version of the construction of the real numbers in the appendix to chapter 1. A side benefit is that some of the ideas are well-known to you but difficult to state formally; so you’ll get some practice in interpreting formally complicated statements.

Definition 1. A word is a non-empty string of letters (like supercalifragilisticexpialidocious or mpqskhdg or r). A little more formally, a word is a symbol

X = x_{1}x_{2} ⋯ x_{r},

where r is a positive integer and each x_{i} is an element of the set {a, b, c, …, x, y, z}. The integer r is called the length of the word X.

The world of words is a fascinating one, but we’re going to look only at one small part of it.

Definition 2. The lexicographic order on words is the relation defined by X < Y if X comes (strictly) before Y in the dictionary. Here’s a more formal definition. First we order the alphabet in the obvious way:

a < b < c < d < ⋯ < w < x < y < z.

Now suppose that

X = x_{1} ⋯ x_{r}, Y = y_{1} ⋯ y_{s}

are two words. Then X < Y if and only if there is a non-negative integer t with the following properties:

i) t ≤ r and t ≤ s; ii) for every positive integer i ≤ t, x_{i} = y_{i}; and iii) either x_{t+1} < y_{t+1}, or t = r and t < s.

Normal people would call this relation “alphabetical order.” Mathematicians prefer the Greek origins of lexicographic to the Anglo-Saxon alphabetical. Whatever it is called, some examples of the relation are

a < aa < aaa < ab < aba.

Proposition 3. The lexicographic order is an order relation on words.

Proof. According to the definition of order relation in Rudin, there are two things we need to prove. The first is that if X and Y are two distinct words, then either X < Y or Y < X but not both. The second is that if X < Y and Y < Z, then X < Z. I will sketch the proof of the first fact only.

Fix distinct words

X = x_{1} ⋯ x_{r}, Y = y_{1} ⋯ y_{s}.

Let t be the largest non-negative integer satisfying conditions i) and ii) of Definition 2. (The integer 0 satisfies the conditions, and no integer larger than r + s satisfies them; so there must be a largest t.) We now divide the proof into four cases; it will be clear that exactly one of these four cases must hold.

Case 1. r = s = t. In this case condition ii) implies that x_{i} = y_{i} for all i, so X = Y. This

contradicts the assumption that X and Y are distinct; so Case 1 is impossible. Case 2. r = t, s > t. In this case, according to Definition 2, X < Y is true and Y < X

is false; so exactly one of the relations is true, as we wished to show. Case 3. r > t, s = t. In this case, according to Definition 2, X < Y is false and Y < X

is true; so exactly one of the relations is true, as we wished to show. Case 4. r > t and s > t. In this case, by the choice of t, t + 1 cannot satisfy condition

i) of Definition 2. This means that the letters x_{t+1} and y_{t+1} must be distinct. Because the ordering on the alphabet is an order relation, it follows that exactly one of the relations x_{t+1} < y_{t+1} and x_{t+1} > y_{t+1} must be true. By Definition 2, this means that exactly one of the relations X < Y and Y < X is true, as we wished to show. We see that in every case exactly one of the relations X < Y and Y < X is

true, so the lexicographic order satisfies Rudin’s first axiom. I’ll leave to you the problem of proving the second axiom. Q.E.D.

The order relations that you ought to be familiar with are the standard ones on the sets ℕ, ℤ, ℚ, and ℝ, and perhaps those on some other subsets of ℝ like the unit interval [0, 1]. Here are some facts to show that the lexicographic order on words is different from all of these. (You should think about which of these facts are true for which of the standard examples above.)

1. There is a first word a, but no last word.

2. Every word has an immediate successor; for example, the immediate successor of mqwm is mqwma.

3. Not every word has an immediate predecessor; for example, mqwm has no immediate predecessor. (For every predecessor of mqwm, like mqwl, we can find another word between the two; in this case

mqwl < mqwld < mqwm,

for example.) You should try to decide exactly which words do have an immediate predecessor.

(One example is mqwma, whose immediate predecessor is mqwm.)

The main point of looking at words in these notes was to look at the idea of least upper bound. One bounded set of words is

E = all words beginning with c or d.

One upper bound for E is the word e. In fact it’s not hard to check (from Definition 2) that the upper bounds for E are precisely the words beginning with one of the letters e, f, g, …, z. Once you know that, you can see that e is the least upper bound of E: e = sup E.

Here’s a more exotic example. Let F be the set of all words with no double letters. You should convince yourself that F is bounded, and that zz is a least upper bound. (What about the set of words with at most one set of double letters?)

Here at last is an example of a bounded set of words with no least upper bound. Let

G = {a, ab, aba, abab, … },

the set of all words beginning with a and consisting of an alternating string of as and bs. One upper bound for G is b, but we can do better: ac is a smaller upper bound, and abb is smaller than that, and abac is smaller than that.

Here is a description of all the upper bounds of G. (The point of stating it is to give you some practice at saying “obvious” but complicated things.)

Proposition 4. Suppose that n = 2m + 1 is a positive odd integer. Then the set of all upper bounds of G having length 2m + 1 consists of all words X of length 2m + 1 such that

X ≥ abab ⋯ abb.

Here the word on the right consists of 2m ab’s followed by b.

Suppose that n = 2m + 2 is a positive odd integer. Then the set of all upper bounds of G having length 2m + 2 consists of all words X of length 2m + 2 such that

X ≥ abab ⋯ abac.

Here the word on the right consists of 2m ab’s followed by ac.

So G has a smallest 1-letter upper bound, a smallest 2-letter upper bound, a smallest 3-letter upper bound, and so on; but each of these is greater than the next, so none of them is a least upper bound. (By contrast, the smallest n-letter upper bound of E is ba ⋯ a (b followed by n−1 as; the first of these is the smallest, and so is the least upper bound of E.)

Corollary 5. The set G of words is bounded, but has no least upper bound. The other point of this example was to illuminate the construction of the real

numbers from the rational numbers. The problem with the rational numbers for doing analysis is that there are “approximate computations” with rational numbers that don’t lead to a rational answer. An example is the old-fashioned square root algorithm that produces the sequence of approximate square roots of 2

1, 1.4, 1.41, 1.414, 1.4142, ….

These rational numbers don’t approach any rational number. One way to talk about this is to say that the set of rational numbers

{1, 1.4, 1.41, 1.414, 1.4142, … }

is bounded, but has no least upper bound. Real numbers are supposed to fix that problem: the central analytic property of the real numbers is that any bounded set of real numbers has a least upper bound.

A problem that Rudin relegates to an appendix (and we’ll mostly omit) is this: why does there exist an ordered field with the least upper bound property? Let’s look at the corresponding problem for the lexicographic order. Can we enlarge the ordered set of words in some way to get the least upper bound property? Start with the set G above. You might think of the words appearing in Proposition 4 as “approximate” least upper bounds. The word they’re trying to approximate is the “infinite word” ababab · · ·. So here’s a way to proceed.

Definition 6. A long word is a non-empty string of letters that may or may not be infinite. A little more formally, a word is a symbol

X = x_{1}x_{2}x_{3} ⋯,

where each x_{i} is either a blank or an element of the set {a, b, c, …, x, y, z}. We require in addition that blanks appear only at the end of the word. Formally,

i) x_{1} is not blank; and ii) If x_{n} is blank, then x_{m} is blank for all m ≥ n.

The word is called finite if some x_{n} is blank. In that case there is a last nonblank letter x_{r}, and the integer r is called the length of the word. The word is called infinite if no x_{n} is blank.

Definition 7. The lexicographic order on long words is the relation defined as follows. Suppose that

X = x_{1}x_{2} ⋯, Y = y_{1}y_{2} ⋯

are two long words. Then X < Y if and only if there is a non-negative integer t with the following properties:

i) x_{t} and y_{t} are not blank. ii) for every positive integer i ≤ t, x_{i} = y_{i}; and iii) either x_{t+1} < y_{t+1}, or x_{t+1} is blank and and y_{t+1} is not.

Proposition 8. The lexicographic order is an order relation on long words. Its restriction to finite words agrees with the lexicographic order already defined there.

You should think carefully about how to modify the proof of Proposition 3 to prove this.

Here are some facts about the order on long words.

1. There is a first long word a, and a last long word zzz · · ·.

2. Every finite word has an immediate successor (obtained by adding an a at the end). The infinite words having an immediate successor are those ending in an infinite string of z’s, except for the last word zzz · · ·. (The immediate successor is obtained by removing the final string of z’s, and increasing the last letter by one. For example, the immediate successor of caszzz ⋯ is cat.)

3. The long words having an immediate predecessor are the finite words, except for the first word a. (If the finite word ends in a, the immediate predecessor is obtained by removing it. If the word ends in a letter after a, the predecessor is obtained by lowering the last letter by one, and adding an infinite string of z’s. For example, the immediate predecessor of b is azzz · · ·.) Fact 1 means in particular that every set of long words is bounded. The big

theorem is

Proposition 9. The lexicographic order on long words has the least upper bound property. In fact every long word is the least upper bound of some non-empty set of finite words.

Proof. Let E be a non-empty set of long words (see Definition 6). E is automatically bounded above by the last long word zzz ⋯; so we must prove that E has a least upper bound. We are going to construct a long word

α = a_{1}a_{2}a_{3} ⋯,

and then prove that α is a least upper bound. We’ll construct the word α by constructing its letters one at a time.

First of all, define

L(E) = set of all first letters of words in E ⊂ {a, b, …, y, z}.

Because E is not empty, L(E) is a non-empty set of letters. Define

a_{1} = largest letter in L(E).

That is, a_{1} is the (alphabetically) last letter that occurs as the first letter of some word in E.

Next, we’re going to define an entirely new set of long words. Define

E_{2} = set of all long words X such that a_{1}X belongs to E.

There are two possibilities. If E_{2} is empty, that means that the only word in E beginning with a_{1} is the one-letter word a_{1}. In that case we define a_{i} to be a blank for all i ≥ 2. It’s not hard to see that the one-letter word a_{1} is a least upper bound for E.

The interesting case is when E_{2} is not empty, so that E has words of at least two letters beginning with a_{1}. We proceed just as we did for E, looking at the non-empty set L(E_{2}) of first letters of words in E_{2}, and defining

a_{2} = largest letter in L(E_{2}).

This means that a_{1}a_{2} is alphabetically the highest possible beginning for a word in E.

From here on we just continue in the same way. Define

E_{3} = set of all long words X such that a_{2}X belongs to E_{2}.

If E_{3} is empty, that means that the only word in E beginning with a_{1}a_{2} is the two-letter word a_{1}a_{2}. In that case we define a_{i} to be a blank for all i ≥ 3, and the two-letter word a_{1}a_{2} is a least upper bound for E.

When E_{3} is not empty, define

a_{3} = largest letter in L(E_{3}).

Continuing in this way, we get a long word

α = a_{1}a_{2}a_{3} ⋯,

which may be finite. I’ll leave to you the task of proving that α is a least upper bound of E.

There was one more assertion in Proposition 9: that every long word is the least upper bound of a non-empty set of finite words. So fix a long word

α = a_{1}a_{2}a_{3} · · · .

If α is finite, then it is the least upper bound of the one-element set E = {α}, and we are done. So suppose α is infinite; that is, that no a_{i} is blank. Define finite words

e_{1} = a_{1}, e_{2} = a_{1}a_{2}, e_{3} = a_{1}a_{2}a_{3}, …,

and define E = {e_{1}, e_{2}, e_{3}, … }. Again I leave to you the proof that α is a least upper bound of E. Q.E.D.