nfa_run_count_fiberwise_sum
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.
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.
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
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.
uses
Set.ncard_eq_toFinset_card',Finset.card_eq_sum_card_fiberwise,Finset.mem_univrw [Set.ncard_eq_toFinset_card'] rw [Finset.card_eq_sum_card_fiberwise (t := Finset.univ) (f := f) (s := S.toFinset) (fun _ _ => Finset.mem_univ _)]
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.
uses
Finset.sum_congrapply Finset.sum_congr rfl intro s _
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.
uses
Set.ncard_eq_toFinset_card',Finset.mem_filter,Set.mem_toFinsetrw [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.
- In Lean, indexing into `Fin ((w ++ [a]).length + 1)` at position `w.length` requires a proof that `w.length < (w ++ [a]).length + 1`, which is discharged by `simp`.
- Switching between the cardinality of a set (`Set.ncard`) and the cardinality of a finite set (`Finset.card`) is a formal translation needed to apply `Finset.card_eq_sum_card_fiberwise`.
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.
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