Challenge 28: The sequence aₙ = n is unbounded
Prove that the sequence \(a_{n} = n\) is unbounded.
To do this, complete the following theory in Lean 4
import Mathlib.Basic.Real.Basic import Mathlib.Tactic def SeqBdd (a : ℕ → ℝ) : Prop := ∃ M > 0, ∀ n, |a n| ≤ M variable {a : ℕ → ℝ} example (ha : ∀ n, a n = n) : ¬ SeqBdd a := by sorry
1. Proofs in natural language
Proof 1 in natural language (NL1)
Suppose that there exists \(M \in \mathbb{R}\) such that \[ \forall n, |a_n| \leq M. \tag{1} \] By the Archimedean property, there exists \(k \in ℕ\) such that \[ M < k \tag{2} \] and recall that \[ \forall n, a_n = n. \tag{3} \] Then \[ \begin{array}{llll} M &< k &&\text{[by (2)]} \\ &= a_k &&\text{[by (3)]} \\ &\leq |a_k| \\ &\leq M &&\text{[by (1)]} \end{array} \] Therefore, \(M < M\), which is a contradiction.
Proof 2 in natural language (NL2)
Suppose that there exists \(M \in \mathbb{R}\) such that \[ \forall n, |a_n| \leq M. \tag{1} \] Let \[ k = ⌈M⌉ + 1 \tag{2} \] and recall that \[ \forall n, a_n = n. \tag{3} \] Then \[ \begin{array}{llll} M &\leq ⌈M⌉ \\ &< ⌈M⌉ + 1 \\ &= k &&\text{[by (2)]} \\ &= a_k &&\text{[by (3)]} \\ &\leq |a_k| \\ &\leq M &&\text{[by (1)]} \end{array} \] Therefore, \(M < M\), which is a contradiction.
2. Proofs in Lean 4
import Mathlib.Basic.Real.Basic import Mathlib.Tactic def SeqBdd (a : ℕ → ℝ) : Prop := ∃ M > 0, ∀ n, |a n| ≤ M variable {a : ℕ → ℝ} -- Proof 1 (corresponding to NL1) -- ============================== example (ha : ∀ n, a n = n) : ¬ SeqBdd a := by rintro ⟨M, -, hM⟩ -- M : ℝ -- hM : ∀ (n : ℕ), |a n| ≤ M -- ⊢ False obtain ⟨k, hk⟩ := exists_nat_gt M -- k : ℕ -- hk : M < ↑k apply lt_irrefl M -- ⊢ M < M calc M < k := hk _ = a k := by simp [ha] _ ≤ |a k| := le_abs_self _ _ ≤ M := hM k -- Proof 2 (corresponding to NL2) -- ============================== example (ha : ∀ n, a n = n) : ¬ SeqBdd a := by rintro ⟨M, -, hM⟩ -- M : ℝ -- hM : ∀ (n : ℕ), |a n| ≤ M -- ⊢ False set k : ℕ := ⌈M⌉₊ + 1 with hk apply lt_irrefl M -- ⊢ M < M calc M ≤ ⌈M⌉₊ := Nat.le_ceil M _ < k := by simp [hk] _ = a k := by simp [ha] _ ≤ |a k| := le_abs_self (a k) _ ≤ M := hM k -- Proof 3 (corresponding to NL2) -- ============================== example (ha : ∀ n, a n = n) : ¬ SeqBdd a := by rintro ⟨M, -, hM⟩ -- M : ℝ -- hM : ∀ (n : ℕ), |a n| ≤ M -- ⊢ False set k : ℕ := ⌈M⌉₊ + 1 with hk apply lt_irrefl M -- ⊢ M < M calc M ≤ ⌈M⌉₊ := Nat.le_ceil M _ < ⌈M⌉₊ + 1 := lt_add_one _ _ = k := by rw [hk, Nat.cast_add_one] _ = a k := by rw [ha k] _ ≤ |a k| := le_abs_self (a k) _ ≤ M := hM k -- Proof 4 (corresponding to NL2) -- ============================== example (ha : ∀ n, a n = n) : ¬ SeqBdd a := by rintro ⟨M, -, hM⟩ -- M : ℝ -- hM : ∀ (n : ℕ), |a n| ≤ M -- ⊢ False set k : ℕ := ⌈M⌉₊ + 1 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 _ = a k := (ha k).symm _ ≤ |a k| := le_abs_self (a k) _ ≤ M := hM k
You can inspect, modify and run the code of these proofs interactively in Lean 4 Web.
3. Collaborative solutions
How can you post your solution?
- 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 ```
- During the week you will be able to compare your approach with those of other participants. The official solution will be published [DATE TO BE CONFIRMED, e.g. Monday 23 November 2026].
Comments