AFTD Auto-Formalizing Theoretical Domains

nfa_run_count_fiberwise_sum

theoremverified

The number of runs of w ++ [a] from p to q is the sum over all states s of the number of runs whose penultimate state is s.

Statement

open Classical in
theorem nfa_run_count_fiberwise_sum {α σ : Type*} [Fintype σ] (M : NFA α σ) (w : List α) (a : α)
    (p q : σ) :
    nfa_run_count_list M (w ++ [a]) p q =
      ∑ s : σ, {r : Fin ((w ++ [a]).length + 1) → σ |
        r 0 = p ∧ r (Fin.last (w ++ [a]).length) = q ∧
        (∀ i : Fin (w ++ [a]).length, r i.succ ∈ M.step (r i.castSucc) ((w ++ [a]).get i)) ∧
        r ⟨w.length, by simp⟩ = s}.ncard
Source
step towards nfa_run_count_list_concat
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • nfa_run_count_listThe number of runs of the word w in the NFA M from state p to state q: state sequences of length |w|+1 that start at p, end at q and…
Used by 1
  • nfa_run_count_list_concatNumber of runs on w++[a] from p to q equals the sum over s of the number of runs on w from p to s, taken over the predecessors s of q on…

The proof, explained

The count of runs of w ++ [a] from p to q is partitioned by the penultimate state of the run, which is the state at index |w|. By defining the projection f mapping each run to its penultimate state, the theorem follows by applying the fiberwise counting identity `Finset.card_eq_sum_card_fiberwise` to the finset of all valid runs.

  1. Formulate the total number of runs as the cardinality of the set S of valid runs, to be partitioned by the penultimate state projection f.

    We define S as the set of runs of w ++ [a] from p to q, and f as the projection sending a run to its state at index |w| (the penultimate state). The index bound |w| < |w ++ [a]| + 1 is proved automatically by `simp`. The goal is then restated via `change` to equate the cardinality of S with the sum over all states s of the cardinalities of the sets of runs whose penultimate state is s.

    lines 9–17

            r ⟨w.length, by simp⟩ = s}.ncard := by
      let S : Set (Fin ((w ++ [a]).length + 1) → σ) :=
        {r | r 0 = p ∧ r (Fin.last (w ++ [a]).length) = q ∧
          ∀ i : Fin (w ++ [a]).length, r i.succ ∈ M.step (r i.castSucc) ((w ++ [a]).get i)}
      let f : (Fin ((w ++ [a]).length + 1) → σ) → σ := fun r => r ⟨w.length, by simp⟩
      change S.ncard = ∑ s : σ, {r : Fin ((w ++ [a]).length + 1) → σ |
            r 0 = p ∧ r (Fin.last (w ++ [a]).length) = q ∧
            (∀ i : Fin (w ++ [a]).length, r i.succ ∈ M.step (r i.castSucc) ((w ++ [a]).get i)) ∧
            r ⟨w.length, by simp⟩ = s}.ncard
  2. Express the size of S as the sum over all states of the sizes of the fibers of f.

    We convert the set cardinality of S to the cardinality of `S.toFinset` using `Set.ncard_eq_toFinset_card'`. By `Finset.card_eq_sum_card_fiberwise`, with the target set being the universal set `Finset.univ` (since every state belongs to it by `Finset.mem_univ`), the total number of runs equals the sum over all states s of the number of runs mapped by f to s.

    lines 18–19

    uses Set.ncard_eq_toFinset_card', Finset.card_eq_sum_card_fiberwise, Finset.mem_univ

      rw [Set.ncard_eq_toFinset_card']
      rw [Finset.card_eq_sum_card_fiberwise (t := Finset.univ) (f := f) (s := S.toFinset) (fun _ _ => Finset.mem_univ _)]
  3. Reduce equality of the two sums over all states to equality of their corresponding terms for each state s.

    Applying `Finset.sum_congr` with identical indexing sets reduces the sum equality to showing that for any fixed state s, the size of the fiber of f over s equals the number of runs having penultimate state s.

    lines 20–21

    uses Finset.sum_congr

      apply Finset.sum_congr rfl
      intro s _
  4. For each state s, the fiber of f over s coincides with the specified set of runs.

    Using `Set.ncard_eq_toFinset_card'`, we convert the right-hand set cardinality to a finset cardinality. By `congr 1`, it suffices to show equality of the underlying finsets. By extensionality (`ext r`), an element belongs to the left-hand finset if and only if it is in `S.toFinset` and satisfies f(r) = s (via `Finset.mem_filter` and `Set.mem_toFinset`). Unfolding the definitions of S and f (`dsimp [S, f]`), this condition is identical to the defining conjunction of the right-hand set, so propositional logic (`tauto`) finishes the proof.

    lines 22–27

    uses Set.ncard_eq_toFinset_card', Finset.mem_filter, Set.mem_toFinset

      rw [Set.ncard_eq_toFinset_card']
      congr 1
      ext r
      simp only [Finset.mem_filter, Set.mem_toFinset]
      dsimp [S, f]
      tauto
Set.ncard_eq_toFinset_card'
The cardinality of a set equals the cardinality of its finset representation.
Finset.card_eq_sum_card_fiberwise
If a map f sends a finset s into a finset t, the cardinality of s equals the sum over b in t of the sizes of the fibers {a ∈ s | f a = b}.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.sum_congr
Two sums over the same finset are equal if their summands agree on every element.
Finset.mem_filter
An element is in `Finset.filter p s` if and only if it is in s and satisfies p.
Set.mem_toFinset
An element is in `s.toFinset` if and only if it is in the set s.

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

open Classical in/-- The total number of runs of w ++ [a] from p to q is the sum over all states s of the number of runs whose penultimate state is s. -/theorem nfa_run_count_fiberwise_sum {α σ : Type*} [Fintype σ] (M : NFA α σ) (w : List α) (a : α)    (p q : σ) :    nfa_run_count_list M (w ++ [a]) p q =      ∑ s : σ, {r : Fin ((w ++ [a]).length + 1) → σ |        r 0 = p ∧ r (Fin.last (w ++ [a]).length) = q ∧        (∀ i : Fin (w ++ [a]).length, r i.succ ∈ M.step (r i.castSucc) ((w ++ [a]).get i)) ∧        r ⟨w.length, by simp⟩ = s}.ncard := by  let S : Set (Fin ((w ++ [a]).length + 1) → σ) :=    {r | r 0 = p ∧ r (Fin.last (w ++ [a]).length) = q ∧      ∀ i : Fin (w ++ [a]).length, r i.succ ∈ M.step (r i.castSucc) ((w ++ [a]).get i)}  let f : (Fin ((w ++ [a]).length + 1) → σ) → σ := fun r => r ⟨w.length, by simp⟩  change S.ncard = ∑ s : σ, {r : Fin ((w ++ [a]).length + 1) → σ |        r 0 = p ∧ r (Fin.last (w ++ [a]).length) = q ∧        (∀ i : Fin (w ++ [a]).length, r i.succ ∈ M.step (r i.castSucc) ((w ++ [a]).get i)) ∧        r ⟨w.length, by simp⟩ = s}.ncard  rw [Set.ncard_eq_toFinset_card']  rw [Finset.card_eq_sum_card_fiberwise (t := Finset.univ) (f := f) (s := S.toFinset) (fun _ _ => Finset.mem_univ _)]  apply Finset.sum_congr rfl  intro s _  rw [Set.ncard_eq_toFinset_card']  congr 1  ext r  simp only [Finset.mem_filter, Set.mem_toFinset]  dsimp [S, f]  tauto
See it in the graphDiscuss this resultChallenge it