What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would a nonstandard amount of time be like?

Solution 1:

Peano arithmetic is a first-order theory, and therefore if it has an infinite model---and it has---then it has models of every cardinality.

Not only that, because it has a model which is pointwise definable (every element is definable), then there are non-isomorphic countable models. Which means that you can find models which are not the standard model already at the countable cardinality.

What do these models look like? Well, it's kinda hard to explain. They all have an initial segment that looks like the natural numbers. That much is easy to prove. Also not hard to show is that the rest of the model can be decomposed into $\Bbb Z$-chains. Namely, if $c$ is a non-standard number, then it has a predecessor (since Peano proves that every non-zero element is a successor). So we can define $f(k)=S^k(c)$, as an order isomorphism between the "chunk" of the model that $x$ lives in.

Harder to prove, but still not impossible, is that at least for the countable parts, the models all look the same as far as the order go, they all have an initial segment of $\Bbb N$, followed by $\Bbb{Q\times Z}$ ordered lexicographically.

To produce such models you can use three standard methods:

1. Compactness. Add a constant $c$, require it to be larger than any numeral, by compactness this is a consistent theory so it has a model. This model cannot be the standard model, because it has an element larger than all the numerals.

2. Ultrapowers. Take a free ultrafilter $\mathcal U$ over $\Bbb N$, and consider the ultrapower $\Bbb{N^N}/\cal U$. Counting arguments will show you that this ultrapower has cardinality $2^{\aleph_0}$, so it is certainly not isomorphic to $\Bbb N$. If you prefer, you can use the fact that $\mathcal U$ is not a countably-complete ultrafilter, and therefore the ultrapower cannot be well-ordered, so without checking for cardinality it cannot be isomorphic to $\Bbb N$.

3. Incompleteness. We know that Peano is not a complete theory. Therefore there are statements which are true in $\Bbb N$, but Peano does not prove. Therefore the negation of such statement is consistent with the rest of the axioms of Peano, and must have a model. But this model cannot be isomorphic to $\Bbb N$. The benefit of this method is that it allows you to obtain very different theories of your models, whereas ultrapowers and compactness arguments tend to result in elementarily equivalent models.

Solution 2:

It should be mentioned that one of the most concrete nonstandard models of PA was developed by Skolem in the 1930s in ZF (without the axiom of choice, unlike the constructions mentioned in the other answer). This is roughly in terms of definable functions on $\mathbb N$ ordered by their asymptotic growth; for details see this 2013 publication in Foundations of Science, Section 3.2, page 272.

Solution 3:

This is a historical footnote to the nice accepted answer above. More precisely, the method in the yellow box in

seems to be already hinted at in Kurt Gödel's review in Zentralblatt, Band 7, Heft 5, of

Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems. Norsk Mat. Forenings Skr., II. Ser. No.1/12, 73-82 (1933).

Strictly speaking, Gödel does not give an argument in the review, only says that Skolem's result follows easily from his own article on the incompleteness theorem; here is Gödel's review of Skolem's paper, with Gödel's hint highlighted in orange (the right-hand side is my translation):

(the above picture larger)