Prueba $y = x + 1$ ' t tienen un fórmula cuantificador-libre en $(\mathbb{Z}, =, <)$

Question

Suponga que la firma es $(\mathbb{Z}, =, <)$ natural con la interpretación, y considerar si el predicado $y = x + 1$ es representable como un cuantificador fórmula libre en esta interpretación.

En primer lugar, claramente, es representable con cuantificadores: $x < y \land \forall z (x < z \rightarrow (y = z \lor y < z))$.

Por otro lado, de forma intuitiva, cualquier cuantificador fórmula libre es sólo una combinación booleana de fórmulas atómicas de la forma $x_i = x_j$ o $x_i < x_j$ (donde $x_i, x_j$ son todos bien $x$ o $y$), y desde cualquier fórmula es, por definición, finito, simplemente no hay suficiente potencia expresiva a enumerar todas las $(x, x+1)$ pares. Pero cómo probar esto rigurosamente?

Answer 1

Cuantificador libre de fórmulas se conservan (y reflejado) por incrustaciones. Es decir, si $M$ $N$ $L$- estructuras, $f\colon M\to N$ es una incrustación, $\varphi(x_1,\dots,x_n)$ es un cuantificador de fórmula libre, y $a_1,\dots,a_n$ es una tupla de $M$, $$M\models \varphi(a_1,\dots,a_n) \iff N\models \varphi(f(a_1),\dots,f(a_n)).$$

Esto es fácil de demostrar: se sigue directamente de la definición de la incrustación de al $\varphi$ es una fórmula atómica, y, a continuación, proceder por inducción sobre la complejidad de $\varphi$.

Ahora el mapa $x\mapsto 2x$ es una incrustación $(\mathbb{Z},=,<)\to (\mathbb{Z},=,<)$, pero no conserva la relación $y = x+1$, por lo que esta relación no es cuantificador-libre definible.