, 2014

Let $\mathcal{F}$ be a finite family of finite sets and let $A$ be an arbitrary finite set. We say that $\mathcal{F}$ shatters the set $A$ if for every $X\subseteq A$ there is a set $F\in \mathcal{F}$ such that $A\cap F=X$. Show that $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets.
(5 pont)