Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered Today in the lecture the lecturer said something I found peculiar, and I felt very inconvenient when I heard it:
He claimed, that if the maximal VCdim of some hypothesis class is $n\in\mathbb N$, then it is possible that there is some $i&lt;n$ such that for every subset C of size i the subset C is not shattered.
Is his claim true? I thought that we can take some subset of size $i,\forall i\in [n]$of the set C* which satisfies the condition for the case where $|C|=n$, and they will shatter as well. Am I missing something?
I agree, the claim as written is incorrect.  If $C^*$ is shattered by $\mathcal{H}$, and $C\subseteq C^*$, then $C$ is also shattered by $\mathcal{H}$; to be possibly over-pedantic:
For each $B\subseteq C$, because then also $B\subseteq C^*$, we have that there is an $H\in\mathcal{H}$ such that $C^*\cap H=B$.  Note that this implies $B\subseteq H$.  Now, $C\subseteq C^*$ implies that $C\cap H\subseteq C^*\cap H$, so we have $C\cap H\subseteq B$.  And having both $B\subseteq C$ and $B\subseteq H$ implies that $B\subseteq C\cap H$.  So $B=C\cap H$.