I am studying the VC-dimension of half spaces. There is a theorem in my book stating that, if $\mathcal H$ is the family of half spaces in $\mathbb R^d$, then VC-$dim(\mathcal H)=d+1.$
And the proof said that any $d+1$ affinely independent points can be shattered by $\mathcal H$.
I cannot see why this is true, can anyone please help me understand it?
It is not true that any $d+1$ points can be shattered (this is not the case if, for example, they lie on a line). But the points $(0,0,\dots 0), (1,0,0,\dots,0), (0,1,0,0,\dots,0),\,$ etc. can be shattered.You can see this easily on the plane or in the tree-dimensional affine space.
In general, it is easy to see that you can shatter the $d$ points $(1,0,0,\dots,0), (0,1,0,0,\dots,0),\,$ etc. using the class of homogeneous half-spaces. Namely, if you want the labels $(y_1,y_2,\dots y_n)$ just take the half-space $\langle w,x\rangle\ge 0$ where $w=(y_1,y_2,\dots y_n)$.
You can now shatter all the previous points plus the origin by choosing the non-homogeneous half-space $\langle w,x\rangle +b\ge 0$ with some small $b$ which you choose to be positive if you want the origin to be positively labeled and negative otherwise. You can always choose a non-zero $b$ like that by continuity (observe that your original half-space is strictly positive on positively-labeled points and strictly negative on negatively-labeled points and you have finitely many points so you can perturb the half-space without changing the sign at those points).
So you have some $d+1$ points shattered by the class. The VC dimension is $d+1$ because you cannot shatter $d+2$ (you can use Radon's theorem or any other argument involving affine dependence).