VC dimension of complement

Question

Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\{X\setminus c\mid c\in C\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$.

Proof:

Let $d:=VC_{dim}(C)$, then there exists $S\subseteq X$, $|S|=d$, s.t. $S$ is shattered by $C$.

Let $d':=VC_{dim}(\bar{C})$, then there exists $S'\subseteq X$, $|S'|=d'$, s.t. $S'$ is shattered by $C$.

Show that $d\leq d'$ and $d' \leq d$. I know that a set $S$ is shattered by $C$ iff $\Pi_C(S):=\{c\cap S\mid c\in C\}=2^S$, but I have no clue how to show the two sides. Can someone help me with that?

Answer 1

First, observe that it is enough to prove that $d\le d'$. Then, the converse inequality follows from the fact that $\overline{\overline{C}}=C$, and by applying the initial argument to $\overline{C}$.

To prove the claim, we actually prove something stronger: we prove that if $C$ shatters $S$, then $\overline{C}$ also shatters $S$.

Let $S$ be a set that is shattered by $C$, and consider $\Pi_{\overline{C}}(S)$. Let $T\subseteq S$, then there exists $c\in C$ such that $c\cap S=S\setminus T$ (since every subset of $S$ can be reached this way). Let $c'=X\setminus c\in \overline{C}$, then $c'\cup c=X$. Thus, $c'\cap S=T$. Therefore, $\Pi_{C}(S)\subseteq\Pi_{\overline{C}}(S)$. Applying the same argument to $\overline{C}$, we get $\Pi_{\overline{C}}(S)\subseteq \Pi_{\overline{\overline{C}}}(S)=\Pi_{C}(S)$, and thus we have the equality we wanted, and we conclude the claim.