is_complete_sequence_const_one
The sequence defined by H(n) = 1 for all n ≥ 1 and H(0) = 0 is a complete sequence.
Statement
theorem is_complete_sequence_const_one : is_complete_sequence (fun n => if 1 ≤ n then 1 else 0)
- Source
- folklore
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_complete_sequenceA sequence of integers H : ℕ → ℤ is complete if every positive integer t ≥ 1 can be expressed as a sum of terms ∑_{i ∈ S} H i over a…
Read back from the Lean
The sequence H : ℕ → ℤ defined by H(n) = 1 for n ≥ 1 and H(0) = 0 is a complete sequence: for every integer t ≥ 1, there exists a finite set S of natural numbers, all ≥ 1, such that the sum of H(i) over i ∈ S equals t.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the sequence H(n) = 1 (for n ≥ 1) is complete, we must express any integer t ≥ 1 as a sum of terms indexed by a finite set of positive natural numbers. We choose the index set to be the interval {1, …, t}. Every index in this interval is at least 1, and each term in the sum evaluates to 1, so the sum of these t ones equals t.
To represent an integer t ≥ 1, we choose the candidate index set S = {1, …, t.toNat}.
We introduce the target integer t and the assumption 1 ≤ t. By definition of a complete sequence, we must exhibit a finite set of positive natural numbers whose corresponding terms sum to t. We provide the closed interval Finset.Icc 1 t.toNat, which reduces the problem to showing that all its elements are at least 1 and that the sum over this set equals t.
intro t ht refine ⟨Finset.Icc 1 t.toNat, ?_, ?_⟩
Every element in the index set is at least 1.
For any element i in Finset.Icc 1 t.toNat, the characterization of closed intervals (Finset.mem_Icc.mp) provides the bounds 1 ≤ i ≤ t.toNat, from which the lower bound 1 ≤ i follows immediately.
uses
Finset.mem_Icc.mp· intro i hi exact (Finset.mem_Icc.mp hi).1
The coercion of t.toNat to ℤ is equal to t.
From 1 ≤ t, linear arithmetic over ℤ (omega) proves 0 ≤ t. The lemma Int.toNat_of_nonneg then ensures that (t.toNat : ℤ) = t.
uses
Int.toNat_of_nonneg· have htn : (t.toNat : ℤ) = t := Int.toNat_of_nonneg (by omega)
Every summand over the interval {1, …, t.toNat} evaluates to 1.
For each index i in the interval, Finset.mem_Icc.mp guarantees 1 ≤ i, so the conditional expression (if 1 ≤ i then 1 else 0) simplifies to 1.
uses
Finset.mem_Icc.mphave h1 : ∀ i ∈ Finset.Icc 1 t.toNat, (if 1 ≤ i then (1:ℤ) else 0) = 1 := by intro i hi simp [(Finset.mem_Icc.mp hi).1]
The sum of the sequence over {1, …, t.toNat} equals t.
Using Finset.sum_congr, we replace the conditional expression by 1 for every element in the interval. The sum of 1 over {1, …, t.toNat} is the cardinality t.toNat, which equals t by the previously established identity htn.
uses
Finset.sum_congrrw [Finset.sum_congr rfl h1] simp [htn]
Finset.mem_Icc.mp- An element belongs to the closed interval [a, b] if and only if it is at least a and at most b.
Int.toNat_of_nonneg- For any non-negative integer a, converting a to a natural number and coercing back to ℤ yields a.
Finset.sum_congr- If two finite sets are equal and two functions agree on every element of the set, their sums over the set are equal.
- In line 13, `simp` automatically evaluates the sum of the constant 1 over the interval `Finset.Icc 1 t.toNat` to its cardinality `t.toNat`, and applies `htn` to conclude that the result equals `t`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The sequence constant 1 for n ≥ 1 is a complete sequence. -/theorem is_complete_sequence_const_one : is_complete_sequence (fun n => if 1 ≤ n then 1 else 0) := by intro t ht refine ⟨Finset.Icc 1 t.toNat, ?_, ?_⟩ · intro i hi exact (Finset.mem_Icc.mp hi).1 · have htn : (t.toNat : ℤ) = t := Int.toNat_of_nonneg (by omega) have h1 : ∀ i ∈ Finset.Icc 1 t.toNat, (if 1 ≤ i then (1:ℤ) else 0) = 1 := by intro i hi simp [(Finset.mem_Icc.mp hi).1] rw [Finset.sum_congr rfl h1] simp [htn]