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.
β {Ξ± : Type u_1} {π : Set (Set Ξ±)} {A : Set Ξ±}, ((fun x => A β© x) '' π).encard β€ {B | B β A β§ Shatters π B}.encardRelations
- Generalised byMTH.C-2026-6005
At Y = Bool this specialises to Pajor's inequality.
Asserted by
Dhruv Gupta
Arguments
| DOI | Author | Date |
|---|---|---|
| MTH.R-2026-6001 | 2026-09-24T00:00:00Z |
Verification
- Library
- FLT_Proofs.VCDimGeneralized.VCDim
- Statement digest
- 3cdd55e82875
- First verified
- 2026-09-24T00:00:00Z