Teorema de cantor

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Cada conjunto es más pequeño que su sistema de potencia

En la teoría del conjunto matemático, Teorema de Cantor es un resultado fundamental que declara que, para cualquier conjunto $A$ , el conjunto de todos los subconjuntos de $A,$ el conjunto de poder $A,$ tiene una cardenalidad estrictamente mayor que $A$ en sí mismo.

Para conjuntos finitos, el teorema de Cantor se puede ver verdadero por la simple enumeración del número de subconjuntos. Contando el conjunto vacío como subconjunto, un conjunto con $n$ elementos tiene un total $2^{n}$ subconjuntos, y el teorema sostiene porque $n}" xmlns="http://www.w3.org/1998/Math/MathML">2n■n{displaystyle 2^{n} {fn}]n}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/95fc6e12d2c5c88bc132626b0e154ae5b0f8e69f" style="vertical-align: -0.338ex; width:6.874ex; height:2.343ex;"/>$ para todos los enteros no negativos.

Mucho más significativo es el descubrimiento de Cantor de un argumento que es aplicable a cualquier conjunto y muestra que el teorema también se cumple para conjuntos infinitos. En consecuencia, la cardinalidad de los números reales, que es la misma que la del conjunto potencia de los enteros, es estrictamente mayor que la cardinalidad de los enteros; ver Cardinalidad del continuo para más detalles.

El teorema lleva el nombre del matemático alemán Georg Cantor, quien lo planteó y demostró por primera vez a finales del siglo XIX. El teorema de Cantor tuvo consecuencias inmediatas e importantes para la filosofía de las matemáticas. Por ejemplo, al tomar iterativamente el conjunto potencia de un conjunto infinito y aplicar el teorema de Cantor, obtenemos una jerarquía infinita de cardinales infinitos, cada uno estrictamente mayor que el anterior. En consecuencia, el teorema implica que no hay un número cardinal más grande (coloquialmente, 'no hay un infinito más grande').

Prueba

Did you mean:

Cantor 's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow.

Theorem (Cantor)—Vamos $f$ ser un mapa del conjunto $A$ a su poder establecido ${mathcal {P}}(A)$ . Entonces... ${displaystyle f:Ato {mathcal {P}}(A)}$ no es subjetivo. En consecuencia, $<math alttext="{displaystyle operatorname {card} (A)tarjeta ()A).tarjeta ()P()A)){displaystyle operatorname {card} (A) wonoperatorname {card} ({mathcal {P}(A)})} <img alt="{displaystyle operatorname {card} (A)$ para cualquier conjunto $A$ .

Prueba

Considere el conjunto ${displaystyle B={xin Amid xnotin f(x)}}$ . Supongamos al contrario que $f$ es subjetivo. Entonces existe ${displaystyle xi in A}$ tales que ${displaystyle f(xi)=B}$ . Pero por construcción, ${displaystyle xi in Biff xi notin f(xi)=B}$ . Esto es una contradicción. Así, $f$ no puede ser subjetivo. Por otro lado, ${displaystyle g:Ato {mathcal {P}}(A)}$ definidas por $xmapsto {x}$ es un mapa inyectable. En consecuencia, debemos tener $<math alttext="{displaystyle operatorname {card} (A)tarjeta ()A).tarjeta ()P()A)){displaystyle operatorname {card} (A) wonoperatorname {card} ({mathcal {P}(A)})} <img alt="{displaystyle operatorname {card} (A)$ . Q.E.D.

Por definición de cardenalidad, tenemos $<math alttext="{displaystyle operatorname {card} (X)tarjeta ()X).tarjeta ()Y){displaystyle operatorname {card} (X) wonoperatorname {card} (Y)} <img alt="{displaystyle operatorname {card} (X)$ para cualquier dos juegos $X$ y $Y$ si y sólo si hay una función inyectable, pero ninguna función bijeactiva $X$ a $Y$ . Suficientes para demostrar que no hay ninguna objeción $X$ a $Y$ . Este es el corazón del teorema de Cantor: no hay función subjetiva de ningún conjunto $A$ a su sistema de poder. Para establecer esto, es suficiente mostrar que ninguna función $f$ que mapea elementos en $A$ a subconjuntos de $A$ podemos llegar a cada subconjunto posible, es decir, sólo necesitamos demostrar la existencia de un subconjunto de $A$ que no es igual a $f(x)$ para cualquier $x$ ▪ $A$ . (Recuerde que cada uno $f(x)$ es un subconjunto de $A$ .) Tal subconjunto es dado por la siguiente construcción, a veces llamada el conjunto diagonal Cantor $f$ :

{displaystyle B={xin Amid xnot in f(x)}.}

Esto significa, por definición, que para todo x ∈ A, x ∈ B si y solo si x ∉ f(x). Para todo x los conjuntos B y f(x) no pueden ser iguales porque B se construyó a partir de elementos de A cuyas imágenes (bajo f) no se incluían a sí mismas. Más específicamente, considere cualquier x ∈ A, luego x ∈ f(x) o x ∉ f(x). En el primer caso, f(x) no puede ser igual a B porque x ∈ f(x) por suposición y x ∉ B por la construcción de B. En el último caso, f(x) no puede ser igual a B porque x ∉ f(x) por suposición y x ∈ B por la construcción de B.

Equivalentemente, y un poco más formalmente, acabamos de demostrar que la existencia de ξ ∈ A tal que f(ξ) = B implica la siguiente contradicción:

{displaystyle {begin{aligned}xi notin f(xi)&iff xi in B&&{text{(by definition of }}B{text{)}};\xi in B&iff xi in f(xi)&&{text{(by assumption that }}f(xi)=B{text{)}};\end{aligned}}}

Por lo tanto, por reductio ad absurdum, la suposición debe ser falsa. Entonces no hay ξ ∈ A tal que f(ξ) = B; en otras palabras, B no está en la imagen de f y f no corresponde a todos los elementos del conjunto de potencia de A , es decir, f no es sobreyectiva.

Finalmente, para completar la prueba, necesitamos exhibir una función inyectiva de A a su conjunto potencia. Encontrar tal función es trivial: simplemente asigne x al conjunto singleton {x}. El argumento ahora está completo y hemos establecido la desigualdad estricta para cualquier conjunto A que card(A) < carta(𝒫(A)).

Otra forma de pensar en la prueba es que B, vacío o no vacío, siempre está en el conjunto potencia de A. Para que f esté sobre, algún elemento de A debe mapear a B. Pero eso conduce a una contradicción: ningún elemento de B puede mapear a B porque eso contradiría el criterio de pertenencia a B, por lo que el elemento mapear a B no debe ser un elemento de B lo que significa que satisface el criterio para ser miembro de B, otra contradicción. Entonces, la suposición de que un elemento de A se asigna a B debe ser falsa; y f no puede ser sobre.

Debido a la doble aparición de x en la expresión "x ∉ f(x)", este es un argumento diagonal. Para un conjunto contable (o finito), el argumento de la prueba anterior puede ilustrarse mediante la construcción de una tabla en la que cada fila esté etiquetada con una única x de A = {x₁, x₂,...}, en este orden. Se supone que A admite un orden lineal para que se pueda construir dicha tabla. Cada columna de la tabla está etiquetada con una y única del conjunto potencia de A; las columnas están ordenadas por el argumento de f, es decir, las etiquetas de las columnas son f(x₁), f(x₂),..., en este orden. La intersección de cada fila x y columna y registra un bit verdadero/falso si x ∈ y. Dado el orden elegido para las etiquetas de fila y columna, la diagonal principal D de esta tabla registra si x ∈ f(x ) para cada x ∈ A. El conjunto B construido en los párrafos anteriores coincide con las etiquetas de fila para el subconjunto de entradas en esta diagonal principal D donde la tabla registra que x ∈ f(x) es falso. Cada columna registra los valores de la función indicadora del conjunto correspondiente a la columna. La función indicadora de B coincide con las entradas lógicamente negadas (intercambiar "verdadero" y "falso") de la diagonal principal. Por lo tanto, la función indicadora de B no concuerda con ninguna columna en al menos una entrada. En consecuencia, ninguna columna representa B.

A pesar de la simplicidad de la prueba anterior, es bastante difícil que un probador de teoremas automatizado la produzca. La principal dificultad radica en un descubrimiento automatizado del conjunto diagonal de Cantor. Lawrence Paulson señaló en 1992 que Otter no podía hacerlo, mientras que Isabelle sí, aunque con cierta dirección en términos de tácticas que quizás podrían considerarse trampa.

Cuando A es contablemente infinito

Examinemos la prueba del caso específico cuando $A$ es contablemente infinito. Sin pérdida de generalidad, podemos tomar $A = N = {1, 2, 3,...}$ , el conjunto de números naturales.

Supongamos que N es equinúmero con su conjunto potencia 𝒫(N). Veamos un ejemplo de cómo se ve 𝒫(N):

{displaystyle {mathcal {P}}(mathbb {N})={varnothing{1,2},{1,2,3},{4},{1,5},{3,4,6},{2,4,6,dots },dots }.}

𝒫(N) contiene infinitos subconjuntos de N, p. el conjunto de todos los números pares {2, 4, 6,...}, así como el conjunto vacío.

Ahora que tenemos una idea de cómo son los elementos de 𝒫(N), intentemos emparejar cada elemento de N con cada elemento de 𝒫 (N) para mostrar que estos conjuntos infinitos son equinumeros. En otras palabras, intentaremos emparejar cada elemento de N con un elemento del conjunto infinito 𝒫(N), de modo que ningún elemento de ninguno de los conjuntos infinitos quede sin emparejar.. Tal intento de emparejar elementos se vería así:

{displaystyle mathbb {N} {begin{Bmatrix}1&longleftrightarrow &{4,5}\2&longleftrightarrow &{1,2,3}\3&longleftrightarrow &{4,5,6}\4&longleftrightarrow &{1,3,5}\vdots &vdots &vdots end{Bmatrix}}{mathcal {P}}(mathbb {N}).}

Dado tal emparejamiento, algunos números naturales se emparejan con subconjuntos que contienen exactamente el mismo número. Por ejemplo, en nuestro ejemplo, el número 2 está emparejado con el subconjunto {1, 2, 3}, que contiene 2 como miembro. Llamemos a esos números egoístas. Otros números naturales se emparejan con subconjuntos que no los contienen. Por ejemplo, en nuestro ejemplo, el número 1 está emparejado con el subconjunto {4, 5}, que no contiene el número 1. Llama a estos números no egoísta. Del mismo modo, 3 y 4 no son egoístas.

Usando esta idea, construyamos un conjunto especial de números naturales. Este conjunto proporcionará la contradicción que buscamos. Sea B el conjunto de todos los números naturales no egoístas. Por definición, el conjunto potencia 𝒫(N) contiene todos los conjuntos de números naturales, por lo que contiene este conjunto B como elemento. Si el mapeo es biyectivo, B debe emparejarse con algún número natural, digamos b. Sin embargo, esto causa un problema. Si b está en B, entonces b es egoísta porque está en el conjunto correspondiente, lo que contradice la definición de B. Si b no está en B, entonces no es egoísta y debería ser miembro de B. Por lo tanto, no puede existir ningún elemento b que corresponda a B.

Dado que no hay un número natural que se pueda emparejar con B, hemos contradicho nuestra suposición original, que hay una biyección entre N y 𝒫( n).

Tenga en cuenta que el conjunto B puede estar vacío. Esto significaría que cada número natural x se asigna a un subconjunto de números naturales que contiene x. Entonces, cada número se asigna a un conjunto no vacío y ningún número se asigna al conjunto vacío. Pero el conjunto vacío es miembro de 𝒫(N), por lo que el mapeo aún no cubre 𝒫(N).

A través de esta prueba por contradicción hemos demostrado que la cardinalidad de N y 𝒫(N) no pueden ser iguales. También sabemos que la cardinalidad de 𝒫(N) no puede ser menor que la cardinalidad de N porque 𝒫(N) contiene todos los singletons, por definición, y estos singletons forman una "copia" de N dentro de 𝒫(N). Por lo tanto, solo queda una posibilidad, y es que la cardinalidad de 𝒫(N) sea estrictamente mayor que la cardinalidad de N, demostrando el teorema de Cantor.

Paradojas relacionadas

Did you mean:

Cantor 's theorem and its proof are closely related to two paradoxes of set theory.

La paradoja de Cantor es el nombre dado a una contradicción siguiendo el teorema de Cantor junto con la suposición de que hay un conjunto que contiene todos los conjuntos, el conjunto universal $V$ . Para distinguir esta paradoja de la siguiente discutida a continuación, es importante señalar lo que es esta contradicción. Por el teorema de Cantor $|X|}" xmlns="http://www.w3.org/1998/Math/MathML">SilencioP()X)Silencio■SilencioXSilencio{displaystyle Silencio{mathcal {fnMicrosoft Sans Serif}|X|}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/35c0323edc544c959a6221653f12c7513e57ad22" style="vertical-align: -0.838ex; width:13.159ex; height:2.843ex;"/>$ para cualquier conjunto $X$ . Por otro lado, todos los elementos ${displaystyle {mathcal {P}}(V)}$ son conjuntos, y así contenidos en $V$ , por lo tanto ${displaystyle |{mathcal {P}}(V)|leq |V|}$ .

Se puede derivar otra paradoja de la prueba del teorema de Cantor al instanciar la función f con la función de identidad; esto convierte el conjunto diagonal de Cantor en lo que a veces se llama el conjunto de Russell de un conjunto determinado A:

R_{A}=left{,xin A:xnot in x,right}.

La prueba del teorema de Cantor se adapta directamente para mostrar que suponiendo que existe un conjunto de todos los conjuntos U, entonces considerando su conjunto de Russell R_U conduce a la contradicción:

R_{U}in R_{U}iff R_{U}notin R_{U}.

Este argumento se conoce como la paradoja de Russell. Como punto de sutileza, la versión de la paradoja de Russell que hemos presentado aquí es en realidad un teorema de Zermelo; podemos concluir de la contradicción obtenida que debemos rechazar la hipótesis de que R_U∈U, refutando así la existencia de un conjunto que contiene todos los conjuntos. Esto fue posible porque hemos utilizado la comprensión restringida (como se presenta en ZFC) en la definición de R_A anterior, que a su vez implicaba que

R_{U}in R_{U}iff (R_{U}in Uwedge R_{U}notin R_{U}).

Si hubiéramos utilizado la comprensión sin restricciones (como en el sistema de Frege, por ejemplo) definiendo el conjunto Russell simplemente como $R=left{,x:xnot in x,right}$ , entonces el sistema de axioma en sí habría implicado la contradicción, sin nuevas hipótesis necesarias.

A pesar de las similitudes sintácticas entre el conjunto de Russell (en cualquiera de sus variantes) y el conjunto diagonal de Cantor, Alonzo Church enfatizó que la paradoja de Russell es independiente de las consideraciones de cardinalidad y sus nociones subyacentes, como la correspondencia uno a uno.

Historia

Cantor proporcionó esencialmente esta prueba en un artículo publicado en 1891 "Über eine elementare Frage der Mannigfaltigkeitslehre", donde también aparece por primera vez el argumento diagonal para la incontabilidad de los reales (anteriormente había demostrado la incontabilidad de los reales). reales por otros métodos). La versión de este argumento que dio en ese documento se expresó en términos de funciones indicadoras en un conjunto en lugar de subconjuntos de un conjunto. Mostró que si f es una función definida en X cuyos valores son funciones de 2 valores en X, entonces la función de 2 valores G(x) = 1 − f(x)(x) no está en el rango de f.

Bertrand Russell tiene una prueba muy similar en Principles of Mathematics (1903, sección 348), donde muestra que hay más funciones proposicionales que objetos. "Supongamos que se ha visto afectada una correlación de todos los objetos y algunas funciones proposicionales, y sea phi-x el correlato de x. Entonces "no-phi-x(x)," es decir, "phi-x no contiene x" es una función proposicional no contenida en esta correlación; pues es verdadero o falso de x según que phi-x sea falso o verdadero de x, y por lo tanto difiere de phi-x para cada valor de x." Atribuye la idea detrás de la prueba a Cantor.

Ernst Zermelo tiene un teorema (al que llama "Teorema de Cantor") que es idéntico a la forma anterior en el artículo que se convirtió en la base de la teoría de conjuntos moderna ("Untersuchungen über die Grundlagen der Mengenlehre I"), publicado en 1908. Ver teoría de conjuntos de Zermelo.

Generalizaciones

Did you mean:

Cantor 's theorem has been generalized to any category with products.

Contenido relacionado

Más resultados...