¿Qué versión del principio del encasillamiento es correcta? Una es mucho más fuerte que la otra

Question

Una versión del principio de Pigeonhole dice que si la cardinalidad de un conjunto $A$ es mayor que la de un conjunto $B$ entonces no puede haber una función unívoca que mapee desde $A$ a $B$ .

Otra versión dice: Si $n$ los elementos se dividen en $m$ subconjuntos, entonces al menos un subconjunto debe contener al menos $\lceil n/m \rceil$ elementos. Tenga en cuenta que el $\lceil \ \rceil$ que encierra el $n/m$ nos dice que redondeemos el valor hacia arriba.

Esta última versión es sólo una versión más potente, ¿no? Me parece extraño que una versión de un teorema pueda dar objetivamente más información que otra, así que es probable que, o bien la última versión no sea correcta, o bien yo esté equivocado al pensar que de alguna manera tiene más utilidad.

¿O es normal? ¿Es común que ciertas versiones de los teoremas tengan simplemente menos utilidad que otras versiones?

Answer 1

La primera versión también se aplica a los conjuntos infinitos. La segunda sólo se aplica a conjuntos finitos. ¿Cómo se puede decir que esta última es más potente? Se aplica a menos situaciones.

Es bastante común que se pueda extraer un poco más de información de una versión finita de un teorema. Pero esa información suele ser inútil cuando se aplica a la versión infinita. Por ejemplo, dado que la cardinalidad de los números reales es estrictamente mayor que la cardinalidad de los enteros, no hay inyección desde los reales a los enteros. Utilizando $|\mathbb{R}|$ y $|\mathbb{Z}|$ para representar las cardinalidades de los reales y los enteros, respectivamente, su segunda versión diría que hay $\lceil |\mathbb{R}|/|\mathbb{Z}| \rceil = |\mathbb{R}|$ reales enviados a al menos un entero. Aunque es cierto para este par de conjuntos infinitos, esto es bastante inútil (gracias, tomasz:) porque puede ser falso para otros pares de conjuntos infinitos.

Además, no es raro encontrar que hay una versión de un teorema fácil de demostrar y otra versión difícil de demostrar que es un poco más aguda. El Teorema de incrustación de Whitney tiene una serie de agudizaciones que son mucho más difíciles de probar.

Answer 2

Además de las dos buenas respuestas ya presentes, me gustaría mencionar que la segunda versión es también un corolario trivial de la primera: en efecto, si se toma $m$ subconjuntos disjuntos $A_1,\ldots,A_m$ de $A$ cada uno de ellos con menos de $\lceil n/m\rceil$ elementos, entonces la unión $\bigcup_{j=1}^m A_j$ tiene como máximo $m\lfloor n/m\rfloor<n$ elementos; por lo tanto, por el "simple" Principio de Colocación no puede haber una inyección $A\to\bigcup_{j=1}^m A_j$ .

Así que, para conjuntos finitos, ambas versiones se ven fácilmente como equivalentes. Como se ha dicho, la primera también se aplica a los conjuntos infinitos.

Answer 3

Esto es perfectamente normal. Si quieres, la primera versión es un corolario de la segunda (suponiendo que te interesen los conjuntos finitos). Tiene menos utilidad en el sentido de que es menos potente, pero más utilidad en el sentido de que se aplica más a menudo.

Answer 4

Qué versión es más útil depende de la situación. Hay muchas situaciones en las que todo lo que se necesita es un agujero con más de una paloma, y además de eso, el número de palomas en cada agujero no es importante.

Como nota adicional, para conjuntos infinitos, la naturaleza de los principios cambia. La definición de cardinalidad es clases de equivalencia definidas en términos de inyectividad, por lo que decir que si |A| > |B| entonces hay una función inyectiva es prácticamente una reformulación de la definición. Y para conjuntos infinitos, si |A| > |B|, entonces, en la medida en que |A|/|B| está definido, es igual a |A|. Por ejemplo, si se asigna a cada número entero un conjunto de números reales, y cada número real está en al menos uno de esos conjuntos, entonces al menos un conjunto tiene la misma cardinalidad que el conjunto de números reales.