AFTD Auto-Formalizing Theoretical Domains

line_min_matching_cost_nonneg

theoremverified

OPT is nonnegative.

Statement

theorem line_min_matching_cost_nonneg {n : ℕ} (a b : Fin n → ℝ) :
    0 ≤ line_min_matching_cost a b
Source
sanity lemma for line_min_matching_cost (OP-1158)
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • line_min_matching_costOPT: the minimum, over all permutations sigma of the n items, of the matching cost sum_i |a_i - b_{sigma(i)}|.

The proof, explained

The minimum matching cost is defined as the infimum over all permutations of the sum of distances between matched points. To show that this infimum is nonnegative, it suffices to show that each matching cost is nonnegative. Since each term in the sum is an absolute value (and thus nonnegative), any matching cost is a sum of nonnegative quantities and is therefore nonnegative.

  1. Expanding the definition rewrites the goal to showing that the infimum of matching costs over all permutations is at least 0.

    By definition, `line_min_matching_cost a b` is the infimum over all permutations $\sigma$ of the finite sum $\sum_{i} |a(i) - b(\sigma(i))|$.

    line 3

      unfold line_min_matching_cost
  2. The infimum of the matching costs is nonnegative.

    By `Finset.le_inf'_iff`, showing $0 \le \inf'_\sigma (\dots)$ reduces to checking that each candidate cost is at least 0. For an arbitrary permutation $\sigma$, the cost is a finite sum of terms $|a(i) - b(\sigma(i))|$. Each term is nonnegative by `abs_nonneg`, so the sum is nonnegative by `Finset.sum_nonneg`.

    line 4

    uses Finset.le_inf'_iff, Finset.sum_nonneg, abs_nonneg

      exact (Finset.le_inf'_iff _ _).2 fun σ _ => Finset.sum_nonneg fun i _ => abs_nonneg _
Finset.le_inf'_iff
A value is bounded below by the infimum of a function over a nonempty finite set if and only if it bounds the value of the function at every element of the set.
Finset.sum_nonneg
A sum of elements over a finite set is nonnegative if every term in the sum is nonnegative.
abs_nonneg
The absolute value of any element in an ordered group is nonnegative.

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 line_min_matching_cost_nonneg {n : ℕ} (a b : Fin n → ℝ) :    0 ≤ line_min_matching_cost a b := by  unfold line_min_matching_cost  exact (Finset.le_inf'_iff _ _).2 fun σ _ => Finset.sum_nonneg fun i _ => abs_nonneg _
See it in the graphDiscuss this resultChallenge it