Articles

9.3: Teorema de Cantor y sus consecuencias

Habilidades para desarrollar

  • Explicar el teorema de Cantor

Una vez que Cantor demostró que había dos tipos de infinidad (numerable e incontable), la siguiente pregunta fue natural: «¿Todos los conjuntos incontables tienen la misma cardinalidad?»

Al igual que no todos los» no perros » son gatos, no hay ninguna razón para creer que todos los juegos incontables deben ser del mismo tamaño. Sin embargo, construir innumerables conjuntos de diferentes tamaños no es tan fácil como parece.

Por ejemplo, qué pasa con el segmento de línea representado por el intervalo \ ( \ ) y el cuadrado representado por el conjunto \( × = \{(x,y)|0 ≤ x,y ≤ 1\}\). Ciertamente, el cuadrado bidimensional debe ser un conjunto infinito más grande que el segmento de línea unidimensional. Sorprendentemente, Cantor demostró que estos dos conjuntos eran la misma cardinalidad. En su correspondencia de 1877 de este resultado a su amigo y compañero matemático Richard Dedekind, incluso Cantor comentó: «¡Lo veo, pero no lo creo!»

fig 9.3.1.png

Figura \(\pageIndex{1}\): Richard Dedekind

Lo siguiente da la idea original de la prueba de Cantor. Cantor ideó la siguiente función \(f:× → \). Primero, representamos las coordenadas de cualquier punto \((x, y)∈×\) por sus representaciones decimales \(x = 0.a_1a_2a_3 …\ ) y \(y = 0.b_1b_2b_3….\ ) Incluso los decimales finales se pueden escribir de esta manera, como podríamos escribir \(0.5 = 0.5000….\ ) Entonces podemos definir \(f (x,y)\) por

\

Esta idea relativamente simple tiene algunas dificultades técnicas relacionadas con el siguiente resultado.

Ejercicio de \(\PageIndex{1}\)

Considere la secuencia \((0.9,0.99,0.999,…)\). Determinar que esta secuencia converge y, de hecho, converge a \(1\). Esto sugiere que \(0.999… = 1\).

Del mismo modo, tenemos \(0.04999… = 0.05000…\), sucesivamente. Para que la representación decimal de un número real en \(\) sea única, debemos hacer una elección consistente de escribir un decimal final como uno que termina en una cadena infinita de ceros o una cadena infinita de nueves . No importa la elección que hagamos, nunca podríamos hacer esta función. Por ejemplo, \(109/1100 = 0.09909090…\ ) tendría como pre-imagen \((0.0999…,0.9000…)\), que sería una mezcla de las dos convenciones.

Cantor fue capaz de superar este tecnicismo para demostrar una correspondencia uno a uno, pero en su lugar notaremos que en cualquier convención, la función es uno a uno, por lo que esto dice que el conjunto \(×\) es la misma cardinalidad que algún subconjunto (incontable) de \(\mathbb{R}\). El hecho de que esto tenga la misma cardinalidad que \(\mathbb{R}\) es algo a lo que volveremos. Pero primero intentaremos construir un conjunto incontable que no tenga la misma cardinalidad que \(\mathbb{R}\). Para abordar este problema, Cantor demostró lo siguiente en 1891.

Teorema \(\Índice de página{1}\): Teorema de Cantor

Sea \(S\) cualquier conjunto. Entonces no hay una correspondencia uno a uno entre \(S\) y \(P(S)\), el conjunto de todos los subconjuntos de \(S\).

Dado que \(S\) se puede poner en correspondencia uno a uno con un subconjunto de \(P(S) (a → \{a\})\), entonces esto dice que \(P(S)\) es al menos tan grande como \(S\). En el caso finito \(/P (S)|\) es estrictamente mayor que \(|S/\) como muestra el siguiente problema. También demuestra por qué \(P(S)\) se llama el conjunto de potencia de \(S\).

Ejercicio De \(\PageIndex{2}\)

Probar: Si \(/S / = n\), entonces \(/P (S)| = 2n\)

Sugerencia

Let \(S = a_1, a_2, …, a_n\). Considere la siguiente correspondencia entre los elementos de \(P(S)\) y el conjunto \(T\) de todos \(n\)-tuplas de sí (\(Y\)) o no (\(N\)):

\

cuántos elementos hay en \(T\)?

Ejercicio \(\Índice de página{3}\)

Probar el Teorema de Cantor.

Sugerencia

Asuma para contradicción, que hay una correspondencia uno a uno \(f: S → P (S)\). Considere \(A = \{x ∈ S / x \not {∈} f(x)\}\). Puesto que \(f\) es onto, entonces hay \(a ∈ A\) tal que \(A = f (a)\). ¿Es \(a ∈ A\) o es \(a \not {∈} A\)?

en Realidad resulta que \(\mathbb{R}\) y \(P(\mathbb{N})\) tienen la misma cardinalidad. Esto se puede ver de forma indirecta utilizando algunas de las ideas anteriores del Ejercicio \(\pageIndex{2}\). Específicamente, sea \(T\) el conjunto de todas las secuencias de ceros o unos (puede usar \(Y\) s o \(N\) s, si lo prefiere). Entonces es sencillo ver que \(T\) y \(P(\mathbb{N})\) tienen la misma cardinalidad.

Si consideramos \((0,1]\), que tiene la misma cardinalidad que \(\mathbb{R}\), entonces podemos ver que también tiene la misma cardinalidad que \(T\). Específicamente, si pensamos en el número en binario, cada número real en \(\) se puede escribir como \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) donde \(a_j ∈ \{0,1\}\). Tenemos que tener en cuenta el hecho de que las representaciones binarias como \(0.0111…\) y \(0.1000…\ ) representa el mismo número real (digamos que ninguna representación terminará en una cadena infinita de ceros), entonces podemos ver que \ ( \ ) tiene la misma cardinalidad que \(T – U\), donde \(U\) es el conjunto de todas las secuencias que terminan en una cadena infinita de ceros. Resulta que \(U\) en sí es un conjunto contable.

Ejercicio \(\Índice de página{4}\)

Let \(U_n = \{(a_1, a_2, a_3,…) | a_j ∈ \{0,1\}\) y \(a_{n+1} = a_{n+2} = ··· = 0\}\). Muestra que para cada \(n\), \(U_n\) es finito y usa esto para concluir que \(U\) es infinitamente numerable.

Los dos problemas siguientes muestran que eliminar un conjunto contable de un conjunto incontable no cambia su cardinalidad.

Ejercicio de \(\PageIndex{5}\)

Sea \(S\) ser un conjunto infinito. Demostrar que \(S\) contiene un subconjunto infinito numerable.

Ejercicio \(\Índice de página{6}\)

Supongamos que \(X\) es un conjunto incontable y \(Y X X\) es infinito numerable. Demostrar que \(X\) y \(X – Y\) tienen la misma cardinalidad.

Pista

Let \(Y = Y_0\). Si \(X-Y_0\) es un conjunto infinito, entonces por el problema anterior contiene un conjunto infinito numerable \(Y_1\). Del mismo modo, si \(X – (Y_0 ∪ Y_1)\) es infinito también contiene un conjunto infinito \(Y_2\). De nuevo, si \(X – (Y_0\ Y_1 \Y_2)\) es un conjunto infinito, entonces contiene un conjunto infinito \ (Y_3\), etc. Para \(n = 1,2,3,…,\) sea \(f_n: Y_{n-1} → Y_n\) una correspondencia uno a uno y defina \(f: X → X-Y\) por

\

Mostrar que \(f\) es uno a uno y onto.

Los problemas anteriores dicen que \(R\), \(T – U\), \(T\) y \(P(N)\) tienen la misma cardinalidad.

Como se indicó anteriormente, el trabajo de Cantor sobre conjuntos infinitos tuvo un profundo impacto en las matemáticas a principios del siglo XX. Por ejemplo, al examinar la prueba del Teorema de Cantor, el eminente lógico Bertrand Russell ideó su famosa paradoja en 1901. Antes de este tiempo, un conjunto se pensaba ingenuamente como una colección de objetos. A través del trabajo de Cantor y otros, los conjuntos se estaban convirtiendo en un objeto central de estudio en matemáticas, ya que muchos conceptos matemáticos se estaban reformulando en términos de conjuntos. La idea era que la teoría de conjuntos fuera un tema unificador de las matemáticas. Esta paradoja puso al mundo matemático en su oreja.

La paradoja de Russell

Considere el conjunto de todos los conjuntos que no son elementos de sí mismos. Llamamos a este conjunto \(D\) y preguntamos, «Is \(D ∈ D\)?»Simbólicamente, este conjunto es

\

Si \(D ∈ D\), entonces, por definición, \(D \no {∈} D\). Si D 6∈ D, entonces, por definición, \(D ∈ D\).

Si nos fijamos en la prueba del teorema de Cantor, esta fue básicamente la idea que nos dio la contradicción. Tener tal contradicción ocurriendo en el nivel más básico de las matemáticas era escandaloso. Obligó a un número de matemáticos y lógicos a diseñar cuidadosamente los axiomas por los que se podrían construir conjuntos. Para ser honesto, la mayoría de los matemáticos todavía abordan la teoría de conjuntos desde un punto de vista ingenuo, ya que los conjuntos con los que normalmente tratamos caen dentro de la categoría de lo que llamaríamos «conjuntos normales».»De hecho, tal enfoque se llama oficialmente Teoría de Conjuntos Ingenua (en oposición a la Teoría de Conjuntos Axiomática). Sin embargo, los intentos de poner la teoría de conjuntos y la lógica sobre bases sólidas llevaron al estudio moderno de la lógica simbólica y, en última instancia, al diseño de la lógica de la computadora (máquina).

Otro lugar donde el trabajo de Cantor tuvo una profunda influencia en la lógica moderna proviene de algo a lo que aludimos antes. Demostramos antes que la unidad cuadrada \ ( × \ ) tenía la misma cardinalidad que un subconjunto incontable de \(\mathbb{R}\). De hecho, Cantor demostró que la unidad cuadrada tenía la misma cardinalidad que \(\mathbb{R}\) y se movió para avanzar en lo siguiente en 1878.

Conjetura (La Hipótesis del Continuo)

Cada subconjunto incontable de \(\mathbb{R}\) tiene la misma cardinalidad que \(\mathbb{R}\).

Cantor fue incapaz de probar o refutar esta conjetura (junto con cualquier otro matemático). De hecho, probar o refutar esta conjetura, que se denominó la Hipótesis del Continuo, fue uno de los famosos problemas \(23\) de Hilbert presentados como un desafío para los matemáticos en el Congreso Internacional de Matemáticos en 1900.

Dado que \(\mathbb{R}\) tiene la misma cardinalidad que \(P (N)\), entonces la Hipótesis del Continuo se generalizó a la:

Conjetura (La Hipótesis del Continuo Generalizado)

Dado un conjunto infinito \(S\), no hay un conjunto infinito que tenga una cardinalidad estrictamente entre la de \(S\) y su conjunto de potencia \(P(S)\).

Los esfuerzos para probar o refutar esto fueron en vano y con buena razón. En 1940, el lógico Kurt Gödel demostró que la Hipótesis del Continuo no podía ser refutada a partir de los Axiomas de Zermelo-Fraenkel de la teoría de conjuntos 1. En 1963, Paul Cohen demostró que la Hipótesis del Continuo no podía probarse utilizando los Axiomas de Zermelo-Fraenkel. En otras palabras, los Axiomas de Zermelo-Fraenkel no contienen suficiente información para decidir la verdad de la hipótesis.

Estamos dispuestos a apostar que en este punto su cabeza podría estar nadando un poco con incertidumbre. Si es así, entonces sepa que estos son los mismos sentimientos que la comunidad matemática experimentó a mediados del siglo XX. En el pasado, las matemáticas se veían como un modelo de certeza lógica. Es desconcertante encontrar que hay afirmaciones que son «indecidibles.»De hecho, Gödel demostró en 1931 que un sistema de axiomas finitos consistentes que contuvieran los axiomas de la aritmética siempre contendrían enunciados indecidibles que no podían probarse verdaderos ni falsos con esos axiomas. El conocimiento matemático siempre estaría incompleto.

 fig 9.3.2.png

Figura \(\pageIndex{2}\): Kurt Gödel

Por lo tanto, al tratar de poner los cimientos del cálculo en un terreno sólido, hemos llegado a un punto en el que nunca podemos obtener certeza matemática. ¿Significa esto que debemos levantar las manos y reconocer la derrota? ¿Deberíamos estar paralizados por el miedo a intentar algo? Por supuesto que no! Como mencionamos antes, a la mayoría de los matemáticos les va bien adoptar un enfoque pragmático: usar sus matemáticas para resolver los problemas que encuentran. De hecho, son típicamente los problemas los que motivan las matemáticas. Es cierto que los matemáticos toman riesgos que no siempre dan resultado, pero todavía toman estos riesgos, a menudo con éxito. Incluso cuando los éxitos conducen a más preguntas, como suelen hacer, abordar esas preguntas generalmente conduce a una comprensión más profunda. Por lo menos, nuestra comprensión incompleta significa que siempre tendremos más preguntas que responder, más problemas que resolver.

¿Qué más podría pedir un matemático?