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?

  • 5
    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}, ... $. – BrianO Jun 6 '16 at 8:01
  • 1
    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. – Asaf Karagila Jun 7 '16 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. – PyRulez Nov 16 '17 at 21:19
up vote 27 down vote accepted

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.

  • 2
    Wow. What a fantastic post, thank you. – user223391 Jun 6 '16 at 7:59
  • 3
    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. – Asaf Karagila Jun 6 '16 at 8:16
  • 3
    I'm not sure what you mean by that. But probably you are thinking about ordered sets and not models of arithmetic. – Asaf Karagila Jun 6 '16 at 10:59
  • 3
    @Bakuriu: But this is not a model of arithmetic. Just a linear order. – Asaf Karagila Jun 6 '16 at 11:10
  • 4
    @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! – Noah Schweber Jun 6 '16 at 19:20

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. – Asaf Karagila Jan 18 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. – Mikhail Katz Jan 18 at 12:00
  • 1
    I am not sure that I understand. Do you claim that you are Skolem? – Asaf Karagila Jan 18 at 12:07
  • 2
    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 – Peter Heinig Jan 29 at 19:39
  • 1
    @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. – Mikhail Katz Jan 30 at 9:39

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

enter image description here

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):

enter image description here

(the above picture larger)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.