¿Puede alguien explicarme el argumento de la diagonalización de Cantor?

Question

Como ¿puede alguien explicarme esto como si fuera un niño de 5 años o algo así? Cada explicación que leo repite exactamente lo mismo que simplemente no entiendo. Esto es lo que dice mi libro:

"Los números reales entre 0 y 1 pueden ser enumerados en algún orden, digamos, $r_1, r_2, r_3, ...$ Sea la representación decimal de estos números reales

$r_1 = 0.d_{11}$$d_{12}$$d_{13}$$d_{14}$... $r_2 = 0.d_{21}$$d_{22}$$d_{23}$$d_{24}$ ... $r_3 = 0.d_{31}$$d_{32}$$d_{33}$$d_{34}$... $r_4 = 0.d_{41}$$d_{42}$$d_{43}$$d_{44}$ ...

Donde $d_{ij}$ es un elemento de {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Entonces para un nuevo número real con expansión decimal r = $d_{1}$$d_{2}$$d_{3}$$d_{4}$... donde los dígitos decimales están determinados por la siguiente regla:

$d_{i}$ = {4 si $d_{ii}$ no es igual a 4, 5 si $d_{ii}$ = 4}.

Y lo siento, pero ¿qué? ¿A dónde quiere llegar todo esto? ¿Qué significa todo eso de r1, r2, r3? ¿Por qué tenemos que crear un "nuevo número real"? ¿Qué sentido tiene? ¿Por qué? ¿Por qué hacemos todo esto? No entiendo nada del proceso que hay detrás y no entiendo cómo todo esto lleva a la conclusión de que los números reales son incontables. No tengo ni idea de lo que está pasando aquí.

Answer 1

Cada argumento es argumento para algo. El argumento de la diagonal de Cantor es un argumento para demostrar que el conjunto de los números reales es incontable.

¿Qué es un conjunto contable? Digamos que un conjunto es contable si podemos empezar a ordenar los elementos de un conjunto como el primero, el segundo y así sucesivamente. Formalmente tenemos que encontrar una biyección con los números naturales.

Para demostrar que los reales son incontables, primero suponemos lo contrario, es decir, que el conjunto de los reales es contable. Luego tenemos que encontrar una contradicción que haga falsa la suposición. Para ello encontramos un número real que no sea contable. El argumento diagonal de Cantor construye tal número real que no se cuenta.

Así que aquí están los pasos:

Objetivo: El conjunto de números reales es incontable.

Paso 1: Supongamos que el conjunto es contable. Esto significa que el conjunto de los números reales se puede escribir como un conjunto con primer elemento, segundo elemento y así sucesivamente, que es $\{r_1,r_2,r_3,\dots\}$ .

Paso 2: Una forma de demostrar que la suposición del paso 2 no es posible es encontrar un número real que no se cuente allí. ¿Cómo? Mediante el argumento de la diagonal de Cantor.

Supongamos que vamos a considerar sólo los números entre 0 y 1. Entonces el nuevo número es tal que es diferente del primer número en el primer dígito, del segundo elemento en el segundo dígito y así sucesivamente. Por ejemplo, mira lo siguiente: $$\begin{matrix} 0.& \color{red}9 & 7& 0& 6& \dots\\ 0.& 8 & \color{red}2& 4& 3& \dots\\ 0.& 4 & 5& \color{red}2& 8& \dots\\ 0.& 1 & 2& 5& \color{red}3& \dots\\ \vdots & \vdots & \vdots& \vdots& \vdots& \dots\\ \hline\\ 0.& 8 & 1& 1& 4& \dots\\ \end{matrix}$$ Se puede ver que el número es diferente de todos los números contados y también se puede ver que se construye utilizando los elementos diagonales de los números contados escritos como arriba, de ahí la nominalización de Argumento diagonal.

Answer 2

El argumento se presenta a menudo como una prueba por contradicción, pero se puede presentar de forma más directa, lo que creo que lo hace un poco más claro:

Teorema. Dejemos que $f$ sea cualquier función $\mathbb{N} \to \mathbb{R}$ . Entonces hay algún número real que no está en la imagen de $f$ eso es, $f$ no es sobreyectiva.

Prueba. Dado $f : \mathbb{N} \to \mathbb{R}$ construye un número real $x$ a través de su expansión decimal infinita; toma su $n$ El dígito $x_n$ sea 4 si el $n$ dígito de la expansión decimal estándar de $f(n)$ es 5, y toma $x_n$ para ser 5 en caso contrario. Ahora para cualquier $n$ , obtenemos que $x$ difiere de $f(n)$ en el $n$ de sus expansiones decimales, por lo que $x \neq f(n)$ . Así que $x$ no puede ser a imagen y semejanza de $f$ . $\square$

Por lo tanto, no hay ninguna sobreproyección $\mathbb{N} \to \mathbb{R}$ ; así que ciertamente no hay biyección, por lo que los reales no son contables.