Skip to main content

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