Nonstandard models of PA

Question

Reading The Incompleteness Phenomenon, by Goldstern and Judah, they show there are nonstandard models of PA by adding a constant greater than any natural number. They then show that any countable model consists of the standard naturals followed by a dense linear order of copies of the integers (though we can't find the origin in any of these copies). The demonstration relies on the fact that $\forall a,b [a\lt b\implies \exists c (c+c=a+b \vee c+c=a+S(b))]$ and that every number except $0$ has a predecessor. There is no mention of multiplication in the argument, so we could delete the two multiplication axioms from PA and get the same restriction on the set of models. Does multiplication not restrict the models of PA in any way?

Answer 1

I've heavily edited my original answer. The answer below is really two separate answers, each of which appeals to a different kind of intuition. The first is just about the very broad nature of the question, the idea being that the models-of-arithmetic language just makes things feel mysterious when they really aren't; the second answer goes into more detail, but may be less comprehensible until the first is read.

---

An algebraic take

At its core, here's what's going on:

• We have three "big classes" $X,Y,Z$ with three distinguished subclasses $A\subseteq X,B\subseteq Y,$ and $C\subseteq Z$. We also have "forgetful" maps $f:X\rightarrow Z$, $g:Y\rightarrow Z$, and $h:X\rightarrow Y$.

• We're told that $f[A]=g[B]=C$, and that $h[A]\subseteq B$. However, despite this we can't figure out much about the relationship between $A$ and $B$. (Perhaps it would be more appropriate to say that we can't from this alone figure out much about the relationship between $A$ and $h^{-1}[B]$ or about the relationship between $B$ and $h[A]$.)

Specifically, $X,Y,$ and $Z$ are the classes of ordered semirings, ordered monoids, and linear orders respectively; $A,B$, and $C$ are the classes of countable models of $\mathsf{PA}$, countable models of Presburger arithmetic $\mathsf{Pres}$, and linear orders isomorphic to either $\mathbb{N}$ or $\mathbb{N}+\mathbb{Z}\cdot\mathbb{Q}$ respectively; and $f,g,$ and $h$ are the "underlying order of an ordered ring," "underlying order of an ordered monoid," and "underlying ordered monoid of an ordered ring" constructions, respectively. And indeed the relationship between $A$ and $B$ is extremely complicated, no matter how you cut it.

In particular, the answer to your question (rephrased for clarity)

Does multiplication [...] restrict the models of PA in any way?

is it most certainly does, and we can see this purely combinatorially as the fact that $A$ is "much smaller than" (and more importantly, much more complicated than) $h^{-1}[B]$.

---

A more logic-y flavor

We have to distinguish between a model and one of its reducts. The key passage is:

They then show that any countable model consists of the standard naturals followed by a dense linear order of copies of the integers

That's not quite true! Rather, the underlying linear order of a countable nonstandard model of $\mathsf{PA}$ is isomorphic to $\mathbb{N}+\mathbb{Z}\cdot\mathbb{Q}$. But a model of $\mathsf{PA}$ is much more than just a linear order, and we can't recover that additional structure from the order alone.

For example, let $M$ be a countable nonstandard model of $\mathsf{PA}+Con(\mathsf{PA})$ and let $N$ be a countable (necessarily nonstandard) model of $\mathsf{PA}+\neg Con(\mathsf{PA})$. The "$\{<\}$-reducts" of $M$ and $N$ are isomorphic, but $M$ and $N$ themselves aren't even elementarily equivalent.

So all that is true is that $\mathsf{PA}$ and Presburger arithmetic each have the same ordertypes of countable models. But this is a very weak fact. In particular, it doesn't rule out $(i)$ the existence of countable models of Presburger arithmetic which cannot be expanded to models of $\mathsf{PA}$ or $(ii)$ the existence of countable models of Presburger arithmetic which can be expanded to models of $\mathsf{PA}$ in multiple distinct - even non-isomorphic - ways.

We can prove that $(i)$ holds via computability theory. Presburger arithmetic has computable nonstandard models (e.g. take the $\{+\}$-reduct of the set of polynomials over $\mathbb{Q}$ with nonnegative leading coefficient and constant term in $\mathbb{Z}$). But the $\{+\}$-reduct of a $\mathsf{PA}$-model can never be computable, by Tennenbaum's theorem (note that this uses the stronger version of the theorem).

I don't immediately see how to show that $(ii)$ holds, but if memory serves it does; I'll add the argument (or counter-argument, if I'm wrong) when I find it.