Exercise 4.17: Infinite VC Dimension
Consider the sets \(I_n = \set{t \in [0, 1] : \sin(2 \pi t / 2^{2-n}) \ge 0}\) for \(n \ge 1\) and \(I_0 = \varnothing\): \begin{equation} I_0 = \varnothing, \quad I_1 = [0, 1], \quad I_2 = [0, \tfrac 12], \quad I_3 = [0, \tfrac 14] \cup [\tfrac12,\tfrac34], \quad \ldots. \end{equation} For \(k\) points, assign to every \((I_i)_{i=0}^{2^k}\) a subset of the \(k\) points. Then, by “tracing through the intervals”, every point is uniquely assigned to an interval in the partition of \([0, 1]\) determined by \(I_{2^k}\). With these assignments, the function class shatters some \(k\) points for all \(k \in \N\), so the VC dimension is infinite.