AFTD Auto-Formalizing Theoretical Domains

two_facility_cost_nonneg

theoremverified

Sanity: every individual cost is nonnegative.

Statement

theorem two_facility_cost_nonneg {ι X : Type*} [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool)
    (i : ι) (c : Fin 2 → X) : 0 ≤ two_facility_cost x p i c
Source
sanity lemma for two_facility_cost (arXiv:2610.18006 (Truthful two-facility location with candidate locations in metric spaces))
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 4

The proof, explained

The definition of `two_facility_cost` expresses the cost as a sum over the two facilities of terms that are either a metric distance or zero. By `Finset.sum_nonneg`, the sum is nonnegative if each summand is nonnegative. A case distinction shows that every summand is nonnegative, since distances are nonnegative (`dist_nonneg`) and zero is nonnegative (`le_refl`).

  1. It suffices to show that each term in the sum defining the facility cost is nonnegative.

    Unfolding the definition of `two_facility_cost`, the cost is given by the sum $\sum_{j \in \{0, 1\}} (\text{if } p(i, j) = \text{true then } \operatorname{dist}(x(i), c(j)) \text{ else } 0)$. By `Finset.sum_nonneg`, a finite sum is nonnegative if every term is nonnegative, so we consider an arbitrary facility $j$.

    lines 3–5

    uses Finset.sum_nonneg

      unfold two_facility_cost
      apply Finset.sum_nonneg
      intro j hj
  2. If facility $j$ is chosen ($p(i, j) = \text{true}$), the term is nonnegative.

    Splitting into cases depending on the boolean condition $p(i, j) = \text{true}$, if the condition holds, the term simplifies to $\operatorname{dist}(x(i), c(j))$. Distance in any metric space is nonnegative by `dist_nonneg`.

    lines 6–7

    uses dist_nonneg

      split_ifs with hp
      · exact dist_nonneg
  3. If facility $j$ is not chosen, the term is nonnegative.

    In the alternative case where $p(i, j) \neq \text{true}$, the term simplifies to $0$. The inequality $0 \le 0$ holds trivially by reflexivity (`le_refl 0`).

    line 8

    uses le_refl

      · exact le_refl 0
Finset.sum_nonneg
A finite sum of nonnegative terms is nonnegative.
dist_nonneg
The distance between any two points in a metric space is nonnegative: $0 \le \operatorname{dist}(x, y)$.
le_refl
The inequality relation is reflexive: $a \le a$ for any $a$.

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 two_facility_cost_nonneg {ι X : Type*} [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool)    (i : ι) (c : Fin 2 → X) : 0 ≤ two_facility_cost x p i c := by  unfold two_facility_cost  apply Finset.sum_nonneg  intro j hj  split_ifs with hp  · exact dist_nonneg  · exact le_refl 0
See it in the graphDiscuss this resultChallenge it