Let \((X, \mathcal{S})\) be a set system, where \(\mathcal{S} \subseteq 2^X\). The primal shatter function \(\pi_{\mathcal{S}} \colon \mathbb{N} \to \mathbb{N}\) is defined by \[\pi_{\mathcal{S}}(m) = \max_{Y \subseteq X,\; |Y| = m} |\mathcal{S}|_Y|,\] where \(\mathcal{S}|_Y = \{ S \cap Y : S \in \mathcal{S} \}\) is the trace of \(\mathcal{S}\) on \(Y\).

Let \((X, \mathcal{S})\) be a set system. A subset \(A \subseteq X\) is shattered by \(\mathcal{S}\) if \(\mathcal{S}|_A = 2^A\), that is, every subset of \(A\) is of the form \(S \cap A\) for some \(S \in \mathcal{S}\).

The VC-dimension of \(\mathcal{S}\), denoted \(\dim(\mathcal{S})\), is the supremum of the sizes of all finite shattered subsets of \(X\). Equivalently, \[\dim(\mathcal{S}) = \sup\{ m : \pi_{\mathcal{S}}(m) = 2^m \}.\]

Let \((X, \mathcal{S})\) be a set system and \(\mu\) a probability measure on \(X\). A subset \(N \subseteq X\) is an \(\varepsilon\)-net for \((X, \mathcal{S})\) with respect to \(\mu\) if \(N \cap S \ne \emptyset\) for every \(S \in \mathcal{S}\) with \(\mu(S) \ge \varepsilon\).

When \(X\) is finite and \(\mu\) is the counting measure (\(\mu(A) = |A|/|X|\)), this says that \(N\) intersects every set \(S \in \mathcal{S}\) with \(|S| \ge \varepsilon |X|\).

Let \((X, \mathcal{S})\) be a set system. The dual shatter function \(\pi_{\mathcal{S}}^* \colon \mathbb{N} \to \mathbb{N}\) is defined by \[\pi_{\mathcal{S}}^*(m) = \max_{\mathcal{Y} \subseteq \mathcal{S},\; |\mathcal{Y}| = m} \bigl|\bigl\{ \{S \in \mathcal{Y} : x \in S\} : x \in X \bigr\}\bigr|.\] Equivalently, \(\pi_{\mathcal{S}}^*(m)\) is the maximum number of nonempty cells in the Venn diagram of \(m\) sets chosen from \(\mathcal{S}\).