# On an equivalent formulation of the Sauer–Shelah lemma.

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.

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.
• Thank you for yout answer! Yes $A \implies B$ is $\neg B \implies \neg A$ but when I apply this to the first statement I get that: if $F$ does not shatter a set of size $k$ (so the VC dimension must be less than $k$) then something but this does not match the premise in the second statement (the VC dimension is $k$). Commented Mar 3, 2018 at 18:29
• Yes, precisely. And Point $2$ starts the same: if the dimension is $k$, then in particular it is less than $k+1$, and the conclusion from this point of view is identical, using $k+1$ instead of $k$. Commented Mar 3, 2018 at 18:32
• Thank you, I am convinced I was thinking of $k$ as fixed between the two stamentes. Commented Mar 3, 2018 at 18:39
• You're welcome :) Commented Mar 3, 2018 at 18:40