Skip to main content

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