# How can I understand the proof of the VC dimension of half-spaces in d-dimensions?

Statement : A half space is set of all points on one side of a linear separator, i.e., a set of the form $$\{x \mid w^{T}x \ge t\}$$. The VC-dimension of half spaces in $$d$$-dimensions is at least $$d+1$$.

Proof Idea. There exists a set of size $$d+1$$ that can be shattered by half-spaces. Select the $$d$$ unit-coordinate vectors plus the origin to be the $$d+1$$ points. Suppose $$A$$ is any subset of these $$d+1$$ points. Without loss of generality assume that the origin is in $$A$$. Take $$0-1$$ vector $$w$$ which has $$1$$'s precisely in the coordinates corresponding to vectors not in $$A$$. Clearly $$A$$ lies in the half-space $$w^{T}x\le 0$$ and complement of $$A$$ lies in the complementary half-space.

The overall idea is to show that a set of size $$d+1$$ can be shattered. My understanding is that they are adding origin into the set of points. So the set size will be $$d+1$$ but I am not getting the last two lines:

Take $$0-1$$ vector $$w$$ which has $$1$$'s precisely in the coordinates corresponding to vectors not in $$A$$. Clearly $$A$$ lies in the half-space $$w^{T}x\le 0$$ and complement of $$A$$ lies in the complementary half-space.

Let us understand the proof by example.

Suppose $$d=3$$.
Select $$d+1=4$$ points, which are the 3 unit-coordinate vectors $$(1,0,0)$$, $$(0,1,0)$$, $$(0,0,1)$$ and the origin $$(0,0,0)$$.
Let $$C$$ be the set of these 4 points.

Suppose $$A$$ is any subset of these 4 points. There are two cases.

• The origin is not in $$A$$.
Let $$0{-}1$$ vector $$w$$ be the sum of all points (vectors) in $$A$$. For examples, if $$A$$ contains $$(1,0,0), (0,0,1)$$, then $$w=(1,0,0) + (0,0,1)=(1,0,1)$$.
Then $$A = C\cap \{x \mid w^{T}x \ge 1\}$$.

• The origin is in $$A$$.

Take $$0{-}1$$ vector $$w$$ which has $$1$$'s precisely in the coordinates corresponding to vectors not in $$A$$.

For example, if $$A=\{(1,0,0\}$$, then $$A$$ does not contain $$(0,1,0)$$ nor $$(0,0,1)$$.

• $$w$$ has $$1$$ at second coordinate since $$(0,1,0)$$ is not in $$A$$.
• $$w$$ has $$1$$ at third coordinate since $$(0,0,1)$$ is not in $$A$$.

So $$w=(0,1,1)$$. (This construction of $$w$$ is the same as letting $$w$$ be the sum of all points not in $$A$$.) Check that

Clearly $$A$$ lies in the half-space $$w^Tx\le0$$ and complement of $$A$$ lies in the complementary half-space.

Note that $$\{x\mid w^Tx\le0\}$$ is indeed of the form $$\{x \mid w^{T}x \ge t\}$$ since $$\{x\mid w^Tx\le0\}=\{x\mid (-w)^Tx\ge0\}$$.

Without loss of generality assume that the origin is in $$A$$.

This "without loss of generality" does not imply that author will adapt the case of the origin not in $$A$$ by "adding origin into" the subset $$A$$.

It means "let us deal with one of the cases. The other case is more or less similar." simply.