alpha_lexical_first_negative_step_exists
A lexical sequence with at least two cells has an elementary lexical successor at its first negative cell.
Statement
theorem alpha_lexical_first_negative_step_exists (a : List ℕ)
(ha : alpha_is_lexical a) (hlen : 2 ≤ a.length) :
∃ b : List ℕ, alpha_elementary_cell_step a b 1 ∧
alpha_is_lexical b ∧ alpha_lexical_lt a b- Source
- Run-length helpers for OP-392, arXiv:2610.24758, Conjecture 1; lexical sequences and elementary operations from arXiv:0810.5205, Definitions 1.1, Section 2, Theorem 3.1 and Corollary 3.3. No new research advance is claimed for these supporting statements.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
- alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.
- alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
- alpha_signed_cellA cell of a positive sequence, with alternating signs and zero padding.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
The theorem establishes that any lexical sequence a with at least two cells admits an elementary lexical step at its first negative cell (index 1) to a strictly greater lexical sequence b. The argument splits on the value of a[1]: if a[1] = 1, a contraction step produces b = [a[0] + 1] ++ a.drop 2, which increases the first cell and remains lexical because all dropped suffixes have first cell bounded by a[0] < a[0] + 1; if a[1] > 1, an expansion step produces b = [a[0], a[1] - 1, 1] ++ a.drop 2, which is strictly greater at cell 1 (odd parity means decreasing a[1] increases the signed value) and remains lexical because dropped suffixes at k = 1, 2 have first cell strictly less than b[0] = a[0] (using a[0] ≥ 2), and suffixes dropped at k ≥ 3 satisfy b.drop k = a.drop (k - 1) <_lex a <_lex b by transitivity.
For any index i ≥ |a|, the signed cell alpha_signed_cell(a, i) is 0.
Unfolding the definition of `alpha_signed_cell`, accessing an index beyond the length of a returns the default value 0 by `List.getD_eq_default`. Since both +0 and -0 equal 0, both parity branches evaluate to 0.
uses
List.getD_eq_defaultdsimp [alpha_signed_cell] rw [List.getD_eq_default _ _ hi] split <;> rfl
If the signed cells of x and z differ at index i, then i < max(|x|, |z|).
Assuming for contradiction that max(|x|, |z|) ≤ i, we get |x| ≤ i by `le_of_max_le_left` and |z| ≤ i by `le_of_max_le_right`. By `alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge`, both signed cells at index i are 0, which contradicts the hypothesis that one is strictly less than the other.
uses
le_of_max_le_left,le_of_max_le_right,alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_geby_contra! hge have hx : x.length ≤ i := le_of_max_le_left hge have hz : z.length ≤ i := le_of_max_le_right hge rw [alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge x i hx, alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge z i hz] at hlt omega
The strict lexical order alpha_lexical_lt is transitive: if x <_lex y and y <_lex z, then x <_lex z.
Let i be the first differing index between x and y, and k between y and z. By `lt_trichotomy`, either i < k, i = k, or k < i. If i < k, y and z agree up to k > i, so x and z first differ at i with signed(x, i) < signed(y, i) = signed(z, i). If i = k, x and z agree up to i and signed(x, i) < signed(z, i) by `lt_trans`. If k < i, x and z first differ at k with signed(x, k) = signed(y, k) < signed(z, k). In each case, `alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt` ensures the difference index is bounded by max(|x|, |z|).
uses
lt_trichotomy,alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt,lt_transrcases hxy with ⟨i, hi, hxy_eq, hxy_lt⟩ rcases hyz with ⟨k, hk, hyz_eq, hyz_lt⟩ rcases lt_trichotomy i k with h | rfl | h · refine ⟨i, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt x z i ?_, fun j hj => ?_, ?_⟩ · rw [← hyz_eq i h]; exact hxy_lt · rw [hxy_eq j hj, hyz_eq j (lt_trans hj h)] · rw [← hyz_eq i h]; exact hxy_lt · refine ⟨i, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt x z i ?_, fun j hj => ?_, ?_⟩ · exact lt_trans hxy_lt hyz_lt · rw [hxy_eq j hj, hyz_eq j hj] · exact lt_trans hxy_lt hyz_lt · refine ⟨k, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt x z k ?_, fun j hj => ?_, ?_⟩ · rw [hxy_eq k h]; exact hyz_lt · rw [hxy_eq j (lt_trans hj h), hyz_eq j hj] · rw [hxy_eq k h]; exact hyz_lt
Indexing into a dropped list satisfies (a.drop k)[j] = a[k + j].
This is proved by rewriting the default lookup with `List.getD_eq_getElem?_getD` and simplifying list dropping via `List.getElem?_drop`.
uses
List.getD_eq_getElem?_getD,List.getElem?_dropsimp only [List.getD_eq_getElem?_getD, List.getElem?_drop]The first element of a.drop k is the k-th element of a: (a.drop k)[0] = a[k].
Specializing `alpha_lexical_first_negative_step_exists_getD_drop` to j = 0 and applying `add_zero`.
uses
alpha_lexical_first_negative_step_exists_getD_drop,add_zerorw [alpha_lexical_first_negative_step_exists_getD_drop, add_zero]In any lexical sequence a, every cell is bounded by the first cell: a[k] ≤ a[0] for all k < |a|.
If k = 0, the claim is trivial. If k > 0, since a is lexical, the suffix a.drop k is strictly lexically smaller than a at some first differing index i. If i = 0, the signed cells give (a.drop k)[0] < a[0], which means a[k] < a[0] by `alpha_lexical_first_negative_step_exists_getD_drop_zero`. If i > 0, the signed cells agree at index 0, so a[k] = a[0]. In both cases, a[k] ≤ a[0].
uses
eq_or_lt_of_le,Nat.zero_le,alpha_lexical_first_negative_step_exists_getD_drop_zerorcases eq_or_lt_of_le (Nat.zero_le k) with rfl | hk0 · rfl · have hlt := ha.2.2 k hk hk0 rcases hlt with ⟨i, hi, heq, hlt⟩ dsimp [alpha_signed_cell] at heq hlt rcases eq_or_lt_of_le (Nat.zero_le i) with rfl | hi0 · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] at hlt; omega · have h0 := heq 0 hi0 rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] at h0; omega
Every in-bounds cell in a lexical sequence is strictly positive: a[k] > 0 for all k < |a|.
Rewriting `getD` to list lookup via `List.getD_eq_getElem`, this directly reflects the second conjunct of `alpha_is_lexical` using `List.getElem_mem`.
uses
List.getD_eq_getElem,List.getElem_memrw [List.getD_eq_getElem a 0 hk] exact ha.2.1 _ (List.getElem_mem hk)
A lexical sequence with at least two cells has first cell at least 2: a[0] ≥ 2.
Suppose for contradiction that a[0] < 2. Since a[0] > 0 by `alpha_lexical_first_negative_step_exists_cell_pos`, we have a[0] = 1. Since a[1] ≤ a[0] by `alpha_lexical_first_negative_step_exists_cell_le_first` and a[1] > 0, we also have a[1] = 1. Now consider the suffix dropped at k = |a| - 1 > 0, which has length 1 by `List.length_drop`. The suffix must be strictly lexically smaller than a at some first differing index i. At index 1, the suffix's signed cell is 0 by `List.getD_eq_default`, while a's signed cell is -1. If i = 0, we get a[k] < a[0] = 1, contradicting positivity. If i = 1, we get 0 < -1, an impossibility. If i > 1, the signed cells at index 1 must agree, yielding 0 = -1, which is also impossible.
uses
alpha_lexical_first_negative_step_exists_cell_pos,alpha_lexical_first_negative_step_exists_cell_le_first,List.getD_eq_default,List.length_drop,eq_or_lt_of_le,Nat.zero_le,alpha_lexical_first_negative_step_exists_getD_drop_zeroby_contra! hlt have hpos0 : 0 < a.getD 0 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha 0 (by omega) have ha0 : a.getD 0 0 = 1 := by omega let k := a.length - 1 have hk : k < a.length := by omega have hk0 : 0 < k := by omega have hdrop_lt := ha.2.2 k hk hk0 rcases hdrop_lt with ⟨i, hi, heq, hlt_i⟩ have hpos1 : 0 < a.getD 1 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha 1 (by omega) have hle1 : a.getD 1 0 ≤ a.getD 0 0 := alpha_lexical_first_negative_step_exists_cell_le_first a ha 1 (by omega) have ha1 : a.getD 1 0 = 1 := by omega have hdrop_1 : alpha_signed_cell (a.drop k) 1 = 0 := by dsimp [alpha_signed_cell] rw [List.getD_eq_default _ _ (by rw [List.length_drop]; omega)] rfl have ha_1 : alpha_signed_cell a 1 = -1 := by dsimp [alpha_signed_cell]; rw [ha1]; rfl rcases eq_or_lt_of_le (Nat.zero_le i) with rfl | hi0 · dsimp [alpha_signed_cell] at hlt_i rw [alpha_lexical_first_negative_step_exists_getD_drop_zero, ha0] at hlt_i have : 0 < a.getD k 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha k hk omega · rcases eq_or_lt_of_le (show 1 ≤ i by omega) with rfl | hi1 · rw [hdrop_1, ha_1] at hlt_i; omega · have h1 := heq 1 hi1 rw [hdrop_1, ha_1] at h1; omega
If x[0] < y[0] and max(|x|, |y|) > 0, then x is strictly lexically less than y.
Witness index 0. Because 0 is even, the signed cells are x[0] and y[0], so signed(x, 0) < signed(y, 0), and all prior indices agree vacuously.
refine ⟨0, hlen, fun j hj => by omega, ?_⟩ dsimp [alpha_signed_cell]; omega
If x[0] = y[0] and y[1] < x[1] with max(|x|, |y|) > 1, then x is strictly lexically less than y.
Witness index 1. The sequences agree at index 0, and at odd index 1 the signed cells are -x[1] and -y[1]. Since y[1] < x[1], we have -x[1] < -y[1], so x <_lex y.
refine ⟨1, hlen, fun j hj => ?_, ?_⟩ · have : j = 0 := by omega subst this dsimp [alpha_signed_cell]; omega · dsimp [alpha_signed_cell]; omega
Accessing index k > 0 of [x] ++ l equals accessing index k - 1 of l.
By induction on k: the base case k = 0 contradicts k > 0, and for k + 1 the identity holds by definition of list concatenation indexing.
rcases k with _ | k · contradiction · rfl
For k ≥ 3, dropping k elements from [a[0], a1 - 1, 1] ++ a.drop 2 yields a.drop (k - 1).
The cases k = 0, 1, 2 are ruled out by k ≥ 3. For k = m + 3, dropping 3 elements removes the three prefix elements, leaving (a.drop 2).drop m = a.drop (m + 2) = a.drop (k - 1) by `List.drop_drop`.
uses
List.drop_droprcases k with _ | _ | _ | k · omega · omega · omega · change (a.drop 2).drop k = a.drop (k + 2) rw [List.drop_drop] congr 1 omega
Taking 1 element from a list of length at least 1 yields [a[0]].
Since |a| > 0, a[0] is the head element of a by `List.getD_eq_getElem`. Case analysis on a rules out the empty list, and taking 1 element from x :: xs yields [x] = [a[0]].
uses
List.getD_eq_getElemhave : 0 < a.length := by omega rw [List.getD_eq_getElem a 0 this] rcases a with _ | ⟨x, xs⟩ · contradiction · rfl
In the main theorem, cell 1 is positive (a[1] > 0), allowing a case distinction between a[1] = 1 and a[1] > 1.
Since |a| ≥ 2, cell 1 is in bounds, so a[1] > 0 by `alpha_lexical_first_negative_step_exists_cell_pos`. Thus 1 ≤ a[1], and `eq_or_lt_of_le` splits the goal into cases a[1] = 1 and 1 < a[1].
uses
alpha_lexical_first_negative_step_exists_cell_pos,eq_or_lt_of_lehave ha1_pos : 0 < a.getD 1 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha 1 (by omega) rcases eq_or_lt_of_le (show 1 ≤ a.getD 1 0 by omega) with ha1 | ha1
When a[1] = 1, the candidate sequence b = [a[0] + 1] ++ a.drop 2 is an elementary cell step from a at cell 1.
We verify the second alternative of `alpha_elementary_cell_step` (contraction step at index 1): 1 < |a|, a[1] = 1, and a.take 0 ++ [a[0] + 1] ++ a.drop 2 = [a[0] + 1] ++ a.drop 2, using `Or.inr`.
uses
Or.inr· refine ⟨[a.getD 0 0 + 1] ++ a.drop 2, ?_, ?_, ?_⟩ · refine ⟨by omega, Or.inr ⟨by omega, ha1.symm, ?_⟩⟩ rfl
When a[1] = 1, the sequence b = [a[0] + 1] ++ a.drop 2 is lexical.
The length of b is |a| - 1 ≥ 1, so b is non-empty. Every element of b is strictly positive: either it is a[0] + 1 > 0 or an element of a.drop 2 ⊆ a (using `List.mem_append`, `List.mem_singleton`, and `List.mem_of_mem_drop`). For any k > 0, the first cell of b.drop k is (a.drop 2)[k - 1] = a[k + 1] by `alpha_lexical_first_negative_step_exists_getD_drop_zero`, `alpha_lexical_first_negative_step_exists_getD_cons_append`, and `alpha_lexical_first_negative_step_exists_getD_drop`. Since a is lexical, a[k + 1] ≤ a[0] < a[0] + 1 = b[0] by `alpha_lexical_first_negative_step_exists_cell_le_first`, so b.drop k <_lex b by `alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt`.
uses
List.mem_append,List.mem_singleton,List.mem_of_mem_drop,alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt,alpha_lexical_first_negative_step_exists_getD_drop_zero,alpha_lexical_first_negative_step_exists_getD_cons_append,alpha_lexical_first_negative_step_exists_getD_drop,alpha_lexical_first_negative_step_exists_cell_le_first· have hblen : ([a.getD 0 0 + 1] ++ a.drop 2).length = a.length - 1 := by simp; omega refine ⟨by simp, fun v hv => ?_, fun k hk hk0 => ?_⟩ · simp only [List.mem_append, List.mem_singleton] at hv rcases hv with rfl | hv · omega · exact ha.2.1 v (List.mem_of_mem_drop hv) · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero, alpha_lexical_first_negative_step_exists_getD_cons_append _ _ k hk0, alpha_lexical_first_negative_step_exists_getD_drop] have hcell := alpha_lexical_first_negative_step_exists_cell_le_first a ha (2 + (k - 1)) (by omega) have : ([a.getD 0 0 + 1] ++ a.drop 2).getD 0 0 = a.getD 0 0 + 1 := rfl omega · rw [hblen]; omega
When a[1] = 1, a <_lex b.
The first cell of a is a[0], whereas the first cell of b is a[0] + 1 > a[0]. By `alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt`, this implies a <_lex b.
uses
alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt· apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · change a.getD 0 0 < a.getD 0 0 + 1; omega · omega
When a[1] > 1, the candidate sequence b = [a[0], a[1] - 1, 1] ++ a.drop 2 is an elementary cell step from a at cell 1.
We verify the first alternative of `alpha_elementary_cell_step` (expansion step at index 1): 1 < a[1], and a.take 1 ++ [a[1] - 1, 1] ++ a.drop 2 equals b because a.take 1 = [a[0]] by `alpha_lexical_first_negative_step_exists_take_one`, using `Or.inl`.
uses
Or.inl,alpha_lexical_first_negative_step_exists_take_one· refine ⟨[a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2, ?_, ?_, ?_⟩ · refine ⟨by omega, Or.inl ⟨ha1, ?_⟩⟩ rw [alpha_lexical_first_negative_step_exists_take_one a (by omega)] rfl
When a[1] > 1, the length of b is |a| + 1 and a <_lex b.
The length identity |b| = |a| + 1 is established by simplifying concatenation lengths with `List.length_append`, `List.length_cons`, `List.length_nil`, and `List.length_drop`. The inequality a <_lex b holds by `alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt` because b[0] = a[0] and b[1] = a[1] - 1 < a[1].
uses
List.length_append,List.length_cons,List.length_nil,List.length_drop,alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt· have hblen : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).length = a.length + 1 := by simp only [List.length_append, List.length_cons, List.length_nil, List.length_drop] omega have hab_lt : alpha_lexical_lt a ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2) := by apply alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt · rfl · have : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 1 0 = a.getD 1 0 - 1 := rfl omega · rw [hblen]; omega
When a[1] > 1, all elements of b are strictly positive.
Any element of b belongs to the prefix [a[0], a[1] - 1, 1] or to a.drop 2 (simplified via `List.mem_append`, `List.mem_cons`, and `List.not_mem_nil`). The element a[0] > 0 by `alpha_lexical_first_negative_step_exists_cell_pos`; a[1] - 1 > 0 since a[1] > 1; 1 > 0; and any element of a.drop 2 belongs to a by `List.mem_of_mem_drop` and is positive because a is lexical.
uses
List.mem_append,List.mem_cons,List.not_mem_nil,alpha_lexical_first_negative_step_exists_cell_pos,List.mem_of_mem_droprefine ⟨by simp, fun v hv => ?_, fun k hk hk0 => ?_⟩ · simp only [List.mem_append, List.mem_cons, List.not_mem_nil] at hv rcases hv with (rfl | rfl | rfl | hF) | hv · exact alpha_lexical_first_negative_step_exists_cell_pos a ha 0 (by omega) · omega · omega · contradiction · exact ha.2.1 v (List.mem_of_mem_drop hv)
When a[1] > 1, the suffix dropped at k = 1 satisfies b.drop 1 <_lex b.
For k = 1 (distinguished using `eq_or_ne`), the first cell of b.drop 1 is b[1] = a[1] - 1 by `alpha_lexical_first_negative_step_exists_getD_drop_zero`. Since a is lexical, a[1] ≤ a[0] by `alpha_lexical_first_negative_step_exists_cell_le_first`, so a[1] - 1 < a[0] = b[0]. By `alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt`, b.drop 1 <_lex b.
uses
eq_or_ne,alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt,alpha_lexical_first_negative_step_exists_getD_drop_zero,alpha_lexical_first_negative_step_exists_cell_le_first· rcases eq_or_ne k 1 with rfl | hk1 · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] have h1 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 1 0 = a.getD 1 0 - 1 := rfl have h0 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 0 0 = a.getD 0 0 := rfl have hle := alpha_lexical_first_negative_step_exists_cell_le_first a ha 1 (by omega) omega · rw [hblen]; omega
When a[1] > 1, the suffix dropped at k = 2 satisfies b.drop 2 <_lex b.
For k = 2 (distinguished using `eq_or_ne`), the first cell of b.drop 2 is b[2] = 1 by `alpha_lexical_first_negative_step_exists_getD_drop_zero`. Since |a| ≥ 2, we have a[0] ≥ 2 by `alpha_lexical_first_negative_step_exists_two_le_first`, so 1 < 2 ≤ a[0] = b[0]. By `alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt`, b.drop 2 <_lex b.
uses
eq_or_ne,alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt,alpha_lexical_first_negative_step_exists_getD_drop_zero,alpha_lexical_first_negative_step_exists_two_le_first· rcases eq_or_ne k 2 with rfl | hk2 · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] have h2 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 2 0 = 1 := rfl have h0 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 0 0 = a.getD 0 0 := rfl have htwo := alpha_lexical_first_negative_step_exists_two_le_first a ha hlen omega · rw [hblen]; omega
When a[1] > 1, for any k ≥ 3, the dropped suffix satisfies b.drop k <_lex b.
For k ≥ 3, `alpha_lexical_first_negative_step_exists_drop_ge_three` gives b.drop k = a.drop (k - 1). Because a is lexical and k - 1 > 0, we have a.drop (k - 1) <_lex a. Since we already established a <_lex b, transitivity (`alpha_lexical_first_negative_step_exists_lt_trans`) implies b.drop k <_lex b.
uses
alpha_lexical_first_negative_step_exists_drop_ge_three,alpha_lexical_first_negative_step_exists_lt_trans· have hk3 : 3 ≤ k := by omega have hdrop_eq : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).drop k = a.drop (k - 1) := alpha_lexical_first_negative_step_exists_drop_ge_three a (a.getD 1 0) k hk3 rw [hdrop_eq] have hkm : k - 1 < a.length := by rw [hblen] at hk; omega have hkm0 : 0 < k - 1 := by omega have hdrop_lt_a := ha.2.2 (k - 1) hkm hkm0 exact alpha_lexical_first_negative_step_exists_lt_trans (a.drop (k - 1)) a ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2) hdrop_lt_a hab_lt
When a[1] > 1, the final condition a <_lex b holds.
As with the earlier check, b[0] = a[0] and b[1] = a[1] - 1 < a[1]. Since index 1 has odd parity, `alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt` together with length calculation using `List.length_append`, `List.length_cons`, `List.length_nil`, and `List.length_drop` establishes a <_lex b.
uses
alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt,List.length_append,List.length_cons,List.length_nil,List.length_drop· apply alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt · rfl · have : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 1 0 = a.getD 1 0 - 1 := rfl omega · have hblen : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).length = a.length + 1 := by simp only [List.length_append, List.length_cons, List.length_nil, List.length_drop] omega rw [hblen]; omega
add_zero- Adding zero to a value leaves it unchanged.
alpha_lexical_first_negative_step_exists_cell_le_first- In a lexical sequence, every cell within bounds is bounded by the first cell: a[k] ≤ a[0].
alpha_lexical_first_negative_step_exists_cell_pos- In a lexical sequence, every cell within bounds is strictly positive: 0 < a[k].
alpha_lexical_first_negative_step_exists_drop_ge_three- Dropping k ≥ 3 elements from [a[0], a1 - 1, 1] ++ a.drop 2 yields a.drop (k - 1).
alpha_lexical_first_negative_step_exists_getD_cons_append- For k > 0, the k-th element of [x] ++ l is the (k - 1)-th element of l.
alpha_lexical_first_negative_step_exists_getD_drop- The j-th cell of a.drop k equals the (k + j)-th cell of a.
alpha_lexical_first_negative_step_exists_getD_drop_zero- The first cell of a.drop k is the k-th cell of a.
alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt- If the signed cells of x and z differ at index i, then i is strictly less than max(|x|, |z|).
alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt- If x[0] < y[0] and at least one sequence is non-empty, then x is strictly lexically less than y.
alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt- If x[0] = y[0] and y[1] < x[1], then x is strictly lexically less than y because cell 1 has odd parity (negative sign).
alpha_lexical_first_negative_step_exists_lt_trans- The strict lexical order alpha_lexical_lt is transitive.
alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge- For any index i ≥ |a|, the signed cell at index i is 0.
alpha_lexical_first_negative_step_exists_take_one- Taking the prefix of length 1 of a non-empty list yields [a[0]].
alpha_lexical_first_negative_step_exists_two_le_first- Any lexical sequence of length at least 2 has its first cell a[0] ≥ 2.
eq_or_lt_of_le- If a ≤ b in a partial order, then either a = b or a < b.
eq_or_ne- For any two elements, either they are equal or they are unequal.
le_of_max_le_left- If max(a, b) ≤ c, then a ≤ c.
le_of_max_le_right- If max(a, b) ≤ c, then b ≤ c.
List.drop_drop- Dropping i elements after dropping j elements is equivalent to dropping j + i elements.
List.getD_eq_default- Accessing an index at or beyond the length of a list returns the default value.
List.getD_eq_getElem- For an in-bounds index n < |l|, accessing with default returns the list element l[n].
List.getD_eq_getElem?_getD- Accessing the i-th element with default equals getting the default from the optional lookup l[i]?.
List.getElem_mem- Any in-bounds element of a list belongs to the list.
List.getElem?_drop- The j-th element of xs.drop i corresponds to the (i + j)-th element of xs.
List.length_append- The length of the concatenation as ++ bs is |as| + |bs|.
List.length_cons- Prepending an element to a list increases its length by 1.
List.length_drop- The length of the dropped list l.drop i is |l| - i.
List.length_nil- The empty list has length 0.
List.mem_append- An element belongs to s ++ t if and only if it belongs to s or to t.
List.mem_cons- An element belongs to b :: l if and only if it equals b or belongs to l.
List.mem_of_mem_drop- Any element of a dropped suffix l.drop i belongs to l.
List.mem_singleton- An element belongs to the singleton [b] if and only if it equals b.
List.not_mem_nil- No element belongs to the empty list.
lt_trans- Strict inequality is transitive: if a < b and b < c, then a < c.
lt_trichotomy- For any two elements in a linear order, exactly one of a < b, a = b, or b < a holds.
Nat.zero_le- Every natural number is greater than or equal to 0.
Or.inl- Disjunction introduction on the left: if a holds, then a ∨ b holds.
Or.inr- Disjunction introduction on the right: if b holds, then a ∨ b holds.
- Out-of-bounds indexing in Lean defaults to 0 via `List.getD`, which evaluates to signed cell value 0 for all indices at or beyond the list length.
- Odd indices carry a negative sign in `alpha_signed_cell`, so decreasing cell 1 from a[1] to a[1] - 1 strictly increases its signed value from -a[1] to -a[1] + 1.
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 alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge (a : List ℕ) (i : ℕ) (hi : a.length ≤ i) : alpha_signed_cell a i = 0 := by dsimp [alpha_signed_cell] rw [List.getD_eq_default _ _ hi] split <;> rfllemma alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt (x z : List ℕ) (i : ℕ) (hlt : alpha_signed_cell x i < alpha_signed_cell z i) : i < max x.length z.length := by by_contra! hge have hx : x.length ≤ i := le_of_max_le_left hge have hz : z.length ≤ i := le_of_max_le_right hge rw [alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge x i hx, alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge z i hz] at hlt omegatheorem alpha_lexical_first_negative_step_exists_lt_trans (x y z : List ℕ) (hxy : alpha_lexical_lt x y) (hyz : alpha_lexical_lt y z) : alpha_lexical_lt x z := by rcases hxy with ⟨i, hi, hxy_eq, hxy_lt⟩ rcases hyz with ⟨k, hk, hyz_eq, hyz_lt⟩ rcases lt_trichotomy i k with h | rfl | h · refine ⟨i, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt x z i ?_, fun j hj => ?_, ?_⟩ · rw [← hyz_eq i h]; exact hxy_lt · rw [hxy_eq j hj, hyz_eq j (lt_trans hj h)] · rw [← hyz_eq i h]; exact hxy_lt · refine ⟨i, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt x z i ?_, fun j hj => ?_, ?_⟩ · exact lt_trans hxy_lt hyz_lt · rw [hxy_eq j hj, hyz_eq j hj] · exact lt_trans hxy_lt hyz_lt · refine ⟨k, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt x z k ?_, fun j hj => ?_, ?_⟩ · rw [hxy_eq k h]; exact hyz_lt · rw [hxy_eq j (lt_trans hj h), hyz_eq j hj] · rw [hxy_eq k h]; exact hyz_ltlemma alpha_lexical_first_negative_step_exists_getD_drop (a : List ℕ) (k j : ℕ) : (a.drop k).getD j 0 = a.getD (k + j) 0 := by simp only [List.getD_eq_getElem?_getD, List.getElem?_drop]lemma alpha_lexical_first_negative_step_exists_getD_drop_zero (a : List ℕ) (k : ℕ) : (a.drop k).getD 0 0 = a.getD k 0 := by rw [alpha_lexical_first_negative_step_exists_getD_drop, add_zero]lemma alpha_lexical_first_negative_step_exists_cell_le_first (a : List ℕ) (ha : alpha_is_lexical a) (k : ℕ) (hk : k < a.length) : a.getD k 0 ≤ a.getD 0 0 := by rcases eq_or_lt_of_le (Nat.zero_le k) with rfl | hk0 · rfl · have hlt := ha.2.2 k hk hk0 rcases hlt with ⟨i, hi, heq, hlt⟩ dsimp [alpha_signed_cell] at heq hlt rcases eq_or_lt_of_le (Nat.zero_le i) with rfl | hi0 · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] at hlt; omega · have h0 := heq 0 hi0 rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] at h0; omegalemma alpha_lexical_first_negative_step_exists_cell_pos (a : List ℕ) (ha : alpha_is_lexical a) (k : ℕ) (hk : k < a.length) : 0 < a.getD k 0 := by rw [List.getD_eq_getElem a 0 hk] exact ha.2.1 _ (List.getElem_mem hk)lemma alpha_lexical_first_negative_step_exists_two_le_first (a : List ℕ) (ha : alpha_is_lexical a) (hlen : 2 ≤ a.length) : 2 ≤ a.getD 0 0 := by by_contra! hlt have hpos0 : 0 < a.getD 0 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha 0 (by omega) have ha0 : a.getD 0 0 = 1 := by omega let k := a.length - 1 have hk : k < a.length := by omega have hk0 : 0 < k := by omega have hdrop_lt := ha.2.2 k hk hk0 rcases hdrop_lt with ⟨i, hi, heq, hlt_i⟩ have hpos1 : 0 < a.getD 1 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha 1 (by omega) have hle1 : a.getD 1 0 ≤ a.getD 0 0 := alpha_lexical_first_negative_step_exists_cell_le_first a ha 1 (by omega) have ha1 : a.getD 1 0 = 1 := by omega have hdrop_1 : alpha_signed_cell (a.drop k) 1 = 0 := by dsimp [alpha_signed_cell] rw [List.getD_eq_default _ _ (by rw [List.length_drop]; omega)] rfl have ha_1 : alpha_signed_cell a 1 = -1 := by dsimp [alpha_signed_cell]; rw [ha1]; rfl rcases eq_or_lt_of_le (Nat.zero_le i) with rfl | hi0 · dsimp [alpha_signed_cell] at hlt_i rw [alpha_lexical_first_negative_step_exists_getD_drop_zero, ha0] at hlt_i have : 0 < a.getD k 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha k hk omega · rcases eq_or_lt_of_le (show 1 ≤ i by omega) with rfl | hi1 · rw [hdrop_1, ha_1] at hlt_i; omega · have h1 := heq 1 hi1 rw [hdrop_1, ha_1] at h1; omegalemma alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt (x y : List ℕ) (hlt : x.getD 0 0 < y.getD 0 0) (hlen : 0 < max x.length y.length) : alpha_lexical_lt x y := by refine ⟨0, hlen, fun j hj => by omega, ?_⟩ dsimp [alpha_signed_cell]; omegalemma alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt (x y : List ℕ) (h0 : x.getD 0 0 = y.getD 0 0) (h1 : y.getD 1 0 < x.getD 1 0) (hlen : 1 < max x.length y.length) : alpha_lexical_lt x y := by refine ⟨1, hlen, fun j hj => ?_, ?_⟩ · have : j = 0 := by omega subst this dsimp [alpha_signed_cell]; omega · dsimp [alpha_signed_cell]; omegalemma alpha_lexical_first_negative_step_exists_getD_cons_append (x : ℕ) (l : List ℕ) (k : ℕ) (hk : 0 < k) : ([x] ++ l).getD k 0 = l.getD (k - 1) 0 := by rcases k with _ | k · contradiction · rfllemma alpha_lexical_first_negative_step_exists_drop_ge_three (a : List ℕ) (a1 : ℕ) (k : ℕ) (hk : 3 ≤ k) : (([a.getD 0 0, a1 - 1, 1] ++ a.drop 2).drop k) = a.drop (k - 1) := by rcases k with _ | _ | _ | k · omega · omega · omega · change (a.drop 2).drop k = a.drop (k + 2) rw [List.drop_drop] congr 1 omegalemma alpha_lexical_first_negative_step_exists_take_one (a : List ℕ) (hlen : 1 ≤ a.length) : a.take 1 = [a.getD 0 0] := by have : 0 < a.length := by omega rw [List.getD_eq_getElem a 0 this] rcases a with _ | ⟨x, xs⟩ · contradiction · rfltheorem alpha_lexical_first_negative_step_exists (a : List ℕ) (ha : alpha_is_lexical a) (hlen : 2 ≤ a.length) : ∃ b : List ℕ, alpha_elementary_cell_step a b 1 ∧ alpha_is_lexical b ∧ alpha_lexical_lt a b := by have ha1_pos : 0 < a.getD 1 0 := alpha_lexical_first_negative_step_exists_cell_pos a ha 1 (by omega) rcases eq_or_lt_of_le (show 1 ≤ a.getD 1 0 by omega) with ha1 | ha1 · refine ⟨[a.getD 0 0 + 1] ++ a.drop 2, ?_, ?_, ?_⟩ · refine ⟨by omega, Or.inr ⟨by omega, ha1.symm, ?_⟩⟩ rfl · have hblen : ([a.getD 0 0 + 1] ++ a.drop 2).length = a.length - 1 := by simp; omega refine ⟨by simp, fun v hv => ?_, fun k hk hk0 => ?_⟩ · simp only [List.mem_append, List.mem_singleton] at hv rcases hv with rfl | hv · omega · exact ha.2.1 v (List.mem_of_mem_drop hv) · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero, alpha_lexical_first_negative_step_exists_getD_cons_append _ _ k hk0, alpha_lexical_first_negative_step_exists_getD_drop] have hcell := alpha_lexical_first_negative_step_exists_cell_le_first a ha (2 + (k - 1)) (by omega) have : ([a.getD 0 0 + 1] ++ a.drop 2).getD 0 0 = a.getD 0 0 + 1 := rfl omega · rw [hblen]; omega · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · change a.getD 0 0 < a.getD 0 0 + 1; omega · omega · refine ⟨[a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2, ?_, ?_, ?_⟩ · refine ⟨by omega, Or.inl ⟨ha1, ?_⟩⟩ rw [alpha_lexical_first_negative_step_exists_take_one a (by omega)] rfl · have hblen : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).length = a.length + 1 := by simp only [List.length_append, List.length_cons, List.length_nil, List.length_drop] omega have hab_lt : alpha_lexical_lt a ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2) := by apply alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt · rfl · have : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 1 0 = a.getD 1 0 - 1 := rfl omega · rw [hblen]; omega refine ⟨by simp, fun v hv => ?_, fun k hk hk0 => ?_⟩ · simp only [List.mem_append, List.mem_cons, List.not_mem_nil] at hv rcases hv with (rfl | rfl | rfl | hF) | hv · exact alpha_lexical_first_negative_step_exists_cell_pos a ha 0 (by omega) · omega · omega · contradiction · exact ha.2.1 v (List.mem_of_mem_drop hv) · rcases eq_or_ne k 1 with rfl | hk1 · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] have h1 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 1 0 = a.getD 1 0 - 1 := rfl have h0 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 0 0 = a.getD 0 0 := rfl have hle := alpha_lexical_first_negative_step_exists_cell_le_first a ha 1 (by omega) omega · rw [hblen]; omega · rcases eq_or_ne k 2 with rfl | hk2 · apply alpha_lexical_first_negative_step_exists_lt_of_first_cell_lt · rw [alpha_lexical_first_negative_step_exists_getD_drop_zero] have h2 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 2 0 = 1 := rfl have h0 : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 0 0 = a.getD 0 0 := rfl have htwo := alpha_lexical_first_negative_step_exists_two_le_first a ha hlen omega · rw [hblen]; omega · have hk3 : 3 ≤ k := by omega have hdrop_eq : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).drop k = a.drop (k - 1) := alpha_lexical_first_negative_step_exists_drop_ge_three a (a.getD 1 0) k hk3 rw [hdrop_eq] have hkm : k - 1 < a.length := by rw [hblen] at hk; omega have hkm0 : 0 < k - 1 := by omega have hdrop_lt_a := ha.2.2 (k - 1) hkm hkm0 exact alpha_lexical_first_negative_step_exists_lt_trans (a.drop (k - 1)) a ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2) hdrop_lt_a hab_lt · apply alpha_lexical_first_negative_step_exists_lt_of_second_cell_gt · rfl · have : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).getD 1 0 = a.getD 1 0 - 1 := rfl omega · have hblen : ([a.getD 0 0, a.getD 1 0 - 1, 1] ++ a.drop 2).length = a.length + 1 := by simp only [List.length_append, List.length_cons, List.length_nil, List.length_drop] omega rw [hblen]; omega