AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_meet_sum_lt_of_ne_of_sum_eq

theoremverified

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

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.

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

    lines 5–8

    uses False.elim

      induction a generalizing b with
      | nil =>
          cases b with
          | nil => exact False.elim (hne rfl)
  2. 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.

    lines 9–12

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

    lines 13–18

    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
              omega
  4. When 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.

    lines 19–21

          | cons y ys =>
              by_cases hxy : x = y
              · subst y
  5. The 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.

    lines 22–28

    uses List.sum_cons

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

    lines 29–32

    uses List.sum_cons

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

    lines 33–35

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

    lines 36–37

    uses Nat.min_eq_left

                · rw [Nat.min_eq_left hh.le]
                  omega
  9. 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.

    lines 38–39

    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

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