Why is the VC dimension different on intervals and half intervals?

Question

As I read this lecture for being familiar with VC dimension we find on p. 8:

VC(half intervals in $\mathbb{R}$ ) = 1 .... no subset of size 2 can be shattered

VC(intervals in $\mathbb{R}$ ) = 2 .... no subset of size 3

It's not clear to me. I read on Wikipedia about the difference of Half Interval and Interval and why VC dimension are different.

For example can this set be half intervals or intervals?

$$ \{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} \right. \} $$

Any direction or hint on this problem?

Answer 1

I assume a half interval $I_a$ is always of the form

$$ \{(-\infty \leq x \leq a) \mid a \in \mathbb{R}\} $$

This means that all points equal or smaller than $a$ belong to the interval. Now, choose any set $S = \{y,z\} \subset \mathbb{R}$ such that $y < z$. $S$ is not shattered, since it is impossible to find a half interval $I_a$ such that $S \cap I_a = \{z\}$ (if $z$ is included in the intersection, than $y$ has to be included as well).

When we consider intervals $I_{a,b} = \{(a \leq x \leq b \mid a,b \in \mathbb{R}\}$ in contrast to half intervals, we are able to find an interval $I_{a,b}$ such that $I_{a,b} \cap S = \{z\}$ (as well as for all other subsets of $S$). This makes the difference in the VC dimension.