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?

• Unfortunately it's quite hard to point to or describe a nonstandard model, because of Tennenbaum's Theorem: no countable nonstandard model of Peano arithmetic (PA) can be recursive. Even more: the $+$ and $\times$ operations can't be recursive. So... you can see why your question is very challenging. A nonstandard amount of time would be... very long: infinitely long, as it comes after every finite number of time units $0, 1, 2, ... 17, ... 10^{10}, ...$. Jun 6, 2016 at 8:01
• I am not sure that I agree with the duplicate here. It's one thing to ask for a countable elementary extension, and it's another to ask about non-standard models in general. I think they are sufficiently different, as witnessed by the very different answers. Jun 7, 2016 at 6:18
• "What would a nonstandard amount of time be like?" depends on which nonstandard model. If its elementary equivalent to the standard model, you won't even notice. If not, all sorts of crazy things could happen, like you proving PA inconsistent or something. Nov 16, 2017 at 21:19

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.

• You need to end up with a model of Peano. Since $c$ is not a numeral, it will have successors and predecessors, and they will have products and differences and factorials and so on and so forth. You end up adding a whole lot. Jun 6, 2016 at 8:16
• I'm not sure what you mean by that. But probably you are thinking about ordered sets and not models of arithmetic. Jun 6, 2016 at 10:59
• @Bakuriu: But this is not a model of arithmetic. Just a linear order. Jun 6, 2016 at 11:10
• @Bakuriu To see that this can't possibly work for models of arithmetic, consider the sentence "$\forall x\exists y(x=y+y \vee x=y+y+1)$." This sentence (and others) shows that $\mathbb{N}+\mathbb{Z}$ cannot be the underlying order-type of any model of PA (or much less, even)! In fact, we can prove that the underlying order-type of any (countable) nonstandard model of $PA$ is $\mathbb{N}+\mathbb{Z}\cdot\mathbb{Q}$. Even though this order has computable copies, though, doesn't mean that any of its expansions to a model of arithmetic do! Jun 6, 2016 at 19:20
• @Donkey_2009 I believe you're mixing up the language of first-order PA (which does indeed have "$+$") with the language of second-order PA (which doesn't, and doesn't need it because it uses second-order logic). See en.wikipedia.org/wiki/… (especially second paragraph: "Therefore, the addition and multiplication operations are directly included in the signature of Peano arithmetic"), and note that because of the general badness of second-order logic, when logicians in the modern era say "PA" they almost always mean first order PA. Aug 4, 2016 at 19:07

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.

• Other than ultrafilters, neither of the other suggestions on my answer requires the axiom of choice. Jan 18, 2018 at 11:43
• Your use of compactness theorem does not specify that you are referring to countable languages (which would of course be sufficient here). The general compactness theorem does require some form of choice. Similar remarks apply to the other possibility which rely on completeness results. Jan 18, 2018 at 12:00
• I am not sure that I understand. Do you claim that you are Skolem? Jan 18, 2018 at 12:07
• Historical footnote: a reference for Skolem's publication from the 1930s is Skolem, Th.: Ü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). Zbl 0007.19305 Jan 29, 2018 at 19:39
• @PeterHeinig, perhaps a more accessible text is Skolem's paper in German from 1934, listed in the bibliography of the article cited in the answer. Jan 30, 2018 at 9:39

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)