On an equivalent formulation of the Sauer–Shelah lemma.

Question

Directly from the Wikipedia entry on the Sauer–Shelah lemma, let $\mathcal {F}=\{S_{1},S_{2},\dots \}$ be a family of sets.

The Wiki page states that the following two statements are equivalent:

• if $\mathcal {F}$ is a family of set with $n$ distinct elements such that $|\mathcal {F}| > \sum_{i=0}^{k-1} \binom{n}{i}$ then $\mathcal {F}$ shatters a set of size $k$.

• If the VC dimension of $\mathcal {F}$ is $k$, then $\mathcal {F}$ can consist of at most $\sum_{i=0}^k \binom{n}{i}$ sets.

Why are these two statements equivalent? It seems to me naively that the directions are opposite.

Answer 1

This is one statement and its contrapositive, hence they are logically equivalent.

The logic behind it is like saying that the following are equivalent:

Let $V$ be a real vector space and $k\in \Bbb N$.

• If you can find a linearly independent set of size $k$ in $V$ then $\dim V\geq k$
• If $\dim V\leq k$, then any linearly independent family in $V$ has at most $k$ elements.