Completion of rational numbers via Cauchy sequences

Can anyone recommend a good self-contained reference for completion of rationals to get reals using Cauchy sequences?

Answer

Update 1

This should be the final edit. Lots of typos have been corrected and the presentation in the section on existence has been greatly improved. It should be very close to a form that can be used as a basis for a project for students.

Update 2

Even more typos corrected. Added example of non-archimedean ordered field. Fleshed out a few bits more.

Update 3

Fixed up the proof sketch in the last exercise. Also I keep finding these small annoying errors… I’m sorry that I keep up bumping this thread, I just hope that you don’t mind too much.

Introduction

I’ll do one better: I’ll write you one (mostly because I actually have already written one – consider this sort of a Cliff’s notes version with most of the details left as exercises). Recall that a first course in analysis typically asserts that there exists a field with an order and the least upper bound property, and you then develop the theory of sequences and series from there. Thus our goal should be to prove existence and uniqueness (up to some isomorphism notion) of such an object.

Uniqueness

Definition 1. An ordered field is a field, K along with a total order on K such that

  1. x,y,zK:xyx+zy+z (Transitivity).
  2. x,yK:0x0y0xy (Positivity of product).

Moreover, define the absolute value function ||:KK by
|x|={xif 0xxotherwise.

Exercise 1. There is an alternate definition of an ordered field: K is said to be ordered if there is a subset P of K – called the positive elements of K – such that

  1. K is the disjoint union of P, P and {0}.
  2. x,yPx+yP and xyP.

Make formal the colloquial statement “The two definitions of ordered field are equivalent” and prove said equivalence.

Note that we could just as well require that the inequality in Definition 1 be strict since x<yx=yxy allows us to pass between strict and non-strict orderings as we please.

Definition 2. Let K and L be ordered fields. An order-preserving (f is order-preserving means that xyf(x)f(y)) ringhomomorphism is called an embedding.

Note that any embedding must be injective since the kernel of a ringhomomorphism is and ideal and 0<1.

Proposition 3. If K is an ordered field, then K has a subfield isomorphic to Q.

Exercise 2. Prove Proposition 3 by showing that φ:NK defined by
φ(n)=1++1n 1s
extends to an embedding of Q in K.

Definition 4. An ordered field K is called an archimedean field if for all nonzero x in K there exists a natural number n such that n|x|>1. Or equivalently: there exists a natural number n such that n>|x|.

Proposition 5. Let K be an ordered field. If K has the least upper bound property, then K is archimedean.

Exercise 3. Show the contrapositive of Proposition 5 by considering the set
I={xK|0<xnN:nx<1}.
Show that I is nonempty, 1 is an upper bound for I and I has no least upper bound [Hint: assume that y is the least upper bound and split in to cases (i) for yI look at 2y, and (ii) for yI look at y/2].

In a bit of an abuse of language, the elements of I can be said to be "infinitely small". For an example of an ordered field which is not archimedean, consider Q(X), the set of rational functions in one variable over Q (see [Wikipedia] for how the order is defined) - 0<1X<q for all positive rationals q.

Now it's time to consider the order topology on ordered and archimedean fields, i.e. the topology generated by the open intervals (a,b) defined in the obvious way.

Exercise 4. Show that the open intervals in an ordered field K are a basis for a topology on K.

Proposition 6. Q is dense in any archimedean field K.

Sketch of proof. Since the open intervals are a basis, we just need to verify that any open interval contains a rational. Define the ceiling function :KZ by
x=min{nZ|nx},
which is well-defined since K is archimedean.

Now let x \in K and a K \owns \varepsilon \gt 0 be given. Since K is archimedean we can find n \in \mathbb{N} such that n\varepsilon > 1. Now we have:
0 \leq \left\lvert \frac{\lceil nx \rceil}{n} - x \right\rvert
\leq \left\lvert \frac{\lceil nx \rceil - nx}{n} \right\rvert
\leq \frac{1}{n} \lt \varepsilon

Hence \frac{\lceil nx \rceil}{n} \in (x-\varepsilon,x+\varepsilon) from which that result follows.

Corollary 7. \mathbb{Q} is densely ordered in any archimedean field, i.e. if K is archimedean, x,y \in K, and x \lt y, then there exists a q \in \mathbb{Q} such that x \lt q \lt y.

Proposition 8. Any archimedean field is 2nd-countable.

Exercise 5. Prove Proposition 8 [Hint: Consider the set of intervals with rational endpoints. Show that it is a basis for a topology. Argue that it is coarser than the standard topology, and then show that any basis set for the standard topology (i.e. an interval) contains an interval with rational endpoints]

Proposition 9. Any archimedean field K is a topological field, i.e. K \times K \owns (x,y) \mapsto x+y \in K, K^\times \times K^\times \owns (x,y) \mapsto xy \in K^\times and K^\times \owns x \mapsto x^{-1} \in K^\times are continuous.

Exercise 6. Prove Proposition 9 [Hint: Consider sequences x_n and y_n that converge to x and y respectively, then use that convergent sequences are bounded].

Note that proposition 9 in fact holds for ordered fields too. You just have to consider nets instead.

Definition 10. Let G be a topological group. A sequence (x_n) in G is said to be a Cauchy sequence if for every neighbourhood U of e exists a N such that m,n \geq N \implies x_nx_m^{-1} \in U. We shall denote the set of Cauchy sequences in G by G^\mathbb{N}_c.

Note that this definition too can be used to define Cauchy nets in topological groups, but we shall not need that. Observe that the intervals with rational endpoints gives us a countable basis at 0 in any archimedean field, so we see that for archimedean fields, the definition boils down to this:
\forall \varepsilon \in \mathbb{Q}^+ \exists N : n,m \geq N \implies |x_n - x_m| < \varepsilon.

Proposition 11. Let K be an archimedean field and (x_n) a sequence in K. The following hold:

  1. If (x_n) is convergent, then (x_n) is a Cauchy sequence, and any subsequence of (x_n) converges to the same limit.
  2. If (x_n) is a Cauchy sequence, then it is bounded.
  3. If (x_n) is bounded, then (x_n) has a Cauchy subsequence ("pre-Bolzano-Weierstraß")
  4. If (x_n) is a Cauchy sequence then any subsequence is a Cauchy sequence. Moreover if (x_n) has a convergent subsequence, then (x_n) converges to the same limit.
  5. If (x_n) is a Cauchy sequence and (x_{k_n}) is a subsequence, then \lim_{n \to \infty} |x_n - x_{k_n}| = 0.

Exercise 7. Prove Proposition 11.

Proposition 12. Let K be an archimedean field. TFAE:

  1. K has the least upper bound property.
  2. Any Cauchy sequence in K is convergent ("K is complete").

Exercise 8. Flesh out the following sketch of a proof of Proposition 12:
1 \implies 2: Let (x_n) be a Cauchy sequence in K. If (x_n) is eventually constant, then it is obviously convergent, so assume that it is not so, and consider the set
X = \lbrace x \in K \;\vert\; \exists N \in \mathbb{N} : n \geq N \implies x \lt x_n \rbrace.

X is nonempty and has an upper bound (why?) and thus \sup X exists, and we claim that x_n \to \sup X. Given an \varepsilon > 0 find N such that |x_n - x_m| < \frac{\varepsilon}{2}, and consider the interval (x_N-\frac{\varepsilon}{2}, x_N + \frac{\varepsilon}{2}). There are only finitely many elements of the sequence outside of this interval, so x_N - \frac{\varepsilon}{2} \in X. Moreover, x + \frac{\varepsilon}{2} is an upper bound for X. The triangle inequality (note: prove the triangle inequality for archimedean fields) now gives
|x_n - \sup X| \leq |x_n - x_N| + |x_N - \sup X| \lt \varepsilon.
2 \implies 1: Let A \subset K be nonempty and bounded above by y_0 \in K. Let x_0 be some non-upper bound for A e.g. a-1 for some a \in A, and recursively define a pair of sequences (x_n) and (y_n) over \mathbb{N}_0 by
\begin{align}
y_{n+1} & = \begin{cases}
\tfrac{y_n + x_n}{2}
& \text{if } \tfrac{y_n+x_n}{2} \text{ is an upper bound for } A, \\\\
y_n & \text{otherwise}
\end{cases} \\\\
x_{n+1} & = \begin{cases}
\tfrac{y_n+x_n}{2}
& \text{if } \tfrac{y_n+x_n}{2} \text{ is a non-upper bound for } A, \\\\
x_n & \text{otherwise.}
\end{cases}
\end{align}

By induction we have that (x_n) is increasing, (y_n) is decreasing, and for all i,j: x_i \leq y_j. Likewise by induction we get that for all i: 0 \leq y_i - x_i \leq 2^{-i}(y_0 - x_0). It is now easy to show that (y_n) is a Cauchy sequence. Assume that n \geq m and we have:
\begin{align}
y_m-y_n & = y_m - y_{m+1} + y_{m+1} - \dotsb - y_{n-1} + y_{n-1} - y_n \\\\
& \leq (2^{-m-1} + 2^{-m-2} + 2^{-n})(y_0 - x_0) \\\\
& \leq 2^{-m}(y_0 - x_0)
\end{align}

from which it is easy to conclude that (y_n) is Cauchy. Similarly (x_n) is shown to be Cauchy. Thus the two sequences are convergent, and their limits must be the same since y_n - x_n \leq 2^{-n}(y_0 - x_0) -- denote the limit by s. Finally observe that for all a \in A, a \leq y_n, so a \leq s (why?) i.e. s is an upper bound for A. Moreover if u is an upper bound for A then x_n \leq u for all n, so s \leq u (why?). Hence s is the least upper bound for A. QED.

Proposition 12. Let K and L be archimedean fields. If f: K \to L and g: L \to K are embeddings, then K and L are isomorphic.

Proof. Let g \circ f = \phi: K \to K. By definition \phi is an embedding. Assume that \phi is not the identity. Then there exists an x for which \phi(x) \neq x. Find a q \in \mathbb{Q} between x and \phi(x) and observe that \phi has to be the identity on \mathbb{Q}, but it can't preserve the ordering of x and q. This gives a contradiction, and thus \phi must be the identity. The proof that f \circ g is the identity is similar. QED.

Lemma 13. Let G and H be topological groups and let G' be a dense subgroup of G. If \phi: G \to H is continuous and \phi|_{G'} is a homomorphism, then \phi is a homomorphism.

Proof. Let x,y \in G and assume that \phi(xy) \neq \phi(x)\phi(y). Since G' is dense there exists nets (x_\alpha) and (y_\alpha) in G' converging to x and y respectively. Since \phi is a homomorphism on G' we have for all \alpha that \phi(x_\alpha y_\alpha) = \phi(x_\alpha)\phi(y_\alpha), and since \phi is continuous and \cdot is continuous we have that \phi(xy) = \phi(x)\phi(y).

Remark. This is not a vacuous use of reductio ad absurdum, since a direct proof would have to work with arbitrary nets converging to x and y. Of course this lemma immediately generalizes to also apply to rings in an obvious manner.

Theorem 14. (Embedding theorem for archimedean fields). Let K and L be archimedean fields where L is complete. Then there exists an embedding \phi: K \to L.

Proof. Define \phi: K \to L by \phi(x) = \sup \lbrace q \in \mathbb{Q} \;\vert\; q \lt x \rbrace. It is easy to show that \phi is order-preserving, so the only hard part is showing that it's a homomorphism. We wish to use the preceding lemma, so first we note that it's obvious that \phi's restriction to \mathbb{Q} is the identity, so the only hard part is verifying that it's continuous. Consider a k \in K and let V be a neighbourhood of \phi(k). Find rationals p and q such that \phi(k) \in (p,q) \subset V. We claim that \phi((p,q)) \subset (p,q). Let k' \in (p,q) \subset K and find q' \in \mathbb{Q} such that p \lt k' \lt q' \lt q. It's easy to see that p \lt \phi(k') \leq q' \lt q, so \phi(k') \in (p,q), and we conclude that \phi is continuous. QED.

Theorem 15. (Uniqueness of complete ordered field) There exists up to order-preserving isomorphism one and only one complete ordered field.

Proof. Let K and L be complete ordered fields. Theorem 14 gives embeddings \phi: K \to L and \varphi: L \to K. Proposition 12 gives that K and L are isomorphic. QED.

Existence

Much more has been written on this subject than uniqueness, so I'll write a lot less here. Recall that \mathbb{Q} under addition is a topological group, so we use the previously established notation for its set of Cauchy sequences: \mathbb{Q}^\mathbb{N}_c.

Proposition 16. \mathbb{Q}^\mathbb{N}_c is a commutative unital ring under coordinatewise addition and multiplication.

Exercise 8. Prove Proposition 16.

Proposition 17. The set of rational Cauchy sequences that converge to zero, i.e.
\mathfrak{z} = \left\lbrace (z_n) \in \mathbb{Q}^\mathbb{N}_c \;\bigg\vert\; z_n \to 0 \right\rbrace,
is a maximal ideal in \mathbb{Q}^\mathbb{N}_c.

Exercise 9. Prove Proposition 17. [Hint: Consider an ideal \mathfrak{a} \supset \mathfrak{z} with a (q_n) \in \mathfrak{a}\setminus\mathfrak{z}. Show that there exists an N such that n \geq N \implies q_n \neq 0 and consider the sequence (z_n) = (1-q_1,\dotsc,1-q_N,0,0,\dotsc). Argue that (q_n + z_n) \in \mathfrak{a} and conclude that \mathfrak{a} = \mathbb{Q}^\mathbb{N}_c.]

Thus \mathfrak{z} is a maximal ideal and hence the quotient, which we shall denote by R, must be a field. From here on out the rest is sketchy as there are a lot of details to check and it's really rather boring.

We adopt the convention that we write sequences with bold, e.g. (x_n) = {\bf x} and use the notation [{\bf x}] for the equivalence class containing {\bf x}.

Define \lt on R by [{\bf p}] \lt [{\bf q}] \iff \exists (p_n) \in [{\bf p}], (q_n) \in [{\bf q}], \alpha \in \mathbb{Q}^+ : p_n \lt q_n + \alpha eventually. In particular note that the existence of the positive \alpha cannot be dropped; e.g. look at (1/n), (0) and (-1/n). Without the requirement that such a positive \alpha exists, you'd thus have 0 \lt 0, which is clearly rubbish.

Exercise 10. Verify that if (p_n) \in [{\bf p}] and (q_n) \in [{\bf q}] are witnesses that [{\bf p}] \lt [{\bf q}], then any pair of representatives will do just as well, i.e. if (p'_n) \in [{\bf p}] and (q'_n) \in [{\bf q}], then (p'_n) and (q'_n) are witnesses as well.

Exercise 11. Show that \lt is a strict total order, i.e. \lt is irreflexive, transitive and total [Hint (for totality): You need to show that exactly one of [{\bf x}] \lt [{\bf y}], [{\bf x}] = [{\bf y}] and [{\bf y}] \lt [{\bf x}] holds, so first show that at least one holds by assuming that none of them holds and derive a contradiction, and then show that at most one holds likewise by contradiction and using that [{\bf x}] \nless [{\bf y}] \iff [{\bf y}] \leq [{\bf x}]. You'll probably need to pass to "nicer" subsequences many times, so Proposition 11(5) will come in handy].

And sit back and reap the reward with the following easy

Exercise 12. Show that R is an ordered field.

Exercise 13. Show that R is archimedean.

Exercise 14. Fill out the details of the following sketch of a proof that any Cauchy sequence in R is convergent:
Proof. Starting with an arbitrary Cauchy sequence ([{\bf q}]^i) of equivalence classes, Proposition 11(4) allows us to assume WLOG that for all i,j with j \geq i that \left\lvert[{\bf q}]^i - [{\bf q}]^j]\right\rvert \lt 4^{-i}. Note that convergence means showing some inequalities hold, so we only need to show those for some representatives, so we are free to pick nice ones.
Pick representatives, (q^i_n), such that |q^i_n - q^i_m| \lt 4^{-n}.
Take {\bf x} = (q^1_1,q^2_2,\dotsc). This is obviously a Cauchy sequence (why?), and we claim that [{\bf q}]^i \to [{\bf x}]. Convince yourself that this is the same as this:
\forall \varepsilon \in \mathbb{Q}^+ \exists K,N : k \geq K, n \geq N \implies \left\lvert q^k_n - q^n_n \right\rvert \lt \varepsilon.
Note that the requirement of the existence of the positive \alpha dropped out since the above has to hold for every \varepsilon > 0. So let \varepsilon \gt 0 be given. We use the standard "trick" of inserting a clever element into the inequality: |q^k_n - q^n_n| \leq |q^k_n - q^k_k| + |q^k_k - q^n_n| and use that the both the sequence and the representatives have that "4^{-m}"-property to conclude that if we choose N,K such that N=K and 2^{-N} \lt \varepsilon then RHS is eventually smaller than \varepsilon.

CONGRATULATIONS! You're done and you now have a fully certified driver's license for the real numbers!

Attribution
Source : Link , Question Author : Derek Scavo , Answer Author : kahen

Leave a Comment