VC dimension

Remarks

Example: let $X = \R$ and let $\mathcal{F}$ be the family of closed intervals $[a, b]$ with $a \le b$. The set $\set{0, 1}$ is shattered: the intersections $\emptyset$, $\set{0}$, $\set{1}$, $\set{0, 1}$ come from $[5, 6]$, $[0, 0]$, $[1, 1]$ and $[0, 1]$. No set $\set{p < q < r}$ is shattered, because an interval that contains $p$ and $r$ contains $q$. So the VC dimension is $2$.

Non-example: for the same family, the set $\set{0, 1, 2}$ is not shattered, since the pattern $\set{0, 2}$ fails the condition $A \cap S = \set{0, 2}$ for every interval $A$.

The family of all subsets of an infinite set has VC dimension $\infty$. The half-planes in $\R^2$ have VC dimension $3$.