AFTD Auto-Formalizing Theoretical Domains

dfa_is_synchronizable_subsingleton

theoremverified

Every deterministic finite automaton whose state type is a subsingleton is synchronizable.

Statement

theorem dfa_is_synchronizable_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) : dfa_is_synchronizable A
Source
folklore
Verified
09 Nov 2026
Axioms
Quot.soundpropext
Built on 3
  • dfa_is_synchronizableA deterministic finite automaton A : DFA α σ is synchronizable if there exists a synchronizing word w : List α for A.
  • dfa_is_synchronizing_subsingletonEvery word is synchronizing for a deterministic finite automaton whose state type is a subsingleton.
  • 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…

Read back from the Lean

For all types α and σ where σ is a subsingleton (has at most one element), and for every deterministic finite automaton A : DFA α σ, A is synchronizable.

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

A deterministic finite automaton is synchronizable if there exists an input word that takes all states to the same state. When the state space is a subsingleton, any two states are already equal, so every word is synchronizing. The theorem is proved by exhibiting the empty word as an explicit witness and invoking `dfa_is_synchronizing_subsingleton`.

  1. The automaton $A$ is synchronizable.

    By definition, an automaton is synchronizable if there exists some word that transitions every state to the same state. The proof provides the empty word `[]` as an explicit witness, and satisfies the requirement that it is synchronizing using `dfa_is_synchronizing_subsingleton`, which holds because the state type $\sigma$ is a subsingleton.

    line 2

    uses dfa_is_synchronizing_subsingleton

    theorem dfa_is_synchronizable_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) : dfa_is_synchronizable A := ⟨[], dfa_is_synchronizing_subsingleton A []⟩
dfa_is_synchronizing_subsingleton
For any deterministic finite automaton whose state type is a subsingleton, every input word is synchronizing.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Sanity lemma: a DFA on a subsingleton state type is synchronizable. -/theorem dfa_is_synchronizable_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) : dfa_is_synchronizable A := ⟨[], dfa_is_synchronizing_subsingleton A []⟩
See it in the graphDiscuss this resultChallenge it