Problema con la prueba de Cantor sobre la Incuentabilidad de los Reales

Question

Hay un problema básico en la prueba de Cantor que no entiendo. Me parece que el método se puede usar para demostrar que cualquier secuencia infinita es incontable. Por ejemplo, aquí hay una 'prueba' de que ni siquiera los números enteros positivos son contables (del mismo modo se puede probar que los números enteros positivos no son contables):

Usando el Teorema de Cantor para demostrar que los números pares no son contables

Lo siguiente es una 'prueba' de que los enteros pares no son contables, utilizando el método en el Teorema de Cantor de que los números reales no son contables. Supongamos que el conjunto de todos los enteros positivos pares, E, es contable. Por lo tanto, pueden estar dispuestos en una correspondencia uno a uno con los enteros positivos. Denotemos a los elementos (los enteros pares) en esta disposición por: x1, x2, x3,... de modo que xi representa el entero positivo i. disponga los números pares en una tabla y represente cada uno por sus dígitos, es decir: x1= a11 a12 a13..
x2= a21 a22 a23..
x3= a31 a32 a33..
. . en general: xn =an1 an2 an3 donde aij denota el j-ésimo dígito del i-ésimo número par. Ahora construimos un número par, llámelo Y, que no está en esta lista. Sea: Y=y1 y2 y3…, Donde: yi=2 si aii ≠ 2 Yi=4 si aii=2 o aii está en blanco (es decir, el número de dígitos en xi es menor que i)

El número Y está definido de manera que difiere de x1 en su primer dígito, de x2 en su segundo dígito, etc. y cada dígito es par por construcción. Por lo tanto, el número Y, que es par, no está en la lista.

Answer 1

El problema con tu "demostración" es que el $Y$ que has construido tiene infinitos dígitos. Es decir, no es un entero y por lo tanto no está en la lista.

---

Aquí hay otra demostración que dio Cantor (antes de su argumento de diagonalización de hecho) de que los números reales son no numerables. Supongamos por contradicción que los números reales son numerables. Póngalos en una correspondencia uno a uno con $\mathbb{N}$

$$X=\{x_1,x_2,...\}$$

Ahora, o bien $x_1 o $x_2. Supongamos que el primer caso es cierto (el argumento es el mismo si es el segundo caso). Ahora, define la nueva secuencia $a_n$. Comienza con $a_1=x_1$ y $a_2=x_2$. Para definir $a_n$ en general, deja que $a_n$ sea el miembro más pequeño (en términos de índice) de $X$ que está entre $a_{n-1}$ y $a_{n-2}$. Por ejemplo, para

$$X=\{0,1,2,1.5,.5,9,-1,.7...\}$$

tendríamos la secuencia $a_n$ que comienza como

$$\{0,1,.5,.7,...\}$$

con el próximo miembro en algún lugar entre $.5$ y $.7$. Ahora, es fácil mostrar que esta secuencia converge al notar que $a_{2n-1}$ es creciente, $a_{2n}$ es decreciente, y que $|a_n-a_{n-1}|$ tiende a cero (trabaja en los detalles si no estás convencido). De hecho, podemos decir que

$$\lim_{n\to\infty} a_{2n-1}=\lim_{n\to\infty}a_{2n}=\lim_{n\to\infty}a_n=L$$

Es decir, $a_{2n-1}$ es una secuencia creciente que converge a $L$ y $a_{2n}$ es una secuencia decreciente que converge a $L$. Esto implica que

$$a_{2n-1}

para todo $n$ ($a_n$ nunca repite un término). Pero esto es una contradicción ya que $L=x_i$ para algún $i\in\mathbb{N}$ (por nuestra suposición original) y por lo tanto es un miembro de $a_n$. Habiendo llegado a una contradicción, concluimos que los números reales son no numerables.

Answer 2

Los números reales tienen infinitos dígitos. Los enteros tienen un número finito de dígitos.

La construcción de Cantor de construir un thing que no está en una lista contable cambiando un componente $k$ del $k$-ésimo elemento para que sea diferente de todos en la lista construirá un thing con componentes infinitos.

Por lo tanto, el argumento de Cantor se puede generalizar así: el conjunto de todos los things que tienen infinitos componentes contables (cada uno de los cuales tiene opciones finitas pero más de una) no es contable.

Sin embargo, el conjunto de todos los things que tienen un número finito de componentes (cada uno de los cuales tiene un número finito de opciones) es contable. La construcción de Cantor creará un thing con infinitos componentes. Y como tiene infinitos componentes, es un tipo de cosa diferente a aquellas con componentes finitos.

Podemos contar aquellos things con un número finito de componentes enumerándolos en orden, aquellos con un componente primero y luego aquellos con dos componentes y así sucesivamente. No podemos usar el método para contar ningún thing con infinitos componentes ya que nunca podremos pasar por todos los things con número finito de componentes antes de poder listar algo con infinitos componentes.

Podemos usar un argumento similar al de Cantor para demostrar que el conjunto de things con un número finito de componentes no puede ser finito. Toma una lista finita de things y haz lo que hiciste. Eventualmente llegarás al elemento más largo de tu lista finita y no tendrás que seguir adelante. El thing que creaste tiene un número finito de componentes pero no es solo tu lista finita.

Sin embargo, puede ser más simple simplemente hacer el argumento de la escuela primaria: toma el thing en la lista con más componentes y agrega otro componente.

Answer 3

En el caso de los números pares $\mathbb{E}$, podemos demostrar que el argumento de Cantor no logra encontrar una contradicción utilizando alguna función biyectiva arbitraria $f: \mathbb{N} \to \mathbb{E}$. Si escribimos $f(n) = d_n^1 d_n^2 \dots$ para los dígitos $d^i_n$, observamos que para cada $n$, existe algún $k_n$ tal que para $j \geq k$, tenemos que $d_n^j = 0$.

En el argumento diagonal de Cantor, se construye un elemento a partir de estos llamado $Y$ al permitir que los dígitos de $y$, denotados como $d_Y^i$, sean tales que $d_Y^i \neq d_i^i$ para todos $i$. Luego, $Y \neq f(n)$ bajo el supuesto de que $Y \in \mathbb{E}$.

Este supuesto es donde falla el argumento. Para que $Y$ sea siquiera un número natural, tendría que cumplir que $d_Y^j = 0$ para todo $j \geq k_Y$. Sin embargo, si esto fuera cierto, entonces $d_n^n \neq 0$ para todos los $n \geq k_Y$. Esto contradiría el hecho de que $f$ es sobreyectiva ya que entonces, $f(n) \geq 10^n$ para todo $n \geq k_Y$.

En contraste, no existen este tipo de restricciones en secuencias infinitas de números naturales, como los dígitos de los reales.