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},\ldots ,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}}'=\{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}}'$ such that $E=H\cap S$.

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

References

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

Understanding Machine Learning, chapter on VC dimension.