Diagonal lema dice que en una teoría con suficiente supuesto para cualquier fórmula $A(x)$ existe una sentencia de $B$ tal que $B$ $\iff$ $A(\#(B))$ es un teorema en la teoría, en la que $\#(B)$ representa el número de Gödel de número de $B$. Yo no tengo ningún problema con la prueba de este lema, pero te pido que me des un ejemplo concreto de aplicación de este lema para una determinada fórmula $A(x)$ tal como : $x$ es un número par. Quiero que este ejemplo para mejorar mi intuición de este lema. Quiero preguntarle ¿cuál es la idea intuitiva detrás de este lema? es decir, a pesar de su prueba matemática, es este lema esperables e intuitivo para que cualquier codificación de fórmulas $B$ $\iff$ $A(\#(B))$ es un teorema en el que la teoría o este lema no es esperable e intuitiva? Por favor explique de forma más intuitiva. Muchas gracias.
Respuestas
¿Demasiados anuncios?
Con :
dame un ejemplo concreto de ...
estás menaing : escribir la fórmula ?
Si es así, como por Asaf'answer, tenemos que empezar con un lenguaje y una codificación de la misma.
Podemos "jugar con" el primer paso de la prueba, tratando de "mejorar nuestra intuición".
Ver Herbert Enderton, Matemáticas, Introducción a la Lógica (2º - 2001).
Consulte la página 235 para la diagonal (o de punto fijo) lema :
Punto fijo Lema : Dado cualquier fórmula $\beta$ en el que sólo se $v_1$ se produce libre, podemos encontrar una frase $\sigma$ tal que $\vdash \sigma \leftrightarrow \beta(S^{\ulcorner \sigma \urcorner}0)$.
Consulte la página 183 para el lenguaje de las $\mathcal N$ :
$\mathcal N = (\mathbb N; 0, S, <, +, \cdot, E)$ (donde $E$ es sinónimo de "exponenciación").
Consulte la página 225 para la codificación :
$0$ es "$\forall$"; $1$ es "("; $2$ es $0$; $3$ es ")"; $4$ es $S$; $5$ es $\lnot$; $6$ es "<"; $7$ es "$\rightarrow$"; $8$ es "$+$"; $9$ es "$=$"; $10$ es "$\cdot$"; $11$ es "$v_1$"; $12$ es "$E$" e $13$, ... son "$v_2$", ...
Véase la parte inferior de la página 225 para el ejemplo de la "codificación" : $(\exists v_3 v_3 = 0)$ cual es (en "primitivo" de la notación) : $(\lnot \forall v_3 (\lnot = v_30))$.
Tenemos que $\ulcorner (\lnot \forall v_3 (\lnot = v_30)) \urcorner = 2^2 \cdot 3^6 \cdot 5^1 \cdot 7^{16} \cdot 11^2 \cdot 13^6 \cdot 17^{10} \cdot 19^{16} \cdot 23^3 \cdot 29^4 \cdot 31^4$.
Este es un gran número, siendo del orden de $1.3 \times 10^{75}$.
Ahora tenemos a "codificar" la fórmula $\beta := Even(v_1)$.
Pero :
$Even(x)$ $\exists y (x = y \cdot 2)$;
así, tenemos a "codificar" : $(\exists v_2 v_1 = v_2 \cdot SS0)$ es decir :
$(\lnot \forall v_2 (\lnot = v_1 \cdot v_2 SS0))$.
Su codificación será : $2^2 \cdot 3^6 \cdot 5^1 \cdot 7^{14} \cdot 11^2 \cdot 13^6 \cdot 17^{10} \cdot 19^{14} \cdot 23^{12} \cdot 29^{11} \cdot 31^{14} \cdot 37^5 \cdot 39^5 \cdot 43^3 \cdot 47^4 \cdot 53^4$,
... Espero.
Hormiga esta fue la "fácil" de la parte : hemos calculado $\ulcorner \beta \urcorner$, es decir, el llamado número de Gödel de la fórmula de $\beta$.
En este punto, ya podemos probar el "ejercicio mental" de considerar la fórmula $\beta(v_1) := Even(v_1)$, y el uso de su número de Gödel $\ulcorner \beta \urcorner$ acaba de definir a "calcular" el número de Gödel de $\beta(\ulcorner \beta \urcorner)$.
Pero esto no es suficiente. Para la prueba de la diagonal lema, tenemos que construir la fórmula [ver página 235] :
(*) $\forall v_3(\theta(v_1, v_1, v_3) \rightarrow \beta(v_3))$
donde $\theta$ [véase página 228] es la fórmula de que "funcionalmente representan" la "sustitución" de la función $S_b$ tal que para un término o una fórmula $\alpha$, la variable $x$, y el plazo $t$ :
$S_b (\ulcorner \alpha \urcorner, \ulcorner x \urcorner, \ulcorner t \urcorner) = \ulcorner \alpha(x/t) \urcorner)$.
Tenemos que tener en cuenta que la fórmula anterior sólo ha $v_1$ gratis. Por lo tanto, se define en $\mathcal N$ un conjunto al que $\ulcorner \alpha \urcorner$ pertenece iff $\ulcorner \alpha(S^{\ulcorner \alpha \urcorner}0) \urcorner$ es en el conjunto definido por $\beta$.
Deje $q$ el número de Gödel de (*). Deje $\sigma$$\forall v_3[\theta (S^q0, S^q0, v_3) \rightarrow \beta(v_3)]$.
Por lo tanto $\sigma$ se obtiene a partir de (*) por la sustitución de $v_1$,$S^q0$.
¿Qué hemos logrado hasta ahora ?
Hemos demostrado que, para cada expresión del sistema, podemos "eficazmente" producir una muy larga fórmula de la teoría de los números que - en principio - se puede "calcular" con el fin de encontrar la "enorme" número de Gödel de la expresión original.
El sistema es un lenguaje para la teoría de números y el "truco" de la codificación (o arithmetization de sintaxis), nos permite utilizar la capacidad expresiva de que el sistema "hablar de" hechos sobre el propio sistema.
Simplificando mucho, podemos decir que la forma en que el sistema de "hablar de" es a través de la informática de los números.
Por lo tanto, la codificación se traduce hechos "acerca de" del sistema, como el "provability" relación en los hechos "en" el sistema, creo.e.los cálculos.
La diagonal lema que nos permite encontrar (me.e.para "calcular" el valor de la codificación de), para cualquier fórmula $\beta$ en el que sólo se $v_1$ se produce libre, una frase $\sigma$ ...
Agregó
Creo que no hay nada intuitiva en la prueba del lema; de hecho, fue necesaria la presencia de un genio como Gödel tener la intuición de que podemos "codificar" hechos sobre el sistema en el propio sistema.
Pero la intuición debe ser "entrenados" a través de la larga y tediosa la prueba de todas las preliminares de los lemas necesarios para completar la tarea de codificación.
En el caso de que $A(n)$ significa que $n$ es incluso hay dos opciones:
- La verdadera oración cuyo número de Gödel es aún.
- Falso frase cuya Gödel número es impar.
Por supuesto, esto depende de la codificación de las fórmulas en los números, ya que hay muchas formas de hacerlo, hay muchas maneras de resolver esto.
El lema asegura que, independientemente de la forma en que se codificaba las fórmulas (siempre que sea razonable), no será una verdadera sentencia cuyo código es o, incluso, habrá una falsa sentencia cuyo código es impar. Y muy posiblemente, las dos opciones puede ser cierto.
Yo no creo que exista fácil intuición que guía a una prueba de la diagonal lema (por ejemplo, el sobre en la Wikipedia). Esta prueba es simplemente una de esas cosas que parece aparecer de la nada; parece increíble que las obras de construcción; y después de aprender el método que usted realmente sabe más de lo que hizo antes.
Aunque los rudimentos de la diagonal lema en el trabajo de Gödel, la diagonal lema sí se demostró por primera vez por Carnap, no por Gödel. Más de la historia, y referencias, se dan en un comentario por Pedro Milne aquí. Creo que esto pone de relieve que , incluso cuando los teoremas de incompletitud fueron probada por primera vez la diagonal lema no era una obvia la intuición. El lema fue descubierto más tarde en la reflexión. Así que no hay razón para pensar que, como estudiante, que el lema será totalmente intuitivo a primera.
