Challenge 29: If aₙ and bₙ are Cauchy sequences, then so is aₙ+bₙ
Prove that if \(a_n\) and \(b_n\) are Cauchy sequences, then so is their sum \(a_n + b_n\).
To do this, 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| < ε variable {a b : ℕ → ℝ} example (ha : IsCauchy a) (hb : IsCauchy b) : IsCauchy (a + b) := by sorry
1. Proof in natural language
Let \(\varepsilon \in \mathbb{R}\) be such that \[ \varepsilon > 0 \tag{1} \] We have to prove that there exists \(N \in \mathbb{N}\) such that \[ \forall n \geq N, \forall m \geq N, |(a + b)(m) - (a + b)(n)| < \varepsilon \tag{2} \]
By (1), we have \[ \dfrac{\varepsilon}{2} > 0 \tag{3} \] and, since \(a_n\) is Cauchy, there exists \(N_1\) such that \[ \forall n \geq N_1, \forall m \geq N_1, |a(m) - a(n)| < \dfrac{\varepsilon}{2} \tag{4} \] and, since \(b_n\) is Cauchy, there exists \(N_2\) such that \[ \forall n \geq N_2, \forall m \geq N_2, |b(m) - b(n)| < \dfrac{\varepsilon}{2} \tag{5} \] Let \[ N = max(N_1, N_2) \tag{6} \] Let us show that (2) holds for \(N\). To do this, let \(n\) and \(m\) be such that \[ n \geq N \tag{7} \] \[ m \geq N \tag{8} \] By (7), (8) and (6), we have \[ n \geq N_1 \text{ and } m \geq N_1 \] and, by (4), we have \[ |a(m) - a(n)| < \dfrac{\varepsilon}{2} \tag{9} \] By (7), (8) and (6), we also have \[ n \geq N_2 \text{ and } m \geq N_2 \] and, by (5), we have \[ |b(m) - b(n)| < \dfrac{\varepsilon}{2} \tag{10} \] Finally, \[ \begin{array}{llll} |(a + b)(m) - (a + b)(n)| &= |(a(m) - a(n)) + (b(m) - b(n))| \\ &≤ |a(m) - a(n)| + |b(m) - b(n)| &&\text{[by the triangle inequality]}\\ &< \dfrac{\varepsilon}{2} + \dfrac{\varepsilon}{2} &&\text{[by (9) and (10)]} \\ &= \varepsilon \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| < ε variable {a b : ℕ → ℝ} -- Proof 1 -- ======= example (ha : IsCauchy a) (hb : IsCauchy b) : IsCauchy (a + b) := by intro ε hε -- ε : ℝ -- hε : 0 < ε -- ⊢ ∃ N, ∀ n ≥ N, ∀ m ≥ N, |(a + b) m - (a + b) n| < ε obtain ⟨N1, hN1⟩ := ha (ε/2) (by positivity) -- N1 : ℕ -- hN1 : ∀ n ≥ N1, ∀ m ≥ N1, |a m - a n| < ε / 2 obtain ⟨N2, hN2⟩ := hb (ε/2) (by positivity) -- N2 : ℕ -- hN2 : ∀ n ≥ N2, ∀ m ≥ N2, |b m - b n| < ε / 2 set N := max N1 N2 use N -- ⊢ ∀ n ≥ N, ∀ m ≥ N, |(a + b) m - (a + b) n| < ε intro n hn m hm -- n : ℕ -- hn : n ≥ N -- m : ℕ -- hm : m ≥ N -- ⊢ |(a + b) m - (a + b) n| < ε calc |(a + b) m - (a + b) n| = |(a m + b m) - (a n + b n)| := rfl _ = |(a m - a n) + (b m - b n)| := by congr; ring _ ≤ |a m - a n| + |b m - b n| := abs_add_le _ _ _ < ε/2 + ε/2 := by grind _ = ε := by grind -- Proof 2 -- ======= example (ha : IsCauchy a) (hb : IsCauchy b) : IsCauchy (a + b) := by intro ε hε -- ε : ℝ -- hε : 0 < ε -- ⊢ ∃ N, ∀ n ≥ N, ∀ m ≥ N, |(a + b) m - (a + b) n| < ε obtain ⟨N1, hN1⟩ := ha (ε/2) (by positivity) -- N1 : ℕ -- hN1 : ∀ n ≥ N1, ∀ m ≥ N1, |a m - a n| < ε / 2 obtain ⟨N2, hN2⟩ := hb (ε/2) (by positivity) -- N2 : ℕ -- hN2 : ∀ n ≥ N2, ∀ m ≥ N2, |b m - b n| < ε / 2 set N := max N1 N2 use N -- ⊢ ∀ n ≥ N, ∀ m ≥ N, |(a + b) m - (a + b) n| < ε intro n hn m hm -- n : ℕ -- hn : n ≥ N -- m : ℕ -- hm : m ≥ N -- ⊢ |(a + b) m - (a + b) n| < ε have h1 : |a m - a n| < ε/2 := by apply hN1 · -- ⊢ n ≥ N1 exact le_of_max_le_left hn · -- ⊢ m ≥ N1 exact le_of_max_le_left hm have h2 : |b m - b n| < ε/2 := by apply hN2 · -- ⊢ n ≥ N2 exact le_of_max_le_right hn · -- ⊢ m ≥ N2 exact le_of_max_le_right hm calc |(a + b) m - (a + b) n| = |(a m + b m) - (a n + b n)| := rfl _ = |(a m - a n) + (b m - b n)| := by congr; ring _ ≤ |a m - a n| + |b m - b n| := abs_add_le _ _ _ < ε/2 + ε/2 := by gcongr _ = ε := by ring -- Proof 3 -- ======= theorem isCauchy_add (ha : IsCauchy a) (hb : IsCauchy b) : IsCauchy (a + b) := by intro ε hε -- ε : ℝ -- hε : 0 < ε -- ⊢ ∃ N, ∀ n ≥ N, ∀ m ≥ N, |(a + b) m - (a + b) n| < ε obtain ⟨N1, hN1⟩ := ha (ε/2) (half_pos hε) -- N1 : ℕ -- hN1 : ∀ n ≥ N1, ∀ m ≥ N1, |a m - a n| < ε / 2 obtain ⟨N2, hN2⟩ := hb (ε/2) (half_pos hε) -- N2 : ℕ -- hN2 : ∀ n ≥ N2, ∀ m ≥ N2, |b m - b n| < ε / 2 set N := max N1 N2 use N -- ⊢ ∀ n ≥ N, ∀ m ≥ N, |(a + b) m - (a + b) n| < ε intro n hn m hm -- n : ℕ -- hn : n ≥ N -- m : ℕ -- hm : m ≥ N -- ⊢ |(a + b) m - (a + b) n| < ε have h1 : |a m - a n| < ε/2 := hN1 n (le_of_max_le_left hn) m (le_of_max_le_left hm) have h2 : |b m - b n| < ε/2 := hN2 n (le_of_max_le_right hn) m (le_of_max_le_right hm) calc |(a + b) m - (a + b) n| = |(a m + b m) - (a n + b n)| := rfl _ = |(a m - a n) + (b m - b n)| := congrArg abs (add_sub_add_comm (a m) (b m) (a n) (b n)) _ ≤ |a m - a n| + |b m - b n| := abs_add_le (a m - a n) (b m - b n) _ < ε/2 + ε/2 := add_lt_add h1 h2 _ = ε := add_halves ε
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 the published ones? 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