Theorem 1.4.3 — Radon: points of split into two parts with intersecting convex hulls
ProvedModernConvex.LPDuality.radon_theoremLet be a collection of vectors in with
Then there is a partition of the index set into two nonempty disjoint subsets and such that
Radon's theorem is the step from which the book derives Helly's theorem (Exercise 1.14), and through it the homogeneous Farkas lemma and the theorem on the alternative.
Formalization Note The collection is a function (repetitions allowed, as for a list of vectors). "Partition into two nonempty disjoint subsets" is: and nonempty, disjoint, with union the whole index set.
import Mathlib
namespace ModernConvex.LPDuality
/-- Ben-Tal–Nemirovski, Theorem 1.4.3 (Radon), p. 38. -/
theorem radon_theorem {n m : ℕ} (a : Fin m → Fin n → ℝ) (hm : n + 2 ≤ m) :
∃ I J : Finset (Fin m), I.Nonempty ∧ J.Nonempty ∧ Disjoint I J ∧ I ∪ J = Finset.univ ∧
(convexHull ℝ (a '' (I : Set (Fin m))) ∩ convexHull ℝ (a '' (J : Set (Fin m)))).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 points in , indexed by . The points need not be distinct: the same point may appear under several indices. The only hypothesis is
The statement asserts that there exist two sets of indices such that:
- is nonempty and is nonempty;
- and are disjoint;
- , so partition the index set;
- the convex hulls of the two image sets meet:
Degenerate cases: the hypothesis can always be satisfied and forces , so the index set always has at least two elements and a partition into two nonempty parts exists. When , has exactly one point, so all coincide and any partition works. If two indices carry the same point, the statement can be met by separating those two indices. The partition is of indices, not of distinct points.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.