= Set shattering
{title2=$\mathcal F_{|Z}=\mathcal P(Z)$}
= Shatters a set
{synonym}
= Shattered
{synonym}
A <set family> $\mathcal F$ shatters a <set> $Z$ when its <trace of a set family> on $Z$ realizes every <subset> of $Z$:
$$
\{A\cap Z:A\in\mathcal F\}=\mathcal P(Z).
$$
Each possible include-or-exclude pattern on $Z$ must occur, although different patterns may come from different members of $\mathcal F$.
For example, on $X=\{1,2\}$ let $\mathcal F=\{\varnothing,\{1\},\{2\}\}$. It shatters either singleton, but it does not shatter $X$, because the <subset> $\{1,2\}$ never occurs as a <trace of a set family>. Its <VC dimension> is therefore one.
The <VC dimension> is the largest finite size of a <shattered> <set>, or infinity if arbitrarily large finite <sets> are <shattered>. The <Sauer-Shelah lemma> bounds the number of traces when a fixed size cannot be <shattered>. This turns a local pattern-realization condition into a global bound on the size of a <set family>.
Back to article page
