# 8.10: Order-Completeness

• • Bob Dumas and John E. McCarthy
• University of Washington and Washington University in St. Louis
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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?

This page titled 8.10: Order-Completeness is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Bob Dumas and John E. McCarthy via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.