9.3: Teorema de Cantor y sus consecuencias
- Page ID
- 109361
- Explicar el teorema de Cantor
Una vez que Cantor demostró que había dos tipos de infinidad (contable e incontable), la siguiente pregunta era natural: “¿Todos los conjuntos incontables tienen la misma cardinalidad? ”
Al igual que no todos los “no perros” son gatos, no hay, de hecho, ninguna razón para creer que todos los conjuntos incontables deben ser del mismo tamaño. Sin embargo construir conjuntos incontables 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\([0,1]\) y el cuadrado representado por el conjunto\([0,1] × [0,1] = \{(x,y)|0 ≤ x,y ≤ 1\}\)? Ciertamente, el cuadrado bidimensional debe ser un conjunto infinito mayor 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!”
Figura\(\PageIndex{1}\): Richard Dedekind
A continuación se da la idea original de la prueba de Cantor. Cantor ideó la siguiente función\(f : [0,1]×[0,1] → [0,1]\). Primero, representamos las coordenadas de cualquier punto\((x,y) ∈ [0,1]×[0,1]\) por sus representaciones decimales\(x = 0.a_1a_2a_3 ...\) e\(y = 0.b_1b_2b_3....\) incluso los decimales terminadores se pueden escribir de esta manera como podríamos escribir\(0.5 = 0.5000....\) Podemos entonces definir\(f(x,y)\) por
\[f((0.a_1a_2a_3 ...,0.b_1b_2b_3 ...)) = 0.a_1b_1a_2b_2a_3b_3 ....\]
Esta idea relativamente simple tiene algunas dificultades técnicas en ella relacionadas con el siguiente resultado.
Considera 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\).
De igual manera\(0.04999... = 0.05000...\), tenemos, etc. para hacer la representación decimal de un número real en\([0,1]\) único, debemos hacer una elección consistente de escribir un decimal de terminación como uno que termina en una cadena infinita de ceros o una cadena infinita de nueves [con la única excepción\(0 = 0.000...\)]. No importa la elección que tomemos, nunca podríamos hacer esta función. Por ejemplo,\(109/1100 = 0.09909090...\) tendría como su pre-imagen\((0.0999...,0.9000...)\) que sería una mezcla de las dos convenciones.
Cantor pudo superar este tecnicismo para demostrar una correspondencia uno a uno, pero en cambio notaremos que en cualquiera de las convenciones, la función es uno a uno, por lo que esto dice que el conjunto\([0,1]×[0,1]\) es el mismo 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 tema, Cantor demostró lo siguiente en 1891.
Dejar\(S\) ser cualquier conjunto. Entonces no hay correspondencia uno a uno entre\(S\) y\(P(S)\), el conjunto de todos los subconjuntos de\(S\).
Dado que se\(S\) 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 poder de\(S\).
Demostrar: Si\(|S| = n\), entonces\(|P(S)| = 2n\)
- Sugerencia
-
Vamos\(S = a_1, a_2, ..., a_n\). Considere la siguiente correspondencia entre los elementos de\(P(S)\) y el conjunto\(T\) de todas\(n\) -tuplas de yes (\(Y\)) o no (\(N\)):
\[\{\}\leftrightarrow {N,N,N,...,N}\\ \{a_1\}\leftrightarrow \{Y,N,N,...,N\}\\ \{a_2\}\leftrightarrow \{N,Y,N,...,N\}\\\vdots \\ S \leftrightarrow \{Y,Y,Y,...,Y\}\]
¿Cuántos elementos hay en\(T\)?
Demostrar el teorema de Cantor.
- Sugerencia
-
Asumir por contradicción, que hay una correspondencia uno a uno\(f : S → P(S)\). Considerar\(A = \{x ∈ S|x \not {∈} f(x)\}\). Ya que\(f\) está en, 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 manera rotonda utilizando algunas de las ideas anteriores de Ejercicio\(\PageIndex{2}\). En concreto, deja\(T\) ser el conjunto de todas las secuencias de ceros o unos (puedes usar\(Y\) s o\(N\) s, si lo prefieres). Entonces es sencillo verlo\(T\) y\(P(\mathbb{N})\) tener la misma cardinalidad.
Si consideramos\((0,1]\), que tiene la misma cardinalidad que\(\mathbb{R}\), entonces podemos ver que esto también tiene la misma cardinalidad.\(T\) Específicamente, si pensamos en los números en binario, entonces cada número real en\([0,1]\) puede escribirse como\(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) dónde\(a_j ∈ \{0,1\}\). Tenemos que dar cuenta del hecho de que las representaciones binarias como\(0.0111...\) y\(0.1000...\) representan el mismo número real (digamos que ninguna representación terminará en una cadena infinita de ceros), entonces podemos ver que\([0,1]\) tiene la misma cardinalidad que\(T - U\), donde\(U\) está el conjunto de todos secuencias que terminan en una cadena infinita de ceros. Resulta que\(U\) en sí mismo es un conjunto contable.
Dejar\(U_n = \{(a_1, a_2, a_3,...) | a_j ∈ \{0,1\}\) y\(a_{n+1} = a_{n+2} = ··· = 0\}\). Demostrar que para cada uno\(n\),\(U_n\) es finito y utilizar esto para concluir que\(U\) es contablemente infinito.
Los dos problemas siguientes muestran que eliminar un conjunto contable de un conjunto incontable no cambia su cardinalidad.
\(S\)Déjese ser un conjunto infinito. Demostrar que\(S\) contiene un subconjunto infinitamente contable.
Supongamos que\(X\) es un conjunto incontable y\(Y ⊂ X\) es contablemente infinito. Demostrar eso\(X\) y\(X - Y\) tener la misma cardinalidad.
- Sugerencia
-
Vamos\(Y = Y_0\). Si\(X - Y_0\) es un conjunto infinito, entonces por el problema anterior contiene un conjunto infinitamente contable\(Y_1\). De igual manera 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,...,\) dejar\(f_n : Y_{n-1} → Y_n\) ser una correspondencia uno a uno y definir\(f : X → X - Y\) por
\[\begin{cases} f(x) = f_n(x), & \text{ if } x \epsilon Y_n, n = 0,1,2,\cdots \\ f(x) = x, & \text{ if } x \epsilon X - \left ( \bigcup_{n=0}^{\infty }Y_n \right ) \end{cases}\]
Demostrar que\(f\) es uno a uno y hacia.
Los problemas anteriores dicen que\(R\),\(T - U\),\(T\), y\(P(N)\) todos 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 esta época, un conjunto era ingenuamente pensado 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 estaban siendo reformulados en términos de conjuntos. La idea era que la teoría de conjuntos iba a ser un tema unificador de las matemáticas. Esta paradoja puso al mundo matemático en su oído.
Paradoja de Russell
Considera el conjunto de todos los conjuntos que no son elementos de sí mismos. Llamamos a este conjunto\(D\) y preguntamos: “\(D ∈ D\)¿Es? ” Simbólicamente, este conjunto es
\[D = \{S | S \not{\epsilon } S\}\]
Si\(D ∈ D\), entonces por definición,\(D \not {∈} D\). Si D 6∈ D, entonces por definición,\(D ∈ D\).
Si miras hacia atrás a la prueba del Teorema de Cantor, ésta 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 fue escandaloso. Forzó a varios matemáticos y logísticos a idear cuidadosamente los axiomas por los cuales se podí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 Naive (a diferencia de 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 computacional (máquina).
Otro lugar donde la obra de Cantor tuvo una profunda influencia en la lógica moderna proviene de algo a lo que aludimos antes. Mostramos antes que la unidad cuadrada\([0,1]×[0,1]\) tenía la misma cardinalidad que un subconjunto incontable de\(\mathbb{R}\). De hecho, Cantor demostró que la plaza unitaria tenía la misma cardinalidad que\(\mathbb{R}\) ella misma y se movió para avanzar lo siguiente en 1878.
Cada subconjunto incontable de\(\mathbb{R}\) tiene la misma cardinalidad que\(\mathbb{R}\).
Cantor no pudo probar o desmentir esta conjetura (junto con cualquier otro matemático). De hecho, probar o desmentir esta conjetura, que fue apodada la Hipótesis del Continuum, fue uno de\(23\) los famosos problemas de Hilbert presentado como un desafío a los matemáticos en el Congreso Internacional de Matemáticos en 1900.
Ya que\(\mathbb{R}\) tiene la misma cardinalidad que\(P(N)\), entonces la Hipótesis del Continuum se generalizó a la:
Dado un conjunto\(S\), there is no infinito conjunto infinito que tiene una cardinalidad estrictamente entre la de\(S\) and its power set \(P(S)\).
Los esfuerzos para probar o desmentir esto fueron en vano y con buena razón. En 1940, el lógico Kurt Gödel demostró que la Hipótesis del Continuum no podía ser desmentida de los Axiomas Zermelo-Fraenkel de la teoría de conjuntos 1. En 1963, Paul Cohen demostró que la Hipótesis del Continuum no se pudo probar utilizando los Axiomas de Zermelo-Fraenkel. Es decir, los Axiomas Zermelo-Fraenkel no contienen suficiente información para decidir la verdad de la hipótesis.
Estamos dispuestos a apostar que en este punto tu cabeza podría estar nadando un poco con incertidumbre. Si es así, entonces sepa que estos son los mismos sentimientos que experimentó la comunidad matemática 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 “indecibles”. De hecho, Gödel demostró en 1931 que un sistema consistente de axiomas finitos que contenía los axiomas de la aritmética siempre contendría declaraciones indecibles que no podían demostrarse verdaderas ni falsas con esos axiomas. El conocimiento matemático siempre estaría incompleto.
Figura\(\PageIndex{2}\): Kurt Gödel
Entonces, al tratar de poner los cimientos del cálculo sobre un terreno sólido, hemos llegado a un punto en el que nunca podremos obtener certeza matemática. ¿Significa esto que debemos levantar las manos y conceder la derrota? ¿Deberíamos estar paralizados de miedo a intentar algo? ¡Desde luego que no! Como mencionamos antes, a la mayoría de los matemáticos les va bien adoptando un enfoque pragmático: usar sus matemáticas para resolver problemas que encuentran. De hecho, suelen ser los problemas los que motivan a las matemáticas. Es cierto que los matemáticos se arriesgan que no siempre salen bien, pero aún así se arriesgan, 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?