Challenge 30: Cauchy sequences are bounded
Prove that if a sequence \(a_n\) is Cauchy, then \(a_n\) is bounded; that is, there exists \(M \in \mathbb{R}\) such that for all \(n \in \mathbb{N}\), \(|a_n| \leq M\).
To do so, complete the following theory
import Mathlib.Basic.Real.Basic import Mathlib.Tactic def IsCauchy (a : ℕ → ℝ) : Prop := ∀ (ε : ℝ), 0 < ε → ∃ N : ℕ, ∀ n ≥ N, ∀ m ≥ N, |a m - a n| < ε def SeqBdd (a : ℕ → ℝ) : Prop := ∃ M > 0, ∀ n, |a n| ≤ M open Finset variable (a : ℕ → ℝ) example (ha : IsCauchy a) : SeqBdd a := by sorry
1. Proof in natural language
The proof is based on the following lemmas: + Lemma 1: If \(a_n\) is Cauchy, then there exists \(k \in \mathbb{N}\) such that \[ \forall n \geq k, |a_n| < |a_k| + 1 \] + Lemma 2: For every \(k \in \mathbb{N}\), there exists \(M \in \mathbb{R}\) such that \[ \forall i < k, |a_i| \leq M \]
Indeed, by Lemma 1, there exists \(k \in \mathbb{N}\) such that \[ \forall n \geq k, |a_n| < |aₖ| + 1 \tag{1} \] Moreover, by Lemma 2, there exists \(C \in \mathbb{R}\) such that \[ \forall i < k, |aᵢ| \leq C \tag{2} \] Let \[ M = \max(|aₖ| + 1, C) \tag{3} \] We first show that \(M > 0\). Indeed, \[ \begin{array}{llll} M &\geq |aₖ| + 1 &&\text{[by (3)]} \\ &\geq 0 + 1 \\ &= 1 \\ &> 0 \end{array} \]
Secondly, we show that for every \(n \in \mathbb{N}\), \(|a_n| \leq M\). We distinguish two cases.
Case 1: Suppose that \(n < k\). Then, \[ \begin{array}{llll} |a_n| &\leq C &&\text{[by (2)]} \\ &\leq M &&\text{[by (3)]} \end{array} \]
Case 2: Suppose that \(n \geq k\). Then, \[ \begin{array}{llll} |a_n| &\leq |aₖ| + 1 &&\text{[by (1)]} \\ &\leq M &&\text{[by (3)]} \end{array} \]
It remains to prove the lemmas. To prove the first lemma, since \(a_n\) is Cauchy, there exists \(k \in \mathbb{N}\) such that \[ \forall i \geq k, \forall j \geq i, |aᵢ - aⱼ| < 1 \tag{4} \] We show that \(k\) satisfies the required condition; that is, \[ \forall n \geq k, |a_n| < |a_k| + 1 \] To this end, let \(n \in \mathbb{N}\) be such that \[ n \geq k \] Then, by (4) and since \(k \geq k\), we have \[ |a_n - a_k| < 1 \tag{5} \] and, therefore, \[ \begin{array}{llll} |a_n| &= |a_k + (a_n - a_k)| \\ &\leq |a_k| + |a_n - a_k| &&\text{[by the triangle inequality]} \\ &< |a_k| + 1 &&\text{[by (5)]} \end{array} \]
To prove Lemma 2, let \[M = \sum_{i \in \mathrm{range}(k)} |a_i| \tag{6} \] that is, \[ M = |a_0| + |a_1| + \dots + |a_{k-1}| \] We show that \(M\) is the required bound; that is, \[ \forall i < k, |a_i| \leq M \] To this end, let \(i \in \mathbb{N}\) be such that \[ i < k \tag{7} \] Then, since \[ \forall i \in \mathrm{range}(k), 0 \leq |a_i| \tag{8} \] and, by (7), \[ i \in \mathrm{range}(k) \tag{9} \] we have that \[ \begin{array}{llll} |a_i| &\leq \sum_{i \in \mathrm{range}(k)} |a_i| &&\text{[by (8) and (9)]}\\ &= M &&\text{[by (6)]} \end{array} \]
2. Proofs in Lean 4
import Mathlib.Basic.Real.Basic import Mathlib.Tactic def IsCauchy (a : ℕ → ℝ) : Prop := ∀ (ε : ℝ), 0 < ε → ∃ N : ℕ, ∀ n ≥ N, ∀ m ≥ N, |a m - a n| < ε def SeqBdd (a : ℕ → ℝ) : Prop := ∃ M > 0, ∀ n, |a n| ≤ M open Finset variable (a : ℕ → ℝ) lemma cauchy_exists_bound_tail_terms (h : IsCauchy a) : ∃ k, ∀ n ≥ k, |a n| < |a k| + 1 := by obtain ⟨k, hk⟩ := h 1 one_pos -- k : ℕ -- hk : ∀ n ≥ k, ∀ m ≥ k, |a m - a n| < 1 use k -- ⊢ ∀ n ≥ k, |a n| < |a k| + 1 intro n hn -- n : ℕ -- hn : n ≥ k -- ⊢ |a n| < |a k| + 1 have h1 : |a n - a k| < 1 := hk k (le_refl k) n hn calc |a n| = |a k + (a n - a k)| := congrArg abs (add_sub_cancel (a k) (a n)).symm _ ≤ |a k| + |a n - a k| := abs_add_le (a k) (a n - a k) _ < |a k| + 1 := add_lt_add_right h1 |a k| lemma exists_bound_first_terms (k : ℕ) : ∃ M, ∀ i < k, |a i| ≤ M := ⟨∑ i ∈ range k, |a i|, fun _ hi => single_le_sum (fun j _ => abs_nonneg (a j)) (mem_range.mpr hi)⟩ example (ha : IsCauchy a) : SeqBdd a := by obtain ⟨k, hk⟩ := cauchy_exists_bound_tail_terms a ha -- k : ℕ -- hk : ∀ n ≥ k, |a n| < |a k| + 1 obtain ⟨C, hC⟩ := exists_bound_first_terms a k -- C : ℝ -- hC : ∀ i < k, |a i| ≤ C set M := max (|a k| + 1) C use M -- ⊢ M > 0 ∧ ∀ (n : ℕ), |a n| ≤ M constructor · -- ⊢ M > 0 calc M ≥ |a k| + 1 := le_max_left (|a k| + 1) C _ ≥ 0 + 1 := add_le_add_left (abs_nonneg (a k)) 1 _ = 1 := zero_add 1 _ > 0 := Real.zero_lt_one · intro n -- n : ℕ -- ⊢ |a n| ≤ M rcases lt_or_ge n k with hn1 | hn2 · -- hn1 : n < k calc |a n| ≤ C := hC n hn1 _ ≤ M := le_max_right (|a k| + 1) C · -- hn2 : k ≤ n calc |a n| ≤ |a k| + 1 := le_of_lt (hk n hn2) _ ≤ M := le_max_left (|a k| + 1) _
You can inspect, modify and run the code of these proofs interactively in Lean 4 Web.
3. Collaborative solutions
Have you found a proof different from those published? You can share it in the comments below by following these steps:
- Write your proof in live.lean-lang.org and check that it compiles without errors.
- Copy the code and post it in the comments of this entry, inside a Lean code block:
```lean -- your proof ```
Comments