El conjunto de enteros impares no es definible en$(\mathbb{Z},+)$ por una fórmula existencial

Question

Me gustaría algún comentario sobre cómo abordar este problema. La parte de la derecha antes de que este problema en mi tarea pide una fórmula existencial que define el conjunto de los números enteros. Por favor, hágamelo saber si mis pensamientos no son correctos o podría ser mejor.

Edit: el lenguaje contiene sólo una función binaria símbolo.

Deje $\phi(v_1)$ ser la fórmula $\exists v_2(v_2+v_2=v_1).$ $\phi(v_1)$ define el conjunto de todos los enteros desde sólo números enteros son divisibles por dos. (no estoy seguro si puedo usar la divisibilidad aquí porque el idioma no tiene brecha símbolo). La negación de la fórmula que define el conjunto de todos los enteros impares. Desde $\lnot \exists v_2(v_2+v_2=v_1) $ es equivalente a $\forall v_2 \lnot (v_2+v_2 = v_1)$, el conjunto de enteros impares no es definible por una fórmula existencial.

Gracias por toda la ayuda de antemano!

Answer 1

Te voy a mostrar el siguiente hecho: si $P(x_1,x_2,...,x_k)$ es cuantificador libre en el lenguaje de la $(\Bbb Z,+)$, entonces para todos los $v_1,...,v_k$ tenemos $P(v_1,...,v_k)\Leftrightarrow P(2v_1,...,2v_k)$. En efecto, por inducción sobre la construcción de un bien fundado fórmulas: fórmula $t_1+...+t_i=t_{i+1}+...+t_j$ es cierto iff $2t_1+...+2t_i=2t_{i+1}+...+2t_j$, debido a la multiplicación por 2 preserva la verdad de tales fórmulas. Además, si $Q(t_1,...,t_i)\Leftrightarrow Q(2t_1,...,2t_i)$$\neg Q(t_1,...,t_i)\Leftrightarrow \neg Q(2t_1,...,2t_i)$, y si también se $R(t_{i+1},...,t_j)\Leftrightarrow R(2t_{i+1},...,2t_j)$,$Q(t_1,...,t_i)\lor r(t_{i+1},...,t_j)\Leftrightarrow Q(2t_1,...,2t_i)\lor R(2t_{i+1},...,2t_j)$. Todos los demás bien fundada fórmulas se puede llegar así.

Ahora supongamos que la fórmula existencial $\exists v_1,...,v_k:P(x,v_1,...,v_k)$ define el conjunto de los números impares. A continuación, podemos encontrar $t_1,...,t_i$, de modo que $P(1,t_1,...,t_i)$. Pero, por encima, luego tenemos a $P(2,2t_1,...,2t_i)$, lo $\exists v_1,...,v_k:P(2,v_1,...,v_k)$, lo que significa que $2$ es número impar. Contradicción.

Answer 2

($\#$) Recuerde que embeddings preservar la verdad de las fórmulas existenciales.

Supongamos que para una contradicción que$\varphi(x)\in L$ define el conjunto de enteros impares. El mapa$f:x\mapsto 2x$ es una incorporación de$(\mathbb{Z},+)$ en sí mismo. Por ($\#$) por encima de$\mathbb{Z}\models\phi(n)$ implica$\mathbb{Z}\models\phi(fn)$ para cada$n\in\mathbb{Z}$. Contradicción.