Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.4.2 — Helley theorem: if every k≤n+1k \le n+1k≤n+1 of finitely many convex sets in Rn\mathbb R^nRn meet, all of them meet

Proved
ModernConvex.LPDuality.helly_theorem

by Shuze Chen · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-geometryhelly-theorem

Let A1,…,AMA_1,\dots,A_MA1​,…,AM​ be a finite collection of convex sets in Rn\mathbb R^nRn. Assume that the intersection of every k≤n+1k \le n+1k≤n+1 sets from the collection is nonempty: for every set S⊆{1,…,M}S \subseteq \{1,\dots,M\}S⊆{1,…,M} of at most n+1n+1n+1 indices,

⋂i∈SAi≠∅.\bigcap_{i \in S} A_i \neq \emptyset .i∈S⋂​Ai​=∅.

Then the intersection of all MMM sets is nonempty:

⋂i=1MAi≠∅.\bigcap_{i=1}^M A_i \neq \emptyset .i=1⋂M​Ai​=∅.

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 {0,…,M−1}\{0,\dots,M-1\}{0,…,M−1}; subcollections are finite sets of indices SSS with ∣S∣≤n+1|S| \le n+1∣S∣≤n+1. The empty subcollection has intersection Rn\mathbb R^nRn, so the hypothesis says nothing for k=0k = 0k=0. No lower bound on MMM is imposed: for M≤n+1M \le n+1M≤n+1 the hypothesis with SSS the whole index set is already the conclusion, exactly as in the book's statement.

Preamble
import Mathlib
Formal statement
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
Source
Ben-Tal & Nemirovski, Lectures on Modern Convex Optimization, SIAM 2001, p. 37, Theorem 1.4.2 (Helley theorem)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix natural numbers nnn and MMM, and a family A1,…,AMA_1, \dots, A_MA1​,…,AM​ of subsets of Rn\mathbb{R}^nRn, indexed by {1,…,M}\{1, \dots, M\}{1,…,M}. The hypotheses are:

  • every AiA_iAi​ is convex. No closedness, boundedness or nonemptiness is assumed separately;
  • for every set of indices S⊆{1,…,M}S \subseteq \{1, \dots, M\}S⊆{1,…,M} with ∣S∣≤n+1|S| \le n+1∣S∣≤n+1, the intersection ⋂i∈SAi\bigcap_{i \in S} A_i⋂i∈S​Ai​ is nonempty.

The conclusion is that the intersection of the whole family is nonempty:

⋂i=1MAi≠∅.\bigcap_{i=1}^{M} A_i \neq \varnothing .i=1⋂M​Ai​=∅.

Degenerate cases:

  • S=∅S = \varnothingS=∅: the hypothesis includes S=∅S = \varnothingS=∅, where the empty intersection is all of Rn\mathbb{R}^nRn, which is nonempty. That instance is automatic.
  • M=0M = 0M=0: the conclusion's intersection is over an empty family, so it equals Rn\mathbb{R}^nRn. The statement is then trivially true.
  • M≤n+1M \le n+1M≤n+1: taking SSS to be all indices, the hypothesis already contains the conclusion.
  • n=0n = 0n=0: R0\mathbb{R}^0R0 is a single point, and the hypothesis with ∣S∣=1|S| = 1∣S∣=1 says each AiA_iAi​ is nonempty, i.e. each AiA_iAi​ is that point.
Human review
  • Endorsed by Community (Bot) · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 20, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me