8.10: Order-Completeness
( \newcommand{\kernel}{\mathrm{null}\,}\)
We give an argument for the uncountability of R depending only on its abstract order properties.
DEFINITION. Order-complete Let (X,≤) be a linearly ordered set. It is called order-complete if, whenever A and B are non-empty subsets of X with the property that (∀a∈A)(∀b∈B)a≤b, then there exists c in X such that (∀a∈A)(∀b∈B)a≤c≤b. Note that any order-complete set must have the least upper bound property - if A is any non-empty bounded set, let B be the set of all upper bounds for A, and then c from (8.20) is the (unique) least upper bound for A.
DEFINITION. Dense Let (X,≤) be a linearly ordered set, and Y⊆ X. We say Y is dense in X if (∀a<b∈X)(∃y∈Y)a<y<b. Definition. Extension Let (X,≤X) and (Y,≤Y) be linearly ordered sets. We say (Y,≤Y) is an extension of (X,≤X) if X⊆Y and, for all x1,x2 in X, x1≤Xx2 iff x1≤Yx2. THEOREM 8.21. Let (X,≤) be an extension of (Q,≤). If (X,≤) is order-complete and Q is dense in X, then X is uncountable.
Proof. Suppose that X is a countable order-complete extension of Q and that Q is dense in X.
Let the sequence ⟨an∣n∈N⟩ be a bijection from N to X. Observe that the sequence imposes an ordering on X. Let ⪯ be defined on X by (∀m,n∈N)am⪯an⟺m≤n. That is, for any x,y∈X,x⪯y if x appears in the sequence ⟨an⟩ before y. Then ⪯ is a well-ordering of X.
Given Y⊆X and y0∈Y, we say that y0 is the ⪯-minimal element of Y if (∀x∈Y)y0⪯x. So every subset of X has a ⪯-minimal element.
We shall define two subsequences of ⟨an⟩, called ⟨af(n)⟩ and ⟨ag(n)⟩, so that for any n∈N
(1) f(n+1)>g(n)
(2) g(n)>f(n)
(3) af(n+1) is the ⪯-minimal element of the set {y∈X∣af(n)<y<ag(n)} (4) ag(n+1) is the ⪯-minimal element of the set {y∈X∣af(n+1)<y<ag(n)}. We define the subsequences by recursion using the sequence ⟨an⟩ to carefully control the construction. This argument is called a backand-forth argument. Given finite sequences of length N satisfying the properties enumerated above, we define af(N+1) subject to constraints imposed by af(N) and ag(N). We then define ag(N+1) subject to constraints imposed by af(N+1) and ag(N). We then define af(N+2),ag(N+2), and so on.
Let f(0)=0. So af(0)=a0. Let g(0) be the smallest integer n such that a0<an. Note that this is equivalent to defining g(0) so that ag(0) is the ⪯-minimal element of X greater than a0. Assume we have defined finite subsequences ⟨af(n)∣n≤N⟩,⟨ag(n)∣n≤N⟩ satisfying the order properties listed above. We shall define af(N+1) and ag(N+1) satisfying the ordering properties listed above. The set X contains the rational numbers and since Q is dense in X, there is an element of X, x, such that af(N+1)<x<g(N+1). Let af(N+1) be the ⪯-minimal element of X such that af(N)<af(N+1)<ag(N). Since ⪯ is a well-ordering of X,f(N+1) is well-defined. We let ag(N+1) be the ⪯-minimal element of X such that af(N+1)<ag(N+1)<ag(N). By our previous discussion, g(N+1) is well-defined. Observe that for any m,n∈N, af(m)<ag(n). Therefore the increasing sequence ⟨af(n)∣n∈N⟩ is bounded above, and by Lemma 8.5, the sequence converges to its least upper bound, a.
For any n∈N, af(n)<a<ag(n).. So a is not a term of either subsequence. We show that a is not a term in the sequence ⟨an⟩. Suppose by way of contradiction that a=an for some n∈N. Since f(0)=0,n≠0. Let Y=(f[N]∪g[N])∩⌜n⌝. Then Y≠∅ is finite, and has a maximal element.
If the maximal element of Y is f(0), then for every 1≤k<n, we must have ak<a0. But then g(0) would be n, which contradicts the fact that n is not in the range of g.
If the maximal element of Y is f(m+1) for some m, then g(m+1)> n, and f(m+1)<n<g(m+1). However af(m+1)<an<ag(m+1)<ag(m).. This is impossible since ag(m+1) is the ⪯-minimal element of X in the open interval (af(m+1),ag(m)).
If the maximal element of Y is g(m) for some m, then f(m+1)>n and g(m)<n<f(m+1). However af(m)<af(m+1)<an<ag(m). This is impossible since af(m+1) is the ⪯-minimal element of X in the open interval (af(m),ag(m)). So a is not a term in the sequence ⟨an⟩. Therefore there is no bijection from N to X, and X is uncountable.
By Exercise 8.20, Q is dense in R. As the set of real numbers is order-complete by the least upper bound theorem, we get:
COROLLARY 8.22. The set of real numbers is uncountable.
THEOREM 8.23. Let (X,≤X) be an order-complete extension of Q in which Q is dense, and such that X has no maximal or minimal element. Then there is an order-preserving bijection from R onto X that is the identity on Q.
Proof. Let us define a map f:R→X. If q∈Q, define f(q)=q. If α∈R∖Q, define f(α) to be the least upper bound in X of {q∈Q∣q≤α}. The function f is well-defined, because X has the Least Upper Bound Property. It is injective, because if α≠β, there are rational numbers between α and β.
To show f is onto, suppose x∈X. Define α∈R to be the least upper bound in R of {q∈Q∣q≤Xx}. Then f(α)=x.
Finally, f is order-preserving because if α≤β, then f(β) is defined as the least upper bound of a superset of the set whose least upper bound is f(α), and so f(α)≤Xf(β).
REMARK. What happens if we drop the requirement that X have no maximal or minimal element?