8.10: Order-Completeness

We give an argument for the uncountability of \(\mathbb{R}\) depending only on its abstract order properties.

DEFINITION. Order-complete Let \((X, \leq)\) 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 \[(\forall a \in A)(\forall b \in B) \quad a \leq b,\] then there exists \(c\) in \(X\) such that \[(\forall a \in A)(\forall b \in B) \quad a \leq c \leq 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, \leq)\) be a linearly ordered set, and \(Y \subseteq\) \(X\). We say \(Y\) is dense in \(X\) if \[(\forall a<b \in X)(\exists y \in Y) a<y<b .\] Definition. Extension Let \(\left(X, \leq_{X}\right)\) and \(\left(Y, \leq_{Y}\right)\) be linearly ordered sets. We say \(\left(Y, \leq_{Y}\right)\) is an extension of \(\left(X, \leq_{X}\right)\) if \(X \subseteq Y\) and, for all \(x_{1}, x_{2}\) in \(X\), \[x_{1} \leq_{X} \quad x_{2} \quad \text { iff } \quad x_{1} \leq_{Y} x_{2} .\] THEOREM 8.21. Let \((X, \leq)\) be an extension of \((\mathbb{Q}, \leq)\). If \((X, \leq)\) is order-complete and \(\mathbb{Q}\) is dense in \(X\), then \(X\) is uncountable.

Proof. Suppose that \(X\) is a countable order-complete extension of \(\mathbb{Q}\) and that \(\mathbb{Q}\) is dense in \(X\).

Let the sequence \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) be a bijection from \(\mathbb{N}\) to \(X\). Observe that the sequence imposes an ordering on \(X\). Let \(\preceq\) be defined on \(X\) by \[(\forall m, n \in \mathbb{N}) a_{m} \preceq a_{n} \Longleftrightarrow m \leq n .\] That is, for any \(x, y \in X, x \preceq y\) if \(x\) appears in the sequence \(\left\langle a_{n}\right\rangle\) before \(y\). Then \(\preceq\) is a well-ordering of \(X\).

Given \(Y \subseteq X\) and \(y_{0} \in Y\), we say that \(y_{0}\) is the \(\preceq\)-minimal element of \(Y\) if \[(\forall x \in Y) y_{0} \preceq x .\] So every subset of \(X\) has a \(\preceq\)-minimal element.

We shall define two subsequences of \(\left\langle a_{n}\right\rangle\), called \(\left\langle a_{f(n)}\right\rangle\) and \(\left\langle a_{g(n)}\right\rangle\), so that for any \(n \in \mathbb{N}\)

(1) \(f(n+1)>g(n)\)

(2) \(g(n)>f(n)\)

(3) \(a_{f(n+1)}\) is the \(\preceq\)-minimal element of the set \[\left\{y \in X \mid a_{f(n)}<y<a_{g(n)}\right\}\] (4) \(a_{g(n+1)}\) is the \(\preceq\)-minimal element of the set \[\left\{y \in X \mid a_{f(n+1)}<y<a_{g(n)}\right\} .\] We define the subsequences by recursion using the sequence \(\left\langle a_{n}\right\rangle\) 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 \(a_{f(N+1)}\) subject to constraints imposed by \(a_{f(N)}\) and \(a_{g(N)}\). We then define \(a_{g(N+1)}\) subject to constraints imposed by \(a_{f(N+1)}\) and \(a_{g(N)}\). We then define \(a_{f(N+2)}, a_{g(N+2)}\), and so on.

Let \(f(0)=0\). So \(a_{f(0)}=a_{0}\). Let \(g(0)\) be the smallest integer \(n\) such that \(a_{0}<a_{n}\). Note that this is equivalent to defining \(g(0)\) so that \(a_{g(0)}\) is the \(\preceq\)-minimal element of \(X\) greater than \(a_{0}\). Assume we have defined finite subsequences \(\left\langle a_{f(n)} \mid n \leq N\right\rangle,\left\langle a_{g(n)} \mid n \leq N\right\rangle\) satisfying the order properties listed above. We shall define \(a_{f(N+1)}\) and \(a_{g(N+1)}\) satisfying the ordering properties listed above. The set \(X\) contains the rational numbers and since \(\mathbb{Q}\) is dense in \(X\), there is an element of \(X\), \(x\), such that \[a_{f(N+1)}<x<g_{(N+1)} .\] Let \(a_{f(N+1)}\) be the \(\preceq\)-minimal element of \(X\) such that \[a_{f(N)}<a_{f(N+1)}<a_{g(N)} .\] Since \(\preceq\) is a well-ordering of \(X, f(N+1)\) is well-defined. We let \(a_{g(N+1)}\) be the \(\preceq\)-minimal element of \(X\) such that \[a_{f(N+1)}<a_{g(N+1)}<a_{g(N)} .\] By our previous discussion, \(g(N+1)\) is well-defined. Observe that for any \(m, n \in \mathbb{N}\), \[a_{f(m)}<a_{g(n)} .\] Therefore the increasing sequence \(\left\langle a_{f(n)} \mid n \in \mathbb{N}\right\rangle\) is bounded above, and by Lemma 8.5, the sequence converges to its least upper bound, \(a\).

For any \(n \in \mathbb{N}\), \[a_{f(n)}<a<a_{g(n) .} .\] So \(a\) is not a term of either subsequence. We show that \(a\) is not a term in the sequence \(\left\langle a_{n}\right\rangle\). Suppose by way of contradiction that \(a=a_{n}\) for some \(n \in \mathbb{N}\). Since \(f(0)=0, n \neq 0\). Let \[Y=(f[\mathbb{N}] \cup g[\mathbb{N}]) \cap\ulcorner n\urcorner .\] Then \(Y \neq \emptyset\) is finite, and has a maximal element.

If the maximal element of \(Y\) is \(f(0)\), then for every \(1 \leq k<n\), we must have \(a_{k}<a_{0}\). 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 \[a_{f(m+1)}<a_{n}<a_{g(m+1)}<a_{g(m) .} .\] This is impossible since \(a_{g(m+1)}\) is the \(\preceq\)-minimal element of \(X\) in the open interval \(\left(a_{f(m+1)}, a_{g(m)}\right)\).

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 \[a_{f(m)}<a_{f(m+1)}<a_{n}<a_{g(m)} .\] This is impossible since \(a_{f(m+1)}\) is the \(\preceq\)-minimal element of \(X\) in the open interval \(\left(a_{f(m)}, a_{g(m)}\right)\). So \(a\) is not a term in the sequence \(\left\langle a_{n}\right\rangle\). Therefore there is no bijection from \(\mathbb{N}\) to \(X\), and \(X\) is uncountable.

By Exercise 8.20, \(\mathbb{Q}\) is dense in \(\mathbb{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 \(\left(X, \leq_{X}\right)\) be an order-complete extension of \(\mathbb{Q}\) in which \(\mathbb{Q}\) is dense, and such that \(X\) has no maximal or minimal element. Then there is an order-preserving bijection from \(\mathbb{R}\) onto \(X\) that is the identity on \(\mathbb{Q}\).

Proof. Let us define a map \(f: \mathbb{R} \rightarrow X\). If \(q \in \mathbb{Q}\), define \(f(q)=q\). If \(\alpha \in \mathbb{R} \backslash \mathbb{Q}\), define \(f(\alpha)\) to be the least upper bound in \(X\) of \(\{q \in \mathbb{Q} \mid q \leq \alpha\}\). The function \(f\) is well-defined, because \(X\) has the Least Upper Bound Property. It is injective, because if \(\alpha \neq \beta\), there are rational numbers between \(\alpha\) and \(\beta\).

To show \(f\) is onto, suppose \(x \in X\). Define \(\alpha \in \mathbb{R}\) to be the least upper bound in \(\mathbb{R}\) of \(\left\{q \in \mathbb{Q} \mid q \leq_{X} x\right\}\). Then \(f(\alpha)=x\).

Finally, \(f\) is order-preserving because if \(\alpha \leq \beta\), then \(f(\beta)\) is defined as the least upper bound of a superset of the set whose least upper bound is \(f(\alpha)\), and so \(f(\alpha) \leq_{X} f(\beta)\).

REMARK. What happens if we drop the requirement that \(X\) have no maximal or minimal element?