Set of odd integers is not definable in $(\mathbb{Z},+)$ by an existential formula

Question

I would like some comments on how I approach this problem. The part right before this problem in my homework asks for an existential formula that defines the set of even integers. Please let me know if my thoughts are not correct or could be better.

Edit: the language contains just one binary function symbol.

Let $\phi(v_1)$ be the formula $\exists v_2(v_2+v_2=v_1).$ Then $\phi(v_1)$ defines the set of all even integers since only even integers are divisible by two. (not sure if I can use divisibility here because language has no divide symbol.) The negation of the formula thus defines the set of all odd integers. Since $\lnot \exists v_2(v_2+v_2=v_1) $ is equivalent to $\forall v_2 \lnot (v_2+v_2 = v_1)$, the set of odd integers is not definable by an existential formula.

Thanks for all help in advance!

Answer 1

I'll show the following fact: if $P(x_1,x_2,...,x_k)$ is quantifier free in the language of $(\Bbb Z,+)$, then for all $v_1,...,v_k$ we have $P(v_1,...,v_k)\Leftrightarrow P(2v_1,...,2v_k)$. Indeed, by induction on construction of well-founded formulas: formula $t_1+...+t_i=t_{i+1}+...+t_j$ is true iff $2t_1+...+2t_i=2t_{i+1}+...+2t_j$ is, because multiplying by 2 preserves truth of such formula. Further, if $Q(t_1,...,t_i)\Leftrightarrow Q(2t_1,...,2t_i)$ then $\neg Q(t_1,...,t_i)\Leftrightarrow \neg Q(2t_1,...,2t_i)$, and if also $R(t_{i+1},...,t_j)\Leftrightarrow R(2t_{i+1},...,2t_j)$, then $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)$. All other well-founded formulas can be reached like that.

Now suppose that existential formula $\exists v_1,...,v_k:P(x,v_1,...,v_k)$ defines set of odd numbers. Then we can find $t_1,...,t_i$ so that $P(1,t_1,...,t_i)$. But, by above, then we have $P(2,2t_1,...,2t_i)$, so $\exists v_1,...,v_k:P(2,v_1,...,v_k)$, meaning that $2$ is odd number. Contradiction.

Answer 2

($\#$) Recall that embeddings preserve the truth of existential formulas.

Suppose for a contradiction that $\varphi(x)\in L$ defines the set of odd integers. The map $f:x\mapsto 2x$ is an embedding of $(\mathbb{Z},+)$ into itself. By ($\#$) above $\mathbb{Z}\models\phi(n)$ implies $\mathbb{Z}\models\phi(fn)$ for every $n\in\mathbb{Z}$. Contradiction.