Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

8.10: Order-Completeness

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

( \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 (aA)(bB)ab, then there exists c in X such that (aA)(bB)acb. 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<bX)(yY)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 XY and, for all x1,x2 in X, x1Xx2 iff x1Yx2. 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 annN be a bijection from N to X. Observe that the sequence imposes an ordering on X. Let be defined on X by (m,nN)amanmn. That is, for any x,yX,xy if x appears in the sequence an before y. Then is a well-ordering of X.

Given YX and y0Y, we say that y0 is the -minimal element of Y if (xY)y0x. 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 nN

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

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

(3) af(n+1) is the -minimal element of the set {yXaf(n)<y<ag(n)} (4) ag(n+1) is the -minimal element of the set {yXaf(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)nN,ag(n)nN 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,nN, af(m)<ag(n). Therefore the increasing sequence af(n)nN is bounded above, and by Lemma 8.5, the sequence converges to its least upper bound, a.

For any nN, 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 nN. Since f(0)=0,n0. 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 1k<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:RX. If qQ, define f(q)=q. If αRQ, define f(α) to be the least upper bound in X of {qQqα}. 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 xX. Define αR to be the least upper bound in R of {qQqXx}. 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?


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.

Support Center

How can we help?

8.9: Cardinality of the Real Numbers
8.11: Exercises