|
it adds new elements corresponding to proper Dedekind cuts
By a linear order, I mean a collection of mutually comparable elements: given any pair of distinct elements a and b, either a < b or b < a -- that is, for any pair of elements a and b, trichotomy holds: one (and only one) of the assertions a < b, a = b, b < a is valid
By dense linear order, I mean a linear order with the following property: given any pair of distinct elements a < b, there is an element c (not necessarily unique) with a < c < b
By countable dense linear order, I mean a dense linear order whose elements can be put in one-to-one correspondence with the natural numbers 1, 2, 3 ... : that is, the elements can be enumerated a(1), a(2), a(3) ... so each element is associated with one (and only one) natural number (and conversely); of course, this correspondence cannot have much to do with the order relation < of the dense linear order
An element b is called a lower bound for the nonempty set S of elements in a linear order if every s in S satisfies: b < s or b = s. A nonempty set S of elements in a linear order is "bounded from below" if there is an element b such b is a lower bound for S. An element b is called the greatest lower bound for the nonempty set S of elements if b is a lower bound for S and every other lower bound c for S satisfies: c < b or b = c
An element b is called an upper bound for the nonempty set S of elements in a linear order if every s in S satisfies: s < b or b = s. A nonempty set S of elements in a linear order is "bounded from above" if there is an element b such b is an upper bound for S. An element b is called the least upper bound for the nonempty set S of elements if b is an upper bound for S and every other upper bound c for S satisfies: b < c or b = c
A linear order is complete if every nonempty set of elements bounded from below has a greatest lower bound and every nonempty set of elements bounded from above has a least upper bound
A proper Dedekind cut in a linear order is a partition of the elements of the linear order into two disjoint nonempty sets L and U, such that: (1) b < c for every b in L and every c in U, and (2) L has no greatest element and U has no least element
Lemma. If a dense linear order admits a proper Dedekind cut, then the linear order is not complete. Proof. Suppose L and U define a proper Dedekind cut in a complete linear order. Let b be the least upper bound for L and c be the greatest lower bound for U. Clearly b cannot belong to L (since L has no largest element) and similarly c cannot belong to U. So b belongs to U and c belongs L. Thus c < b. Since the linear order is dense, there is some element d with c < d < b. There must be at least one element f of L between d and b, since otherwise d would be upper bound for L with d < b, contradicting the fact that b is the least upper bound for L; similarly, there must be at least one element g of U between c and d; but then g < f, contradicting the fact that L and U define a proper Dedekind cut
Lemma. If a dense linear order admits no proper Dedekind cuts, then the linear order is complete. Proof. Suppose there is a nonempty set S with upper bound x but without least upper bound. Then no upper bound for S belongs to S. Let U be the collection of all upper bounds for S; then U is nonempty, since it contains x. Similarly let L be the set of all elements of the linear order than are not upper bounds for S; L is nonempty since it contains all of S. Obviously b < c for any b in L and c in U. Since L and U do not define a proper Dedekind cut, either L has a greatest element f or U has a smallest element g. But if L has a greatest element f, then f is not an upper bound for S, so there some s in S with f < s; therefore s must be in U, and so s must be the least upper bound of S, a contradiction. So L has no greatest element and therefore U has a smallest element g, which is obviously a least upper bound for S, another contradiction. Thus every nonempty set S bounded from above but has a least upper bound. Similarly, one sees that every nonempty set S bounded from below but has a greatest lower bound.
Theorem. A dense linear order is complete if and only if it admits no proper Dedekind cuts. Proof. The two lemmas above.
Theorem. A countable dense linear order admits a proper Dedekind cut. Proof. We will construct an increasing sequence of elements with an upper bound but no least upper bound. Begin by listing the elements a(1), a(2), a(3), ... Find the first element a(j) in the list with the property that the linear order contains some element b < a(j); set a(u(1)) = a(j); this will be an upper bound to our sequence. Cross off the list a(u(1)) and all the other a(j) satisfying a(u(1)) < a(j). Find the first remaining a(j) such that a(j) < a(u(1)); set a(j) = a(n(1)); this will be the first element of our increasing sequence. Cross off all the a(j) satisfying a(j) < a(n(1)). Supposing that we have defined a(n(1)) < a(n(2)) < ... < a(n(k)) < a(u(k)) < ... < a(u(2)) < a(u(1)) and have crossed off the list all a(j) such that a(j) < a(n(k)) or a(u(k)) < a(j). We do not want the sequence to have least upper bound a(u(k)). So find the first remaining a(j) such that a(n(k)) < a(j) < a(u(k)), set a(u(k+1)) = a(j) and then cross off the list a(u(k+1)) and all the a(j) satisfying a(u(k+1)) < a(j). We want the sequence to increase. So find the first remaining a(j) such that a(n(k)) < a(j) < a(u(k + 1)), set a(n(k+1)) = a(j) and then cross off the list a(n(k+1)) and all the a(j) satisfying a(j) < a(n(k+1)). Proceeding, we obtain an infinite increasing sequence a(n(1)) < a(n(2)) < a(n(3)) < ... with an infinite decreasing sequence of upper bounds ... < a(u(3)) < a(u(2)) < a(u(1)). Notice that every element gets crossed off the list at some point: at stage k > 1, for example, the element a(j) with smallest index j that still remains on the list will be crossed off, and certainly j is at least k - 1. Now suppose the sequence a(n(i)) has a least upper bound b; then b = a(k) for some k, and b = a(k) has certainly been crossed off the list by the time we are done with stage k + 1. But being an upper bound for the increasing sequence, it cannot have been crossed off the list for being some a(n(j)) or being being smaller than some a(n(j)); and being a least upper bound for the sequence, it cannot have been crossed off the list for being some a(u(j)) or being being greater than some a(u(j)); hence it has not been crossed off the list, a contradiction. Thus the increasing sequence has no least upper bound. (Similarly, we could construct a decreasing sequence of elements with a lower bound but no greatest lower bound.) Thus the countable dense linear order is not complete; hence it admits a Dedekind cut.
To summarize: Countable dense linear orders (like the rational numbers) have gaps in them. These gaps must be filled if one wants to use analytical tools like the least upper principle
|