Nombre del Cantor del argumento diagonal

Question

Hay dos resultados famoso asociado con el Cantor de celebración de la diagonal argumento. La primera es la prueba de que los reales son innumerables.

Esto muestra claramente que el mismo nombre de la diagonal argumento en este caso. Sin embargo, me han dicho que la prueba del teorema de Cantor también implica una diagonal argumento. Dado un conjunto $S$, supongamos que existe un bijection $f:S\longrightarrow\ P(S)$ $S$ a su powerset. La construcción del conjunto $$B=\{b\in S\mid b\notin f(b)\}$$ se dice que un argumento diagonal debido a la doble aparición de $b$$b\notin f(b)$. Ahora, no estoy exactamente seguro de por qué esto se llama un argumento diagonal. Hay una representación geométrica de este argumento como la de la foto de arriba? O es simplemente una analogía a la primera prueba a usar la idea de la construcción de un testigo para mostrar $f$ no es surjective?

Answer 1

Diagonalización es un método común en las matemáticas. Esencialmente, esto significa que "escribir en un infinito de la matriz y, a continuación, caminar a lo largo de una coordenada de la línea de los enfoques infinito en ambos ejes".

El "Cantor de la diagonal argumento", dice escribir los números en una matriz, y tomar la $n$-ésimo número de $n$-ésimo dígito, y el cambio.

El teorema de Cantor es una forma de diagonalización porque lo que realmente hace es escribir la función en la forma de la matriz:

$$\begin{array}{|c|c|c|c|c} &x_1 & x_2 & x_3 & \ldots\\ \hline f(x_1)\\ \hline f(x_2)\\ \hline f(x_3)\\ \hline \vdots \end{array}$$

Ahora podemos escribir la $1$ en las celdas en blanco si $x_i\in f(x_j)$, e $0$ lo contrario. La prueba se toma el conjunto de todos los $x\in X$ tal que $x\notin f(x)$, Que es caminar a lo largo de la diagonal, y tomar las coordenadas que dan $0$. Esto define un subconjunto de a $X$ que no está en el rango de $f$, muy similar a la diagonal argumento da un número que no está en la enumeración.

---

Similar, pero con diferentes argumentos que se dan a la hora de mostrar los números reales pueden ser definidas como secuencias de Cauchy de racionales a algunos de equivalencia, y que este es un completo espacio. Tomamos una secuencia de Cauchy de secuencias de Cauchy y tomamos la $k$-ésimo elemento de la $k$-ésimo de la secuencia.

Por supuesto, esto no es exactamente lo que hacemos, pero es lo suficientemente cerca. Necesitamos juguete con $\epsilon-\delta$ y definir la diagonal vamos a caminar por la $k$-ésimo elemento que desee tomar parte $x^k_j$ $j$ lo suficientemente grande, así y así...)

Answer 2

SUGERENCIA $\ $ ver la analogía, representan subconjuntos de bits en vectores, por lo que los i-ésimos de los elementos del vector es $1$ si la i-esima elemento está en el subconjunto, y 0 si no. Entonces las filas de la matriz son los bits vectores de los subconjuntos, y dijo: powerset de diagonalización corresponde simplemente a la posibilidad de complementar la diagonal de bits en el de los bits de la matriz.

Ignorando el pedido, se reduce a un simple hecho de que cuando tenemos al menos como muchos de los "componentes" (índices) como "objetos" (vectores), entonces siempre se puede construir un objeto diferente simplemente asegurándose de que difiere de cada objeto en al menos uno de los componentes. La introducción de un pedido simplemente proporciona una vívida forma de visualizar esto de la construcción, mediante la colocación de los cambios de los componentes a lo largo de la diagonal.

Answer 3

Si el primer 'diagonalización' se exhibió está sobre el alfabeto $\{0,1\}$ $S=\mathbb{N}$ en el segundo 'diagonalización', a continuación, los argumentos son los mismos. Para ver esto, observe que cada número real en $[0,1]$ corresponde a un conjunto de números naturales cuando se ve como una función característica del conjunto. El (función característica de la) set $B$ es entonces exactamente el nuevo número real generado en la primera diagonal argumento. Usted debe trabajar los detalles.

Answer 4

La prueba de que el primer resultado que dan menciona

el 1er dígito del número 1, y
el 2º dígito del número 2, y
el 3er dígito de la 3ª serie, y
el 4 de ditit de la 4ª número, y

........ etc. Vea el "doble aparición" de algo aquí. También se puede ver que el primer dígito del primer número no es el mismo como el primer dígito del número que usted está construyendo, y el segundo dígito del segundo número no es el mismo como el segundo dígito del número que usted está construyendo y así sucesivamente. Lo mismo sucede con la segunda prueba.