= Solution
A <set family> <shatters a set> $Z$ when its traces on $Z$ include all of $\mathcal P(Z)$. The <Sauer-Shelah lemma> says that a <set family> $\mathcal F\subseteq\mathcal P([n])$ which shatters no $k$-set satisfies
$$
\boxed{|\mathcal F|\leq\sum_{i=0}^{k-1}\binom ni.}
$$
Equivalently, if $|\mathcal F|$ exceeds this sum, it shatters a $k$-set. <Binomial coefficients> with index greater than $n$ are zero; if $k>n$ the inequality reduces to the whole-power-set bound. The <VC dimension> formulation puts $k=d+1$.
We give the full inductive proof. Split $\mathcal F$ according to the last coordinate, deleting that coordinate from the present section, and write these two <set families> on $[n-1]$ as $\mathcal F_0,\mathcal F_1$. Put
$$
\mathcal C=\mathcal F_0\cup\mathcal F_1,\qquad
\mathcal D=\mathcal F_0\cap\mathcal F_1.
$$
The <inclusion-exclusion principle> gives $|\mathcal F|=|\mathcal C|+|\mathcal D|$. If $\mathcal C$ shattered a $k$-set, then $\mathcal F$ would shatter it too. If $\mathcal D$ shattered a $(k-1)$-set $Z$, both versions of each required trace, with and without the last coordinate, would occur in $\mathcal F$, which would shatter $Z\cup\{n\}$. Thus the two <mathematical induction> bounds apply:
$$
|\mathcal F|\leq\sum_{i=0}^{k-1}\binom{n-1}{i}
+\sum_{i=0}^{k-2}\binom{n-1}{i}
=\sum_{i=0}^{k-1}\binom ni,
$$
using <Pascal's identity>. For $n=0$ the <set family> has at most one member. For $k=1$, the intersection section must be empty, since any nonempty <set family> shatters the empty <set>. These supply the <mathematical induction> bases; the forbidden-empty-set case has an empty <set family> and an empty sum. Sharpness is attained by all <subsets> of size at most $k-1$, which cannot shatter a $k$-set.
Now fix $k\geq1$ in the infinite-ground-set problem. Choose, using the hypothesis with $2k$, a <set> $Y$ of size $2k$ with at least $2^{2k-1}$ distinct traces. If its trace <set family> shattered no $k$-set, the <Sauer-Shelah lemma> would give
$$
|\mathcal A_{|Y}|\leq\sum_{i=0}^{k-1}\binom{2k}{i}
=\frac{2^{2k}-\binom{2k}{k}}2
<2^{2k-1},
$$
a contradiction. Therefore some $Z\subseteq Y$ of size $k$ is shattered by the trace <set family>, and hence by $\mathcal A$ itself. Thus \b[every finite shattering size occurs]. The use of $2k$ makes the contradiction strict, even though the hypothesis only gives a half-power-set lower bound.
An infinite realization does not follow. For a concrete <unbounded finite shattering without an infinite universal trace> construction, partition $X=\mathbb N$ into disjoint finite blocks
$$
B_j=\left\{\frac{j(j-1)}2+1,\ldots,\frac{j(j+1)}2\right\},\qquad |B_j|=j,
$$
and take
$$
\boxed{\mathcal A=\bigcup_{j\geq1}\mathcal P(B_j).}
$$
Every member is finite. Given $k$, choose $Y=B_k$; its trace <set family> is the full <power set>, so it has $2^k\geq2^{k-1}$ members and is shattered. However, an infinite $Z$ cannot be contained in one finite block. Choose $x,y\in Z$ from different blocks. No member of $\mathcal A$ contains both, so $\{x,y\}$ is not a trace on $Z$. Consequently \b[there need not be an infinite $Z$ whose traces contain every finite <subset> of $Z$].
Back to article page
