Sobre una formulación equivalente del lema de Sauer-Shelah.

Question

Directamente de la entrada de Wikipedia sobre el El lema de Sauer-Shelah , dejemos que $\mathcal {F}=\{S_{1},S_{2},\dots \}$ sea una familia de conjuntos.

La página Wiki afirma que las dos afirmaciones siguientes son equivalentes:

• si $\mathcal {F}$ es una familia de conjuntos con $n$ elementos distintos, de manera que $|\mathcal {F}| > \sum_{i=0}^{k-1} \binom{n}{i}$ puis $\mathcal {F}$ rompe un conjunto de tamaño $k$ .

• Si la dimensión VC de $\mathcal {F}$ est $k$ entonces $\mathcal {F}$ puede consistir en un máximo de $\sum_{i=0}^k \binom{n}{i}$ conjuntos.

¿Por qué son equivalentes estas dos afirmaciones? Me parece, ingenuamente, que las direcciones son opuestas.

Answer 1

Se trata de una afirmación y su contrapositivo, por lo que son lógicamente equivalentes.

La lógica detrás de esto es como decir que lo siguiente es equivalente:

Dejemos que $V$ sea un espacio vectorial real y $k\in \Bbb N$ .

• Si se puede encontrar un conjunto linealmente independiente de tamaño $k$ en $V$ puis $\dim V\geq k$
• Si $\dim V\leq k$ entonces cualquier familia linealmente independiente en $V$ tiene como máximo $k$ elementos.