MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Construction of the Real Numbers via Cauchy Sequences

1 Definition of the real numbers

Definition. On the rational numbers, we define the absolute value function |−| : ℚ → ℚ as follows:

|x| = \{ \begin{matrix}x & if x ⩾ 0, \\ −x & if x < 0. \end{matrix}

Lemma 1. The following hold for all x, y ∈ ℚ:

(a) |x| ⩾ 0.

(b) x ⩽ |x| and |x| = | − x|.

(c) |xy| = |x| · |y| and, if x ≠ 0, |x^{−1}| = |x|^{−1}.

(d) |x + y| ⩽ |x| + |y| (triangle inequality).

Proof. (a) through (c) are proved by easy case distinction. For (d), there are two cases: if x + y ⩾ 0, then |x + y| = x + y ⩽ |x| + |y| by (b), and if x + y < 0, then |x + y| = −(x + y) = (−x) + (−y) ⩽ | − x| + | − y| = |x| + |y| by (b). □

In the following, when we say ϵ > 0, we always mean that ϵ is a rational number.

Definition. A Cauchy sequence is a sequence of rational numbers s : ω → ℚ, such that

(∀ϵ > 0)(∃k ∈ ω)(∀m, n > k) |s_{m} − s_{n}| < ϵ.

Two Cauchy sequences s, r are said to be equivalent, in symbols s ∼ r, if

(∀ϵ > 0)(∃k ∈ ω)(∀n > k) |s_{n} − r_{n}| < ϵ.

Lemma 2. The relation ∼ is an equivalence relation on the set of Cauchy sequences.

Proof. Reflexivity and symmetry are straightforward. To show transitivity, assume s ∼ r and r ∼ t. Consider arbitrary ϵ > 0. Since s ∼ r, there exists k_{0} ∈ ω such that for all n > k_{0}, we have |s_{n} − r_{n}| < ϵ/2. Similarly, since r ∼ t, there exists k_{1} ∈ ω such that for all n > k_{1}, we have |r_{n} − t_{n}| < ϵ/2. Let k = max{k_{0}, k_{1}}. Then for all n > k, one has

|s_{n} − t_{n}| = |s_{n} − r_{n} + r_{n} − t_{n}|
⩽ |s_{n} − r_{n}| + |r_{n} − t_{n}| by the triangle inequality
< ϵ/2 + ϵ/2 = ϵ.

Since ϵ was arbitrary, this shows that s ∼ t. □

Let C be the set of Cauchy sequences. We define the set of real numbers to be ℝ = C/ ∼.

The following lemma provides two facts about Cauchy sequences that we will use repeatedly: any Cauchy sequence is bounded, and if s ≁ 0, then s is bounded away from 0.

Lemma 3. 1. If s is a Cauchy sequence, then there exists M ∈ ℚ such that for all n ∈ ω, |s_{n}| < M.

2. If s is a Cauchy sequence and s ≁ 0, then there exists ϵ_{0} > 0 and k_{0} ∈ ω such that for all n > k_{0}, |s_{n}| > ϵ_{0}.

Proof. 1.: Because s is a Cauchy sequence, there exists k ∈ ω such that for all m, n > k, |s_{m} − s_{n}| < 1. Let B = {|s_{0}|, |s_{1}|, …, |s_{k}|, |s_{k+1}|}, and define M = (max B) + 1; notice that since B ⊆ ℚ is finite, this maximum exists. We claim that for all n ∈ ω, |s_{n}| < M. There are two cases: if n ⩽ k, then |s_{n}| ∈ B, and thus |s_{n}| ⩽ max B < M. If k < n, then

|s_{n}| = |s_{n} − s_{k+1} + s_{k+1}| ⩽ |s_{n} − s_{k+1}| + |s_{k+1}| < 1 + |s_{k+1}| ⩽ M.

2.: Because s ≁ 0, it follows from the definition of “∼” that there exists ϵ > 0 such that

(∀k ∈ ω)(∃m > k) |s_{m} − 0| ⩾ ϵ.  (1)

Also, since s is a Cauchy sequence, there is k_{0} such that for all m, n > k_{0}, |s_{m} − s_{n}| < ϵ/2. Now let ϵ_{0} = ϵ/2. We claim that ϵ_{0} and k_{0} satisfy the desired conclusion, namely, that |s_{n}| > ϵ_{0} for all n > k_{0}. To prove this, take an arbitrary n > k_{0}. By (1), there exists m > k_{0} such that |s_{m}| ⩾ ϵ. Then we have

ϵ ⩽ |s_{m}| = |s_{m} − s_{n} + s_{n}| ⩽ |s_{m} − s_{n}| + |s_{n}| < ϵ/2 + |s_{n}|,

and thus, ϵ_{0} = ϵ/2 < |s_{n}|, as desired. □

2 Arithmetic operations

Next, we want to equip ℝ with some operations to make it into a field. We first define the operations on Cauchy sequences, and later we show that they are compatible with ∼. We sometimes use the notation (s_{n})_{n∈ω} to denote the sequence s.

Definition. Let 0 = (0)_{n∈ω} and 1 = (1)_{n∈ω} be the constant zero, respectively one, sequence. On the set of Cauchy sequences, we define the following operations:

\begin{aligned}s + r & = & (s_{n} + r_{n})_{n∈ω}, \\ −s & = & (−s_{n})_{n∈ω}, \\ s · r & = & (s_{n} · r_{n})_{n∈ω}. \end{aligned}

Moreover, if s ≁ 0, then we define

s^{−1} = (t_{n})_{n∈ω}, where t_{n} = \{ \begin{matrix}s_{n}^{−1} & if s_{n} ≠ 0, \\ 0 & otherwise. \end{matrix} .

Lemma 4. The four operations in the previous definition are well-defined operations on Cauchy sequences, i.e., if s and r are Cauchy sequences, then so are s + r, −s, and s · r; moreover, if s ≁ 0, then s^{−1} is a Cauchy sequence.

Proof. Suppose that s, r are Cauchy sequences. To show that s + r is a Cauchy sequence, consider arbitrary ϵ > 0. Since s is a Cauchy sequence, there exists k_{0} ∈ ω such that for all m, n > k_{0}, |s_{m} − s_{n}| < ϵ/2. Also, since r is a Cauchy sequence, there exists k_{1} ∈ ω such that for all m, n > k_{1}, |r_{m} − r_{n}| < ϵ/2. Now let k = max{k_{0}, k_{1}}. Then for all m, n > k, one has

|(s_{m} + r_{m}) − (s_{n} + r_{n})| = |s_{m} − s_{n} + r_{m} − r_{n}|
⩽ |s_{m} − s_{n}| + |r_{m} − r_{n}|
< ϵ/2 + ϵ/2
= ϵ.

Since ϵ was arbitrary, this shows that (s_{n} + r_{n})_{n∈ω} is a Cauchy sequence.

To show that −s is a Cauchy sequence, consider arbitrary ϵ > 0. Since s is a Cauchy sequence, there exists k ∈ ω such that for all m, n > k, |s_{m} − s_{n}| < ϵ. Thus, for all m, n > k, one also has |(−s_{m}) − (−s_{n})| < ϵ, and thus (−s_{n})_{n∈ω} is a Cauchy sequence.

To show that s · r is a Cauchy sequence, we first notice that by Lemma 3, s and r are bounded. Let M be a bound for both s and r, i.e., such that |s_{n}| < M and |r_{n}| < M for all n ∈ ω. Since s is a Cauchy sequence, there exists k_{0} ∈ ω such that for all m, n > k_{0}, |s_{m} − s_{n}| < ϵ/2M. Also, since r is a Cauchy sequence, there exists k_{1} ∈ ω such that for all m, n > k_{1}, |r_{m} − r_{n}| < ϵ/2M. Now let k = max{k_{0}, k_{1}}. Then for all m, n > k, one has

|s_{m} · r_{m} − s_{n} · r_{n}| = |s_{m} · r_{m} − s_{m} · r_{n} + s_{m} · r_{n} − s_{n} · r_{n}|
⩽ |s_{m} · r_{m} − s_{m} · r_{n}| + |s_{m} · r_{n} − s_{n} · r_{n}|
= |s_{m}| · |r_{m} − r_{n}| + |s_{m} − s_{n}| · |r_{n}|
< M · ϵ/2M + ϵ/2M · M
= ϵ.

Since ϵ was arbitrary, this shows that (s_{n} · r_{n})_{n∈ω} is a Cauchy sequence.

Now assume that s ≁ 0, and let t = s^{−1}. To show that t is a Cauchy sequence, consider an arbitrary ϵ > 0. By Lemma 3, there exist ϵ_{0} > 0 and k_{0} ∈ ω such that for all n > k_{0}, |s_{n}| > ϵ_{0}. Also, since s is a Cauchy sequence, there exists k_{1} ∈ ω such that for all m, n > k_{1}, |s_{m} −s_{n}| < ϵ ϵ_{0}^{2}. Let k = max{k_{0}, k_{1}}. Then for all m, n > k, one has |s_{n}| > ϵ_{0} and |s_{m}| > ϵ_{0}, which in particular implies s_{n}, s_{m} ≠ 0. We calculate

|t_{m} − t_{n}| = |s_{m}^{−1} − s_{n}^{−1}| = |\frac{s_{n} − s_{m}}{s_{n}s_{m}} | = \frac{|s_{n} − s_{m}|}{|s_{n}| · |s_{m}|} < \frac{ϵ ϵ_{0}^{2}}{ϵ_{0} · ϵ_{0}} = ϵ.

This shows that s^{−1} is a Cauchy sequence, which finishes the proof of Lemma 4.□

Lemma 5. The four operations, plus, minus, times, and inverse, are compatible with equivalence of Cauchy sequences. Thus, they give rise to operations on ℝ.

Proof. The show that addition is a compatible operation, suppose s, s′, r, r′ are Cauchy sequences such that s ∼ s′ and r ∼ r′. We need to show that s + r ∼ s′ + r′. Consider arbitrary ϵ > 0. Since s ∼ s′, there exists k_{0} ∈ ω such that for all n > k_{0}, |s_{n} − s′_{n}| < ϵ/2. Also, since r ∼ r′, there exists k_{1} ∈ ω such that for all n > k_{1}, |r_{n} − r′_{n}| < ϵ/2. Now let k = max{k_{0}, k_{1}}. Then for all n > k, one has

|(s_{n} + r_{n}) − (s′_{n} + r′_{n})| = |s_{n} − s′_{n} + r_{n} − r′_{n}|
⩽ |s_{n} − s′_{n}| + |r_{n} − r′_{n}|
< ϵ/2 + ϵ/2
= ϵ.

Since ϵ was arbitrary, this shows that s + r ∼ s′ + r′.

To show that negation is a compatible operation, assume s ∼ s′. We want to show −s ∼ −s′. Consider arbitrary ϵ > 0. Since s ∼ s′, there exists k ∈ ω such that for all n > k, |s_{n} − s′_{n}| < ϵ. Thus, for all n > k, one also has |(−s_{n}) − (−s′_{n})| < ϵ, and thus −s ∼ −s′.

To show that multiplication is a compatible operation, assume s ∼ s′ and r ∼ r′. We need to show s · r ∼ s′ · r′. First notice that since s, s′, r, r′ are Cauchy sequences, they are bounded by Lemma 3. Let M be a bound for all of them, i.e., let M ∈ ℚ such that |s_{n}|, |s′_{n}|, |r_{n}|, |r′_{n}| < M for all n ∈ ω. Since s ∼ s′, there exists k_{0} ∈ ω such that for all n > k_{0}, |s_{n} − s′_{n}| < ϵ/2M. Also, since r ∼ r′, there exists k_{1} ∈ ω such that for all n > k_{1}, |r_{n} − r′_{n}| < ϵ/2M. Now let k = max{k_{0}, k_{1}}. Then for all n > k, one has

|s_{n} · r_{n} − s′_{n} · r′_{n}| = |s_{n} · r_{n} − s_{n} · r′_{n} + s_{n} · r′_{n} − s′_{n} · r′_{n}|
⩽ |s_{n} · r_{n} − s_{n} · r′_{n}| + |s_{n} · r′_{n} − s′_{n} · r′_{n}|
= |s_{n}| · |r_{n} − r′_{n}| + |s_{n} − s′_{n}| · |r′_{n}|
< M · ϵ/2M + ϵ/2M · M
= ϵ.

This shows that s · r ∼ s′ · r′, as desired.

To show that (−)^{−1} is a compatible operation, assume s ≁ 0 and s ∼ s′. First notice that this implies s′ ≁ 0, for otherwise one would have s ∼ 0 by transitivity. Let t = s^{−1} and t′s′^{−1}. We need to show that t ∼ t′. So consider an arbitrary ϵ > 0. By Lemma 3, there exist ϵ_{0} > 0 and k_{0} ∈ ω such that for all n > k_{0}, |s_{n}| > ϵ_{0}, and there exist ϵ_{1} > 0 and k_{1} ∈ ω such that for all n > k_{1}, |s′_{n}| > ϵ_{1}. Also, since s ∼ s′, there exists k_{2} ∈ ω such that for all n > k_{2}, |s_{n}−s′_{n}| < ϵ ϵ_{0} ϵ_{1}. Let k = max{k_{0}, k_{1}, k_{2}}. Then for all n > k, one has |s_{n}| > ϵ_{0} and |s′_{n}| > ϵ_{1}, which in particular implies s_{n}, s′_{n} ≠ 0. We calculate

|t_{n} − t′_{n}| = |s_{n}^{−1} − s′_{n}^{−1}| = |\frac{s′_{n} − s_{n}}{s′_{n}s_{n}} | = \frac{|s′_{n} − s_{n}|}{|s′_{n}| · |s_{n}|} < \frac{ϵ ϵ_{0} ϵ_{1}}{ϵ_{1} · ϵ_{0}} = ϵ.

Since ϵ was arbitrary, this shows that t ∼ t′ as desired, which finishes the proof of Lemma 5. □

As a consequence of Lemma 5 and a version of Theorem 3Q, there exist welldefined operations on real numbers + : ℝ × ℝ → ℝ, − : ℝ → ℝ, · : ℝ × ℝ → ℝ and (−)^{−1} : ℝ\{0} → ℝ, satisfying

\begin{aligned}[s] + [r] & = & [s + r], \\ −[s] & = & [−s], \\ [s] · [r] & = & [s · r], and \\ [s]^{−1} & = & [s^{−1}], \end{aligned}

where [s] ≠ [0] in the last equation.

Proposition 6. ⟨ℝ, [0], +, −, [1], ·, (−)^{−1}⟩ is a field.

Proof. Each of the defining equations of a field follows easily from the corresponding equation for the rational numbers. For example, to show distributivity, consider any x, y, z ∈ ℝ. Let s, r, t be Cauchy sequences such that x = [s], y = [r], and z = [t]. Then

(s + r)t = ((s_{n} + r_{n})t_{n})_{n∈ω} = (s_{n}t_{n} + r_{n}t_{n})_{n∈ω} = st + rt.

This implies (x + y)z = xz + yz.

For multiplicative inverses, consider any x ∈ ℝ\{0}. Let s be a representative Cauchy sequence for x, i.e., x = [s]. Then x^{−1} = [s^{−1}]. Let t = s^{−1}. Notice that s ≁ 0, so by Lemma 3(2), there exists k_{0} ∈ ω such that for all n > k_{0}, s_{n} ≠ 0, and thus t_{n} = s_{n}^{−1}. Then, for all n > k, we have

s_{n} · t_{n} = 1,

and hence s · s^{−1} = (s_{n} · t_{n})_{n∈ω} ∼ 1, which implies x · x^{−1} = [1].

The other equations of a field follow similarly. □

3 Linear order

Definition. On the set of Cauchy sequences, we define the following relation: s < r if and only if

(∃ϵ > 0)(∃k ∈ ω)(∀n > k) s_{n} + ϵ < r_{n}.

Lemma 7. The relation “<” is compatible with equivalence of Cauchy sequences, which is to say, if s < r and s ∼ s′ and r ∼ r′, then s′ < r′.

Proof. Suppose s < r, s ∼ s′, and r ∼ r′. By definition of s < r, there exists ϵ > 0 and k ∈ ω such that for all n > k, s_{n} + ϵ < r_{n}. Notice that this implies s_{n} − r_{n} < −ϵ. Now since s ∼ s′, there exists k_{0} ∈ ω such that for all n > k_{0}, |s_{n} − s′_{n}| < ϵ/3. Also, since r ∼ r′, there exists k_{1} ∈ ω such that for all n > k_{1}, |r_{n} − r′_{n}| < ϵ/3. Now let ϵ′ = ϵ/3, and let k′ = max{k, k_{0}, k_{1}}. We claim that this ϵ′ and k′ satisfy the definition of s′ < r′. Indeed, for all n > k′, one has

s′_{n} + ϵ′ = s′_{n} − s_{n} + s_{n} − r_{n} + r_{n} − r′_{n} + r′_{n} + ϵ′
⩽ |s′_{n} − s_{n}| + s_{n} − r_{n} + |r_{n} − r′_{n}| + r′_{n} + ϵ′
< ϵ/3 − ϵ + ϵ/3 + r′_{n} + ϵ′
= r′_{n}.

This shows that s′ < r′. □

As a consequence of the previous lemma, we can define a relation on the real numbers as follows:

[s] < [r] iff s < r.

Lemma 8. The relation < defines a linear order on ℝ.

Proof. We show transitivity, irreflexivity, and connectedness. For transitivity, suppose x, y, z ∈ ℝ such that x < y and y < z. Let s, r, t be Cauchy sequences such that x = [s], y = [r], and z = [t]. Then s < r and r < t. It follows, by definition of “<”, that there exist ϵ_{0}, ϵ_{1} > 0 and k_{0}, k_{1} ∈ ω such that for all n > k_{0}, s_{n} + ϵ_{0} < r_{n}, and for all n > k_{1}, r_{n} + ϵ_{1} < t_{n}. Let ϵ = ϵ_{0} + ϵ_{1} and let k = max{k_{0}, k_{1}}. Then for all n > k, s_{n} + ϵ = s_{n} + ϵ_{0} + ϵ_{1} < r_{n} + ϵ_{1} < t_{n}. It follows that s < t, hence x < z.

For irreflexivity, notice that there can never be an ϵ > 0 and n ∈ ω such that s_{n} + ϵ < s_{n}. Thus, for no Cauchy sequence, s < s. It follows that for no real number, x < x.

For connectedness, consider x, y ∈ ℝ such that neither x < y nor y < x. We will show that x = y. Let x = [s] and y = [r]. It suffices to show that s ∼ r. We know that s ≮ r and r ≮ s. By using the definition of “<”, it follows that

(∀ϵ > 0)(∀k ∈ ω)(∃n > k) s_{n} + ϵ ⩾ r_{n},  (2)
(∀ϵ > 0)(∀k ∈ ω)(∃n > k) r_{n} + ϵ ⩾ s_{n}.  (3)

We claim that s ∼ r, i.e.

(∀ϵ > 0)(∃k ∈ ω)(∀n > k) |s_{n} − r_{n}| < ϵ.  (4)

To prove this, take an arbitrary ϵ > 0. Because s is a Cauchy sequence, there exists k_{0} ∈ ω such that |s_{m} − s_{n}| < ϵ/3 for all m, n > k_{0}. Similarly, there exists k_{1} ∈ ω such that |r_{m} − r_{n}| < ϵ/3 for all m, n > k_{1}. Let k = max{k_{0}, k_{1}}. By (2), there exists n_{0} > k such that s_{n_{0}} + ϵ/3 ⩾ r_{n_{0}}. Also, by (3), there exists n_{1} > k such that r_{n_{1}} + ϵ/3 ⩾ s_{n_{1}}. Now we claim that (4) holds for this ϵ and k. So let n > k. Then

s_{n} − r_{n} = s_{n} − s_{n_{1}} + s_{n_{1}} − r_{n_{1}} + r_{n_{1}} − r_{n}
⩽ |s_{n} − s_{n_{1}}| + s_{n_{1}} − r_{n_{1}} + |r_{n_{1}} − r_{n}|
< ϵ/3 + ϵ/3 + ϵ/3
= ϵ
r_{n} − s_{n} = r_{n} − r_{n_{0}} + r_{n_{0}} − s_{n_{0}} + s_{n_{0}} − s_{n}
⩽ |r_{n} − r_{n_{0}}| + r_{n_{0}} − s_{n_{0}} + |s_{n_{0}} − s_{n}|
< ϵ/3 + ϵ/3 + ϵ/3
= ϵ

The two inequalities together imply that |s_{n} − r_{n}| < ϵ, as desired. Since ϵ was arbitrary, this implies s ∼ r, and thus x = y. This finishes the proof that “<” is a linear order on ℝ. □

Proposition 9. ⟨ℝ, [0], +, −, [1], ·, (−)^{−1}, <⟩ is an ordered field.

Proof. We already know it is a field, and < is a linear order. It remains to show that for all x, y, z ∈ ℝ, x < y ⇒ x + z < y + z, and if z > 0, then x < y ⇒ xz < yz. Let x = [s], y = [r], and z = [t].

To prove the first property, assume x < y, i.e., s < r. Then there exist ϵ > 0 and k ∈ ω such that for all n > k, s_{n} + ϵ < r_{n}, and thus s_{n} + t_{n} + ϵ < r_{n} + t_{n}. This implies s + t < r + t, and thus x + z < y + z.

To prove the second property, assume x < y and z > 0. Then s < r, and thus there exist ϵ_{0} > 0 and k_{0} ∈ ω such that for all n > k_{0}, s_{n} + ϵ_{0} < r_{n}. Also, 0 < t, and thus there exist ϵ_{1} > 0 and k_{1} ∈ ω such that for all n > k_{1}, 0 + ϵ_{1} < t_{n}. Let ϵ = ϵ_{0} ϵ_{1} and k = max{k_{0}, k_{1}}. Then for all n > k, r_{n} − s_{n} > ϵ_{0} and t_{n} > ϵ_{1}, thus

ϵ = ϵ_{0} ϵ_{1} < (r_{n} − s_{n})t_{n} = r_{n}t_{n} − s_{n}t_{n},

which implies s_{n}t_{n} + ϵ < r_{n}t_{n}. Since this holds for all n > k, we have st < rt, and thus xz < yz. □

4 Completeness

In this section, we show that the real numbers are complete. By this we mean that any Cauchy sequence of real numbers has a limit. It is an interesting fact that the real numbers are, up to isomorphism, the only complete ordered field, but we will not prove this here.

First, notice that there is a natural function ℚ → ℝ that maps each rational number q to the real number [(q)_{n∈ω}]. This map is one-to-one, and it is a homomorphism of ordered fields. We write \overline{q} for the image of q under this map; thus \overline{q} is the number q regarded as a real number.

The absolute value function |−| is defined on reals in the same way as on rationals, i.e., |x| = x for x ⩾ 0, and |x| = −x otherwise.

We begin with a useful lemma:

Lemma 10. 1. For any real number x > 0, there exists a rational number q > 0 such that \overline{q} < x.

2. The rational numbers are dense in ℝ, i.e., for any x ∈ ℝ and any real ϵ > 0, there exists q ∈ ℚ such that |x − \overline{q}| < ϵ.

Proof. 1.: Let s be a Cauchy sequence such that x = [s]. Since 0 < s, there exists rational ϵ > 0 and k ∈ ω such that 0 + ϵ < s_{n} for all n > k. Let q = ϵ/2. Then for all n > k, q + ϵ/2 = ϵ < s_{n}, and thus (q)_{n∈ω} < s, which implies \overline{q} < x.

2.: Suppose x, ϵ ∈ ℝ are given and ϵ > 0. By 1., we can assume without loss of generality that ϵ is rational. Let s be a Cauchy sequence such that x = [s]. Then there exists k ∈ ω such that for all m, n > k, |s_{m} − s_{n}| < ϵ/2. Let q = s_{k+1}. Then for all n > k,

\begin{matrix}s_{n} − q + ϵ/2 ⩽ |s_{n} − q| + ϵ/2 < ϵ/2 + ϵ/2 = ϵ \\ q − s_{n} + ϵ/2 ⩽ |q − s_{n}| + ϵ/2 < ϵ/2 + ϵ/2 = ϵ \end{matrix}

The first inequality shows that x−\overline{q} < ϵ, and the second one shows that \overline{q}−x < ϵ. Taken together, we get |x − \overline{q}| < ϵ, as desired. □

A Cauchy sequence of real numbers is defined just like a Cauchy sequence of rational numbers. Notice that by Lemma 10(1), it does not make a difference in the following definition whether we take ϵ > 0 to be a rational or a real number.

Definition. A real Cauchy sequence is a sequence of real numbers x : ω → ℝ, such that

(∀ϵ > 0)(∃k ∈ ω)(∀m, n > k) |x_{m} − x_{n}| < ϵ.

We say that a real Cauchy sequence x converges to l ∈ R if

(∀ϵ > 0)(∃k ∈ ω)(∀n > k) |x_{n} − l| < ϵ.

In this case, we also say that l is a limit of the sequence.

Proposition 11 (Completeness of the real numbers). Any real Cauchy sequence has a limit.

Proof. Let (x_{n})_{n∈ω} be a real Cauchy sequence. We define a (rational) Cauchy sequence s : ω → ℚ as follows: For any n ∈ ω, let s_{n} be a rational number such that |x_{n} −\overline{s_{n}}| < 1/n. For each n, such a number exists by Lemma 10(2); we may apply the axiom of choice to obtain a sequence (s_{n})_{n∈ω} of such numbers. We claim that s is a Cauchy sequence. So take arbitrary rational ϵ > 0. Since (x_{n})_{n∈ω} is a real Cauchy sequence, there exists k_{0} ∈ ω such that for all m, n > k_{0}, |x_{m} − x_{n}| < ϵ/3. Let k_{1} ∈ ω be a natural number that is greater than 3/ϵ, and let k = max{k_{0}, k_{1}}. Then for all m, n > k, we have m > 3/ϵ and n > 3/ϵ, and thus

|s_{m} − s_{n}| = |\overline{s_{m}} − \overline{s_{n}}|
= |\overline{s_{m}} − x_{m} + x_{m} − x_{n} + x_{n} − \overline{s_{n}}|
⩽ |\overline{s_{m}} − x_{m}| + |x_{m} − x_{n}| + |x_{n} − \overline{s_{n}}|
< 1/m + ϵ/3 + 1/n
< ϵ/3 + ϵ/3 + ϵ/3
= ϵ.

This proves that s is a Cauchy sequence. Now let l = [s]. We claim that l is a limit of (x_{n})_{n∈ω}. So take any ϵ > 0; by Lemma 10(1), we can assume without loss of generality that ϵ is rational. Since s is a Cauchy sequence, we can find k_{0} ∈ ω such that for all m, n > k_{0}, |s_{m} − s_{n}| < ϵ/3. Consider an arbitrary n > k_{0}. Then we have that for all m > k_{0}, s_{n} − s_{m} + ϵ/3 < 2ϵ/3, and s_{m} − s_{n} + ϵ/3 < 2ϵ/3. The first inequality implies that \overline{s_{n}} − l < \overline{2ϵ/3}, and the second inequality implies that l − \overline{s_{n}} < \overline{2ϵ/3}, so we get |\overline{s_{n}} − l| < \overline{2ϵ/3}. Notice that this holds for arbitrary n > k_{0}. Now let k_{1} be a natural number greater than 3/ϵ. Then for any n > max{k_{0}, k_{1}}, we have

|x_{n} − l| ⩽ |x_{n} − \overline{s_{n}}| + |\overline{s_{n}} − l|
< 1/n + 2ϵ/3
< ϵ/3 + 2ϵ/3
= ϵ.

Since ϵ was arbitrary, this shows that l is a limit of (w_{n})_{n∈ω}. □