Principio del casillero para caso infinito

Question

Supongamos que $X_n$ son conjuntos finitos para cualquier entero natural $n$. que $Y$ sea un subconjunto infinito de $\prod_n X_n$. ¿Existen $y$ y $y'$ $Y$ y un subconjunto infinito $S$ $\mathbb N$ tal que $y_n=y'_n$ % todo $n$$S$?

Answer 1

Creo que lo que usted pide es imposible. Dado cualquier elemento de $\prod_n X_n$ el elemento está determinada únicamente por su imagen en cada uno de los $X_n$'s. Así que si dos elementos de $Y$ está de acuerdo en cada una de las $X_n$, que debe ser el mismo elemento.

En un lenguaje similar a la suya, lo que probablemente quiera para el caso finito es "Si $X$ $Y$ son finitos conjuntos tales que a $|X| < |Y|$ $f:Y\rightarrow X$ es cualquier mapa, entonces existe un elemento $x\in X$ tal que $|f^{-1}(x)| > x$." Más en general, dado cualquier secuencia finita $X_1,\ldots,X_n$ finito de conjuntos y cualquier conjunto $Y$ tal que $|Y| > |X_1|\cdot|X_2|\cdots|X_n|$ y cualquier secuencia de mapas de $f_i:Y\rightarrow X_i$ entonces existe una secuencia de elementos $x_1,\ldots,x_n$ y dos elementos de $y,y'\in Y$ tal que $f_i(y) = f_i(y')$ cualquier $i$.

El problema con el infinito, el caso es que hay inyectiva pero no surjective mapas entre los conjuntos infinitos con la misma cardinalidad. Sin embargo, es cierto que, dada una secuencia finita de conjuntos de $X_1,X_2,\ldots$ y un conjunto $Y$ con cardinalidad mayor que la de $\prod X_n$, si usted tiene cualquier secuencia de mapas de $f_i:Y\rightarrow X_i$ entonces existe un incontable subconjunto $Z\subseteq Y$ tal que para cualquier par de elementos de a $z,z'$ $Z$ $f_i(z) = f_i(z')$ todos los $i$.

Aún más a la generalidad, creo que si usted tiene cualquier conjunto de conjuntos de $\{X_\alpha\}$ y cualquier conjunto $Y$ de manera tal que la cardinalidad de a $Y$ es mayor que la cardinalidad de a$\prod_\alpha X_\alpha$, entonces usted tiene una declaración similar.

Answer 2

¿$X_n=\left\lbrace 1,2,3,...,n\right\rbrace$ Y $Y$ que consta de la secuencias $\left(1,1,1,...,1,2,3,4,5,6,...\right)$ $n$ los todos $n\in\mathbb N$?

Cierto lo primero que viene a mi mente cuando escucho "Principio del casillero para caso infinito" son algunos teoremas en teoría de Ramsey infinito, como este.

Answer 3

En primer lugar, permítanme mejorar los contables contraejemplo de Darij Grinberg, dando un incontable contraejemplo Y. De hecho, yo voy a dar finito de conjuntos X_n y un subconjunto S de que el producto ΠX_n que tiene un tamaño continuo (es decir, tan grande como sea posible), de tal manera que las dos distintas y, y' Y en tiene sólo un número finito de valores comunes.

Sea X_n tiene 2ⁿ elementos, consistente en de las secuencias binarias de longitud n. Ahora, para cada uno de los infinitos secuencia binaria s, vamos a y_s se secuencia en el producto ΠX_n cuyo n^th valor es s|n, la longitud n del segmento inicial de s. Sea Y consisten en todos estos y_s. Ya que hay un continuum muchos s, de ello se sigue que Y tiene el tamaño de continuo.

Tenga en cuenta que si s y t son distintas secuencias binarias, luego con el tiempo los segmentos inicial de s y t están en desacuerdo. Así, a la larga, los valores de y_s e y_tson diferentes. Por lo tanto, y_s e y_t sólo tienen un número finito de valores comunes. De modo que Y es muy grande contraejemplo, como deseado.

Un argumento similar funciona aún si la X_ncrecer más lentamente de tamaño, mientras liminf|X_n| = infinito. Uno simplemente se propaga la construcción un poco además, hasta que el tamaño de la X_i es grande suficiente para dar cabida a la misma idea. Es decir, si el liminf de los tamaños de la X_n's es infinito, entonces uno puede hacer un contraejemplo conjunto Y de tamaño continuo.

En contraste, en el otro caso, no hay infinito contraejemplos. Me dicen que si infinitamente muchos X_n tienen un tamaño en la mayoría de los k y y es un subconjunto de ΠX_n tener k+1 muchos elementos, entonces los hay de distintos y,y' en Y tener infinidad de común valores. Para ver esto, suponga que Y tiene la propiedad de que distintas y, y' en Y tiene sólo un número finito de valores comunes. En este caso, cualquiera de los dos y, y' el tiempo debe tener diferentes valores. Así que si S tiene k+1 muchos elementos, a continuación, finalmente, para la lo suficientemente grande n, estos k+1 muchas secuencias en Y debe ser adoptando diferentes valores en cada X_n. Pero desde unboundedly a menudo sólo hay k posibles valores en X_n, esto es imposible.

En resumen, la situación es la siguiente:

Teorema. Supongamos que X_n es finito y no vacío.

• Si liminf |X_n| es infinito, entonces no es Y subconjunto ΠX_n de tamaño continuo, de tal manera que distintas y, y' en Y tiene sólo un número finito de valores en común.
• De lo contrario, infinitamente muchos X_n tienen un tamaño en la mayoría de los k para algún k, y en este caso, cada subconjunto Y ΠX_n de tamaño k+1 tiene distintas y,y' en Y con infinitamente muchos valores en común.

En particular, si X_n vuelto cada vez más de gran tamaño, entonces hay muy mala contraejemplos a la pregunta, y si la X_n son infinitamente a menudo limitado en tamaño, entonces existe una muy fuerte respuesta positiva a la la pregunta.