Theorem 1.4.2 — Helley theorem: if every of finitely many convex sets in meet, all of them meet
ProvedModernConvex.LPDuality.helly_theoremLet be a finite collection of convex sets in . Assume that the intersection of every sets from the collection is nonempty: for every set of at most indices,
Then the intersection of all sets is nonempty:
In the book (which spells the name "Helley") this theorem gives the "intelligent", purely algebraic proof of the homogeneous Farkas lemma (Exercise 1.13), and hence of the theorem on the alternative and of LP duality.
Formalization Note The sets are indexed by ; subcollections are finite sets of indices with . The empty subcollection has intersection , so the hypothesis says nothing for . No lower bound on is imposed: for the hypothesis with the whole index set is already the conclusion, exactly as in the book's statement.
import Mathlib
namespace ModernConvex.LPDuality
/-- Ben-Tal–Nemirovski, Theorem 1.4.2 (Helley theorem), p. 37. -/
theorem helly_theorem {n M : ℕ} (A : Fin M → Set (Fin n → ℝ)) (hconv : ∀ i, Convex ℝ (A i))
(hinter : ∀ S : Finset (Fin M), S.card ≤ n + 1 → (⋂ i ∈ S, A i).Nonempty) :
(⋂ i, A i).Nonempty := by sorry
end ModernConvex.LPDuality
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix natural numbers and , and a family of subsets of , indexed by . The hypotheses are:
- every is convex. No closedness, boundedness or nonemptiness is assumed separately;
- for every set of indices with , the intersection is nonempty.
The conclusion is that the intersection of the whole family is nonempty:
Degenerate cases:
- : the hypothesis includes , where the empty intersection is all of , which is nonempty. That instance is automatic.
- : the conclusion's intersection is over an empty family, so it equals . The statement is then trivially true.
- : taking to be all indices, the hypothesis already contains the conclusion.
- : is a single point, and the hypothesis with says each is nonempty, i.e. each is that point.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.