VC dimension of left-sided intervals

Question

Consider the class of left-sided half intervals in $\mathbb{R}^d$: $$\mathcal{S}^d:=\{(-\infty,t_1]\times(-\infty,t_2]\times\dots\times(-\infty,t_d]|(t_1,\dots,t_d)\in\mathbb{R}^d\}.$$ My question is how to show that the VC dimension of $\mathcal{S}^d$ is $d$. It is easy to check that there exists $d$ points in $\mathbb{R}^d$ that can be shattered by $\mathcal{S}^d$ such that VC dim $\geq d$, but I don't know how to clarify the opposite. Thanks for your reading.

Answer 1

Consider an arbitrary collection of $d+1$ points $x_1,\ldots,x_{d+1}$ and consider for each $i$ $\displaystyle t_i:=\max_{1\leq j \leq d+1} (x_j)_i$. There are at most $d$ distinct points on the boundary of $(-\infty,t_1]\times \ldots\times (-\infty,t_d]$.

Label these points with $1$ and all the rest with $0$. It is not possible to find an element of $\mathcal S^d$ that produces this labelling.