Q:

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$)

A:

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.

