The Harris–Kleitman inequality
ProvedFamousTheorems.harris_kleitmanThe Harris–Kleitman inequality. Let be a finite set with and let be down-closed families of subsets of (lower sets under inclusion). Then
Dividing by , this says that decreasing events are positively correlated under the uniform measure on . It is the simplest correlation inequality and is generalised by the FKG and Ahlswede–Daykin inequalities. Harris used it in percolation theory, and Kleitman in extremal set theory.
Formalization note. Mathlib's IsLowerSet.le_card_inter_finset. Families are Finset (Finset α) for a finite type α playing the role of . Mathlib also has the variants for two upper sets and for an upper and a lower set.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem harris_kleitman {α : Type*} [DecidableEq α] [Fintype α] {𝒜 ℬ : Finset (Finset α)} (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `IsLowerSet.le_card_inter_finset`. Proof here reduces to that Mathlib result.