AFTD Auto-Formalizing Theoretical Domains

nfa_run_count_list_nil

theoremverified

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

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

    lines 5–6

    uses List.length_nil, Fin.last_zero, IsEmpty.forall_iff, and_true

      unfold nfa_run_count_list
      simp only [List.length_nil, Fin.last_zero, IsEmpty.forall_iff, and_true]
  2. 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).

    line 7

      split_ifs with h
  3. 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`).

    lines 8–19

    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]
  4. 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`).

    lines 20–25

    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.

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