A question about shattering of sets

101 Views Asked by At

For any $A \subseteq X$ and $\mathcal{C} \subseteq 2^X$, let $A \mathbin\Delta \mathcal{C} := \big\{A \mathbin\Delta C: C \in \mathcal{C} \big\} $. Then for any finite $F \subseteq X$, $\mathcal{C}$ shatters $F$ if and only if $A \mathbin\Delta \mathcal{C}$ does.

We say $\mathcal{C}$ ‎‎$\textbf{shatters}$‎ $F$ when $\mathcal{C}|^F = \big\{C \cap F : C \in \mathcal{C}\big\}$ equals to the set $2^F$.

I've tried set theoretic and also algebraic approaches, but none of them lead me to the complete answer. Would be grateful for any hints or solutions. If necessary I could share my partial solution.

1

There are 1 best solutions below

0
On BEST ANSWER

Assume $\mathcal C$ shatters the (not necessarily finite) set $F$, i.e., for every $E\subset F$ there exists $C\in\mathcal C$ with $C\cap F=E$. One direction of the claim is that $A\mathop\Delta \mathcal C$ shatters $F$. To prove it, let $E\subseteq F$ be any subset and $E'=(E\mathop\Delta A)\cap F$. We know that there exists $C\in\mathcal C$ with $C\cap F=E'$. Then $(C\mathop\Delta A)\cap F=E$ as desired.

As $A\mathop\Delta(A\mathop \Delta\mathcal C)=\mathcal C$, the reverse implication follows as well.

Note that finiteness of $F$ was not needed.