Exercise 4.12: VC Dimension of Left-Sided Intervals
The standard basis can clearly be shattered, hence \(\nu(\mathcal{S}_\text{left}^d) \geq d\). On the other hand, consider any collection of \(d + 1\) distinct points. Take \(M_j = \max_{i \in [d + 1]} x_{i j}\) (maximum over the \(j^\text{th}\) coordinate among the \(d+1\) points), and consider the following two cases: (i) there is a point \(x_i\) such that \(x_{ij} < M_j\) for all \(j \in [d]\), and (ii) there is no such point.
If (i) is the case, the point \(x_i\) can never be the only one with zero label. If (ii) is the case, there must be at least two points \(x_{i} \neq x_{i'}\) such that \(x_{ij} = x_{i'j}\) for some \(j\). Then for at least one of these points, the labelling which assigns the \(+1\) label to all but this point is not realisable by any set in \(\mathcal{S}_\text{left}^d\). Combined with the above lower bound, we thus have \(\nu(\mathcal{S}_\text{left}^d) = d\).
The bound \(|\mathcal{S}_\text{left}^d (x_1^n)| \leq (n + 1)^d\) then follows by Proposition 4.18 (Vapnik–Chervonenkis, Sauer and Shelah).