Kleitman's theorem on unions of intersecting families
ProvedFamousTheorems.kleitman_intersecting_familiesKleitman's theorem on intersecting families. Let be a nonempty finite set with and intersecting families of subsets of (any two members of the same family meet). Then
For it recovers the classical bound for a single intersecting family. Kleitman's bound is sharp and answered a question of Erdős on unions of intersecting families.
Formalization note. Mathlib's Finset.card_biUnion_le_of_intersecting. The families are indexed by a finset s of size , and Set.Intersecting means any two members have nonempty intersection. Subtraction is truncated subtraction on ℕ, which is harmless since .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem kleitman_intersecting_families {ι α : Type*} [Fintype α] [DecidableEq α] [Nonempty α] (s : Finset ι) (f : ι → Finset (Finset α))
(hf : ∀ i ∈ s, (f i : Set (Finset α)).Intersecting) :
(s.biUnion f).card ≤ 2 ^ Fintype.card α - 2 ^ (Fintype.card α - s.card) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.card_biUnion_le_of_intersecting`. Proof here reduces to that Mathlib result.