AFTD Auto-Formalizing Theoretical Domains

is_complete_sequence_const_one

theoremverified

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.

  1. 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.

    lines 4–5

      intro t ht
      refine ⟨Finset.Icc 1 t.toNat, ?_, ?_⟩
  2. 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.

    lines 6–7

    uses Finset.mem_Icc.mp

      · intro i hi
        exact (Finset.mem_Icc.mp hi).1
  3. 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.

    line 8

    uses Int.toNat_of_nonneg

      · have htn : (t.toNat : ℤ) = t := Int.toNat_of_nonneg (by omega)
  4. 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.

    lines 9–11

    uses Finset.mem_Icc.mp

        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]
  5. 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.

    lines 12–13

    uses Finset.sum_congr

        rw [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.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it