two_facility_cost_nonneg
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
- two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
- Used by 4
- fixed_dictator_social_cost_le_of_doubletonCase 1 of Theorem 4.5: if the facilities are at the two closest candidate locations w_1, w_2 of an agent i approving both, then SC(w) ≤…
- fixed_dictator_social_cost_le_of_one_approvedCase 3 of Theorem 4.5: when only F_k is approved and it is placed at a closest candidate of an approving agent i (the other facility at…
- two_facility_max_cost_nonnegFor a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.
- fixed_dictator_social_cost_le_of_singletonsCase 2 of Theorem 4.5: with no agent approving both facilities, if F_1 is at a closest candidate w_1 of an agent i approving F_1 and F_2…
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`).
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$.
uses
Finset.sum_nonnegunfold two_facility_cost apply Finset.sum_nonneg intro j hj
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`.
uses
dist_nonnegsplit_ifs with hp · exact dist_nonneg
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`).
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
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 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