AFTD Auto-Formalizing Theoretical Domains

binary_extremizer_has_singleton_sccs

theoremverified

For every natural number n, the binary extremizer NFA binary_extremizer_nfa n has singleton strongly connected components.

Statement

theorem binary_extremizer_has_singleton_sccs (n : ℕ) :
    nfa_has_singleton_sccs (binary_extremizer_nfa n)
Source
arXiv:2610.08525, Stronger bounds on the degree of ambiguity of finite automata
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • binary_extremizer_nfaFor each n, binary_extremizer_nfa n is the NFA over alphabet Fin 2 with states Fin n, unique initial state 0, unique accepting state n -…
  • nfa_has_singleton_sccsAn NFA M has singleton strongly connected components if for all states p and q, whenever q is reachable from {p} by some word and p is…

Read back from the Lean

For every natural number $n$, the NFA binary_extremizer_nfa n has singleton strongly connected components: for any two states $p, q : \text{Fin } n$, if $q$ is reachable from $\{p\}$ via some word $w_1$ over $\text{Fin } 2$ and $p$ is reachable from $\{q\}$ via some word $w_2$ over $\text{Fin } 2$, then $p = q$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof shows that any reachable path in the binary extremizer NFA cannot decrease state indices. First, case analysis on the transition relation shows that every single transition from p to q satisfies p.val ≤ q.val. By induction on word length and transitivity of ≤, this non-decreasing property extends to all paths. Therefore, any two mutually reachable states p and q must satisfy both p.val ≤ q.val and q.val ≤ p.val, forcing p = q by antisymmetry and ensuring that all strongly connected components are singletons.

  1. Any single transition preserves non-decreasing state indices: if q ∈ step p k, then p.val ≤ q.val.

    Unfolding the definition of the binary extremizer NFA's transition relation reveals three cases: either p.val < q.val (which implies p.val ≤ q.val by le_of_lt), or p.val = 0 and q.val = 0 (which gives 0 ≤ 0), or q.val = p.val (which holds reflexively).

    lines 3–7

    uses le_of_lt

      dsimp [binary_extremizer_nfa] at h
      rcases h with hlt | ⟨-, hp, hq⟩ | ⟨-, -, hqp⟩
      · exact le_of_lt hlt
      · rw [hp, hq]
      · rw [hqp]
  2. Evaluating on the empty word preserves state index ordering: if q ∈ evalFrom {p} [], then p.val ≤ q.val.

    We proceed by induction on the word w, generalizing over p. In the base case w = [], the set of states reached from {p} is just {p} by NFA.evalFrom_nil and Set.mem_singleton_iff, so q = p and reflexivity gives p.val ≤ q.val.

    lines 11–13

    uses NFA.evalFrom_nil, Set.mem_singleton_iff

      induction' w with a w ih generalizing p
      · simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h
        rw [h]
  3. Evaluating on any non-empty word preserves state index ordering: if q ∈ evalFrom {p} (a :: w), then p.val ≤ q.val.

    In the inductive step for a :: w, applying NFA.evalFrom_cons, NFA.stepSet_singleton, and NFA.mem_evalFrom_iff_exists shows that reaching q requires transitioning on symbol a to some intermediate state r, and then reaching q from r via w. By binary_extremizer_has_singleton_sccs_step_le, p.val ≤ r.val, and by the induction hypothesis on w, r.val ≤ q.val. Transitivity of inequality (le_trans) then gives p.val ≤ q.val.

    lines 14–19

    uses NFA.evalFrom_cons, NFA.stepSet_singleton, NFA.mem_evalFrom_iff_exists, binary_extremizer_has_singleton_sccs_step_le, le_trans

      · rw [NFA.evalFrom_cons, NFA.stepSet_singleton] at h
        rw [NFA.mem_evalFrom_iff_exists] at h
        rcases h with ⟨r, hr, hq⟩
        have h1 := binary_extremizer_has_singleton_sccs_step_le hr
        have h2 := ih hq
        exact le_trans h1 h2
  4. Mutually reachable states p and q satisfy p.val ≤ q.val and q.val ≤ p.val.

    Assume p and q are mutually reachable, witnessed by words w₁ taking p to q and w₂ taking q to p. Applying binary_extremizer_has_singleton_sccs_evalFrom_le to each path yields p.val ≤ q.val and q.val ≤ p.val.

    lines 24–26

    uses binary_extremizer_has_singleton_sccs_evalFrom_le

      intro p q ⟨w1, hw1⟩ ⟨w2, hw2⟩
      have h1 := binary_extremizer_has_singleton_sccs_evalFrom_le n w1 hw1
      have h2 := binary_extremizer_has_singleton_sccs_evalFrom_le n w2 hw2
  5. p = q, proving that every strongly connected component is a singleton.

    By extensionality for Fin n (ext), equality of p and q reduces to equality of their numerical values, p.val = q.val. Linear integer arithmetic (omega) deduces p.val = q.val from the mutual inequalities p.val ≤ q.val and q.val ≤ p.val.

    lines 27–28

      ext
      omega
binary_extremizer_has_singleton_sccs_step_le
Any single transition from state p to state q in the binary extremizer NFA satisfies p.val ≤ q.val.
binary_extremizer_has_singleton_sccs_evalFrom_le
If state q is reachable from state p via an input word w in the binary extremizer NFA, then p.val ≤ q.val.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
le_trans
The inequality relation ≤ is transitive: a ≤ b and b ≤ c imply a ≤ c.
NFA.evalFrom_nil
Evaluating an NFA from a set of states on the empty word yields the starting set itself.
Set.mem_singleton_iff
An element belongs to a singleton set {b} if and only if it equals b.
NFA.evalFrom_cons
Evaluating an NFA on a word a :: x from a set of states S equals evaluating x from the set of states reached from S on symbol a.
NFA.stepSet_singleton
Transitioning a singleton set {s} on an input symbol a yields the step set of s on a.
NFA.mem_evalFrom_iff_exists
A state is reachable from a set S on word x if and only if it is reachable on x from some state in 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

lemma binary_extremizer_has_singleton_sccs_step_le {n : ℕ} {p q : Fin n} {k : Fin 2}    (h : q ∈ (binary_extremizer_nfa n).step p k) : p.val ≤ q.val := by  dsimp [binary_extremizer_nfa] at h  rcases h with hlt | ⟨-, hp, hq⟩ | ⟨-, -, hqp⟩  · exact le_of_lt hlt  · rw [hp, hq]  · rw [hqp]lemma binary_extremizer_has_singleton_sccs_evalFrom_le (n : ℕ) (w : List (Fin 2)) {p q : Fin n}    (h : q ∈ (binary_extremizer_nfa n).evalFrom {p} w) : p.val ≤ q.val := by  induction' w with a w ih generalizing p  · simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h    rw [h]  · rw [NFA.evalFrom_cons, NFA.stepSet_singleton] at h    rw [NFA.mem_evalFrom_iff_exists] at h    rcases h with ⟨r, hr, hq⟩    have h1 := binary_extremizer_has_singleton_sccs_step_le hr    have h2 := ih hq    exact le_trans h1 h2/-- The binary extremizer automaton has singleton strongly connected components. -/theorem binary_extremizer_has_singleton_sccs (n : ℕ) :    nfa_has_singleton_sccs (binary_extremizer_nfa n) := by  intro p q ⟨w1, hw1⟩ ⟨w2, hw2⟩  have h1 := binary_extremizer_has_singleton_sccs_evalFrom_le n w1 hw1  have h2 := binary_extremizer_has_singleton_sccs_evalFrom_le n w2 hw2  ext  omega
See it in the graphDiscuss this resultChallenge it