Mathesis

Pajor's inequality, with no finiteness assumptions: the traces of π’œ on A are at most as many as the subsets of A shattered by π’œ. For a finite trace family this is a descent on the number of traces that never consumes the ground set; an infinite trace family forces infinitely many shattered singletons, and both sides are ⊀.

Dvir, Filmus and Moran, A Sauer-Shelah-Perles Lemma for Lattices, credit the Boolean lattice case to Pajor (Sous-espaces ℓ₁ⁿ des espaces de Banach, Travaux en Cours 16, Hermann, Paris, 1985) and to Aharoni and Holzman, unpublished. Their Theorem 1.2 is the lattice form, for finite lattices with nonvanishing MΓΆbius function: a family shatters at least as many elements as it has members. Reading that for a family of traces on a ground set is the standard translation into the language of set families, and the statement here carries no finiteness hypothesis, which theirs does.

Declencard_image_inter_le_encard_shatters
βˆ€ {Ξ± : Type u_1} {π’œ : Set (Set Ξ±)} {A : Set Ξ±}, ((fun x => A ∩ x) '' π’œ).encard ≀ {B | B βŠ† A ∧ Shatters π’œ B}.encard

Relations

Arguments

DOIAuthorDate
MTH.R-2026-6001Dhruv GuptaDhruv Gupta2026-09-24T00:00:00Z
DOIMTH.C-2026-6001
Cite

Verification

Library
FLT_Proofs.VCDimGeneralized.VCDim
Statement digest
3cdd55e82875
First verified
2026-09-24T00:00:00Z