Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
14  
"How many models of Peano arithmetic are there that are isomorphic to the standard model?" One, up to isomorphism. –  Guillaume Brunerie Mar 24 '12 at 19:34
2  
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. –  Andres Caicedo Mar 24 '12 at 20:14
2  
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. –  Jason Rute Mar 25 '12 at 15:44
add comment

2 Answers

up vote 12 down vote accepted

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

share|improve this answer
    
@JoelDavidHamkins: This answer is very helpful! Thank you! –  Samuel Reid Mar 24 '12 at 23:02
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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