AFTD Auto-Formalizing Theoretical Domains

op75_tm2_iter_measure_bound

theoremverified

If every transition of a partial state machine increases a natural-valued measure by at most C, then any n-step run increases it by at most C times n.

Statement

theorem op75_tm2_iter_measure_bound {α : Type} (f : α → Option α) (measure : α → ℕ) (C : ℕ)
    (hstep : ∀ a b, f a = some b → measure b ≤ measure a + C)
    (n : ℕ) (a b : α)
    (h : ((fun o : Option α => o.bind f))^[n] (some a) = some b) :
    measure b ≤ measure a + C*n
Source
OP-75 Karp-reduction composition: finite-statement stack-growth bound in the repository TM2 model.
Verified
15 Nov 2026
Axioms
Quot.soundpropext
Used by 1
  • op75_tm2_output_linear_boundFor any finite TM2, there is a constant C such that for every input and output, a halting run of at most n steps has output length at most…

The proof, explained

The theorem is proved by induction on the number of steps n, generalizing over the final state b. For n = 0, the state is unchanged (a = b) and the bound is trivial. For n + 1 steps, the run is decomposed into an n-step prefix reaching an intermediate state mid followed by one final step to b; applying the induction hypothesis to the prefix and the single-step bound to the last transition gives the result by linear arithmetic.

  1. The base case n = 0 holds because running zero steps leaves the state unchanged, so a = b.

    We proceed by induction on n, keeping the destination b general. In the base case n = 0, applying zero transitions is the identity function (Function.iterate_zero, id_eq), reducing the run hypothesis to some a = some b. By injectivity of the some constructor (Option.some.inj), we have a = b. The goal then simplifies to measure a ≤ measure a + C * 0, which holds trivially.

    lines 6–10

    uses Function.iterate_zero, id_eq, Option.some.inj

      induction n generalizing b with
      | zero =>
          simp only [Function.iterate_zero, id_eq] at h
          cases Option.some.inj h
          simp
  2. In the inductive step for n + 1, the computation factors into an n-step run reaching an intermediate state mid and a final step from mid to b.

    For n + 1 iterations, we rewrite the (n + 1)-fold application as the transition f applied to the result of n iterations (Function.iterate_succ_apply'). We then case-split on whether the first n steps terminate in none or reach some state mid. If they yielded none, binding f would immediately yield none, contradicting the assumption that the run reached some b. Therefore, after n steps the state must be some mid.

    lines 11–15

    uses Function.iterate_succ_apply'

      | succ n ih =>
          rw [Function.iterate_succ_apply']  at h
          cases hp : ((fun o : Option α => o.bind f))^[n] (some a) with
          | none => simp [hp] at h
          | some mid =>
  3. The measure of mid is bounded by measure a + C * n, and the measure of b is bounded by measure mid + C.

    Applying the induction hypothesis (ih) to the n-step run reaching mid bounds the measure of mid by measure a + C * n. Simplifying the full run equation with this intermediate state reveals that the final transition is f mid = some b. Applying the assumption on single transitions (hstep) to this final step gives measure b ≤ measure mid + C.

    lines 16–18

              have hm := ih mid hp
              have hf : f mid = some b := by simpa [hp] using h
              have hs := hstep mid b hf
  4. The bound measure b ≤ measure a + C * (n + 1) follows by linear arithmetic.

    Rewriting C * (n + 1) as C * n + C (Nat.mul_succ) and combining the bound on mid from the induction hypothesis with the single-step bound from mid to b yields the desired inequality by linear arithmetic (omega).

    lines 19–20

    uses Nat.mul_succ

              simp only [Nat.mul_succ]
              omega
Function.iterate_zero
Iterating any function zero times is the identity function: f^[0] = id.
id_eq
Applying the identity function returns the argument unchanged: id a = a.
Option.some.inj
The some constructor is injective: some x = some y implies x = y.
Function.iterate_succ_apply'
Iterating a function n + 1 times equals applying it once to the result of iterating it n times: f^[n + 1] x = f (f^[n] x).
Nat.mul_succ
Multiplication distributes over successor for natural numbers: n * (m + 1) = n * m + n.

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

theorem op75_tm2_iter_measure_bound {α : Type} (f : α → Option α) (measure : α → ℕ) (C : ℕ)    (hstep : ∀ a b, f a = some b → measure b ≤ measure a + C)    (n : ℕ) (a b : α)    (h : ((fun o : Option α => o.bind f))^[n] (some a) = some b) :    measure b ≤ measure a + C*n := by  induction n generalizing b with  | zero =>      simp only [Function.iterate_zero, id_eq] at h      cases Option.some.inj h      simp  | succ n ih =>      rw [Function.iterate_succ_apply']  at h      cases hp : ((fun o : Option α => o.bind f))^[n] (some a) with      | none => simp [hp] at h      | some mid =>          have hm := ih mid hp          have hf : f mid = some b := by simpa [hp] using h          have hs := hstep mid b hf          simp only [Nat.mul_succ]          omega
See it in the graphDiscuss this resultChallenge it