Un Sperner tipo de problema en el infinito antichains

Question

Deje $\mathcal{A} \subset 2^{\mathbb{N}}$ ser un antichain (con respecto a la contención). Yo quiero medir el tamaño de $\mathcal{A}$ en la siguiente forma: I crear un conjunto, $S$, arrojando una moneda para cada número natural $x \in \mathbb{N}$, si los jefes me agregue$x$$S$, de lo contrario no. A continuación, la "medida" de $\mathcal{A}$ será la probabilidad de $S \in \mathcal{A}$.

Un amigo me dijo acerca de cilíndrico establece que parecen captura de esta noción. Tomar esas colecciones que consta de $k \in \mathbb{N}$ fijo de bits (elementos o nonelements) y definir su medida a $\frac{1}{2^k}$. Para un ejemplo de una colección tome $\mathcal{F} = \{A \subset \mathbb{N}: 3 \in A, 8 \in A, 11 \notin A\}$ aquí $\mu(\mathcal{F}) = 1/8$. Deje $\mu$ ser la medida generados a partir de estos conjuntos. Por desgracia, $\mu$ parece difícil de trabajar, y me he metido en ninguna parte.

Pregunta: Si $\mathcal{A}$ es un antichain en $2^{\mathbb{N}}$ medibles con respecto a $\mu$, no se sigue que la $\mu(\mathcal{A}) = 0$?

Antecedentes: La motivación está tratando de extender Sperner del Thoerem a un infinito valor. Otras infinitas versiones de Sperner del Teorema se han considerado, pero en otras estructuras de conjuntos.

Answer 1

Esta no es una respuesta, pero es definitivamente demasiado largo para el formato habitual. Como Thomas Andrews, comentó que la probabilidad es probablemente cero. Dado que este es un problema probabilístico, es probable que cuando $\mu({\cal A})=p>0$, en el caso de $S\subseteq T,S\in{\cal A},T\in{\cal A}$ no sólo ocurre, pero ocurre con probabilidad positiva. Es probable también que no es un uniforme obligado, es decir, hay un positivo $c(p)>0$ dependiendo únicamente de la $p$, que $P(S\subseteq T,S\in{\cal A},T\in{\cal A}) \geq c(p)$ siempre $\mu({\cal A})=p$ $S,T$ son independientes de las variables con valores en $2^{\mathbb N}$, distribuido como se indica en la OP.

Esta última afirmación es a su vez equivalente a la declaración sobre otros análogos $2^{\lbrace 1,2,\ldots,n \rbrace}$ grandes $n$ en lugar de $2^{\mathbb N}$, y después nos quedamos con un número finito de conteo problema.

Una de las pruebas de Sperner del teorema utiliza el bien conocido el hecho de que $U_n=2^{\lbrace 1,2,\ldots,n \rbrace}$ se puede dividir en $g_n=\binom{n}{\lfloor\frac{n}{2} \rfloor}$ cadenas. Considere la posibilidad de dicha partición, y para ${\cal A}\subseteq U_n$ con $|{\cal A}| \geq p|U_n|$, nos vamos a denotar por $d$ el número de cadenas de cuya intersección con $\cal A$ tiene un tamaño de al menos $2$. Entonces

$$ p2^n \leq | {\cal A}| \leq dn+(g_n-d) \etiqueta{1} $$

Podemos deducir

$$ P(S\subseteq T,S\in{\cal A},T\in{\cal A})\geq \frac{d}{2^{2n}} \geq \frac{p2^n-g_n}{(n-1)2^{2n}} \etiqueta{2} $$

Tenga en cuenta que el lado derecho es asintóticamente equivalente a $\frac{1}{n2^n}$ porque $g_n\sim \frac{2^n}{\sqrt{n}}$ por la fórmula de Stirling.Este es un crudo obligado que tiende a cero muy rápido, pero tal vez una más cuidado contar argumento a lo largo de esas líneas de trabajo.

Answer 2

$\def\ZZ{\mathbb{Z}}$Suponiendo que el axioma de elección y la hipótesis continua, esto es falso! Voy a "construir" un antichain con exterior de medida $1$.

La notación será conveniente trabajar con $\{ 0,1 \}^{\ZZ}$ en lugar de $\{ 0,1 \}^{\mathbb{N}}$; esto es isomorfo medir el espacio. Podemos abreviar $\{0,1 \}^{\ZZ}$$\Sigma$. Escribimos un elemento de $\Sigma$$(s_i)_{i \in \ZZ}$. Deje $\Sigma_0$ denotar los elementos de $\Sigma$ que $s_i$ toma valores infinitamente a menudo como $i \to \infty$. Para $A$ $B$ distintos subconjuntos finitos de $\ZZ$, escribimos $\Omega(A,B)$ para el subconjunto de $\Sigma$ donde$s_i = 0$$i \in A$$s_i = 1$$i \in B$. Por lo que el $\Omega(A,B)$ son una base de vecindades de $\Sigma$,$\mu(\Omega(A,B)) = 2^{-|A|-|B|}$. Escribimos $\Omega_0(A,B) = \Sigma_0 \cap \Omega(A,B)$. Escribimos $\tau$ para el mapa de $\Sigma \to \Sigma$$\tau(s)_i = s_{i+1}$.

La Fuerte Mezcla Lema Deje $U$ $V$ ser medibles pone en $\Sigma$. A continuación,$\lim_{n \to \infty} \mu(U \cap \tau^n V) = \mu(U) \mu(V)$.

Prueba de Esto es muy estándar ergodic theory. La primera fuente en internet he podido encontrar es la página 108 en el Descriptivo de la Teoría de conjuntos y Sistemas Dinámicos. $\square$

Clave lema Deje $K$ ser un conjunto cerrado en $\Sigma$ con medida positiva y vamos a $s^1$, $s^2$, ... ser una contables (o finito) subconjunto de $\Sigma_0$. A continuación, hay un elemento $t \in K \cap \Sigma_0$ que es incomparable con todos los $s^i$.

Prueba primero Nos reemplace $K$ por una más pequeña (pero todavía medida positiva) conjunto cerrado $L$, que está contenida en $\Sigma_0$. Definir $U$ para el conjunto de la $s$ $\Sigma$ donde $s_0=0$, al menos uno de $(s_1, s_2)$$1$, al menos uno de $(s_3,s_4, s_5)$$0$, al menos uno de $(s_6, s_7, s_8, s_9)$$1$, etcétera. Este es un punto de intersección de conjuntos cerrados, por lo $U$ es cerrado. Tenga en cuenta que$\mu(U) = \prod_{j \geq 1} (1-2^{-j}) > 0$, por lo que, por la fuerte mezcla de lema, $\mu(K \cap \tau^n U) > \mu(K) \mu(U)/2$ $n$ lo suficientemente grande. Tome $L = K \cap \tau^n U$. Como había prometido, $L$ es un conjunto cerrado, de medidas positivas, y que figuran en el $\Sigma_0$.

Desde $s^1$$\Sigma_0$, hay una infinidad de $n$'s para que $s^1_n=0$ y una infinidad de $m$'s para que $s^1_m=1$. Por lo tanto, por la fuerte mezcla de lema, podemos encontrar $n_1$, de modo que $s^1_{n_1}=0$$\mu(L \cap \Omega(\emptyset, \{ n_1 \})) > (1/3) \mu(L)$. Podemos repetir este truco para encontrar$m_1$, de modo que $s^1_{m_1} = 1$ y $\mu(L \cap \Omega(\emptyset, \{ n_1 \}) \cap \Omega(\{ m_1 \}, \emptyset)) > (1/3) \mu(L \cap \Omega(\emptyset, \{ n_1 \})$. La combinación de las dos desigualdades, $$\mu(L \cap \Omega(\{m_1 \}, \{ n_1 \})) > (1/9) \mu(L).$$ Ahora hemos garantizado que cualquier elemento de a $L \cap \Omega(\{m_1 \}, \{ n_1 \})$ es incomparable a $s^1$.

Set $L_1 = L \cap \Omega(\{m_1 \}, \{ n_1 \})$. Ahora nos introducirá, encontrando $(m_2, n_2)$, de modo que $\mu(L_1 \cap \Omega(\{m_2 \}, \{ n_2 \}) > (1/9) \mu(L_1)$ y cada elemento de a $L_2$ es incomparable con $s^2$. También, desde la $L_1 \supseteq L_2$, cada elemento de la $L_2$ es incomparable con $s^1$. En general, construimos $L \supseteq L_1 \supseteq L_2 \supseteq \cdots$ $\mu(L_k) > 9^{-k} \mu(L)$ y cada elemento de a $L_k$ es incomparable con $s^1$, $s^2$, ..., $s^k$.

Desde ese $L^k$ tiene medida positiva, son no vacíos. Desde $\Sigma$ es compacto, $\bigcap L_k$ es no vacío. Deje $t \in \bigcap L_k$. A continuación,$t \in L \subset \Sigma_0$, e $t \in L \subset K$, e $t$ es incomparable a todos $s^k$. $\square$

Lema $\Sigma$ tiene continuidad a los numerosos conjuntos.

La prueba Hay countably muchos conjuntos de la forma $\Omega(A,B)$, por lo que hay continuum muchas colecciones de conjuntos de la forma $\Omega(A,B)$. Cada conjunto abierto es la unión de una colección, por lo que hay en la mayoría de continuo abiertas pone en $\Sigma$. También, $\Sigma \setminus \{ x \}$ está abierto para cualquier $x \in \Sigma$, así que hay al menos continuo a los numerosos conjuntos en $\Sigma$. $\square$

Deje $\mathcal{K}$ ser la colección de subconjuntos cerrados de $\Sigma$ con medida positiva. Desde la complementación es una bijeciton entre subconjuntos cerrados y abiertos subconjuntos, el anterior lema muestra que $\mathcal{K}$ tiene la cardinalidad del continuo. Ahora, con NUESTROS SUPUESTOS de la TEORÍA de conjuntos, poner $\mathcal{K}$ en bijection con el primer uncouteable ordinal $\omega_1$. Para $a \in \omega_1$, escribimos $K_a$ para el positivo correspondiente área de conjunto cerrado.

Ahora usamos la inducción transfinita (y el Axioma de Elección) para encontrar los elementos de $t_a$$\Sigma$, para cada una de las $a \in \omega_1$, por lo que el $t_a \in K_a \cap \Sigma_0$ y cada una de las $t_a$ es incomparable a$t_b$$b < a$. La clave lema maneja el sucesor caso, y el límite del caso es inmediata. (Si no has visto la inducción transfinita antes, puedo escribir más, pero esto es mucho tiempo ya.)

Yo reclamo que $\mathcal{A} := \{ t_a \}_{a \in \omega_1}$ es mi deseado antichain. Es un antichain, desde cualquiera de los dos elementos son incomparables. Deje $U$ ser cualquier conjunto abierto de medida $<1$ y deje $K = \Sigma \setminus U$. A continuación,$\mu(K)>0$, lo $K$ es igual a algunos $K_a$. A continuación, $K \cap \mathcal{A}$ contiene $t_a$ y por lo tanto es no vacío, por lo $\mathcal{A} \not \subseteq U$. Hemos demostrado que $\mathcal{A}$ no está incluido en cualquier conjunto abierto de medir menos de $1$, por lo que la medida exterior de $A$$1$.