Mejorar mi comprensión de la Diagonal de Cantor Argumento

Question

Estudié Cantor Diagonal de Argumento en la escuela años atrás y siempre me molestó (como estoy seguro de que muchos otros). En mi cabeza tengo dos argumentos en contra de Cantor en Diagonal del Argumento. Yo no soy un mathy persona, por lo que obviamente, estos deben tener explicaciones que todavía no he comprendido.

Mi primer problema es que el Cantor de la Diagonal Argumento (como maravillosamente explicado por Arturo Magidin) puede ser visto de una manera ligeramente diferente de la luz, que aparece para dar a conocer una falla en el argumento. Si asumimos que s_f es una imagen de f en algún índice n, entonces no tiene sentido definir s_f ($s_f=(s_1,s_2,s_3,…,s_n,…)$ donde $\begin{equation} s_k = \begin{cases}0 & \mathrm{if\ } f(n)_n = 1\\1 & \mathrm{if\ } f(n)_n = 0\end{cases}\end{equation}$

desde entonces el $n$ésimo elemento de a $s_f$ podría ser definido como el opuesto de sí mismo. Desde el Cantor de la Diagonal Argumento utiliza esta definición que no tendría sentido si s_f tiene un índice, a continuación, s_f no debe tener un índice, y a partir de ahí parece obvio que iban a llegar a la conclusión de que s_f no es una imagen de f. No es que la mendicidad a la pregunta?

Mi segundo problema es más complicado, y menos articuladas, pero básicamente es que cuando intento poner los números en la Diagonal de Cantor Argumento, que podrían demostrar que la "falta" elemento fue el dentro de una distancia constante desde el último elemento en la "serie", lo que significa que todos los infinitos otros números debe ser antes, lo que significa que no importa cómo es largo de contar, nunca llegar a él. Por ejemplo, si uno se pone a estos en el más obvio el fin de "contar" 0000..., 1000..., 0100...., 1100..., 0010... a continuación, el elemento que se encuentra, obviamente, es el elemento donde todos los $s_k = 1$, que sería el "último" elemento en que orden. Pero que también parece que se aplican a los números de contar, que también parece violar el Cantor de los Argumentos.

Answer 1

Esto podría estar poniendo el carro delante del caballo, pero me deja la dirección de su segunda edición.

cuando intento poner los números en la Diagonal de Cantor Argumento, que podrían demostrar que la "falta" elemento fue el dentro de una distancia constante desde el último elemento en la "serie"

Este parece ser un sorprendentemente común la confusión. No hay un "último elemento" de una serie infinita. Una serie infinita va para siempre, lo que significa que no hay final, lo que significa que no hay ningún elemento en la final. Es como preguntar cuál es el último dígito de la $\pi$ = 3.14159... es.

Cuando decimos que algo es un elemento de una serie infinita, lo que queremos decir es que es el $n$ésimo elemento de la serie para algún número natural $n$. Por ejemplo, el 1 dígito de $\pi$ es 3, el 2º dígito es 1, el 3er dígito es 4, el 100 dígito de las unidades es 7, y así sucesivamente. Si usted dice que 2 aparece en los dígitos de $\pi$, usted tiene que ser capaz de mostrar algunos de los $n$ para que el $n$th dígitos de $\pi$ es de 2. No para decir que es "el último", porque eso no significa nada.

Tal vez ahora podemos ver el defecto en su segundo argumento:

Por ejemplo, si uno se pone a estos en el más obvio el fin de "contar" 0000..., 1000..., 0100...., 1100..., 0010... a continuación, el elemento que se encuentra, obviamente, es el elemento donde todos los $s_k=1$, que sería el "último" elemento en que orden.

De verdad que no. Su encargo sólo cubre las secuencias binarias con un número finito de unidades. Y esos son, de hecho, contables, como el pedido de muestra! Pero, ¿de dónde 01010101..., por ejemplo, aparecer en su pedido? (No digo "a medio camino".) Esa secuencia, y la secuencia con todos, y muchos otros, ninguno de ellos es el $n$th elemento de su pedido. En otras palabras, no aparecer en su pedido.

Pero que también parece aplicarse a los números de contar, que también parece violar el Cantor de los Argumentos.

No, porque no hay ninguna último número natural. Si usted aplica la diagonal argumento de los números naturales, que podría producir una secuencia de dígitos con un número infinito de dígitos distintos de cero. Su conclusión sería que se ha producido un dígito de la secuencia que no aparece en la lista de los números naturales, lo cual es correcto, porque no hay ningún número natural con un número infinito de dígitos.

Answer 2

Mi primer problema es que el Cantor de la Diagonal Argumento parece a mendigar a la pregunta.

Es una prueba por contradicción. Suponemos que cada número real está en la lista, y la construcción de un elemento que no se puede estar en la lista (la "diagonal elemento"), que contradice nuestra suposición. En consecuencia, podemos deducir que la negación de la hipótesis: los números reales no numerable.

---

En cuanto a tu segunda pregunta se refiere, he aquí una primera puñalada. Si has perdido tu intención, hágamelo saber y voy a tratar de replantear como sea necesario.

Para la construcción de la diagonal elemento, el "contar" no es necesario: no tenemos que ir físicamente a través de cada tupla mencionados por $f$. Cada dígito de $s_f$ está dado por su definición ($f$).

Pero realmente tu pregunta es contestada sólo por considerar el conjunto de $\mathbb{N}$ con su orden natural: tiene un primer elemento, $0$, pero no el último elemento. Así que incluso si fuera importante que nos iterar a través de cada elemento, no habría ningún elemento sin un predecesor (aparte de $0$). Por lo que el escenario sugiere usted no puede suceder.

Answer 3

"Petición de principio" significa "suponiendo que lo que usted está tratando de demostrar." La prueba por contradicción es diferente. Usted asume la negación de lo que están tratando de probar, y luego derivar una contradicción. Usted puede entonces concluir que lo que usted está tratando de demostrar que debe ser correcta, a partir de su negación conduce a un problema.

Answer 4

Supongamos que yo podría lista de todos los números Reales en una lista para que cada uno tenía un número de serie que fue un entero positivo.

Entonces yo podría construir un número no está en la lista por tomar el opuesto de cada elemento diagonal en turno. Comprobar esto se puede hacer - es bien definido.

Verificación: lo que tenemos es un número, y que debería estar en la lista. Pero podemos ver que no es - no está de acuerdo con cada número en la lista por la forma en que hemos construido, y que es una contradicción.

Así que algo debe estar mal - se puede ver que, por lo que usted ha escrito. Y que sugieren la resolución diciendo que la diagonal número no puede ser construida. Pero ese no puede ser el error, porque la receta por que es tan fácil, y claramente está bien definido. No existe una manera de tener un número de la lista que impide la receta.

También podemos comprobar fácilmente que lo que se construye es un número y que debería estar en la lista.

Así que la única cosa que puede haber ido mal, es la hipótesis original - que debe ser malo. Y debido a que no especifica ningún método en particular para la creación de la lista, sólo se supone que la lista existido, no podemos evitarlo cambio de la lista o por la búsqueda de una astucia método. La única posibilidad que le queda es que no hay tal lista existe.

Answer 5

El comentario de Marc Bennett parece convincente. Sin embargo, hay un aspecto importante, sin embargo, para ser considerado, a saber, que (a veces) un número real puede ser representada por dos diferentes infinito de cadenas. Para ser precisos, una cadena binaria S seguido por 01111111111... representa el mismo número que la cadena binaria S seguido por 100000000000... Esto se puede verificar fácilmente, haciendo un resumen de la infinita cadena de 1.

Ahora vamos a elaborar una lista de los números reales R, representado por las cadenas de S: R(1) = 0.5 S(1) = {1} R(2) = 0.25 S(2) = {0,1} R(3) = 0.75 S(3) = {1,1} R(4) = 0.125 S(4) = {0,0,1} R(5) = 0.375 S(5) = {0,1,1} R(6) = 0.625 S(6) = {1,0,1} R(7) = 0.875 S(7) = {1,1,1} etcétera.

La aplicación de Cantor en diagonal del método, lleva a la construcción de un número real X, representada por la cadena {0,0,1,1,1,1,1,1,1...}. Como se muestra arriba, esta cadena es equivalente a la cadena {0,1,0,0,0,0....} que representa el número real X = 0.25. Y este número está en nuestra lista como la segunda entrada: X = R(2). Así que este es un ejemplo donde la diagonal método falla.