Exercise 4.8: Operations on VC Classes
(a)
A collection of points \(x_{1}^n = (x_1, \ldots, x_n)\) is shattered by \(\mathcal{S}\) if and only if for every labelling in \(\{ 0, 1 \}^n\), the complement labelling with ones and zeros swapped also belongs to \(\mathcal{S}(x_1^n)\). Hence \(\nu(\mathcal{S})=\nu(\mathcal{S}^c)\).
(b)
Notice that for any \(S \in \mathcal{S}\) and \(T \in \mathcal{T}\), \(\ind_{S \cap T} = \ind_S \ind_T\), which combined with Proposition 4.18 implies \begin{align} |(\mathcal{S} \sqcap \mathcal{T})(x_1^n) | \leq |\mathcal{S}(x_1^n)| |\mathcal{T}(x_1^n)| \leq (n + 1)^{\nu(\mathcal{S}) + \nu(\mathcal{T})} \, . \end{align}
(c)
This follows by \((S \cup T)^c = S^c \cap T^c\), and combination of (a) and (b).