# How to prove $\mathcal H$ with VC dimension $d$ shatter all subsets with size less than $d-1$?

I was wondering that if a certain hypothesis class $$H$$ has a VC dimension $$d$$ over domain $$X$$ how to prove that $$H$$ will shatter all subsets of $$X$$ with size less than $$d$$ i.e $$H$$ will shatter $$A \subset X$$ where $$|A| \leq d-1$$.

• What's the formal definition of the VC dimension? If the VC dimension of $H$ is $d$, does it mean that $H$ shatters all subsets of size $d$ or at least one subset of size $d$? – nbro Mar 28 at 22:06
• @nbro at least one subset of size $d$ and no subset of size $d+1$ – DuttaA Mar 28 at 22:09
• You said that "if a certain hypothesis class $H$ has a VC dimension d over domain $X$". So, it doesn't mean that $X$ is shattered by $H$. Right? In other words, You say $X$‌ as a domain, not as a set that is shattered by $H$. Right? – OmG Mar 29 at 0:17
• @OmG yes. Probably should have added $|X| > d$. – DuttaA Mar 29 at 0:24

We can show that it is not true by a counterexample. For example, $$X = \{1,2,3\}$$ and $$\mathcal H = \{\{\},\{1\},\{2\},\{1,2\}\}$$ is the finite set hypothesis class. By the definition, $$\mathcal V \mathcal C$$ dimension of $$\mathcal H$$ over domain $$X$$ is $$d=2$$. Although, $$A = \{3\} \subset X$$, whose size is smaller than the $$\mathcal V \mathcal C$$ dimenion i.e $$|A| it is not shattered by $$\mathcal H$$.