¿Qué se entiende por "diagonalización argumento"?

Question

De La Wikipedia:

Una variedad de diagonal argumentos son utilizados en matemáticas.

• Cantor de la diagonal argumento
• El teorema de Cantor
• Detener problema
• Diagonal lema

Además de los anteriores cuatro ejemplos, hay otro que yo he encontrado en un blog. De demostrar que "si una secuencia de medir las asignaciones converge en la medida, entonces hay una larga convergencia de una.e.", la construcción de la larga es también llamado de diagonalización:

El método para establecer este resultado es bastante típico de tales argumentos: dependemos de diagonalización junto con el control que Borel-Cantelli nos da. Deje $f_n$ ser una secuencia que converge en medida a $f$. Esto significa que para cualquier n tenemos una $f_{m_n}$ con $\mu(|f_{m_n} - f| > 1/n) < 2^{-n} $. La aplicación de Borel-Cantelli a la secuencia de conjuntos de $A_n = \{x | |f_{m_n}(x) - f(x)| > 1/n\}$ rendimientos $\mu(\limsup_m \cup_{n=m}^\infty A_n) = 0$. Pero esto es simplemente decir que el conjunto de puntos en que $f_{m_n}$ no concurre $f$ ha medir el $0$.

Como alguien que no ha estado muy expuesto a los "diagonalización argumentos", me pregunto si los ejemplos anteriores tienen algo en común, por lo que podemos responder a lo que "diagonalización argumento de que" es y qué tipos de problemas puede ayudar a resolver?

Answer 1

Alguien con más experiencia pueden ser mejor equipados para hacer frente a esta cuestión, pero aquí es mi punto de vista. "En Diagonal argumentos" a menudo se invoca cuando trato con las funciones o los mapas. Con el fin de demostrar la existencia o la no existencia de un cierto tipo de mapa, podemos crear una gran variedad de todas las posibles entradas y salidas. Moviéndose a lo largo de la diagonal, vamos a usar un auto-referencial de la construcción para introducir un objeto que no puede estar en la lista, y el objeto deseado es obtenido.

Cantor de la Diagonal Argumento: Los mapas son elementos en $\mathbb{N}^{\mathbb{N}} = \mathbb{R}$. La diagonalización se realiza mediante el cambio de un elemento en cada diagonal de la entrada.

Detener Problema: Los mapas son funciones recursivas parciales. El asesino de $K$ programa codifica la diagonalización.

Diagonal Lema / Punto Fijo Lema: Los mapas son fórmulas, con entrada y los códigos de las sentencias. La diagonalización se logra por una confusa auto-referencial de la construcción.

El Cantor del Teorema de ($|A| < |P(A)|$) : Los mapas son las correspondencias entre los elementos de las $A$ y elementos en $P(A)$. Diagonalización se logra mediante la consideración de un auto-referencial subconjunto en $P(A)$ que nada mapa.

Answer 2

Sí, yo consideraría la "diagonal argumento de" un general de la prueba técnica de construcción, similar a la de, digamos, el principio del palomar o de otros principios combinatorios.

Tal vez el más general de la forma de la diagonal argumento es el siguiente:

Teorema: Vamos a $X$ ser un conjunto con más de un miembro, vamos a $I$ ser un conjunto no vacío, y deje $X^I$ denota el conjunto de funciones de$I$$X$. Entonces no existe ningún surjection de$I$$X^I$.

Prueba: Vamos a $f$ ser una función de$I$$X^I$, y deje $a$ $b$ ser miembros distintos de $X$. Para los métodos de representación de la conveniencia, vamos a $f_i$ denotar la función de $f(i)$. Construimos una función de $g \in X^I$ como sigue:

$$g(i) = \begin{cases} a & \text{if }f_i(i) \ne a \\ b & \text{if }f_i(i) = a \end{cases}$$

Por construcción, por cada $i \in I$, $g(i) \ne f_i(i)$, y por lo tanto $g \ne f_i$. Por lo tanto, $g$ no está en la imagen de $f$, y por lo tanto $f$ no es un surjection. $\square$

Mediante la configuración de un bijection entre el powerset $\mathcal P(I)$ y el conjunto de $\{0,1\}^I$ (a veces escrito como $2^I$), también obtenemos el siguiente corolario:

Corolario: Si $I$ no está vacía, no existe ningún surjection de$I$$\mathcal P(I)$.

Una característica interesante de esta forma particular de la diagonal argumento es que hace muy pocos lógico o supuestos teóricos: por ejemplo, no utilice la prueba por contradicción o hacer cualquier referencia a las cardinalidades. Por lo tanto, funciona incluso en muchos bicho raro versiones de la lógica y teoría de conjuntos que algunas personas que ocasionalmente considerar. Sin embargo, en el estándar de la teoría de conjuntos, el teorema anterior se puede dar más escueta forma:

Corolario: Si $I$ es no vacío y $X$ tiene más de un miembro, a continuación, $X^I$ ha estrictamente mayor cardinalidad de a $I$. También, si $I$ no está vacía, $\mathcal P(I)$ ha estrictamente mayor cardinalidad de a $I$.

Answer 3

El Arzelà teorema de Ascoli es un ejemplo de esto. Ver http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem. Lo que es interesante acerca de este ejemplo es que este teorema tiene aplicaciones en ecuaciones diferenciales. Un ejemplo de una aplicación es el teorema de que en una superficie hiperbólica, todo libre homotopy clase de bucles tiene una única geodésica en esa clase.