de las matemáticas a la lógica

Question

Cómo se traduce la frase de Godel sobre los números enteros en "Esta frase no es demostrable" y la frase de Rosser en "Si esta frase es demostrable, hay una prueba más corta de su negación".

Si escribo una frase en lógica, ¿cómo se puede traducir en una afirmación sobre los enteros naturales?

¿Qué palabras puedo utilizar para que se pueda traducir en un enunciado matemático sobre los números enteros?

¿Cuál es una forma precisa de traducir enunciados lógicos en enunciados matemáticos sobre números enteros? Por ejemplo, el operador AND y "Esta frase" y "X es demostrable".

Answer 1

Es una historia bastante larga, y la mejor manera de entenderla es probablemente trabajar a través de una demostración en un libro de texto de lógica o en una popularización como Nagel y Newman.

Answer 2

Una herramienta importante utilizada en este tipo de construcciones es La función β de Gödel . También estos artículos de Wikipedia cubren las ideas principales:

Numeración de Gödel

Esquema de la demostración del primer teorema de incompletitud de Gödel

Answer 3

Los puntos principales son estos:

• es necesario tener una formalización completa del lenguaje y del sistema deductivo (es decir, las reglas de deducción)
• una vez que el lenguaje está completamente formalizado se puede definir una codificación que adjunte un número a cualquier declaración formal (aka fórmula )
• una vez formalizado el sistema deductivo y codificado el lenguaje con números, se pueden expresar todas las reglas deductivas como operaciones aritméticas complejas sobre los números-código
• la declaración "de $A$ sigue $B$ a través de las reglas de deducción" puede traducirse ahora en un enunciado aritmético de la forma "a partir del número $Code(A)$ se puede derivar el número $Code(B)$ mediante la aplicación de estas operaciones aritméticas"
• por lo que a estas alturas cualquier afirmación sobre la demostrabilidad de las fórmulas se ha convertido en una afirmación sobre los números y la aritmética.

Para llevar a cabo cada uno de estos pasos es necesario resolver varios problemas técnicos; para más detalles, véanse las referencias anteriores.