Alphabeta MathHow statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Sauer–Shelah: a family on of VC dimension at most has at most members
Statement
Let have VC dimension at most . Then
Facts & Assumptions
Given: a family with .
Iterated down-shifting terminates in a downward-closed family (Applying down-shifts until none changes the family terminates, and the result is closed under taking subsets).
Down-shifting preserves the number of sets (, and with equality only when ).
Down-shifting creates no new shattered set (Every set shattered by is shattered by ).
A downward-closed family shatters each of its members (If is closed under taking subsets then shatters every ).
The -element subsets of are counted by (The set of -element subsets and the binomial coefficient ).
Proof
Apply [L1] to obtain a downward-closed family by iterated shifting from .
By [L2], the shift process preserves the number of sets, so ; and by [L3], the VC dimension does not increase, so .
Because is downward closed, [L4] says that every member of is shattered. Since , every member of therefore has size at most .
So is a subset of the union of the layers , whose total size is by [F1]. Using step 2.1, the same bound holds for .
Remarks
- The argument is purely combinatorial. The page later gives a second proof through multilinear polynomials, but this theorem itself uses only shifting.
Depends on
- Shattering and the Vapnik–Chervonenkis dimension of a set family
- The down-shift $S_j$ of a set family at a point $j$
- $\lvert S_j(\mathcal{F})\rvert=\lvert\mathcal{F}\rvert$, and $w(S_j(\mathcal{F}))\le w(\mathcal{F})$ with equality only when $S_j(\mathcal{F})=\mathcal{F}$
- Every set shattered by $S_j(\mathcal{F})$ is shattered by $\mathcal{F}$
- Applying down-shifts until none changes the family terminates, and the result is closed under taking subsets
- If $\mathcal{F}$ is closed under taking subsets then $\mathcal{F}$ shatters every $F\in\mathcal{F}$
- The set $[A]^{k}$ of $k$-element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$
- The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition
- The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form
Used by
- For d≥1 a family on [n] of VC dimension at most d has at most (n+1)ᵈ members Corollary
- All subsets of [4] of size at most 2: VC dimension 2 and exactly ∑_i≤2C(4, i)=11 members Example
- FALSE: a family on [n] of VC dimension at most d has at most nᵈ members False statement
- The shifting proof of Sauer–Shelah uses no field and no vector space Remark
- A second proof of Sauer–Shelah, from the multilinear polynomial space Theorem
Dependency tree · two levels
29 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, §7.4 (standard reference, not scraped)