pell_nfa_no_ida
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.
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.
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_tableinduction 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
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.
uses
pell_nfa_step_tablehave := 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
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.
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.extrw [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⟩
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.
uses
pell_nfa_no_ida_evalFrom_self_cons,List.mem_cons.mp,pell_nfa_no_ida_step_selfinduction 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
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.
uses
pell_nfa_step_tablehave := 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
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.
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_meminduction 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
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}.
uses
pell_nfa_step_tablehave := 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
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.
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_meminduction 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
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.
uses
NFA.evalFrom_nil,Set.mem_singleton_iffintro 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
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.
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 <;> omegaState 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.
uses
pell_nfa_no_ida_evalFrom_self_letters,pell_nfa_no_ida_evalFrom_p_plus_1_letters,Or.inlrcases 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
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.
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.
- Several case analyses on automaton transitions (notably in pell_nfa_no_ida_step_in_range, pell_nfa_no_ida_step_p_plus_1_letter, and the final step of pell_nfa_no_ida) decompose into dozens of subcases where the resulting arithmetic and modular conditions are discharged by Lean's omega decision procedure.
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.
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