AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_lt_cons_same

theoremverified

Prepending the same head to both sequences reverses the alternating lexical order on their tails.

Statement

theorem alpha_lexical_lt_cons_same (x : ℕ) (xs ys : List ℕ) :
    alpha_lexical_lt (x :: xs) (x :: ys) ↔ alpha_lexical_lt ys xs
Source
step towards alpha_lexical_lt_iff_inverse_prefix
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
Used by 1

The proof, explained

Prepending a common head element x to two sequences preserves agreement at index 0 and shifts every subsequent cell by one position, inverting the sign of each entry in the alternating lexical order. Consequently, the first differing index between x :: xs and x :: ys cannot be 0 and must be of the form j + 1, where j is the first differing index between the tails xs and ys. Because the signs at position j + 1 are negated relative to position j, the strict inequality between the cells reverses direction, making x :: xs < x :: ys equivalent to ys < xs.

  1. For any head element x, tail xs, and index j, the signed cell of x :: xs at position j + 1 is the negation of the signed cell of xs at position j.

    Expanding the definitions of `alpha_signed_cell` and list indexing (`List.getD_cons_succ`), the (j + 1)-th entry of `x :: xs` is the j-th entry of `xs`. We case split on whether j is even or odd (`Nat.mod_two_eq_zero_or_one`). If j is even, then j + 1 is odd, so the condition `(j + 1) % 2 = 0` is false while `j % 2 = 0` is true; rewriting with `if_neg` and `if_pos` reduces both sides to `-xs.getD j 0`. If j is odd, then j + 1 is even; rewriting with `if_pos`, `if_neg`, and double negation (`neg_neg`) reduces both sides to `xs.getD j 0`. In both cases, prepending x flips the alternating sign of every tail cell.

    lines 3–6

    uses List.getD_cons_succ, Nat.mod_two_eq_zero_or_one, if_neg, if_pos, neg_neg

      simp only [alpha_signed_cell, List.getD_cons_succ]
      rcases Nat.mod_two_eq_zero_or_one j with h | h
      · rw [if_neg (by omega), if_pos h]
      · rw [if_pos (by omega), if_neg (by omega), neg_neg]
  2. To prove the equivalence, we split into implications; in the forward direction, the distinguishing index cannot be zero.

    We split the if-and-only-if goal into two directions (`constructor`). For the forward direction, assume `alpha_lexical_lt (x :: xs) (x :: ys)`, giving a distinguishing index i with equality at all prior indices and strict inequality `hlt` at index i. We case split on i. If i = 0, both lists have x at index 0, so their signed cells are both x; the inequality `hlt` then simplifies to `x < x`, which is contradictory. Thus i must be a successor j + 1.

    lines 11–14

      constructor
      · rintro ⟨i, hi, heq, hlt⟩
        cases i with
        | zero => simp [alpha_signed_cell] at hlt
  3. The predecessor index j witnesses that ys is strictly less than xs in the alternating lexical order, proving the forward implication.

    With i = j + 1, we propose j as the witness for `alpha_lexical_lt ys xs`. First, the bound `j + 1 < max (x :: xs).length (x :: ys).length` simplifies via `List.length_cons` to `j < max ys.length xs.length`. Second, for any k < j, we have k + 1 < j + 1, so the agreement hypothesis `heq` holds at k + 1; rewriting both sides using `alpha_lexical_lt_cons_same_signed_succ` gives `-alpha_signed_cell xs k = -alpha_signed_cell ys k`, which yields agreement between ys and xs at index k. Third, rewriting the strict inequality `hlt` at index j + 1 with `alpha_lexical_lt_cons_same_signed_succ` transforms `-alpha_signed_cell xs j < -alpha_signed_cell ys j` into `alpha_signed_cell ys j < alpha_signed_cell xs j` by linear arithmetic.

    lines 15–22

    uses List.length_cons, alpha_lexical_lt_cons_same_signed_succ

        | succ j =>
          refine ⟨j, ?_, fun k hk => ?_, ?_⟩
          · simp only [List.length_cons] at hi; omega
          · have := heq (k + 1) (by omega)
            rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ] at this
            linarith
          · rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ] at hlt
            linarith
  4. The successor index j + 1 witnesses that x :: xs is strictly less than x :: ys, proving the reverse implication and completing the equivalence.

    Conversely, assume `alpha_lexical_lt ys xs` with distinguishing index j. We claim j + 1 witnesses `alpha_lexical_lt (x :: xs) (x :: ys)`. First, the length bound `j + 1 < max (x :: xs).length (x :: ys).length` follows from `j < max ys.length xs.length` using `List.length_cons` and linear arithmetic. Second, for any k < j + 1, we verify agreement of the signed cells: if k = 0, both lists start with x and agree definitionally (`rfl`); if k is a successor k + 1 with k + 1 < j + 1, then k < j, and rewriting with `alpha_lexical_lt_cons_same_signed_succ` together with the tail agreement hypothesis `heq k` shows their signed cells match. Third, at index j + 1, rewriting with `alpha_lexical_lt_cons_same_signed_succ` turns the required inequality into `-alpha_signed_cell xs j < -alpha_signed_cell ys j`, which follows by linear arithmetic from the assumed inequality `alpha_signed_cell ys j < alpha_signed_cell xs j`.

    lines 23–32

    uses List.length_cons, alpha_lexical_lt_cons_same_signed_succ

      · rintro ⟨j, hj, heq, hlt⟩
        refine ⟨j + 1, ?_, fun k hk => ?_, ?_⟩
        · simp only [List.length_cons]; omega
        · cases k with
          | zero => rfl
          | succ k =>
            rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ,
              heq k (by omega)]
        · rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ]
          linarith
alpha_lexical_lt_cons_same_signed_succ
The signed cell of `x :: xs` at index `j + 1` equals the negation of the signed cell of `xs` at index `j`.
List.getD_cons_succ
Accessing index `n + 1` of `x :: xs` with default value `d` returns the same element as accessing index `n` of `xs`.
Nat.mod_two_eq_zero_or_one
Any natural number modulo 2 is either 0 or 1.
if_neg
If a proposition `c` is false, `if c then t else e` evaluates to `e`.
if_pos
If a proposition `c` is true, `if c then t else e` evaluates to `t`.
neg_neg
Negating an element twice returns the original element: `- -a = a`.
List.length_cons
The length of `a :: as` is `as.length + 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

lemma alpha_lexical_lt_cons_same_signed_succ (x : ℕ) (xs : List ℕ) (j : ℕ) :    alpha_signed_cell (x :: xs) (j + 1) = -alpha_signed_cell xs j := by  simp only [alpha_signed_cell, List.getD_cons_succ]  rcases Nat.mod_two_eq_zero_or_one j with h | h  · rw [if_neg (by omega), if_pos h]  · rw [if_pos (by omega), if_neg (by omega), neg_neg]/-- Prepending the same head to both sequences reverses the alternating lexical order on their tails. -/theorem alpha_lexical_lt_cons_same (x : ℕ) (xs ys : List ℕ) :    alpha_lexical_lt (x :: xs) (x :: ys) ↔ alpha_lexical_lt ys xs := by  constructor  · rintro ⟨i, hi, heq, hlt⟩    cases i with    | zero => simp [alpha_signed_cell] at hlt    | succ j =>      refine ⟨j, ?_, fun k hk => ?_, ?_⟩      · simp only [List.length_cons] at hi; omega      · have := heq (k + 1) (by omega)        rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ] at this        linarith      · rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ] at hlt        linarith  · rintro ⟨j, hj, heq, hlt⟩    refine ⟨j + 1, ?_, fun k hk => ?_, ?_⟩    · simp only [List.length_cons]; omega    · cases k with      | zero => rfl      | succ k =>        rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ,          heq k (by omega)]    · rw [alpha_lexical_lt_cons_same_signed_succ, alpha_lexical_lt_cons_same_signed_succ]      linarith
See it in the graphDiscuss this resultChallenge it