# How do you prove that the following 2 hypothesis classes' VC-dimensions are equal?

Given a hypothesis class $$H=\{h:X\to\{0,1\}\}$$.

Let $$c\in H$$ be the correct predictor.

Denote $$H^c = \{c\Delta h:h\in H\}$$, where $$c\Delta h=(h\backslash c)\cup (c\backslash h)$$.

Please prove that VCdim($$H^c$$) = VCdim($$H$$)

If some $$A = (a_1,\dots,a_d\}\subset X$$ is shattered by $$H$$, then, for any vector $$b$$ = $$\{0,1\}^d$$,$$\exists$$ $$h \in H s.t. (h(a_1),\dots,h(a_d)) = b$$.

It suffices to prove that for any vector $$(h(a_1),\dots,h(a_d)) = b$$, $$\exists$$ $$h' \in H s.t. (c\Delta h'(a_1),\dots,c\Delta h'(a_d)) = (h(a_1),\dots,h(a_d))$$.

Proof of my claim:

$$\forall x_i \in A$$, if $$c(a_i) = 0$$,let $$h'(a_i) = h(a_i)$$, then $$c\Delta h' (a_i) = h(a_i)$$.

If $$c(a_i) = 1$$, let $$h'(a_i) = -h(a_i)$$, then $$c\Delta h'(a_i) = h(a_i)$$.

Then $$(c\Delta h'(a_1),\dots,c\Delta h'(a_d)) = (h(a_1),\dots,h(a_d))$$.

For the same reason, the inverse is also true.