AFTD Auto-Formalizing Theoretical Domains

two_facility_max_cost_nonneg

theoremverified

For a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.

Statement

theorem two_facility_max_cost_nonneg {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X]
    (x : ι → X) (p : ι → Fin 2 → Bool) (c : Fin 2 → X) :
    0 ≤ two_facility_max_cost x p c
Source
folklore
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • two_facility_cost_nonnegSanity: every individual cost is nonnegative.
  • two_facility_cost_le_max_costFor a finite nonempty set of agents, every agent i incurs individual cost under solution c that is at most the max cost of c.
  • two_facility_max_costGiven a finite and nonempty set of agents ι, a metric space X, agent positions x, approval preferences p, and facility locations c, the…
  • two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
Used by 3

Read back from the Lean

Given a finite, nonempty type ι, a metric space X, a function x : ι → X, a boolean indicator function p : ι → Fin 2 → Bool, and a function c : Fin 2 → X, the value two_facility_max_cost x p c is greater than or equal to 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that the maximum cost is nonnegative, we choose an arbitrary agent from the nonempty set of agents. The cost incurred by this agent is nonnegative, and by definition, any individual agent's cost is at most the maximum cost across all agents. Transitivity of inequality then implies that the maximum cost is at least zero.

  1. There exists an agent i in ι.

    By assumption, the index set ι of agents is nonempty, so we may choose an arbitrary agent i.

    line 5

      obtain ⟨i⟩ := ‹Nonempty ι›
  2. 0 ≤ two_facility_max_cost x p c

    The cost for agent i is nonnegative (by two_facility_cost_nonneg) and is bounded above by the maximum cost over all agents (by two_facility_cost_le_max_cost). Combining these two inequalities using transitivity (le_trans) establishes that the maximum cost is at least 0.

    line 6

    uses le_trans, two_facility_cost_nonneg, two_facility_cost_le_max_cost

      exact le_trans (two_facility_cost_nonneg x p i c) (two_facility_cost_le_max_cost x p i c)
le_trans
If a ≤ b and b ≤ c, then a ≤ c (transitivity of inequality).
two_facility_cost_nonneg
The two-facility cost for any individual agent is nonnegative.
two_facility_cost_le_max_cost
The two-facility cost for any individual agent is at most the maximum cost across all agents.

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

/-- The max cost of any two-facility solution is nonnegative. -/theorem two_facility_max_cost_nonneg {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X]    (x : ι → X) (p : ι → Fin 2 → Bool) (c : Fin 2 → X) :    0 ≤ two_facility_max_cost x p c := by  obtain ⟨i⟩ := ‹Nonempty ι›  exact le_trans (two_facility_cost_nonneg x p i c) (two_facility_cost_le_max_cost x p i c)
See it in the graphDiscuss this resultChallenge it