¿Fórmula de primer orden en el lenguaje de primer orden, otro lenguaje abierto donde verdadera equivalencia en los productos naturales?

Question

Para cualquier primer orden fórmula $X$ en el lenguaje de primer orden $\langle 0, S, \le\rangle$ (posiblemente con variables libres) ¿necesariamente existe otro % fórmula abierto $Y$tal que el % de equivalencia $X \equiv Y$es cierto en el conjunto de todos los números enteros no negativos?

Answer 1

Sí, esto es cierto. La estructura $(\mathbb{N}; 0, S, \le)$ admite eliminación del cuantificador, y la prueba de esto es a través de la inducción en la complejidad de $X$. Un ejemplo de tal prueba, vea este, que pasa a través de la prueba de eliminación del cuantificador para una versión de la aritmética de Presburger.