---
tag: 14HX3QF45H
kind: definition
name: VC dimension
msc: [05D05, 68Q32]
defines: KCFXR9K3GD
uses: [0C21Q694AG, 00E0YZCERH, 0HBRW4E6G1]
sources:
  - url: https://en.wikipedia.org/wiki/Vapnik–Chervonenkis_dimension
---

## Definition

Let $X$ be a set and let $\mathcal{F}$ be a [[family|0C21Q694AG]] of subsets of $X$.
A finite set $S \subseteq X$ is *shattered* by $\mathcal{F}$ if the set of [[intersections|0HBRW4E6G1]] $\set{A \cap S : A \in \mathcal{F}}$ is the whole [[power set|00E0YZCERH]] of $S$.
The *VC dimension* of $\mathcal{F}$ is the supremum of $|S|$ over all finite sets $S \subseteq X$ shattered by $\mathcal{F}$.
If $\mathcal{F}$ is nonempty, the empty set is shattered, so the VC dimension is a nonnegative integer or $\infty$.

## 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$.