prove that 2 collection have the same VC-dimensions

Question

I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand.

The question goes like this:

Suppose that $ F\subseteq\{0,1\}^\Omega $ is some collection of Boolean functions over $\Omega $.

Define $\Omega'=\Omega\times\{0,1\}$ and define $F'$ to be the collection of Boolean functions over $\Omega$ as follows:

for every $f\in F$, there is some $f'\in F'$ that maps $(x,y)\in\Omega'$ to $1[f(x)\neq y]$.
(Furthermore, $F'$ consists only of such $f'$; no other functions are allowed.)

Prove that the VC-dimensions of $F$ and $F'$ are equal.

What I was able to understand is that there is a collection of some functions $F$, and that all these functions with the addition of $0$ and $1$ are also in $F '$

I think $F '$is like $F$ only if an addition of $0$ and $1$ to the functions.

Can't figure out how to prove it.

Answer 1

Every $f \in F$ is mapped to $f' \in F'$ defined as follows: $f'|_{\Omega \times \{0\}} = f$ and $f'|_{\Omega \times \{1\}} = 1 - f$.

Let us call a subset of $\Omega'$ mixed if it contains both $(\omega,0)$ and $(\omega,1)$ for some $\omega \in \Omega$.

For $S' \subseteq \Omega'$, let $S'|_{\Omega} = \{ \omega \in \Omega : (\omega,0) \in S' \text{ or } (\omega,1) \in S' \}$.

For all $S \subseteq \Omega$, the set $S' = S \times \{0\}$ is not mixed and satisfies $S'|_{\Omega} = S$.

The proof is a combination of two simple observations:

1. $F'$ doesn't shatter any mixed set.
2. If $S'$ is not mixed then $F'$ shatters $S'$ iff $F$ shatters $S'|_{\Omega}$.