dfa_is_synchronizing_subsingleton
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 automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all… - pair_encode_injectiveThe pair encoding is injective: if pairEncode w₁ c₁ = pairEncode w₂ c₂ then w₁ = w₂ and c₁ = c₂.
- dfa_is_synchronizingA word
- Used by 1
- dfa_is_synchronizable_subsingletonEvery deterministic finite automaton whose state type is a subsingleton is synchronizable.
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.
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.)
uses
dfa_is_synchronizing,pair_encode_injectivetheorem 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₂.
- The proof script uses a fallback `first | ...` chain generated by automated proof search that mentions `pair_encode_injective`. The lemma `pair_encode_injective` is irrelevant to synchronization; `simpa` succeeds solely because the state type σ is a subsingleton, which `simp` uses to equate any two states in σ.
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.
/-- 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)