AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_first_negative_step_exists

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

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

    lines 4–6

    uses List.getD_eq_default

      dsimp [alpha_signed_cell]
      rw [List.getD_eq_default _ _ hi]
      split <;> rfl
  2. 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.

    lines 12–17

    uses le_of_max_le_left, le_of_max_le_right, alpha_lexical_first_negative_step_exists_signed_cell_eq_zero_of_ge

      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
      omega
  3. 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|).

    lines 22–36

    uses lt_trichotomy, alpha_lexical_first_negative_step_exists_lt_max_of_signed_cell_lt, lt_trans

      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_lt
  4. 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`.

    line 40

    uses List.getD_eq_getElem?_getD, List.getElem?_drop

      simp only [List.getD_eq_getElem?_getD, List.getElem?_drop]
  5. 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`.

    line 44

    uses alpha_lexical_first_negative_step_exists_getD_drop, add_zero

      rw [alpha_lexical_first_negative_step_exists_getD_drop, add_zero]
  6. 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].

    lines 49–57

    uses eq_or_lt_of_le, Nat.zero_le, alpha_lexical_first_negative_step_exists_getD_drop_zero

      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; omega
  7. 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`.

    lines 62–63

    uses List.getD_eq_getElem, List.getElem_mem

      rw [List.getD_eq_getElem a 0 hk]
      exact ha.2.1 _ (List.getElem_mem hk)
  8. 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.

    lines 68–93

    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_zero

      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; omega
  9. 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.

    lines 98–99

      refine ⟨0, hlen, fun j hj => by omega, ?_⟩
      dsimp [alpha_signed_cell]; omega
  10. 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.

    lines 105–109

      refine ⟨1, hlen, fun j hj => ?_, ?_⟩
      · have : j = 0 := by omega
        subst this
        dsimp [alpha_signed_cell]; omega
      · dsimp [alpha_signed_cell]; omega
  11. 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.

    lines 113–115

      rcases k with _ | k
      · contradiction
      · rfl
  12. 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`.

    lines 119–126

    uses List.drop_drop

      rcases k with _ | _ | _ | k
      · omega
      · omega
      · omega
      · change (a.drop 2).drop k = a.drop (k + 2)
        rw [List.drop_drop]
        congr 1
        omega
  13. 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]].

    lines 130–134

    uses List.getD_eq_getElem

      have : 0 < a.length := by omega
      rw [List.getD_eq_getElem a 0 this]
      rcases a with _ | ⟨x, xs⟩
      · contradiction
      · rfl
  14. 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].

    lines 140–142

    uses alpha_lexical_first_negative_step_exists_cell_pos, eq_or_lt_of_le

      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
  15. 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`.

    lines 143–145

    uses Or.inr

      · refine ⟨[a.getD 0 0 + 1] ++ a.drop 2, ?_, ?_, ?_⟩
        · refine ⟨by omega, Or.inr ⟨by omega, ha1.symm, ?_⟩⟩
          rfl
  16. 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`.

    lines 146–160

    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
  17. 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.

    lines 161–163

    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
  18. 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`.

    lines 164–167

    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
  19. 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].

    lines 168–176

    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
  20. 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.

    lines 177–184

    uses List.mem_append, List.mem_cons, List.not_mem_nil, alpha_lexical_first_negative_step_exists_cell_pos, List.mem_of_mem_drop

          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)
  21. 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.

    lines 185–192

    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
  22. 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.

    lines 193–200

    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
  23. 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.

    lines 201–209

    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
  24. 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.

    lines 210–217

    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.

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