Shattering, VC dimension, and first-unshattered index for set classes

Let $\mathcal{C}\subseteq \mathcal{P}(X)$ be a family of subsets of an arbitrary set $X$. For a finite $T\subseteq X$, its trace is

$\mathcal{C}{\mathrm{\mid }}_T:=\{C\cap T:C\in \mathcal{C}\}\mathrm{.}$

The family $\mathcal{C}$ shatters $T$ when $\mathcal{C}{\mathrm{\mid }}_T=\mathcal{P}(T)$. This extends the finite-ground-set trace convention of Shattering and the Vapnik–Chervonenkis dimension of a set family: any finite $T$ can be relabeled by $[\mathrm{\mid }T\mathrm{\mid }]$, and relabeling preserves all traces and their cardinalities.

For a nonempty class, its VC dimension $d(\mathcal{C})$ is the greatest size of a finite shattered set if those sizes are bounded, is $0$ if no singleton is shattered, and is $+\mathrm{\infty }$ if finite shattered sets have unbounded size. When the dimension is finite, its VC index is

$V(\mathcal{C}):=d(\mathcal{C})+1,$

equivalently the least positive integer $V$ such that no $V$-point subset is shattered. The empty class is assigned $V=0$ by convention and is treated separately in the entropy theorem.