¿Por qué la aritmética de Peano es indecidible?

Question

He leído que la aritmética de Presburger es decidible y aritmética de Peano es indecidible, realmente arithmaetic de Peano extiende aritmética de Presburger sólo con la adición del operador de multiplicación. ¿Alguien por favor me puede dar la idea de 'intutive' detrás de esto?

O probablemente una fórmula en la aritmética de Peano que no puede ser probada. ¿Tiene algo que ver con la paradoja de la auto referencia en Teorema del estado incompleto de Goedel?

Saludos

Answer 1

Esencialmente, sí, pero creo que el undecidability de la aritmética de Peano (en adelante, PA) se sigue de la forma en que la prueba de Gödel del teorema de la incompletitud va, en lugar de ser una consecuencia del hecho de que el PA es incompleta. La prueba (descritas a continuación) empieza mostrando que la PA puede hablar computable de las relaciones, y se va a mostrar de esta manera usted puede construir una improbable frase. Sin embargo, podemos tomar un enfoque diferente para mostrar que la PA es indecidible: si PA puede hablar computable relaciones, entonces se puede formular una frase en el idioma de PA que es verdadera si y sólo si un determinado algoritmo se detiene / no se puede detener. (Brevemente: Un algoritmo es la misma cosa como una computable de la función parcial, y un algoritmo se detiene en algunos de entrada si y sólo si el parcial correspondiente función está definida en esa entrada.) Así que si un algoritmo puede decidir si arbitrarias condenas en PA es comprobable o no, tenemos un algoritmo que resuelve el cese problema... pero hay nonesuch. Así que el punto clave es que la ap es lo suficientemente rico como para hablar de la computación. Un ingrediente esencial para hablar acerca de la computación es la capacidad para codificar un par de números como el número y la capacidad de recuperar el par original a partir de la codificación. No es inmediatamente claro para mí que $+$ es insuficiente para hacer esto, pero es ciertamente plausible que ustedes necesitan, al menos, dos operaciones binarias.

Aquí es un boceto de la prueba de Gödel del primer teorema de la incompletitud: Primero vamos a seleccionar un suficientemente potente teoría de la $T$, por ejemplo, PA, y asumir que es una constante de la teoría, es decir, no prueba una contradicción.

1. Demostramos que podemos codificar las fórmulas y de las pruebas en los modelos de $T$.
2. Nos muestran que $T$ es lo suficientemente potente como para hablar computable de las relaciones.
3. Nos muestran que no es computable en relación $\mathrm{Prf}(m, n)$ que tiene si y sólo si $m$ codifica una prueba válida de la frase codificada por $n$.
4. Lo anterior muestra que existe una computable relación $Q(m, n)$ que tiene si y sólo si $n$ codifica una fórmula $F(-)$ con una variable libre y $m$ ¿ no codifican una prueba válida de $F(n)$.
5. Por lo que podemos definir una fórmula $P(x)$$\forall m. Q(m, x)$. Esto significa $P(x)$ mantiene si y sólo si no hay ninguna prueba válida de $F(x)$, asumiendo $x$ codifica una fórmula $F(-)$ con una variable libre.
6. Pero $P(-)$ es una fórmula con una variable libre, y puede ser codificada por un número $n$. Así es la frase $P(n)$ comprobable o no? Supongamos que se fueron. Entonces, quiere decir $P(n)$ es verdadero, de modo que la teoría afirma que no hay ninguna prueba válida de $P(n)$ - una contradicción.
7. Así que nos vemos forzados a concluir que la sentencia de $P(n)$ no es demostrable. Esta es la sentencia de Gödel que hemos querido demostrar la existencia de, por lo que estamos por hacer.

Nota: yo no he dicho nada acerca de si $P(n)$ es realmente cierto. Resulta que hay algunos sutileza. Gödel de la integridad teorema nos dice que todo lo que puede ser demostrado en un primer orden de teoría es verdadera en todos los modelos de la teoría y de que cada oración que es verdadera en todo modelo de primer orden de la teoría puede ser probada a partir de los axiomas de la teoría. Con algunos de los más fuertes de la consistencia de los supuestos, también se puede mostrar que el $\lnot P(n)$ es también no es demostrable en PA, y esto significa que hay modelos de PA donde $P(n)$ es verdadera y modelos donde es falso.

El punto clave es que las frases "$n$ codifica una fórmula ..." y "$m$ codifica una prueba válida de ..." son estrictamente fuera de la teoría. La interpretación de un número en particular, como una fórmula o una prueba se define externamente, y que sólo se definen para el "estándar" de los números. El resultado de esto es que en un modelo de $\mathcal{M}$ de los PA donde $P(n)$ es falso, hay algunos no estándar número $m \in \mathcal{M}$ $\mathcal{M}$ "cree" es una prueba válida de $P(n)$, pero porque no es estándar, no podemos traducir en una verdadera prueba.

Answer 2

Mientras que esto puede no ser la idea intuitiva de que usted está buscando, voy a notar que las mismas ideas detrás de Gödel prueba de que la Aritmética de Peano es incompleta (es decir, que no son verdaderas sentencias de PA que no puede ser demostrado) también puede ser aplicado para mostrar que la Aritmética de Presburger es 'duro' en un sentido tangible; esencialmente, se puede codificar la multiplicación de los pequeños números suficientes (en concreto, el predicado '$x\times y = z$' con $x$, $y$ y $z$ 'sólo' doblemente exponencial en la longitud de la fórmula) en una fórmula que involucra sólo la adición. Esto significa que si las penas en la Aritmética de Presburger de longitud $n$ podría ser decidido sin multiplicar los números de tamaño de al menos (aproximadamente) $2^{2^n}$, entonces la Aritmética de Presburger sufriría la misma Godelian paradoja de que la Aritmética de Peano hace y estar incompleta. Paul Young escribió un mejor exposición de este para una conferencia hace un par de décadas de lo que puedo dar; echar un vistazo a http://books.google.com/books?id=2vvg3mRzDtwC&pg=PA503&lpg=PA503 para los detalles.

Answer 3

Aritmética de Peano es lo suficientemente fuerte como para razonar sobre máquinas de Turing. Así, si la aritmética de Peano fuera decidible, el problema de Halting sería decidible. Aprendí esencialmente esta idea de Scott Aaronson.

Answer 4

@hardmath: "Es un buen punto, que undecidability de una formales de primer orden de la teoría implica imperfección, pero no a la inversa" - que no es simplemente verdad. El teorema (que es en realidad una fácil consecuencia de Post del teorema) que tenemos aquí es:

Para cualquier FO-teoría T, si T es recursivamente axiomatizable y completo, entonces es decidable.

Esto no significa que un indecidible teoría es necesariamente incompleta - puede ser completo, pero falta recursiva axiomatization. Que, por ejemplo, es el caso de ${Th(N, +, \times, 0, 1)}$. Por otra parte, hay teorías que son recursivas y decidable, pero incompleta, por ejemplo,$T=\{0=0\}$.