nLab Teorema de Cantor's
Resumen
Georg Cantor probó muchos teoremas, pero el generalmente llamado teorema de Cantor es el primer teorema no trivial de la nueva teoría de conjuntos de Cantor: que algunos infinitos son más grandes que otros; en particular, cualquier número cardinal infinito (o conjunto infinito) genera uno más grande tomando el conjunto de potencias.
(El teorema se aplica a todos los conjuntos, no solo a los infinitos, aunque es bastante obvio para los conjuntos finitos.)
El teorema de Cantor no debe confundirse con el teorema de Bernstein de Cantor (ver número cardinal), que es diferente (pero relacionado, ya que es importante justificar la interpretación de Cantor de su teorema).
Historia
Antes de Cantor, la gente tendía a pensar en el infinito (creyera en él o no) como un concepto absoluto: todos los infinitos son equivalentes. Se había notado (por Galileo, por ejemplo) que es posible dar a un conjunto infinito una autoinyección que no es una sobreinyección; por ejemplo, la inclusión de los enteros pares en los enteros duplicando. Así, aquí hay dos infinitos-el infinito EE de enteros pares y el infinito NN de todos los enteros-que son realmente equivalentes, aunque a primera vista parecería que EE es más pequeño.
Cantor mostró que tal equivalencia falla con los números reales RR: ningún mapa de NN a RR puede ser sobreyectivo (por lo que RR es incontable). Su primer argumento fue ad hoc, pero luego lo generalizó con el argumento diagonal para mostrar que ningún mapa de cualquier conjunto SS a su conjunto de potencia ð ‘” S \ mathcal{P}S podría ser sobreyectivo. (Esto cubría la incontabilidad de RR, ya que Cantor encontró una biyección entre RR y ð ‘” N \ mathcal{P}N, que ahora podemos considerar como una instancia del Teorema de Bernstein de CantorâSchröderâ. Como hay un mapa inyectivo obvio (el mapa de un solo elemento) de SS a ð”S\mathcal{P}S, Cantor concluyó que la cardinalidad de uno es estrictamente menor que la cardinalidad del otro.
El argumento de Cantor, como toda su teoría de conjuntos, fue controvertido en ese momento. Aquellos que, como Kronecker, creían que todas las matemáticas debían ser matemáticas finitas, las consideraban sin sentido. Incluso los constructivistas tempranos más moderados, como Brouwer y Weyl, encontraron que tenía poco sentido. (En particular, no dice nada directamente sobre RR, ya que la biyección entre RR y ð”N\mathcal{P}N no es constructivamente válida, aunque la prueba original de Cantor de que RR es incontable se puede hacer que funcione.)
Sin embargo, las versiones del teorema que se indican a continuación son constructivamente válidas, y el teorema es incluso predicativamente válido (siempre que uno tenga conjuntos de funciones); los constructivistas modernos generalmente los aceptan como teoremas. (La interpretación, sin embargo, no es tan clara. De hecho, son teoremas en el lenguaje interno de cualquier topos (y el teorema es un teorema en cualquier Î \Pi-pretopos).
Declaraciones y pruebas
Teorema
(versión de Lawvere.)
Dados los conjuntos SS y VV, supongamos que hay una sobreyección de SS al conjunto de funciones SâVS \a V (también escrito V SV^S). Entonces cada mapa n: VâVn\dos puntos V \a V tiene un punto fijo; es decir, n(x)=xn (x) = x para algunos x:Vx\colon V.
(Esto se generaliza al teorema del punto fijo de Lawvere.)
Prueba
sea f:Sâ(SâV)f\colon S \a (S \V) ser cualquier función, y considere la función g:SâVg\colon S \a V dada por
Es decir, si se usa el curtido para interpretar ff como una función de SÃSS \times S a VV, entonces gg se define utilizando el mapa diagonal Î “S\Delta_S como
Ahora supongamos que ff es sobreyectivo. A continuación, debe haber algún elemento a:Sa\colon S tal que f(a)=gf(a) = g. Pero, a continuación,
por lo que g(a)g(a) es un punto fijo de nn.
La presencia del mapa diagonal Î ” S\Delta_S aquí explica por qué esta prueba se llama argumento diagonal. (Esta explicación es anacrónica pero moralmente correcta. La prueba de Lawvereâ € ™ también explica(de hecho generaliza) el combinador de punto fijo o YYâ en el cálculo lambda sin tipo, donde Y(n)Y (n) es un punto fijo para cualquier término nn.
Se deduce de inmediato (incluso de forma constructiva) que si VV tiene un mapeo automático sin punto fijo, entonces ningún mapa de SS a SâVS \to V puede ser una suposición. De hecho, tenemos algo ligeramente más fuerte que (pero clásicamente equivalente a) el fracaso de ff para ser una sobreyección: en realidad existe un elemento gg de SâVS \to V que no es igual a ningún valor en el rango de ff. (Si VV tiene una relación de separación, entonces puede obtener un resultado aún más fuerte para una hipótesis correspondientemente más fuerte en nn, pero eso no se aplica a las versiones a continuación.)
Teorema
(versión de Cantor.)
Dado un conjunto SS, no hay sobrejección de SS al conjunto de potencia ð ‘” S \ mathcal{P}S.
Proof
Deje que VV sea el conjunto de valores de verdad, y deje que n:Vâ ‘ Vn\colon V \ to V sea negación. Dado que nn no tiene punto fijo, aplique el teorema .
Tenga en cuenta que aunque la negación no tiene todas sus propiedades habituales en matemáticas constructivas, p=Âpp = \neg{p} sigue siendo imposible.
La siguiente versión es clásicamente equivalente a la versión anterior (al menos si comprueba que ð”S\mathcal{P}S está habitada), pero no es constructivamente equivalente. (De hecho, a diferencia del teorema , aparentemente no tiene un análogo constructivo cuando ð”S\mathcal{P}S es reemplazado por V SV^S.) Este argumento es de la Proposición 2.8.8 de los Fundamentos Prácticos de Taylor (aunque no se si realmente se originó allí).
Teorema
(versión de Taylor.)
Dado un conjunto de SS, no hay inyección de ð ‘” S\mathcal{P}S a SS.
Prueba
Let i: ð ‘” SâSi \ colon \ mathcal{P}S \ to S sea cualquier función. Defina f: Sâ ‘ð ‘” Sf \ colon S \to \ mathcal{P}S de la siguiente manera:
Si ii es una inyección, entonces ff es una retracción de ii y, por lo tanto, una sobreyección, que es imposible por teorema .
Por supuesto, Cantor también probó el teorema, pero su prueba no fue constructiva.
Podemos combinar teoremas y en la siguiente declaración aún más general, tomada de D4.1. 8 del Elefante de Johnstone.
Teorema
(versión de Johnstone.)
Dado un conjunto SS, su conjunto de potencia ð ‘” S \ mathcal{P}S no puede expresarse como un subcotiente de SS.
Prueba
Supongamos que tenemos un conjunto BB, una inyección i:Bâªsi\colon B \hookrightarrow S y una inyección f:Bâð”Sf\colon B \to \mathcal{P}S. Entonces la función de imagen previa i *:ðSâð”Bi^*\colon\mathcal{P}S \to \mathcal{P}B sería una inyección (porque i *⃠i=1 ð”Bi^\ast \exists_i = 1_{\mathcal{P}B}), al igual que la función de imagen:ð”Bâð”ð”S\exists_f\colon \mathcal{P}B \a \mathcal{P}\mathcal{P}S (porque ∃ ff *=1 ð”ð”S\exists_f f^\ast = 1_{\mathcal{P}\mathcal{P}S}). Por lo tanto, su compuesto sería una suposición ð”Sâð”ð”S\mathcal{P}S \to \mathcal{P}\mathcal{P}S, que es imposible por teorema .
Interpretación
Tenga en cuenta que existe una inyección de SS a ð”S\mathcal{P}S, dada por el mapa singleton. Así que en la aritmética de números cardinales, tenemos
Pero como no hay tal sobreyección, ciertamente no hay biyección, y tenemos
Así que concluimos que
Es decir, cada conjunto es estrictamente más pequeño en cardinalidad que su conjunto de potencia.
Esta interpretación se basa en una buena relación entre â¤\leq y == en la clase de números cardinales; en particular, el teorema de Bernstein de CantorâSchroederâque â¤\leq es antisimétrico. En matemáticas constructivas, esta relación es deficiente, y es muy posible que dos conjuntos sean estrictamente más pequeños que los demás en el sentido anterior. Gracias al teorema, esto no es posible para un conjunto y su conjunto de potencia, pero sí significa que la interpretación de <\lt como tamaño relativo es problemática-de hecho, casi tan problemática como la idea de que hay menos enteros pares que enteros!
Paul Taylor ha argumentado que el valor esencial del Teorema de Cantor es el lema, implícito en la prueba de Cantor, que Bill Lawvere aisló como teorema . Como la interpretación principal del Teorema es significativa solo en un contexto teórico de conjuntos específico (en particular, uno en el que se sostiene el teorema de Bernstein del Cantor Schroeder), puede que no sobreviva a una “revolución” que derroque la primacía de ese contexto. Pero el lema de Lawvere sobrevivirá, ya que âhace el trabajoâ € mientras que el teorema de Cantor âse lleva el credito. (Vea Taylor 2009 a continuación para una discusión más detallada de âLemas que hacen el trabajo y Teoremas que toman el credito.)
En posets
Se puede formular un teorema análogo al teorema de Cantor para conjuntos para otras categorías cerradas cartesianas. En particular, se puede preguntar si es posible tener una sobreyección Xâ2 XX \a 2^X entre posets, donde la base 22 no es el poset discreto{0,1}\{0, 1\} sino más bien el orden {0â¤1}\{0 \leq 1\}.
La respuesta es que no existe tal suposición f:Xâ2 Xf: X \to 2^X, pero esto no se deriva de una simple aplicación del teorema de punto fijo de Lawvere, donde se intenta descartar tal ff invocando la existencia de un mapa 2â22 \to 2 que no tiene punto fijo (¡no existe tal mapa poset 2â22 \to 2!). Tampoco podemos apelar a algún argumento crudo de cardinalidad; por ejemplo, si XX es el ordinal Ï\omega, entonces 2 X2^X es el orden ⚥âšÏ op\bot \sqcup \omega^{op} (une libremente un elemento inferior ⚥\bot a Ï op\omega^{op}), que tiene la misma cardinalidad. Así que hay que buscar otra prueba.
Probar que no hay sobrejección Xâ ‘ 2 XX \to 2^X es un ejercicio divertido. Una línea de ataque (que se internaliza a cualquier topos) se puede encontrar aquí.
- Teorema de punto fijo de Lawvere
