Challenge 31: The identity sequence has no convergent subsequences
Let \(a_n\) be the identity sequence; that is, \(a_n = n\) for all \(n\). Prove that \(a_n\) has no convergent subsequences.
To do so, complete the following theory
import Mathlib.Basic.Real.Basic import Mathlib.Tactic def SeqLim (a : ℕ → ℝ) (L : ℝ) : Prop := ∀ ε > 0, ∃ k : ℕ, ∀ n ≥ k, |a n - L| < ε def SeqConv (a : ℕ → ℝ) : Prop := ∃ L, SeqLim a L def SeqBdd (a : ℕ → ℝ) : Prop := ∃ M > 0, ∀ n, |a n| ≤ M def IsExtraction (φ : ℕ → ℕ) : Prop := StrictMono φ def Subseq (v u : ℕ → ℝ) : Prop := ∃ φ, IsExtraction φ ∧ v = u ∘ φ variable (a : ℕ → ℝ) example (ha : ∀ n, a n = n) : ¬ ∃ b, Subseq b a ∧ SeqConv b := by sorry
1. Proof in natural language
Suppose that \(a\) is the identity sequence and that it has a convergent subsequence \[ b = a \circ \varphi \tag{1} \] with \(\varphi\) strictly increasing. Since \(b\) is convergent, it is bounded (Challenge 17); let \(M\) be a bound, that is, \[ \forall n, |b_n| \leq M \tag{2} \] By the Archimedean property, there exists \(k \in \mathbb{N}\) such that \[ M < k \tag{3} \] Then \[ \begin{array}{llll} M &< k &&\text{[by (3)]} \\ &\leq \varphi(k) &&\text{[because \(\varphi\) is strictly increasing]} \\ &= a(\varphi(k)) &&\text{[since \(a\) is the identity sequence]} \\ &= b_k &&\text{[by (1)]} \\ &\leq |b_k| &&\text{[because \(x \leq |x|\)]} \\ &\leq M &&\text{[by (2)]} \\ \end{array} \] Hence, \(M < M\), which is a contradiction.
2. Proofs in Lean 4
import Mathlib.Basic.Real.Basic import Mathlib.Tactic variable (a : ℕ → ℝ) def SeqLim (a : ℕ → ℝ) (L : ℝ) : Prop := ∀ ε > 0, ∃ k : ℕ, ∀ n ≥ k, |a n - L| < ε def SeqConv (a : ℕ → ℝ) : Prop := ∃ L, SeqLim a L def SeqBdd (a : ℕ → ℝ) : Prop := ∃ M > 0, ∀ n, |a n| ≤ M def IsExtraction (φ : ℕ → ℕ) : Prop := StrictMono φ def Subseq (v u : ℕ → ℝ) : Prop := ∃ φ, IsExtraction φ ∧ v = u ∘ φ open Finset lemma Challenge17_L1 (h : SeqLim a L) : ∃ k, ∀ n ≥ k, |a n| < |L| + 1 := (h 1 one_pos).imp fun _k hk n hn => -- _k : ℕ -- hk : ∀ n ≥ _k, |a n - L| < 1 -- n : ℕ -- hn : n ≥ _k -- ⊢ |a n| < |L| + 1 calc |a n| = |L + (a n - L)| := congrArg abs (add_sub_cancel L (a n)).symm _ ≤ |L| + |a n - L| := abs_add_le L (a n - L) _ < |L| + 1 := add_lt_add_right (hk n hn) |L| lemma Challenge17_L2 (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)⟩ lemma seqBdd_of_seqConv -- from Challenge 17 (ha : SeqConv a) : SeqBdd a := by obtain ⟨L, hL⟩ := ha -- L : ℝ -- hL : SeqLim a L obtain ⟨k, hk⟩ := Challenge17_L1 a hL -- k : ℕ -- hk : ∀ n ≥ k, |a n| < |L| + 1 obtain ⟨C, hC⟩ := Challenge17_L2 a k -- C : ℝ -- hC : ∀ i < k, |a i| ≤ C set M := max (|L| + 1) C -- hM : M = max (|L| + 1) C use M -- ⊢ M > 0 ∧ ∀ (n : ℕ), |a n| ≤ M constructor · -- ⊢ M > 0 calc M ≥ |L| + 1 := le_max_left (|L| + 1) C _ ≥ 0 + 1 := add_le_add_left (abs_nonneg L) 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 _ C · -- hn2 : k ≤ n calc |a n| ≤ |L| + 1 := le_of_lt (hk n hn2) _ ≤ M := le_max_left (|L| + 1) _ -- Solutions to the challenge -- ========================== -- Proof 1 -- ======= example (ha : ∀ n, a n = n) : ¬ ∃ b, Subseq b a ∧ SeqConv b := by rintro ⟨b, hb1, hb2⟩ -- b : ℕ → ℝ -- hb1 : Subseq b a -- hb2 : SeqConv b -- ⊢ False have h1 : SeqBdd b := seqBdd_of_seqConv b hb2 obtain ⟨M, -, hM⟩ := h1 -- M : ℝ -- hM : ∀ (n : ℕ), |b n| ≤ M obtain ⟨k, hk⟩ := exists_nat_gt M -- k : ℕ -- hk : M < ↑k obtain ⟨φ, hφ, hb⟩ := hb1 -- hφ : IsExtraction φ -- hb : b = a ∘ φ apply lt_irrefl M -- ⊢ M < M calc M < (k : ℝ) := by grind _ ≤ (φ k : ℝ) := by exact_mod_cast hφ.le_apply _ = a (φ k) := by grind _ = b k := (congrFun hb k).symm _ ≤ |b k| := by grind _ ≤ M := by grind -- Proof 2 -- ======= example (ha : ∀ n, a n = n) : ¬ ∃ b, Subseq b a ∧ SeqConv b := by rintro ⟨b, hb1, hb2⟩ -- b : ℕ → ℝ -- hb1 : Subseq b a -- hb2 : SeqConv b -- ⊢ False have h1 : SeqBdd b := seqBdd_of_seqConv b hb2 obtain ⟨M, -, hM⟩ := h1 -- M : ℝ -- hM : ∀ (n : ℕ), |b n| ≤ M obtain ⟨k, hk⟩ := exists_nat_gt M -- k : ℕ -- hk : M < ↑k obtain ⟨φ, hφ, hb⟩ := hb1 -- hφ : IsExtraction φ -- hb : b = a ∘ φ apply lt_irrefl M -- ⊢ M < M calc M < (k : ℝ) := hk _ ≤ (φ k : ℝ) := by exact_mod_cast hφ.le_apply _ = a (φ k) := (ha (φ k)).symm _ = b k := (congrFun hb k).symm _ ≤ |b k| := le_abs_self (b k) _ ≤ M := hM k -- Proof 3 -- ======= example (ha : ∀ n, a n = n) : ¬ ∃ b, Subseq b a ∧ SeqConv b := by rintro ⟨_, ⟨φ, hφ, rfl⟩, hb2⟩ -- φ : ℕ → ℕ -- hφ : IsExtraction φ -- hb2 : SeqConv (a ∘ φ) -- ⊢ False obtain ⟨M, -, hM⟩ := seqBdd_of_seqConv (a ∘ φ) hb2 -- M : ℝ -- hM : ∀ (n : ℕ), |(a ∘ φ) n| ≤ M obtain ⟨k, hk⟩ := exists_nat_gt M -- k : ℕ -- hk : M < ↑k exact lt_irrefl M <| calc M < (k : ℝ) := hk _ ≤ (φ k : ℝ) := mod_cast hφ.le_apply _ = (a ∘ φ) k := (ha (φ k)).symm _ ≤ |(a ∘ φ) k| := le_abs_self _ _ ≤ M := hM k -- Proof 4 -- ======= example (ha : ∀ n, a n = n) : ¬ ∃ b, Subseq b a ∧ SeqConv b := by rintro ⟨b, hb1, hb2⟩ -- b : ℕ → ℝ -- hb1 : Subseq b a -- hb2 : SeqConv b -- ⊢ False have h1 : SeqBdd b := seqBdd_of_seqConv b hb2 obtain ⟨M, -, hM⟩ := h1 -- M : ℝ -- hM : ∀ (n : ℕ), |b n| ≤ M set k : ℕ := ⌈M⌉₊ + 1 obtain ⟨φ, hφ, hb⟩ := hb1 -- hφ : IsExtraction φ -- hb : b = a ∘ φ apply lt_irrefl M -- ⊢ M < M calc M ≤ ⌈M⌉₊ := Nat.le_ceil M _ < ⌈M⌉₊ + 1 := lt_add_one (⌈M⌉₊ : ℝ) _ = k := (Nat.cast_add_one ⌈M⌉₊).symm _ ≤ (φ k : ℝ) := by exact_mod_cast hφ.le_apply _ = a (φ k) := (ha (φ k)).symm _ = b k := (congrFun hb k).symm _ ≤ |b k| := le_abs_self (b k) _ ≤ M := hM k
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