Godel demostró que cada sistema lo suficientemente fuerte como para incluir aritmética estándar con multiplicación es incompleta. Pero he leido que los sistemas que no incluyan multiplicación son completos. Pero la multiplicación es simplemente repetida adición. Por lo tanto, ¿cómo puede un sistema ser completa y otros incompleta? Me doy cuenta de que la integridad es demostrable con respecto a la aritmética de Presburger, pero quiero entender por qué. ¿Cuál es la diferencia profunda entre los dos sistemas que permite esto?
Respuesta
¿Demasiados anuncios?
Mark Beadles
Puntos
449
La operación $\times$ no es una operación primitiva en la aritmética de Presburger. Ahora, ciertamente podría definir un convenio donde $\times$ es un símbolo reemplaza con una serie repetida de $+$'s, donde el número de repeticiones es igual a uno de los multiplicands. Por lo $x\times2$ se podría definir como $x+x$, e $x\times3$$x+x+x$, y del mismo modo para 4, etc. Se trata de la etc. ese es el problema.
Tendría que hacer de esta definición un número infinito de veces. El problema es que no hay una regla de inducción, que permite definir $\times$ para todos los posibles multiplicands. Sólo puede definir la multiplicación por un conjunto de constantes. No hay una regla general que permite a decir $x\times y$, para las dos variables$x$$y$.
Aquí es donde la debilidad del sistema de mentiras. El axioma esquema no es lo suficientemente potente como para definir generalizada de la multiplicación de las variables, y por lo tanto no es lo suficientemente potente como para ser sometido a la técnica de Gödel.
