12 votos

Entendiendo el argumento diagonal de Cantor

Estoy tratando de captar el Cantor diagonal de argumento para entender la prueba de que el poder conjunto de los números naturales es incontable. En la Wikipedia, es la siguiente ilustración:

enter image description here

La explicación de la prueba dice lo siguiente:

Por construcción, s difiere de cada sn, ya que su enésima dígitos diferentes (resaltado en el ejemplo). Por lo tanto, s no puede ocurrir en la enumeración.

No entiendo por qué la secuencia s en la parte inferior puede ocurrir en cualquier lugar de la enumeración de las secuencias anteriores. He leído la prueba alrededor de cinco veces, pero todavía no estoy consiguiendo. Creo que estoy teniendo un error en el razonamiento. Podría alguien por favor me explique por qué s no puede estar en la enumeración con un ejemplo?

14voto

Théophile Puntos 7913

La clave es que es diferente al de la construcción, lo que significa que usted está eligiendo los dígitos de $s$ específicamente para ello, que será diferente de todos los demás elementos en la lista.

Compare $s$$s_1$: se ve de inmediato que son diferentes debido a que el primer dígito es diferente. Ahora compare $s$$s_2$: son diferentes en el segundo dígito. Lo mismo vale para el resto de las $s_i$. La razón por la que esto sucede es precisamente porque hemos elegido los dígitos de $s$ tener esta propiedad.

4voto

fleablood Puntos 5913

Básicamente, el diagonalizing método es que hagan todo lo posible el número uno en un momento y decir "yo puedo hacer un número que es diferente y distinto a cualquier número hasta ahora". !!*!SI!!!* el número resultante hizo existen en la lista, entonces habría llegado a través de ella y le habría dicho: "yo puedo hacer un número diferente" y que tendría, por lo que el número no puede estar en la lista.

Ese número no puede ser el primer número, porque tiene un distinto primer término. No puede ser el segundo número, porque tiene un segundo término. No puede ser el enésimo número, porque tiene diferentes término n-ésimo.

Así que vamos a suponer que el número está en la lista. Bien, ¿qué número de la lista tiene? Digamos que es el coopledinkyfudgeth número en la lista. Así, cuando hacemos la diagonalización y llegamos a la coopledinkyfudgeth número cambiamos el coopledinkyfudgeth plazo y obtener un número diferente. Por lo que NO es el coopledinkyfudgeth número después de todo!

No está en la lista! La lista es imposible y no hay ninguna lista.

0voto

Mick dK Puntos 13

La razón de que esto funcione es porque estamos asumiendo que podemos enumerar cada cadena posible en una secuencia, pero el punto de la prueba es mostrar que esto no se puede hacer. Si$\textit{could}$ hace una lista, entonces$s$ tiene que ser un término en la secuencia, y por lo tanto tendría que ser igual a algún$s_N$. Pero por nuestra construcción de$s$, cambiamos el$N$ - ésimo dígito de$s_N$. Por lo tanto,$s$ es una nueva cadena de$0$ y$1$ s - lo cual es una contradicción con la suposición de que podemos hacer una lista.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X