AFTD Auto-Formalizing Theoretical Domains

dfa_is_synchronizing_subsingleton

theoremverified

Every word is synchronizing for a deterministic finite automaton whose state type is a subsingleton.

Statement

theorem dfa_is_synchronizing_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) (w : List α) : dfa_is_synchronizing A w
Source
folklore
Verified
09 Nov 2026
Axioms
Quot.soundpropext
Built on 2
  • dfa_is_synchronizingA word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all…
  • pair_encode_injectiveThe pair encoding is injective: if pairEncode w₁ c₁ = pairEncode w₂ c₂ then w₁ = w₂ and c₁ = c₂.
Used by 1

Read back from the Lean

For any alphabet type α and state type σ such that σ is a subsingleton (has at most one element), for every DFA A with state type σ and alphabet α, and for every word w : List α, w is a synchronizing word for A (dfa_is_synchronizing A w).

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

To show that any word w synchronizes a deterministic finite automaton A whose state type σ is a subsingleton, we unfold the definition of a synchronizing word: running w from any two states q₁ and q₂ must reach the same state. Because σ is a subsingleton, any two states in σ are equal, making the condition hold trivially.

  1. Every word w is synchronizing for DFA A when the state type σ is a subsingleton. automation

    Unfolding the definition of a synchronizing word (`dfa_is_synchronizing`), the goal becomes showing that for any two states q₁, q₂ : σ, running w from q₁ and from q₂ leads to the same state: A.evalFrom q₁ w = A.evalFrom q₂ w. Since the state space σ is a subsingleton, any two states in σ are necessarily equal. The simplifier recognizes this subsingleton property and closes the goal immediately. (The lemma `pair_encode_injective` passed to `simpa` is a remnant of automated proof search and plays no role in the mathematical argument.)

    line 2

    uses dfa_is_synchronizing, pair_encode_injective

    theorem dfa_is_synchronizing_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) (w : List α) : dfa_is_synchronizing A w := by first | exact pair_encode_injective | (apply pair_encode_injective <;> assumption) | (apply pair_encode_injective <;> simp_all) | simpa using pair_encode_injective | (simp only [dfa_is_synchronizing] at *; first | exact pair_encode_injective | (apply pair_encode_injective <;> assumption) | (apply pair_encode_injective <;> simp_all) | simpa using pair_encode_injective)
dfa_is_synchronizing
A word w is synchronizing for automaton A if evaluating w from any two states q₁ and q₂ yields the same resulting state: ∀ q₁ q₂ : σ, A.evalFrom q₁ w = A.evalFrom q₂ w.
pair_encode_injective
The pairing encoding of lists is injective: if pairEncode w₁ c₁ = pairEncode w₂ c₂, then w₁ = w₂ and c₁ = c₂.

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

/-- Every word synchronizes a DFA whose state type is a subsingleton. -/theorem dfa_is_synchronizing_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) (w : List α) : dfa_is_synchronizing A w := by first | exact pair_encode_injective | (apply pair_encode_injective <;> assumption) | (apply pair_encode_injective <;> simp_all) | simpa using pair_encode_injective | (simp only [dfa_is_synchronizing] at *; first | exact pair_encode_injective | (apply pair_encode_injective <;> assumption) | (apply pair_encode_injective <;> simp_all) | simpa using pair_encode_injective)
See it in the graphDiscuss this resultChallenge it