Indexed shattering and VC dimension of a binary class

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space and let $H$ be a nonempty class of measurable functions $h:\mathcal{X}\to \{0,1\}$. For an integer $m\ge 0$ and an indexed tuple $\mathbf{x}=(x_1,\dots ,x_m)\in {\mathcal{X}}^m$, define its trace by

${\mathrm{tr}}_H(\mathbf{x}):=\{(h(x_1),\dots ,h(x_m)):h\in H\}\subseteq \{0,1{\}}^m\mathrm{.}$

The tuple $\mathbf{x}$ is shattered by $H$ if ${\mathrm{tr}}_H(\mathbf{x})=\{0,1{\}}^m$. Its coordinates are indexed: repeated instance points remain distinct coordinates, although their labels must agree for every $h\in H$. For $m=0$, $\mathbf{x}=()$ and $\{0,1{\}}^0=\{()\}$, so the empty tuple is shattered. The VC dimension of $H$ is

$\mathrm{VCdim}(H):=\sup \{m\in {\mathbb{N}}_0:\text{some }\mathbf{x}\in {\mathcal{X}}^m\text{ is shattered by }H\}\in {\mathbb{N}}_0\cup \{+\mathrm{\infty }\}\mathrm{.}$

Shattering and the Vapnik–Chervonenkis dimension of a set family: its current definition treats a family $\mathcal{F}\subseteq \mathcal{P}([n])$; on an indexed sample, identify each $h$ with the subset $\{i\in [m]:h(x_i)=1\}$, keeping repeated sample points at separate indices.

Mohri et al., Definition 3.10: VC dimension of a hypothesis class.

Bartlett and Mendelson, Theorem 6: sample-restricted VC dimension.