FO-definability de los enteros en (Q, +, <)

Question

Con $Q$ el conjunto de los números racionales, me pregunto:

Es el predicado "Int($x$) $\equiv$ $x$ es un número entero" de primer orden definible en $(Q, +, <)$, donde hay una constante símbolo de cada elemento de $P$?

Sé que esto en el caso de la multiplicación es permitido. Supongo que el hecho de que $<$ es densa implicaría una respuesta negativa a esta pregunta, a través de un EF juego tal vez; hay una estructura similar, con una densa orden, pero con Int($x$) FO-definible?

Answer 1

Esta es una pregunta muy interesante.

La respuesta es no.

En primer lugar, afirmo que la teoría de la estructura $\langle\mathbb{Q},+,\lt\rangle$, admite la eliminación de cuantificadores. Es decir, cada formula $\varphi(\vec x)$ en este lenguaje es el equivalente de esta teoría a un cuantificador fórmula libre. Esto puede ser demostrado por una fuerza bruta de las manos-en la inducción sobre las fórmulas. Permítanme simplemente esbozar el argumento. Es cierto que ya para las fórmulas atómicas, y la propiedad de ser equivalente a un cuantificador libre de fórmulas es conservado por los operadores Booleanos. Así que considere la posibilidad de una fórmula de la forma $\exists x\varphi(x,\vec z)$, donde $\varphi$ es cuantificador. Podemos poner de $\varphi$ en forma normal disyuntiva y, a continuación, distribuir el cuantificador más la disparidad, que reduce al caso en que $\varphi$ es un conjunto de atómica y negada fórmulas atómicas. Podemos suponer que $x$ aparece libremente en cada uno de estos conjuntos (ya que de lo contrario nos puede quitar del alcance del cuantificador). Si una fórmula de la forma $x+y=z$ aparece en $\varphi$, entonces podemos reemplazar todas las ocurrencias de $$ x $z$ y eliminando así la necesidad de cuantificar los más de $x$ (uno también debe posteriormente eliminar el signo menos después de la sustitución, pero esto es fácil por operaciones algebraicas elementales). Podemos hacer esto incluso si $x$ aparece multiplicar, como en $x+x+y=z$, para luego reemplazamos $x$ en todas partes con $(z-y)/2$, pero luego claro la $2$ y el signo menos elemental manipulaciones algebraicas. Por lo tanto, podemos asumir que la igualdad atómica afirmaciones aparecen sólo negativamente en $\varphi$. Todas las otras afirmaciones meramente preocupación por el orden. Tenga en cuenta que un negado el fin de la relación $\neg(u\lt v)$ es equivalente a $v\lt u\v v=u$, y podemos distribuir el cuantificador de nuevo a través de esta tensión dialéctica. Tan negado relaciones de orden no aparecen en $\varphi$. La atómica fin de que las fórmulas de la forma $x+y\lt u+v$ y así sucesivamente. Podemos cancelar similar variables en cada lado, y por lo que $x$ sólo aparece en uno de los lados. Permitiendo menos, vemos que cada conjunto fórmula en $\varphi$ dice que $a\cdot x\neq t$ o que $b\cdot x\lt s$ o que $u\lt c\cdot x$, para algunos de los términos $t,s,u$, de los cuales $+$ e $-$ puede aparecer, y donde $a$, $b$ y $c$ son fijos entero positivo constantes. Por el temporal que permite racional constante coeficientes, podemos mover estos coeficientes para el otro lado, lejos de la $x$. Por lo tanto, la afirmación de $\exists x\,\varphi(x,\vec t,\vec s,\vec u)$ es equivalente a la afirmación de que cada $\frac{1}{c}u$ es menos de $\frac 1b s$. Podemos, a continuación, desactive la introdujo racional constante múltiplos multiplicando por (lo que significa que añadir que muchas veces, en el otro lado). Claramente, si $x$ existe, entonces este será el caso, y si este es el caso, entonces no va a ser de $x$'s en el medio, y así infinitamente muchos, así que al menos uno de ellos será desigual a los $t$s'. Esta última afirmación puede ser re-expresado sin menos, y por lo tanto el original afirmación es equivalente a un cuantificador libre de afirmación. De modo que la teoría admite la eliminación de cuantificadores.

Ahora sigue que la definibles clases están todos definidos por el cuantificador libre de fórmulas. Por inducción, es fácil ver que cualquier clase será una unión finita de intervalos, y así la clase de los enteros no es definible.