An intersecting family of subsets of an n-set has at most 2^(n−1) members
ProvedFamousTheorems.intersecting_family_card_le_6bAn intersecting family of subsets of an -set has at most members. Let be a family of subsets of an -element set such that any two members of intersect. Then .
The proof is short: a set and its complement cannot both lie in . The bound is sharp, as the family of all sets containing a fixed point shows. This is the unrestricted version of the Erdős–Ko–Rado theorem and one of the first results of extremal set theory.
Formalization note. Mathlib's Set.Intersecting.card_le, stated for a finite Boolean algebra : an intersecting family satisfies . Two elements intersect when their meet is nonzero. Taking to be the power set of an -element set gives .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem intersecting_family_card_le_6b {α : Type*} [BooleanAlgebra α] [Fintype α] {s : Finset α} (hs : (s : Set α).Intersecting) :
2 * s.card ≤ Fintype.card α := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Set.Intersecting.card_le`. Proof here reduces to that Mathlib result.