AFTD Auto-Formalizing Theoretical Domains

line_min_matching_cost_le

theoremverified

OPT is at most the cost of any perfect matching.

Statement

theorem line_min_matching_cost_le {n : ℕ} (a b : Fin n → ℝ) (σ : Equiv.Perm (Fin n)) :
    line_min_matching_cost a b ≤ ∑ i, |a i - b (σ i)|
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)}|.
Used by 3

The proof, explained

The optimal matching cost is defined as the infimum of the matching cost over all permutations of Fin n in the finite universe Finset.univ. Since any particular permutation σ belongs to this universal set, the infimum is at most the cost evaluated at σ.

  1. The minimum matching cost line_min_matching_cost a b is bounded above by the cost of the permutation σ.

    By definition, line_min_matching_cost a b is the infimum of the matching cost function over all permutations in the universal finite set Finset.univ. Since the permutation σ trivially belongs to Finset.univ by Finset.mem_univ, Finset.inf'_le implies that the infimum over Finset.univ is at most the value of the cost function evaluated at σ.

    line 3

    uses Finset.inf'_le, Finset.mem_univ

      Finset.inf'_le _ (Finset.mem_univ σ)
Finset.inf'_le
For any element b in a finite set s, the infimum of a function f over s is at most f(b).
Finset.mem_univ
Every element of a finite type belongs to the universal finite set univ.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). 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_le {n : ℕ} (a b : Fin n → ℝ) (σ : Equiv.Perm (Fin n)) :    line_min_matching_cost a b ≤ ∑ i, |a i - b (σ i)| :=  Finset.inf'_le _ (Finset.mem_univ σ)
See it in the graphDiscuss this resultChallenge it