Skip to main content

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