¿Cómo se construye una frase de Godel?

Question

Me estoy perdiendo algo en el argumento de Gödel Primer Teorema de la Incompletitud, y espero que alguien pueda aclarar mi confusión.

Gödel construye una oración que es verdadera iff es improbable. Aquí está mi comprensión de cómo se construye (tomado de Peter Smith):

1. Considere la posibilidad de U(y), con abierta y variable. U(y) se define como "Para todo x, x no codifica para una secuencia de números que constituye una prueba de la diagonalización de la wff codificada por y".
2. La sentencia de Gödel es la diagonalización de la U(y). Sentido, la sentencia de Gödel es "Para todo x, x no codifica para una secuencia de números que constituye una prueba de la diagonalización de la U(y)."

La cosa que estoy teniendo problemas para conseguir mi cabeza alrededor de es este: no es U(y) un enunciado abierto? Sentido, la variable " y " es libre en la U(y). Fue mi entendimiento de que la apertura de las sentencias no son el tipo de cosas que podemos probar o no probar.

Ahora, entiendo que la diagonalización de la U(y) en sí no es un enunciado abierto, ya que es de U(y) como entrada. Aún así, estoy teniendo problemas para entender lo que una prueba de la U(y) o su diagonalización incluso podría parecer. Parece trivial para mí que la diagonalización de una pena no tener una prueba.

Puede alguien comprobar mi entendimiento? Lo que me estoy perdiendo o malentendido? Gracias de antemano.

Answer 1

El real Gödel frase es obtenida por la toma de la fórmula general $U_T(y)$, que tiene una variable libre $y$, y la sustitución de un determinado cerrado plazo (es decir, una expresión de la forma $1+1+\cdots+1$ con un cierto número de 1s) a $y$. El término correspondiente a un número de $n$ podría denotarse $\underline{n}$, $\dot{n}$, o $\ulcorner n \urcorner$ dependiendo del texto que usted use. Voy a utilizar $\ulcorner n \urcorner$, y voy a utilizar $\#(\phi)$ a que se refieren el número de Gödel de una fórmula $\phi$.

En Gödel de la prueba original, la fórmula $U(y)$ es elegido de manera que, en el modelo estándar, para cualquier fórmula $\phi$, $U_T(\ulcorner \#(\phi) \urcorner)$ vale si y sólo si $\phi$ no es demostrable a partir de los axiomas de la teoría de la $T$.

El número de $n$ que está enchufado es elegido de tal manera que ese $U_T(\ulcorner n \urcorner)$ es equivalente, en $T$,$U_T(\ulcorner \#(U_T(\ulcorner{}n\urcorner))\urcorner)$. El hecho de que ese $n$ existe es una consecuencia de la Diagonal Lema.

La sentencia de Gödel se define para ser la sentencia de $U_T(\ulcorner n \urcorner)$. Esto no tiene variables libres debido a que el plazo para $n$ ha sido sustituido por la única variable libre de $U_T(y)$.

Es cierto, por separado, que la prueba usual de los sistemas de primer orden de la lógica de hacer vamos a probar frases abiertas. Resulta que probando un enunciado abierto es esencialmente el mismo como la demostración de su universal de cierre. Pero esto no es realmente importante para el caso que nos ocupa, porque la sentencia de Gödel no tiene variables libres.

Answer 2

De hecho, puede resultar una fórmula abierta. Por ejemplo, $\forall x (x = x)$ puede deducir $x = x$. Aunque no se puede asignar el último un truth-value en la misma forma que para el anterior, todavía se trata de una deducción válida. Si tienes algunas notas o texto de referencia, ver la regla de eliminación universal, dirá precisamente cuando puede eliminar un cuantificador universal y verás en particular que le permite deducir fórmulas abiertas de frases cerradas.