¿Qué es "mágico" acerca de la combinación de adición y multiplicación en aritmética formal?

Question

Goedel la incompletitud nos dice que cualquier sistema que contenga Robinson aritmética es incompleta. OTOH, la Aritmética de Presburger, que contiene sólo el sucesor y, además, es muy completa. Estoy bastante seguro de que he leído que es posible definir una completa aritméticas con sólo sucessor y la multiplicación de los axiomas. Así que esto plantea la pregunta acerca de qué es especial acerca de la combinación de la adición y la multiplicación.

En la revisión de la prueba de Goedel del teorema, pensé que me había situado el punto clave: el $\beta$-función implica tanto la suma y la mutliplication. Sin eso, no podemos llegar a la primitiva recursiva funciones, lo que significa que no podemos arithmetize sintaxis, por lo que no puede formar parte de la Goedel de la frase, y no hay nada que dice que no puede ser demostrado. Esto no es un 100% de satisfacción, sino que hace una cierta cantidad de sentido.

Pero luego me enteré de que no son auto-verificación de teorías que pueden arithmetize sintaxis a pesar de ser mucho más débil que la aritmética de Robinson. De modo que no puede ser buena.

Hay, entonces, una explicación simple de por qué la combinación de la adición y la multiplicación es necesario para la incompletitud para patear en?

Answer 1

Averiguar exactamente cuánto "fuerza" de un sistema necesita tener antes de Gödel se aplica a es una tarea complicada, y un montón de preguntas sobre este tema, tanto aquí en mathoverflow (ver, por ejemplo, esta pregunta o esta otra pregunta).

Sin embargo, no es una ágil respuesta a la pregunta más específica

Hay, entonces, una explicación simple de por qué la combinación de la adición y la multiplicación es necesario para la incompletitud para patear en?

La necesaria (pero no suficiente!) componente de aquí es ser capaz de representar secuencias finitas - esto es necesario incluso para expresar la coherencia del sistema en su propio idioma! Si tenemos tanto la adición y la multiplicación, podemos hacerlo a través de la $\beta$-función de observar (y por cierto, esta es la razón por la que es mucho más fácil demostrar el carácter incompleto de la PA con la exponenciación, desde tirar la exponenciación en la mezcla hace que sea muy fácil de secuencias de código de manera apropiada). Si, sin embargo, sólo tenemos uno de los dos, no podemos; una anterior de matemáticas.stackexchange pregunta demuestra que no hay ninguna vinculación función definible en $(\mathbb{N};+)$, y no es difícil demostrar que el mismo es cierto para $(\mathbb{N}, \times)$.

Esto deja abierta la pregunta de cómo podemos tener teorías que se puede hablar de $+$ $\times$ y sigue evitar Gödel (se nota que me fue muy cuidadoso en decir que las secuencias de codificación no es una condición suficiente para que Gödel para aplicar!). El culpable aquí es que estas teorías puede hablar de $+$$\times$, pero "hechos básicos" sobre estas operaciones no son demostrables en la teoría de la solo - por ejemplo, la teoría no puede demostrar que $\times$ es total! (La forma en que esto funciona sintácticamente es que, en lugar de una operación binaria símbolo, tenemos una relación ternaria símbolo que representa "$a$ veces $b$ es igual a $c$.") Así que, aunque técnicamente correcto decir que una teoría puede hablar de $+$ o $\times$, lo que no significa que lo que tendemos a pensar que esto significa: a grandes rasgos, por Gödel argumento para aplicar necesitamos ser capaces de secuencias de código adecuadamente y demostrar hechos básicos acerca de la (imagen dentro de la teoría de la codificación aparato; y esta es la segunda parte de la auto-comprobación de teorías hábilmente esquivar.