5
$\begingroup$

I am currently writing a paper on non-standard models of Peano arithmetic and I am having trouble finding references or information that discuss the relative sizes of how many models of Peano arithmetic there are in the standard and the non-standard cases.

I see it quoted all over the place that, "It is familiar that there are continuum-many pairwise non-isomorphic countable models of $\mathsf{PA}$". From this I take it that there are $\mathcal{c}$-many ($\aleph$-many) non-standard models of Peano arithmetic. Where can I find a proof of this fact? How many models of Peano arithmetic are there that are isomorphic to the standard model?

Thank you!

$\endgroup$
3
  • 20
    $\begingroup$ "How many models of Peano arithmetic are there that are isomorphic to the standard model?" One, up to isomorphism. $\endgroup$ Mar 24, 2012 at 19:34
  • 3
    $\begingroup$ Two excellent references: 1. "Models of Peano Arithmetic" by R. Kaye. (In particular, the specific fact you ask for and several variants are discussed there.) 2. "The structure of models of Peano Arithmetic", by R. Kossak and J. Schmerl. $\endgroup$ Mar 24, 2012 at 20:14
  • 2
    $\begingroup$ Samuel, as for your question about how many isomorphic models of the standard model there are, it doesn't have a very useful answer. The simple answer is that there is as many as there are sets (in say ZFC), which is to say the class of standard models of PA is a proper class. For each set $A$ just consider the model of pairs $(n,A)$ where each $n$ is a standard natural number (properly coded). With an appropriate multiplication and addition intepretation this is a model of PA. That is why we usually count models (or algebraic structures) up to isomorphism only. $\endgroup$
    – Jason Rute
    Mar 25, 2012 at 15:44

2 Answers 2

17
$\begingroup$

Here is another way to do it.

By the Gödel-Rosser theorem, there are continuum many distinct consistent completions of PA. One can see this by building a tree of finite extensions of PA, using the Gödel-Rosser theorem at each node to branch with the Rosser sentence or its negation relative to that theory (and also deciding the $n^{\rm th}$ sentence), so that every branch through the tree is a complete consistent extension of PA. Every such consistent completion of PA has a countable model. Since different complete theories cannot have isomorphic models, you get continuum many non-isomorphic countable model of PA.

(Meanwhile, Andreas's answer applies not just to PA, but to any fixed theory, and so in fact, the compactness argument he mentions shows that each of these continuum many extensions of PA has continuum many non-isomorphic models.)

$\endgroup$
4
  • $\begingroup$ @JoelDavidHamkins: This answer is very helpful! Thank you! $\endgroup$ Mar 24, 2012 at 23:02
  • $\begingroup$ Is it possible to count (up to isomorphism) models of PA of a higher cardinality, say, $\aleph_1$ or $\mathfrak c$? $\endgroup$ Apr 20, 2021 at 5:24
  • 1
    $\begingroup$ Yes. There are $2^{\omega_1}$ many distinct $\omega_1$-like models of PA (and of ZFC), as explained in this article: jdh.hamkins.org/…. $\endgroup$ Apr 20, 2021 at 7:09
  • $\begingroup$ @MikhailKatz That is interesting. I'd suggest you specify exactly what you mean by "hyperreals" e.g. what is the language, what is the theory, which models, etc. and also in the general case what counts as hypernaturals, etc. $\endgroup$ Dec 18, 2023 at 15:46
25
$\begingroup$

For any set $S$ of (standard) prime numbers, there is, by a compactness argument, a non-standard countable model $M(S)$ of PA containing an element divisible by exactly the primes in $S$. (Actually there are many such models but I need just one.) The same model $M$ might serve as $M(S)$ for several differnt $S$´s, but only countably many, since $M$ is countable. Since there are continuum many choices for $S$, there must be continuum many non-isomorphic $M(S)$´s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.