# prove that 2 collection have the same VC-dimensions

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.

• It's hard to understand a question if you don't understand the symbols used in it. Given that this is the trouble you're having, you should have asked for clarifications on the problem statement rather than for a proof. I suggest asking a new question with your actual doubts. Oct 23, 2021 at 15:29
• – D.W.
Oct 26, 2021 at 3:32
• cs.stackexchange.com/q/145044/755
– D.W.
Oct 26, 2021 at 3:35

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}$$.
• Thanks for the help, can you please explain to me this part: $f'|_{\Omega \times \{1\}} = 1 - f$ It is not clear to me how you got this connection between the 2 collections
– hah
Oct 20, 2021 at 18:57
• This is not supposed to be a complete answer. You'll have to flesh it out. Oct 20, 2021 at 19:02