¿Error en mi razonamiento sobre$\dim_{VC}(H)=1\Rightarrow|H|\leq 1$?

Question

Deje $S$ ser un conjunto con $n$ elementos.

Deje $P(S)=\{X\mid X\subseteq S\}$

Deje $H\subseteq\mathcal{P}(S)$ (hypergraph con el conjunto de borde $S$).

Deje $H_{|U}=\{U\cap A\mid A\in H\}$

Deje $\dim_{\text{VC}}(H)=1+\max\{|U|\mid U\subseteq S\text{ and }H_{|U}=\mathcal{P}(U)\}$

---

Tengo que demostrar que $\dim_{\text{VC}}(H)=1\Rightarrow|H|\leq 1$

Sin embargo, eso significaría que (a menos que sea una media del ejercicio) que exista $H$, de modo que $\dim_{\text{VC}}(H)=1$ $|H|=1$ (de lo contrario, ¿por qué '$\leq$' ?)

A partir de la definición de $\dim_{\text{VC}}(H)$ llegué a la conclusión de que $\dim_{\text{VC}}(H)=1$ significa que no existe ningún subconjunto $U$ $S$ verificación de $H_{|U}=\mathcal{P}(U)$.

Deje $H=\{\{a_1,a_2,...,a_m\}\},(a_1,...,a_m)\in S^m$; tenemos $|H|=1$. Ahora vamos a $U=\{a_1\}$,$\mathcal{P}(U)=\{\{a_1\}\}$. Bien, $H_{|U}=\{\{a_1\}\}=\mathcal{P}(U)$.

Por lo tanto hemos demostrado que $|H|= 1\Rightarrow\dim_{\text{VC}}(H)>1$. O he cometido un error en alguna parte ? Me parece extraño.

Answer 1

Considerar $S=\{\emptyset \}$. Por lo tanto $P(S)=\{\{\emptyset \}\}$. Elegimos$H=P(S)$, por lo que obviamente$H\subseteq P(S)$ confirma. Además,$|H|=1$ y cada$U\subseteq S$ que elijamos es el conjunto vacío, por lo tanto,$\dim_{\text{VC}}(H)=1$, y tenemos un caso donde$|H|=\dim_{\text{VC}}(H)=1$.

Usar esto un poco más cuidadosamente de lo que lo formulé y luego declarar que suponemos que$S$ es diferente del conjunto vacío, seguido de una prueba un poco más cuidadosa como la anterior, debería ser suficiente para demostrar lo que se necesita.