AFTD Auto-Formalizing Theoretical Domains

pell_nfa_no_ida

theoremverified

The Pell automaton A_n does not comply with IDA: there are no distinct states p, q and no word v such that p is reachable from p by v, q from p by v, and q from q by v.

Statement

theorem pell_nfa_no_ida (n : ℕ) : ¬ nfa_complies_ida (pell_nfa n)
Source
step towards finitely_ambiguous_nfa_pell_lower_bound
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • pell_nfaFor every n, the 5-letter automaton A_n of the paper's lower bound: a chain q_1,…,q_n in which, for each 1 ≤ i ≤ n-2, the letter c_i…
  • nfa_complies_idaAn NFA complies with IDA if there exist distinct states p and q and a word v such that p is reachable from p by v, q is reachable from p…
  • pell_nfa_step_tableIn A_n, if q is reachable from p in one step on letter k, then one of the following holds: (i) k ≡ p (mod 5) and q = p or q = p+1; (ii) k…

The proof, explained

The theorem is proved by contradiction: assuming an IDA pattern with distinct states p and q and word v such that p loops on v, q loops on v, and v drives p to q, path monotonicity implies p < q. Because self-loops at p restrict all letters of v to {p mod 5, (p+1) mod 5}, the state reached from p cannot exceed p + 2, limiting q to p + 1 or p + 2. If q = p + 1, self-loops at both states force all letters to be (p+1) mod 5, which preserves {p, p+2} and skips p + 1. If q = p + 2, the first letter must fix both p and p + 2, but the modulo 5 letter requirements for self-loops at indices separated by 2 are disjoint.

  1. If state q is reachable from state p along word v, then p ≤ q.

    By induction on v. For the empty word, q = p and reflexivity applies. For a :: v, the path begins with a step p → m on letter a; the transition table pell_nfa_step_table shows that every transition leaves the state invariant or increases it by 1 or 2, so p ≤ m. The induction hypothesis gives m ≤ q, whence p ≤ q by transitivity.

    lines 3–21

    uses NFA.evalFrom_nil, Set.mem_singleton_iff, le_rfl, NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists, NFA.stepSet, Set.mem_iUnion, pell_nfa_step_table

      induction v generalizing p with
      | nil =>
        simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h
        subst h
        exact le_rfl
      | cons a v ih =>
        rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at h
        rcases h with ⟨m, hm, hq⟩
        rw [NFA.stepSet, Set.mem_iUnion] at hm
        rcases hm with ⟨p', hp'⟩
        rw [Set.mem_iUnion] at hp'
        rcases hp' with ⟨hp_eq, hm_step⟩
        simp only [Set.mem_singleton_iff] at hp_eq
        subst hp_eq
        have h1 : (p' : ℕ) ≤ (m : ℕ) := by
          have := pell_nfa_step_table n hm_step
          rcases this with ⟨-, h'⟩ | ⟨-, h'⟩ | ⟨-, h'⟩ <;> omega
        have h2 := ih hq
        omega
  2. A self-loop at state p on letter k requires k ≡ p (mod 5) or k ≡ p + 1 (mod 5).

    From pell_nfa_step_table, a transition from p to p on letter k can only arise from the first two cases (where k = p % 5 or k = (p + 1) % 5). The third case requires the target state to be at least p + 1, which contradicts reaching p.

    lines 26–30

    uses pell_nfa_step_table

      have := pell_nfa_step_table n h
      rcases this with ⟨hk, -⟩ | ⟨hk, -⟩ | ⟨hk, hq⟩
      · left; exact hk
      · right; exact hk
      · rcases hq with h | h <;> omega
  3. If word a :: v loops at state p, the automaton loops at p on letter a and also loops at p on suffix v.

    The first letter a takes p to some state m from which v leads back to p. Since transitions never decrease states, p ≤ m, and by pell_nfa_no_ida_evalFrom_le, m ≤ p. Hence m = p, establishing both p ∈ step p a and p ∈ evalFrom {p} v.

    lines 35–50

    uses NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists, NFA.stepSet, Set.mem_iUnion, Set.mem_singleton_iff, pell_nfa_step_table, pell_nfa_no_ida_evalFrom_le, Fin.ext

      rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at h
      rcases h with ⟨m, hm, hq⟩
      rw [NFA.stepSet, Set.mem_iUnion] at hm
      rcases hm with ⟨p', hp'⟩
      rw [Set.mem_iUnion] at hp'
      rcases hp' with ⟨hp_eq, hm_step⟩
      simp only [Set.mem_singleton_iff] at hp_eq
      subst hp_eq
      have h1 : (p' : ℕ) ≤ (m : ℕ) := by
        have := pell_nfa_step_table n hm_step
        rcases this with ⟨-, h'⟩ | ⟨-, h'⟩ | ⟨-, h'⟩ <;> omega
      have h2 : (m : ℕ) ≤ (p' : ℕ) := pell_nfa_no_ida_evalFrom_le n hq
      have h_eq : m = p' := Fin.ext (by omega)
      subst h_eq
      exact ⟨hm_step, hq⟩
    
  4. Every letter in a word looping at state p is congruent to p or p + 1 modulo 5.

    By induction on v. The base case is vacuously true. For a :: v, the previous lemma shows that p loops on a and on v. The letter a satisfies the congruence by pell_nfa_no_ida_step_self, and all letters in v satisfy it by the induction hypothesis.

    lines 54–62

    uses pell_nfa_no_ida_evalFrom_self_cons, List.mem_cons.mp, pell_nfa_no_ida_step_self

      induction v with
      | nil => intros k hk; contradiction
      | cons a v ih =>
        intros k hk
        obtain ⟨ha_step, hp_v⟩ := pell_nfa_no_ida_evalFrom_self_cons n h
        rcases List.mem_cons.mp hk with rfl | hk_v
        · exact pell_nfa_no_ida_step_self n ha_step
        · exact ih hp_v k hk_v
    
  5. Letters fixing p preserve the three-state neighborhood {p, p+1, p+2} in one step. automation

    Assuming s ∈ {p, p+1, p+2} and k ∈ {p % 5, (p+1) % 5}, case analysis on the transitions given by pell_nfa_step_table shows that any target state t remains in {p, p+1, p+2}, with each case verified by linear arithmetic.

    lines 68–73

    uses pell_nfa_step_table

      have := pell_nfa_step_table n h_step
      rcases this with ⟨hk', ht⟩ | ⟨hk', ht⟩ | ⟨hk', ht⟩ <;>
        rcases hs with hs | hs | hs <;>
        rcases hk with hk | hk <;>
        rcases ht with ht | ht <;>
        omega
  6. Words consisting of letters fixing p preserve the neighborhood {p, p+1, p+2}.

    By induction on the word v. The empty word preserves the state. For a :: v, the first step lands in {p, p+1, p+2} by pell_nfa_no_ida_step_in_range, and the induction hypothesis applies to the rest of the path.

    lines 81–100

    uses NFA.evalFrom_nil, Set.mem_singleton_iff, NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists, NFA.stepSet, Set.mem_iUnion, List.mem_cons_self, pell_nfa_no_ida_step_in_range, List.mem_cons_of_mem

      induction v generalizing s with
      | nil =>
        simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at ht
        subst ht
        exact hs
      | cons a v ih =>
        rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at ht
        rcases ht with ⟨m, hm, ht⟩
        rw [NFA.stepSet, Set.mem_iUnion] at hm
        rcases hm with ⟨s', hs'⟩
        rw [Set.mem_iUnion] at hs'
        rcases hs' with ⟨hs_eq, hm_step⟩
        simp only [Set.mem_singleton_iff] at hs_eq
        subst hs_eq
        have ha : (a : ℕ) = (p : ℕ) % 5 ∨ (a : ℕ) = ((p : ℕ) + 1) % 5 :=
          hv a List.mem_cons_self
        have hm_range := pell_nfa_no_ida_step_in_range n hs ha hm_step
        have hv' : ∀ k ∈ v, (k : ℕ) = (p : ℕ) % 5 ∨ (k : ℕ) = ((p : ℕ) + 1) % 5 :=
          fun k hk => hv k (List.mem_cons_of_mem a hk)
        exact ih hv' hm_range ht
  7. A step on letter (p+1) % 5 preserves the two-element set {p, p+2}. automation

    Assuming s ∈ {p, p+2} and k = (p+1) % 5, pell_nfa_step_table restricts the possible destinations. Linear arithmetic confirms that the intermediate state p + 1 cannot be reached, so t ∈ {p, p+2}.

    lines 107–111

    uses pell_nfa_step_table

      have := pell_nfa_step_table n h_step
      rcases this with ⟨hk', ht⟩ | ⟨hk', ht⟩ | ⟨hk', ht⟩ <;>
        rcases hs with hs | hs <;>
        rcases ht with ht | ht <;>
        omega
  8. Words consisting entirely of letter (p+1) % 5 preserve {p, p+2}.

    By induction on v, applying pell_nfa_no_ida_step_p_plus_1_letter on each step.

    lines 119–138

    uses NFA.evalFrom_nil, Set.mem_singleton_iff, NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists, NFA.stepSet, Set.mem_iUnion, List.mem_cons_self, pell_nfa_no_ida_step_p_plus_1_letter, List.mem_cons_of_mem

      induction v generalizing s with
      | nil =>
        simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at ht
        subst ht
        exact hs
      | cons a v ih =>
        rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at ht
        rcases ht with ⟨m, hm, ht⟩
        rw [NFA.stepSet, Set.mem_iUnion] at hm
        rcases hm with ⟨s', hs'⟩
        rw [Set.mem_iUnion] at hs'
        rcases hs' with ⟨hs_eq, hm_step⟩
        simp only [Set.mem_singleton_iff] at hs_eq
        subst hs_eq
        have ha : (a : ℕ) = ((p : ℕ) + 1) % 5 :=
          hv a List.mem_cons_self
        have hm_range := pell_nfa_no_ida_step_p_plus_1_letter n hs ha hm_step
        have hv' : ∀ k ∈ v, (k : ℕ) = ((p : ℕ) + 1) % 5 :=
          fun k hk => hv k (List.mem_cons_of_mem a hk)
        exact ih hv' hm_range ht
  9. Under the IDA hypothesis, the connecting word v cannot be empty.

    Assume for contradiction that IDA holds, giving distinct states p ≠ q and a word v such that p loops on v, q loops on v, and v takes p to q. If v is nil, evaluation from {p} yields {p}, forcing q = p, which contradicts p ≠ q.

    lines 142–147

    uses NFA.evalFrom_nil, Set.mem_singleton_iff

      intro h_ida
      rcases h_ida with ⟨p, q, hpq, v, hp_v, hqp_v, hq_v⟩
      cases v with
      | nil =>
        simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at hqp_v
        exact hpq hqp_v.symm
  10. State q must be either p + 1 or p + 2.

    Because v is non-empty and takes p to q, path monotonicity (pell_nfa_no_ida_evalFrom_le) gives p ≤ q, and since p ≠ q, p < q. Because p loops on v, every letter in v is in {p % 5, (p+1) % 5} (pell_nfa_no_ida_evalFrom_self_letters), so pell_nfa_no_ida_evalFrom_in_range confines q to {p, p+1, p+2}. Combined with p < q, q must be p + 1 or p + 2.

    lines 148–157

    uses pell_nfa_no_ida_evalFrom_le, eq_or_lt_of_le, Fin.ext, pell_nfa_no_ida_evalFrom_self_letters, pell_nfa_no_ida_evalFrom_in_range, Or.inl

      | cons a v =>
        have h_le : (p : ℕ) ≤ (q : ℕ) := pell_nfa_no_ida_evalFrom_le n hqp_v
        have h_lt : (p : ℕ) < (q : ℕ) := by
          rcases eq_or_lt_of_le h_le with heq | hlt
          · exfalso; exact hpq (Fin.ext heq)
          · exact hlt
        have hv_p := pell_nfa_no_ida_evalFrom_self_letters n hp_v
        have h_range := pell_nfa_no_ida_evalFrom_in_range n hv_p (Or.inl rfl) hqp_v
        have h_q_val : (q : ℕ) = (p : ℕ) + 1 ∨ (q : ℕ) = (p : ℕ) + 2 := by
          rcases h_range with h1 | h2 | h3 <;> omega
  11. State q cannot be p + 1.

    If q = p + 1, then because q loops on v, every letter in v must belong to {q % 5, (q+1) % 5} = {(p+1) % 5, (p+2) % 5}. Intersecting this with the requirement from p that every letter belongs to {p % 5, (p+1) % 5} forces every letter of v to be (p+1) % 5. But then pell_nfa_no_ida_evalFrom_p_plus_1_letters shows that any path from p stays in {p, p+2}, so it cannot reach q = p + 1.

    lines 158–166

    uses pell_nfa_no_ida_evalFrom_self_letters, pell_nfa_no_ida_evalFrom_p_plus_1_letters, Or.inl

        rcases h_q_val with h_plus_1 | h_plus_2
        · have hv_q := pell_nfa_no_ida_evalFrom_self_letters n hq_v
          have hv_all : ∀ k ∈ a :: v, (k : ℕ) = ((p : ℕ) + 1) % 5 := by
            intro k hk
            have hk_p := hv_p k hk
            have hk_q := hv_q k hk
            omega
          have h_q_res := pell_nfa_no_ida_evalFrom_p_plus_1_letters n hv_all (Or.inl rfl) hqp_v
          omega
  12. State q cannot be p + 2, completing the contradiction. automation

    If q = p + 2, pell_nfa_no_ida_evalFrom_self_cons implies that the first letter a of v must satisfy both p ∈ step p a and q ∈ step q a. Consulting pell_nfa_step_table for both transitions yields incompatible constraints modulo 5 on a, which linear integer arithmetic (omega) refutes.

    lines 167–171

    uses pell_nfa_no_ida_evalFrom_self_cons, pell_nfa_step_table

        · obtain ⟨hp_step, -⟩ := pell_nfa_no_ida_evalFrom_self_cons n hp_v
          obtain ⟨hq_step, -⟩ := pell_nfa_no_ida_evalFrom_self_cons n hq_v
          have h_step_p := pell_nfa_step_table n hp_step
          have h_step_q := pell_nfa_step_table n hq_step
          omega
NFA.evalFrom_nil
Evaluating an NFA from a state set on the empty word yields the state set itself.
Set.mem_singleton_iff
An element belongs to the singleton {b} if and only if it equals b.
le_rfl
Any element in a preorder satisfies a ≤ a.
NFA.evalFrom_cons
Evaluating an NFA on a :: v equals evaluating the one-step successor set on v.
NFA.mem_evalFrom_iff_exists
A state is reachable from a set S on word x iff it is reachable from some state in S on x.
NFA.stepSet
The one-step image of a state set is the union of the one-step transitions of its elements.
Set.mem_iUnion
Membership in an indexed union is equivalent to membership in at least one set of the family.
pell_nfa_step_table
Every transition p → q on letter k in the Pell NFA falls into one of three explicit cases relating k, p, and q.
pell_nfa_no_ida_evalFrom_le
Transitions in the Pell NFA never decrease the state index: if q is reachable from p, then p ≤ q.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
pell_nfa_no_ida_step_self
A self-loop at state p on letter k requires k ≡ p (mod 5) or k ≡ p + 1 (mod 5).
pell_nfa_no_ida_evalFrom_self_cons
If a word a :: v loops at state p, then the automaton loops at p on letter a and on the suffix v.
List.mem_cons.mp
An element in the list a :: l either equals a or belongs to l.
List.mem_cons_self
The head element a belongs to the list a :: l.
List.mem_cons_of_mem
An element belonging to l also belongs to y :: l.
pell_nfa_no_ida_step_in_range
If s ∈ {p, p+1, p+2} and k ∈ {p mod 5, (p+1) mod 5}, any one-step successor of s on k remains in {p, p+1, p+2}.
pell_nfa_no_ida_evalFrom_in_range
If every letter in v is in {p mod 5, (p+1) mod 5} and s ∈ {p, p+1, p+2}, any state reachable from s on v is in {p, p+1, p+2}.
pell_nfa_no_ida_step_p_plus_1_letter
If s ∈ {p, p+2} and k = (p+1) mod 5, any one-step successor of s on k remains in {p, p+2}.
pell_nfa_no_ida_evalFrom_p_plus_1_letters
If every letter in v is (p+1) mod 5 and s ∈ {p, p+2}, any state reachable from s on v remains in {p, p+2}.
eq_or_lt_of_le
If a ≤ b in a partial order, then a = b or a < b.
Or.inl
Proves a disjunction A ∨ B from a proof of A.
pell_nfa_no_ida_evalFrom_self_letters
Every letter in a word that loops at state p must be congruent to p or p + 1 modulo 5.

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

lemma pell_nfa_no_ida_evalFrom_le (n : ℕ) {v : List (Fin 5)} {p q : Fin n}    (h : q ∈ (pell_nfa n).evalFrom {p} v) : (p : ℕ) ≤ (q : ℕ) := by  induction v generalizing p with  | nil =>    simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h    subst h    exact le_rfl  | cons a v ih =>    rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at h    rcases h with ⟨m, hm, hq⟩    rw [NFA.stepSet, Set.mem_iUnion] at hm    rcases hm with ⟨p', hp'⟩    rw [Set.mem_iUnion] at hp'    rcases hp' with ⟨hp_eq, hm_step⟩    simp only [Set.mem_singleton_iff] at hp_eq    subst hp_eq    have h1 : (p' : ℕ) ≤ (m : ℕ) := by      have := pell_nfa_step_table n hm_step      rcases this with ⟨-, h'⟩ | ⟨-, h'⟩ | ⟨-, h'⟩ <;> omega    have h2 := ih hq    omegalemma pell_nfa_no_ida_step_self (n : ℕ) {p : Fin n} {k : Fin 5}    (h : p ∈ (pell_nfa n).step p k) :    (k : ℕ) = (p : ℕ) % 5 ∨ (k : ℕ) = ((p : ℕ) + 1) % 5 := by  have := pell_nfa_step_table n h  rcases this with ⟨hk, -⟩ | ⟨hk, -⟩ | ⟨hk, hq⟩  · left; exact hk  · right; exact hk  · rcases hq with h | h <;> omegalemma pell_nfa_no_ida_evalFrom_self_cons (n : ℕ) {a : Fin 5} {v : List (Fin 5)} {p : Fin n}    (h : p ∈ (pell_nfa n).evalFrom {p} (a :: v)) :    p ∈ (pell_nfa n).step p a ∧ p ∈ (pell_nfa n).evalFrom {p} v := by  rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at h  rcases h with ⟨m, hm, hq⟩  rw [NFA.stepSet, Set.mem_iUnion] at hm  rcases hm with ⟨p', hp'⟩  rw [Set.mem_iUnion] at hp'  rcases hp' with ⟨hp_eq, hm_step⟩  simp only [Set.mem_singleton_iff] at hp_eq  subst hp_eq  have h1 : (p' : ℕ) ≤ (m : ℕ) := by    have := pell_nfa_step_table n hm_step    rcases this with ⟨-, h'⟩ | ⟨-, h'⟩ | ⟨-, h'⟩ <;> omega  have h2 : (m : ℕ) ≤ (p' : ℕ) := pell_nfa_no_ida_evalFrom_le n hq  have h_eq : m = p' := Fin.ext (by omega)  subst h_eq  exact ⟨hm_step, hq⟩lemma pell_nfa_no_ida_evalFrom_self_letters (n : ℕ) {v : List (Fin 5)} {p : Fin n}    (h : p ∈ (pell_nfa n).evalFrom {p} v) :    ∀ k ∈ v, (k : ℕ) = (p : ℕ) % 5 ∨ (k : ℕ) = ((p : ℕ) + 1) % 5 := by  induction v with  | nil => intros k hk; contradiction  | cons a v ih =>    intros k hk    obtain ⟨ha_step, hp_v⟩ := pell_nfa_no_ida_evalFrom_self_cons n h    rcases List.mem_cons.mp hk with rfl | hk_v    · exact pell_nfa_no_ida_step_self n ha_step    · exact ih hp_v k hk_vlemma pell_nfa_no_ida_step_in_range (n : ℕ) {p s t : Fin n} {k : Fin 5}    (hs : (s : ℕ) = (p : ℕ) ∨ (s : ℕ) = (p : ℕ) + 1 ∨ (s : ℕ) = (p : ℕ) + 2)    (hk : (k : ℕ) = (p : ℕ) % 5 ∨ (k : ℕ) = ((p : ℕ) + 1) % 5)    (h_step : t ∈ (pell_nfa n).step s k) :    (t : ℕ) = (p : ℕ) ∨ (t : ℕ) = (p : ℕ) + 1 ∨ (t : ℕ) = (p : ℕ) + 2 := by  have := pell_nfa_step_table n h_step  rcases this with ⟨hk', ht⟩ | ⟨hk', ht⟩ | ⟨hk', ht⟩ <;>    rcases hs with hs | hs | hs <;>    rcases hk with hk | hk <;>    rcases ht with ht | ht <;>    omegalemma pell_nfa_no_ida_evalFrom_in_range (n : ℕ) {p : Fin n} {v : List (Fin 5)}    (hv : ∀ k ∈ v, (k : ℕ) = (p : ℕ) % 5 ∨ (k : ℕ) = ((p : ℕ) + 1) % 5)    {s t : Fin n}    (hs : (s : ℕ) = (p : ℕ) ∨ (s : ℕ) = (p : ℕ) + 1 ∨ (s : ℕ) = (p : ℕ) + 2)    (ht : t ∈ (pell_nfa n).evalFrom {s} v) :    (t : ℕ) = (p : ℕ) ∨ (t : ℕ) = (p : ℕ) + 1 ∨ (t : ℕ) = (p : ℕ) + 2 := by  induction v generalizing s with  | nil =>    simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at ht    subst ht    exact hs  | cons a v ih =>    rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at ht    rcases ht with ⟨m, hm, ht⟩    rw [NFA.stepSet, Set.mem_iUnion] at hm    rcases hm with ⟨s', hs'⟩    rw [Set.mem_iUnion] at hs'    rcases hs' with ⟨hs_eq, hm_step⟩    simp only [Set.mem_singleton_iff] at hs_eq    subst hs_eq    have ha : (a : ℕ) = (p : ℕ) % 5 ∨ (a : ℕ) = ((p : ℕ) + 1) % 5 :=      hv a List.mem_cons_self    have hm_range := pell_nfa_no_ida_step_in_range n hs ha hm_step    have hv' : ∀ k ∈ v, (k : ℕ) = (p : ℕ) % 5 ∨ (k : ℕ) = ((p : ℕ) + 1) % 5 :=      fun k hk => hv k (List.mem_cons_of_mem a hk)    exact ih hv' hm_range htlemma pell_nfa_no_ida_step_p_plus_1_letter (n : ℕ) {p s t : Fin n} {k : Fin 5}    (hs : (s : ℕ) = (p : ℕ) ∨ (s : ℕ) = (p : ℕ) + 2)    (hk : (k : ℕ) = ((p : ℕ) + 1) % 5)    (h_step : t ∈ (pell_nfa n).step s k) :    (t : ℕ) = (p : ℕ) ∨ (t : ℕ) = (p : ℕ) + 2 := by  have := pell_nfa_step_table n h_step  rcases this with ⟨hk', ht⟩ | ⟨hk', ht⟩ | ⟨hk', ht⟩ <;>    rcases hs with hs | hs <;>    rcases ht with ht | ht <;>    omegalemma pell_nfa_no_ida_evalFrom_p_plus_1_letters (n : ℕ) {p : Fin n} {v : List (Fin 5)}    (hv : ∀ k ∈ v, (k : ℕ) = ((p : ℕ) + 1) % 5)    {s t : Fin n}    (hs : (s : ℕ) = (p : ℕ) ∨ (s : ℕ) = (p : ℕ) + 2)    (ht : t ∈ (pell_nfa n).evalFrom {s} v) :    (t : ℕ) = (p : ℕ) ∨ (t : ℕ) = (p : ℕ) + 2 := by  induction v generalizing s with  | nil =>    simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at ht    subst ht    exact hs  | cons a v ih =>    rw [NFA.evalFrom_cons, NFA.mem_evalFrom_iff_exists] at ht    rcases ht with ⟨m, hm, ht⟩    rw [NFA.stepSet, Set.mem_iUnion] at hm    rcases hm with ⟨s', hs'⟩    rw [Set.mem_iUnion] at hs'    rcases hs' with ⟨hs_eq, hm_step⟩    simp only [Set.mem_singleton_iff] at hs_eq    subst hs_eq    have ha : (a : ℕ) = ((p : ℕ) + 1) % 5 :=      hv a List.mem_cons_self    have hm_range := pell_nfa_no_ida_step_p_plus_1_letter n hs ha hm_step    have hv' : ∀ k ∈ v, (k : ℕ) = ((p : ℕ) + 1) % 5 :=      fun k hk => hv k (List.mem_cons_of_mem a hk)    exact ih hv' hm_range ht/-- A_n does not comply with IDA: no single word v can carry q_p → q_p, q_p → q_q and q_q → q_q with p ≠ q, because letters that keep the state fixed at index p are dead two places to the right. -/theorem pell_nfa_no_ida (n : ℕ) : ¬ nfa_complies_ida (pell_nfa n) := by  intro h_ida  rcases h_ida with ⟨p, q, hpq, v, hp_v, hqp_v, hq_v⟩  cases v with  | nil =>    simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at hqp_v    exact hpq hqp_v.symm  | cons a v =>    have h_le : (p : ℕ) ≤ (q : ℕ) := pell_nfa_no_ida_evalFrom_le n hqp_v    have h_lt : (p : ℕ) < (q : ℕ) := by      rcases eq_or_lt_of_le h_le with heq | hlt      · exfalso; exact hpq (Fin.ext heq)      · exact hlt    have hv_p := pell_nfa_no_ida_evalFrom_self_letters n hp_v    have h_range := pell_nfa_no_ida_evalFrom_in_range n hv_p (Or.inl rfl) hqp_v    have h_q_val : (q : ℕ) = (p : ℕ) + 1 ∨ (q : ℕ) = (p : ℕ) + 2 := by      rcases h_range with h1 | h2 | h3 <;> omega    rcases h_q_val with h_plus_1 | h_plus_2    · have hv_q := pell_nfa_no_ida_evalFrom_self_letters n hq_v      have hv_all : ∀ k ∈ a :: v, (k : ℕ) = ((p : ℕ) + 1) % 5 := by        intro k hk        have hk_p := hv_p k hk        have hk_q := hv_q k hk        omega      have h_q_res := pell_nfa_no_ida_evalFrom_p_plus_1_letters n hv_all (Or.inl rfl) hqp_v      omega    · obtain ⟨hp_step, -⟩ := pell_nfa_no_ida_evalFrom_self_cons n hp_v      obtain ⟨hq_step, -⟩ := pell_nfa_no_ida_evalFrom_self_cons n hq_v      have h_step_p := pell_nfa_step_table n hp_step      have h_step_q := pell_nfa_step_table n hq_step      omega
See it in the graphDiscuss this resultChallenge it