Sets shattered by $\mathcal{F}=\{\emptyset, \{2\},\{3\},\{1,2\},\{1,2,3\}\}$

62 Views Asked by At

I have worked through this problem and determined that the $\mathcal{F}$ listed in the title is shattering-extremal and shatters the following sets: $\emptyset, \{2\},\{3\},\{2,3\},\{1,3\}$.

Now I was fairly confident that I had correctly found the collection of shattered sets, however it misaligns with a supposedly true necessary and sufficient condition. I'm hoping that someone can verify that I have correctly identified all the sets shattered by $\mathcal{F}$. I know there can't be more than 5 by the Sauer inequality, however maybe I mixed one up. A second pair of eyes would be very useful here!

1

There are 1 best solutions below

2
On BEST ANSWER

The Sauer inequality says that $\mathscr{F}$ cannot shatter fewer than $5$ sets. If I’m not mistaken, it shatters six and so is not extremal: in addition to the five that you named, it shatters $\{1\}$: $\varnothing=\{1\}\cap\varnothing$, and $\{1\}=\{1\}\cap\{1,2\}$, for instance.