Nonstandard models of PA with a decidable order relation.

Question

There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright < $ is isomorphic to $(\mathbb{N}, \prec)$, where $\prec$ is the relation defined earlier, and $M \vDash PA$ is countable and nonstandard (which means that $+^M$ and $\cdot^M$ are not recursive for Tennenbaum's theorem). Now, I can't understand how I should define this relation. The standard relation obviously doesn't work, because there would be no isomorphism, but I can't find a suitable one.

Answer 1

Let $M$ be a countable non-standard model. From an order-theoretic point of view, the model consists of a copy of the natural numbers, followed by an ordered set which is isomorphic to $I\times \mathbb{Z}$. Here $I$ is a densely ordered set with no first or last element, $\mathbb{Z}$ has the natural order, and $I\times Z$ is ordered lexicographically.

But all countable densely ordered sets with no first or last element are order-isomorphic to the rationals.

Added: We give more detail on existence of a recursive ordering. For any natural number $n$ (we are including $0$), let the type of $n$ be the kargest $k$ such that $2^k$ divides $n$. We map the type $0$ numbers bijectively to $\mathbb{N}$, the type $1$ numbers bijectively to a copy of $\mathbb{Z}$, the rype $2$ objects bijectively to a copy of $\mathbb{Z}$, and so on.

It remains to define the order. List the rationals in the interval $(0,1)$ as $r_1,r_2, r_2,\dots$. The set non-zero types (previous paragraph) can be bijectively identified with the rationals. Now on the types, define the order inherited from the rationals.