# 8.10: Order-Completeness

• Bob Dumas and John E. McCarthy
• University of Washington and Washington University in St. Louis

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

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.