alpha_lexical_meet_sum_lt_of_ne_of_sum_eq
The common lexical meet of two distinct positive integer sequences of equal sum has strictly smaller sum than either input.
Statement
theorem alpha_lexical_meet_sum_lt_of_ne_of_sum_eq
(a b : List ℕ) (hapos : ∀ v ∈ a, 0 < v) (hbpos : ∀ v ∈ b, 0 < v)
(hne : a ≠ b) (hsum : a.sum = b.sum) :
(alpha_lexical_meet a b).sum < a.sum- Source
- Proper-meet helpers for the published lexical adjacency criterion, arXiv:0810.5205v2, Theorem3.1 and Corollary3.3, supporting the run-length route for OP-392. These routine reductions do not prove the adjacency theorem and no research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
- Used by 1
- alpha_prime_lexical_meet_nondvd_of_neFor any distinct lexical sequences of the same prime degree, the meet degree is a proper nontrivial value and does not divide the ambient…
The proof, explained
The proof proceeds by induction on the first list a, generalizing over the second list b. The cases where either list is empty are ruled out immediately: if both are empty they cannot be distinct, and if exactly one is empty its sum is zero while the other has a strictly positive head. When both lists are non-empty, the proof branches on whether their leading elements agree: if they do, the induction hypothesis applies to the tails; if they differ, the meet reduces to the single element min(x, y), which linear arithmetic shows is strictly less than the total sum in both orderings x < y and y < x.
The case where both lists are empty is ruled out by distinctness.
We proceed by induction on a, generalizing over b. In the base case where a = [], we case-split on b. If b is also [], then a = b, which contradicts the hypothesis a ≠ b (hne).
uses
False.eliminduction a generalizing b with | nil => cases b with | nil => exact False.elim (hne rfl)
The case where a = [] and b is non-empty is ruled out by positivity.
If b = y :: ys, the positivity hypothesis hbpos gives y > 0. Expanding the sums in the equality a.sum = b.sum produces 0 = y + ys.sum. Because y > 0, this is an arithmetic contradiction.
uses
List.sum_nil,List.sum_cons| cons y ys => have hy := hbpos y (by simp) simp only [List.sum_nil, List.sum_cons] at hsum omegaThe case where a is non-empty and b = [] is ruled out symmetrically.
In the inductive step where a = x :: xs, we case-split on b. If b = [], the positivity hypothesis hapos gives x > 0. Expanding the sums yields x + xs.sum = 0, which is impossible in ℕ since x > 0.
uses
List.sum_nil,List.sum_cons| cons x xs ih => cases b with | nil => have hx := hapos x (by simp) simp only [List.sum_nil, List.sum_cons] at hsum omegaWhen both lists are non-empty, we first consider the case where their heads are equal.
With a = x :: xs and b = y :: ys, we branch on whether x = y. When x = y, we substitute y with x, reducing the lists to x :: xs and x :: ys.
| cons y ys => by_cases hxy : x = y · subst yThe tails xs and ys are distinct and have equal sum.
If the tails were identical (xs = ys), the full lists would be identical (x :: xs = x :: ys), contradicting a ≠ b. Furthermore, expanding the sums in x + xs.sum = x + ys.sum and subtracting x yields xs.sum = ys.sum.
uses
List.sum_conshave htail : xs ≠ ys := by intro he apply hne rw [he] have hstail : xs.sum = ys.sum := by simp only [List.sum_cons] at hsum omega
When the heads are equal, the induction hypothesis completes the step.
Because every element of xs and ys is drawn from x :: xs and x :: ys respectively, the tails inherit the positivity property. We apply the induction hypothesis to xs and ys, obtaining (alpha_lexical_meet xs ys).sum < xs.sum. By definition, the meet of x :: xs and x :: ys is x :: alpha_lexical_meet xs ys, so adding x to both sides establishes the inequality.
uses
List.sum_conshave hh := ih ys (fun v hv => hapos v (by simp [hv])) (fun v hv => hbpos v (by simp [hv])) htail hstail simp only [alpha_lexical_meet, ↓reduceIte, List.sum_cons] omega
When the heads differ, the meet reduces to [min x y], and we split into x < y and y < x.
When x ≠ y, alpha_lexical_meet (x :: xs) (y :: ys) evaluates to [min x y], whose sum is min x y. The equality of sums expands to x + xs.sum = y + ys.sum. Since x ≠ y, we split into the two cases x < y and y < x.
uses
if_neg,List.sum_cons,List.sum_nil,lt_or_gt_of_ne· simp only [alpha_lexical_meet, if_neg hxy, List.sum_cons, List.sum_nil] simp only [List.sum_cons] at hsum rcases lt_or_gt_of_ne hxy with hh | hh
If x < y, the sum of the meet is strictly less than a.sum.
When x < y, min x y evaluates to x. Because x + xs.sum = y + ys.sum and x < y, linear arithmetic over ℕ implies xs.sum > 0, so x < x + xs.sum.
uses
Nat.min_eq_left· rw [Nat.min_eq_left hh.le] omega
If y < x, the sum of the meet is strictly less than a.sum.
When y < x, min x y evaluates to y. Linear arithmetic gives y < x ≤ x + xs.sum, so y < x + xs.sum as desired.
uses
Nat.min_eq_right· rw [Nat.min_eq_right hh.le] omega
False.elim- From False (a contradiction), any proposition can be deduced (ex falso quodlibet).
List.sum_nil- The sum of the elements in the empty list is 0.
List.sum_cons- The sum of a non-empty list x :: xs is x + xs.sum.
if_neg- If a condition c is false, the conditional expression if c then t else e simplifies to e.
lt_or_gt_of_ne- For distinct elements in a linear order, either a < b or b < a.
Nat.min_eq_left- If a ≤ b, then min a b = a.
Nat.min_eq_right- If b ≤ a, then min a b = b.
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.
theorem alpha_lexical_meet_sum_lt_of_ne_of_sum_eq (a b : List ℕ) (hapos : ∀ v ∈ a, 0 < v) (hbpos : ∀ v ∈ b, 0 < v) (hne : a ≠ b) (hsum : a.sum = b.sum) : (alpha_lexical_meet a b).sum < a.sum := by induction a generalizing b with | nil => cases b with | nil => exact False.elim (hne rfl) | cons y ys => have hy := hbpos y (by simp) simp only [List.sum_nil, List.sum_cons] at hsum omega | cons x xs ih => cases b with | nil => have hx := hapos x (by simp) simp only [List.sum_nil, List.sum_cons] at hsum omega | cons y ys => by_cases hxy : x = y · subst y have htail : xs ≠ ys := by intro he apply hne rw [he] have hstail : xs.sum = ys.sum := by simp only [List.sum_cons] at hsum omega have hh := ih ys (fun v hv => hapos v (by simp [hv])) (fun v hv => hbpos v (by simp [hv])) htail hstail simp only [alpha_lexical_meet, ↓reduceIte, List.sum_cons] omega · simp only [alpha_lexical_meet, if_neg hxy, List.sum_cons, List.sum_nil] simp only [List.sum_cons] at hsum rcases lt_or_gt_of_ne hxy with hh | hh · rw [Nat.min_eq_left hh.le] omega · rw [Nat.min_eq_right hh.le] omega