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.


1 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.
  • $\begingroup$ 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$). $\endgroup$
    – Monolite
    Commented Mar 3, 2018 at 18:29
  • $\begingroup$ 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$. $\endgroup$ Commented Mar 3, 2018 at 18:32
  • $\begingroup$ Thank you, I am convinced I was thinking of $k$ as fixed between the two stamentes. $\endgroup$
    – Monolite
    Commented Mar 3, 2018 at 18:39
  • $\begingroup$ You're welcome :) $\endgroup$ Commented Mar 3, 2018 at 18:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .