nfa_isomorphic_up_to_perm_refl
Every NFA is isomorphic to itself up to state bijection and alphabet permutation, witnessed by the identity bijection on states and the identity permutation on the alphabet.
Statement
theorem nfa_isomorphic_up_to_perm_refl {α σ : Type*} (M : NFA α σ) : nfa_isomorphic_up_to_perm M M
- Source
- folklore
- Verified
- 29 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- nfa_isomorphic_up_to_permTwo NFAs M₁ and M₂ over alphabet α with state sets σ₁ and σ₂ are isomorphic up to state bijection and alphabet permutation if there exist…
Read back from the Lean
For any types α and σ and any NFA M with alphabet α and state type σ, M is isomorphic up to a permutation of the alphabet to itself (nfa_isomorphic_up_to_perm M M).
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 theorem establishes that the relation of NFA isomorphism up to state bijection and alphabet permutation is reflexive. Unfolding the definition, the proof exhibits the identity equivalence on states and the identity permutation on the alphabet as witnesses. Under these identity mappings, all requirements on start states, accept states, and transition relations reduce to trivial equivalences, which are closed by simplification.
To show that an NFA is isomorphic to itself, it suffices to verify that the identity bijection on states and the identity permutation on the alphabet preserve start states, accept states, and transitions.
Unfolding the definition of isomorphism up to permutation (`nfa_isomorphic_up_to_perm`), we must exhibit a state equivalence $e : \sigma \simeq \sigma$ and an alphabet permutation $\pi : \alpha \simeq \alpha$ that preserve the start states, accept states, and transition relations. We provide the identity equivalence `Equiv.refl` for both $e$ and $\pi$.
uses
Equiv.reflunfold nfa_isomorphic_up_to_perm refine ⟨Equiv.refl σ, Equiv.refl α, ?_⟩
The identity maps preserve start states, accept states, and transitions.
Because `Equiv.refl` maps every state $s$ to $s$ and every alphabet symbol $a$ to $a$, each preservation condition simplifies to a reflexive equivalence ($s \in M.\mathrm{start} \leftrightarrow s \in M.\mathrm{start}$, $s \in M.\mathrm{accept} \leftrightarrow s \in M.\mathrm{accept}$, and $t \in M.\mathrm{step}(s, a) \leftrightarrow t \in M.\mathrm{step}(s, a)$), which Lean's simplifier discharges immediately.
simp
Equiv.refl- The identity equivalence between a type and itself, mapping every element to itself.
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.
/-- NFA isomorphism up to state bijection and alphabet permutation is reflexive. -/theorem nfa_isomorphic_up_to_perm_refl {α σ : Type*} (M : NFA α σ) : nfa_isomorphic_up_to_perm M M := by unfold nfa_isomorphic_up_to_perm refine ⟨Equiv.refl σ, Equiv.refl α, ?_⟩ simp