¿Por qué la diagonalización no demuestra que los enteros no son contables?

Question

Entiendo cómo funciona el argumento de la diagonalización de Cantor con respecto a la refutación de que puede existir una biyección entre números enteros y reales. Lo que no entiendo es por qué el mismo razonamiento no se aplica a una biyección de números enteros a números enteros. Considere el argumento como se describe aquí:

http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#An_uncountable_set

Mi intuición me dice que lo mismo no es posible porque la representación de un número entero dado es de longitud finita. Me doy cuenta de que esta pregunta ya se ha planteado aquí: ¿Por qué el argumento de la diagonal de Cantor no se aplica también a los números naturales?

Pero las respuestas me parecieron algo opacas. Por eso vuelvo a preguntar.

Answer 1

Como se ha explicado en esas respuestas, el argumento diagonal de Cantor funciona porque estamos trabajando con cadenas de $0$ s y $1$ s sin ningún tipo de restricción, mientras que los números naturales acabarán siendo "cero", es decir, la secuencia acabará convirtiéndose en una cadena infinita de ceros. Por lo tanto, si se trabaja con todos los $$\{(a_0,a_1,\ldots):a_i\in\{0,1\})=2^{\Bbb N}$$ entonces el contraejemplo producido por el algoritmo de Cantor será de nuevo un elemento de los conjuntos de secuencias de ceros y unos, pero si se trabaja con un subconjunto adecuado de esto, a saber $$\{(a_0,a_1,\ldots):a_i\in\{0,1\} \text{ and } a_n=0 \text{ eventually} )\subsetneq 2^{\Bbb N}$$

puede darse el caso de que el "contraejemplo" no sea uno en absoluto, ya que no será finalmente cero. Por tanto, el argumento falla. No es demasiado difícil plantear un problema de este tipo:

Considere $2,4,8,16,\ldots$ . Esto es $(0,1,0,\ldots)$ , $(0,0,1,0,\ldots)$ , $(0,0,0,1,\ldots),\ldots$ y Cantor dicta que tomemos $(1,1,1,1,\ldots)$ como contraejemplo. Pero $(1,1,1,1,\ldots)$ ¡no es finalmente cero!