line_min_matching_cost_nonneg
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.
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))|$.
unfold line_min_matching_costThe 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`.
uses
Finset.le_inf'_iff,Finset.sum_nonneg,abs_nonnegexact (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
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 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 _