6
$\begingroup$

I have to prove the following statement:

Prove that there is no formula $\psi=\psi(x_0,x_1)$ in the language $\operatorname{Th}((\mathbb{Z},S))$ such that the relation $\{(m,n)\in\mathbb{Z}\times\mathbb{Z}: (\mathbb{Z},S)\models \psi[m,n]\}$ is a linear ordering of $\mathbb{Z}$. Conclude that the relation $<$ on $\mathbb{Z}$ is not definable in the structure $(\mathbb{Z},S)$

Notice that $S$ is the successor function and $\psi(x_0,x_1)$ a formula with two free variables. Can someone help me with this question because I have no idea how to solve this problem. I thought about quantifier elimination, but can you solve this also without quantifier elimination, for example with automorphisms?

1 Answers 1