AFTD Auto-Formalizing Theoretical Domains

nfa_isomorphic_up_to_perm_refl

theoremverified

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.

  1. 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$.

    lines 4–5

    uses Equiv.refl

      unfold nfa_isomorphic_up_to_perm
      refine ⟨Equiv.refl σ, Equiv.refl α, ?_⟩
  2. 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.

    line 6

      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

/-- 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
See it in the graphDiscuss this resultChallenge it