alpha_lexical_lt_cons_same
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
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.
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.
uses
List.getD_cons_succ,Nat.mod_two_eq_zero_or_one,if_neg,if_pos,neg_negsimp 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]
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.
constructor · rintro ⟨i, hi, heq, hlt⟩ cases i with | zero => simp [alpha_signed_cell] at hlt
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.
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 linarithThe 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`.
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
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_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