nfa_run_count_list_nil
There is exactly one empty run from p to q if p = q and none otherwise.
Statement
open Classical in theorem nfa_run_count_list_nil {α σ : Type*} [Fintype σ] (M : NFA α σ) (p q : σ) : nfa_run_count_list M [] p q = if p = q then 1 else 0
- Source
- step towards pell_nfa_run_count_lower_bound
- Verified
- 19 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
- pell_prefix_base_countThe prefix c_1c_2 has 1 run from q_1 to q_2, 2 runs from q_1 to q_3, 1 run from q_1 to q_4, and no runs to any other state, in A_n.
The proof, explained
The proof unfolds the definition of run count for the empty word, where a run is a function from Fin 1 to the state space σ. Because the empty list has length 0, the step conditions hold vacuously, leaving only the boundary requirements that the initial and final state (both r(0)) equal p and q respectively. A case split on p = q then concludes: if p = q, the unique run is the constant function at p (giving cardinality 1), and if p ≠ q, the requirements r(0) = p and r(0) = q are contradictory (giving the empty set of cardinality 0).
The count of runs for the empty word reduces to the cardinality of the set of functions r : Fin 1 → σ satisfying r(0) = p and r(0) = q.
Unfolding the definition of `nfa_run_count_list` for the empty word w = [], the domain of a run is Fin (|w| + 1) = Fin 1, since the empty list has length 0 (`List.length_nil`). The step conditions quantify over Fin 0, which is empty, so they are vacuously satisfied (`IsEmpty.forall_iff`, `and_true`). With `Fin.last 0 = 0` (`Fin.last_zero`), the endpoint condition r(last) = q reduces to r(0) = q, leaving the condition r(0) = p ∧ r(0) = q.
uses
List.length_nil,Fin.last_zero,IsEmpty.forall_iff,and_trueunfold nfa_run_count_list simp only [List.length_nil, Fin.last_zero, IsEmpty.forall_iff, and_true]
It suffices to evaluate the cardinality separately for p = q and p ≠ q.
We split into the two branches of the `if p = q then 1 else 0` expression: assuming p = q (where the target count is 1) and assuming p ≠ q (where the target count is 0).
split_ifs with h
When p = q, the set of runs consists solely of the constant function at p, so its cardinality is 1.
Substituting q = p (`subst h`), the condition on a run r becomes r(0) = p ∧ r(0) = p, which simplifies to r(0) = p (`and_self`). Since Fin 1 contains only the single element 0, any function r with r(0) = p is identical to the constant function x ↦ p. Thus the set of runs is the singleton {x ↦ p} (`Set.mem_singleton_iff`), whose cardinality is 1 (`Set.ncard_singleton`).
uses
and_self,Set.mem_singleton_iff,Set.ncard_singleton· subst h have : {r : Fin 1 → σ | r 0 = p ∧ r 0 = p} = {fun _ => p} := by ext r simp only [and_self, Set.mem_singleton_iff] constructor · intro hr ext i fin_cases i exact hr · rintro rfl rfl rw [this, Set.ncard_singleton]
When p ≠ q, the set of runs is empty, so its cardinality is 0.
If there were a run r : Fin 1 → σ, it would satisfy both r(0) = p and r(0) = q, which by symmetry and transitivity would imply p = q. This contradicts the assumption p ≠ q (`Set.mem_empty_iff_false`, `iff_false`). Hence no such run exists, the set of runs is empty, and its cardinality is 0 (`Set.ncard_empty`).
uses
Set.mem_empty_iff_false,iff_false,Set.ncard_empty· have : {r : Fin 1 → σ | r 0 = p ∧ r 0 = q} = ∅ := by ext r simp only [Set.mem_empty_iff_false, iff_false] rintro ⟨h1, h2⟩ exact h (h1.symm.trans h2) rw [this, Set.ncard_empty]
List.length_nil- The empty list has length 0.
Fin.last_zero- The last element of Fin 1 (indexed by 0) is 0.
IsEmpty.forall_iff- A universal quantification over an empty type is vacuously true.
and_true- Conjoining a proposition with True is equivalent to the proposition itself.
and_self- Conjoining a proposition with itself is equivalent to the proposition.
Set.mem_singleton_iff- An element belongs to a singleton set if and only if it equals the member of that set.
Set.ncard_singleton- The cardinality of a singleton set is 1.
iff_false- An equivalence between a proposition and False is equivalent to the negation of the proposition.
Set.mem_empty_iff_false- Belonging to the empty set is false for any element.
Set.ncard_empty- The cardinality of the empty set is 0.
- Formalizing that a function from Fin 1 to σ is uniquely determined by its value at 0 requires function extensionality followed by finite case exhaustion (`fin_cases i`), whereas on paper this identification is immediate.
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/-- There is exactly one run of the empty word from p to q, namely when p = q. -/theorem nfa_run_count_list_nil {α σ : Type*} [Fintype σ] (M : NFA α σ) (p q : σ) : nfa_run_count_list M [] p q = if p = q then 1 else 0 := by unfold nfa_run_count_list simp only [List.length_nil, Fin.last_zero, IsEmpty.forall_iff, and_true] split_ifs with h · subst h have : {r : Fin 1 → σ | r 0 = p ∧ r 0 = p} = {fun _ => p} := by ext r simp only [and_self, Set.mem_singleton_iff] constructor · intro hr ext i fin_cases i exact hr · rintro rfl rfl rw [this, Set.ncard_singleton] · have : {r : Fin 1 → σ | r 0 = p ∧ r 0 = q} = ∅ := by ext r simp only [Set.mem_empty_iff_false, iff_false] rintro ⟨h1, h2⟩ exact h (h1.symm.trans h2) rw [this, Set.ncard_empty]