Shattering

Let $\mathcal{X}$ be a set of objects one wants to label as 0 or 1, and let $\mathcal{H}$ be a class of functions from $\mathcal{X}$ to $\{0,1\}$, called a hypothesis class. In other words, $\mathcal{H}\subseteq \{0,1{\}}^{\mathcal{X}}$. Let $S=\{p_1,\dots ,p_n\}\subseteq \mathcal{X}$ be a set of points in $\mathcal{X}$. The hypothesis class $\mathcal{H}$ shatters $S$ iff for every label assignment $f:S\to \{0,1\}$ there exists some $h\in \mathcal{H}$ such that $h(p)=f(p)$ for all $p\in S$.

We can use the idea of function restriction to restate this idea:

The hypothesis class $\mathcal{H}$ shatters $S$ iff for every label assignment $f:S\to \{0,1\}$ there exists some $h\in \mathcal{H}$ such that $h{|}_S=f$.

The hypothesis class $\mathcal{H}$ shatters $S$ iff $\{h{|}_S:h\in \mathcal{H}\}=\{0,1{\}}^S$.

Since functions going into $\{0,1\}$ can be seen as subsets of the domain, we can also state the definition using just sets. Let $\mathcal{H}\text{'}=\{h^{-1}(\{1\}):h\in \mathcal{H}\}$ be the set of possible regions that the hypothesis class can label as positive.

The hypothesis class $\mathcal{H}$ shatters $S$ iff for each subset $E$ of $S$ there exists some set $H\in {{\mathcal{H}}^{\prime }}^{\prime }$ such that $E=H\cap S$.

The hypothesis class $\mathcal{H}$ shatters $S$ iff $\mathcal{P}(S)=\{H\cap S:H\in {{\mathcal{H}}^{\prime }}^{\prime }\}$.

References

https://en.wikipedia.org/wiki/Shattered_set

Understanding Machine Learning, chapter on VC dimension.