AFTD Auto-Formalizing Theoretical Domains

pell_run_encard_eq_count

theoremverified

The set of accepting runs of u_n in A_n has encard equal to the number of runs from q_1 to q_n.

Statement

open Classical in
theorem pell_run_encard_eq_count (n : ℕ) (hn : 3 ≤ n) :
    Set.encard {r : Fin ((pell_word n).length + 1) → Fin n |
        r 0 ∈ (pell_nfa n).start ∧
        r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧
        ∀ i : Fin (pell_word n).length,
          r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)}
      = (nfa_run_count_list (pell_nfa n) (pell_word n) ⟨0, by omega⟩ ⟨n - 1, by omega⟩ : ℕ∞)
Source
step towards pell_nfa_run_count_lower_bound
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • pell_wordThe word u_n = c_1 c_2 c_2 c_3 c_3 c_4 ⋯ c_(n-2) c_(n-1), i.e. the concatenation, over 1 ≤ i ≤ n-2, of the two-letter block c_i c_(i+1),…
  • pell_nfaFor every n, the 5-letter automaton A_n of the paper's lower bound: a chain q_1,…,q_n in which, for each 1 ≤ i ≤ n-2, the letter c_i…

The proof, explained

The theorem shows that the extended cardinality of accepting runs of the Pell word in the Pell automaton equals the run count from state 0 to state n - 1. The proof first characterizes the set of accepting runs as the set of runs starting at state 0 and ending at state n - 1, since the automaton's start and accept sets are singletons containing 0 and n - 1, respectively. Finally, rewriting along this set equality and unfolding the definition of the run count expresses both sides as the cardinality of the underlying finite set of runs in ℕ∞.

  1. The initial state 0 and target state n - 1 are well-defined elements of Fin n.

    The theorem statement uses the states ⟨0, ·⟩ and ⟨n - 1, ·⟩ in Fin n. Under the assumption 3 ≤ n, linear arithmetic (`omega`) verifies 0 < n and n - 1 < n, ensuring both state expressions are well-typed.

    line 9

          = (nfa_run_count_list (pell_nfa n) (pell_word n) ⟨0, by omega⟩ ⟨n - 1, by omega⟩ : ℕ∞) := by
  2. The set of accepting runs of pell_word n in pell_nfa n is identical to the set of runs from state 0 to state n - 1.

    We establish the auxiliary equality `hset` by set extensionality (`ext r`). Unfolding the definition of `pell_nfa`, a run is accepting if its initial state has value 0 and its final state has value satisfying `q.val + 1 = n`. Since states belong to `Fin n`, equality of elements is equivalent to equality of their values via `Fin.ext_iff`. For any accepting run, the initial state must be ⟨0, ·⟩ and, since `q.val + 1 = n`, the final state must be ⟨n - 1, ·⟩ by linear arithmetic. Conversely, any run starting at ⟨0, ·⟩ and ending at ⟨n - 1, ·⟩ satisfies the start condition (0 = 0) and the accept condition ((n - 1) + 1 = n). The step conditions are identical on both sides.

    lines 10–30

    uses pell_nfa, Set.mem_setOf_eq, Fin.ext_iff, Fin.val_mk

      have hset : {r : Fin ((pell_word n).length + 1) → Fin n |
            r 0 ∈ (pell_nfa n).start ∧
            r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧
            ∀ i : Fin (pell_word n).length,
              r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)}
          = {r : Fin ((pell_word n).length + 1) → Fin n |
            r 0 = ⟨0, by omega⟩ ∧
            r (Fin.last (pell_word n).length) = ⟨n - 1, by omega⟩ ∧
            ∀ i : Fin (pell_word n).length,
              r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} := by
        ext r
        simp only [pell_nfa, Set.mem_setOf_eq]
        constructor
        · rintro ⟨h1, h2, h3⟩
          refine ⟨?_, ?_, h3⟩
          · rw [Fin.ext_iff]; exact h1
          · rw [Fin.ext_iff]; simp only [Fin.val_mk]; omega
        · rintro ⟨h1, h2, h3⟩
          refine ⟨?_, ?_, h3⟩
          · rw [h1]
          · rw [h2]; simp only [Fin.val_mk]; omega
  3. The extended cardinality of the set of accepting runs equals the run count from state 0 to state n - 1 in ℕ∞.

    Rewriting with the set equality `hset`, the accepting runs are replaced by runs from 0 to n - 1. By `Set.encard_eq_coe_toFinset_card`, the extended cardinality of this finite set of runs is represented as the coercion of its finset cardinality. Unfolding `nfa_run_count_list`, the right-hand side is defined as the natural cardinality (`ncard`) of the same set of runs, which by `Set.ncard_eq_toFinset_card'` also equals the coercion of its finset cardinality. Both sides are identical, concluding the proof.

    lines 31–34

    uses Set.encard_eq_coe_toFinset_card, nfa_run_count_list, Set.ncard_eq_toFinset_card'

      rw [hset]
      rw [Set.encard_eq_coe_toFinset_card]
      unfold nfa_run_count_list
      rw [Set.ncard_eq_toFinset_card']
pell_nfa
The non-deterministic finite automaton for the Pell language on states `Fin n`, with start states satisfying `p.val = 0` and accept states satisfying `q.val + 1 = n`.
Set.mem_setOf_eq
An element `x` belongs to the set `{y | p y}` if and only if the predicate `p x` holds.
Fin.ext_iff
Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Fin.val_mk
For `m < n`, the value of the `Fin n` element `⟨m, h⟩` as a natural number is `m`.
Set.encard_eq_coe_toFinset_card
For a finite set `s`, its extended cardinality in `ℕ∞` equals the coercion of the cardinality of its associated `Finset`.
nfa_run_count_list
The number of runs of automaton `M` on word `w` from state `p` to state `q`, defined as the cardinality (`ncard`) of the set of valid runs.
Set.ncard_eq_toFinset_card'
For a finite set `s`, its natural number cardinality `ncard` equals the cardinality of its associated `Finset`.

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 set of accepting runs of u_n in A_n has the same cardinality as the run count from q_1 to q_n. -/theorem pell_run_encard_eq_count (n : ℕ) (hn : 3 ≤ n) :    Set.encard {r : Fin ((pell_word n).length + 1) → Fin n |        r 0 ∈ (pell_nfa n).start ∧        r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧        ∀ i : Fin (pell_word n).length,          r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)}      = (nfa_run_count_list (pell_nfa n) (pell_word n) ⟨0, by omega⟩ ⟨n - 1, by omega⟩ : ℕ∞) := by  have hset : {r : Fin ((pell_word n).length + 1) → Fin n |        r 0 ∈ (pell_nfa n).start ∧        r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧        ∀ i : Fin (pell_word n).length,          r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)}      = {r : Fin ((pell_word n).length + 1) → Fin n |        r 0 = ⟨0, by omega⟩ ∧        r (Fin.last (pell_word n).length) = ⟨n - 1, by omega⟩ ∧        ∀ i : Fin (pell_word n).length,          r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} := by    ext r    simp only [pell_nfa, Set.mem_setOf_eq]    constructor    · rintro ⟨h1, h2, h3⟩      refine ⟨?_, ?_, h3⟩      · rw [Fin.ext_iff]; exact h1      · rw [Fin.ext_iff]; simp only [Fin.val_mk]; omega    · rintro ⟨h1, h2, h3⟩      refine ⟨?_, ?_, h3⟩      · rw [h1]      · rw [h2]; simp only [Fin.val_mk]; omega  rw [hset]  rw [Set.encard_eq_coe_toFinset_card]  unfold nfa_run_count_list  rw [Set.ncard_eq_toFinset_card']
See it in the graphDiscuss this resultChallenge it