Why does the undefinability proof fail for $\mathbb{N}$ in $(\mathbb{Z}, 0, <)$?

72 Views Asked by At

An exercise asks to prove that:

$\mathbb{N}$ is not definable in $(\mathbb{Z}, <)$, but definable in $(\mathbb{Z}, 0, <)$ (in the first-order logic).

The solution to the former one relies on the theorem that "An automorphism preserves the definable relations". Specifically, consider the automorphism $f(n) = n - 1$ of $\mathbb{Z}$. Because $f(\mathbb{N}) \neq \mathbb{N}$, $\mathbb{N}$ must not be definable in $\mathbb{Z}$.

For the latter one, we can easily define $\mathbb{N}$ as $\{x \mid \varphi(x) \iff (\mathbb{Z, 0 , <}) \models x \ge 0 \}$.


My problem: I can follow the idea of each proof. However, I am confused when putting them together. Specifically, why cannot I apply the "undefinability proof" for the former one to the latter problem, reaching a contradiction? What makes $(\mathbb{Z}, 0, <)$ so distinct from $(\mathbb{Z},<)$, from the perspective of $\mathbb{N}$?

1

There are 1 best solutions below

1
On BEST ANSWER

$f(n) = n-1$ is not an automorphism of $(\Bbb Z,0,<)$ because $f(0) \neq 0$