Tengo una pregunta acerca de modelos no estándar de la Aritmética de Presburger. He leído que un ejemplo de un modelo no estándar es el conjunto de polinomios con coeficientes racionales positivos coeficiente inicial y un (positivo) entero coeficiente constante. Es evidente que todos los otros axiomas de la inducción axioma esquema satified; pero, ¿cómo puede uno demostrar que el axioma de inducción se mantiene?
Respuesta
¿Demasiados anuncios?
sewo
Puntos
58
Como usted lo describe,
el conjunto de polinomios con coeficientes racionales positivos coeficiente inicial y un (positivo) entero coeficiente constante
es no un modelo de la aritmética de Presburger. La aritmética de Presburger demuestra $$ \forall a : a=0 \lor a=1 \lor \exists b: a=b+1+1 $$ pero esto no es cierto en el modelo para $a=X+1$ (donde $X$ es la formal variable en el polinomio).
Creo que usted podría conseguir un modelo si se permite que el término constante a ser negativo cuando no es el primer coeficiente. En ese caso $X$ intuitivamente modelo de "infinito", y $X^2$ aún más infinito y así sucesivamente. A continuación, una más o menos estándar compacidad argumento muestra que la aritmética de Presburger debe tener un modelo que contiene , al menos, todos estos elementos, pero no me pida la prueba de que hay suficiente de ellos para constituir un modelo.
Una prueba de que probablemente no intenta verificar cada axioma directamente, pero en lugar de demostrar que el modelo es elementarily equivalente a la ordinaria de los naturales, en relación a las restricciones del lenguaje de la Aritmética de Presburger. Alguna forma de eliminación de cuantificadores pueden trabajar.
