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

Countable models of PA fall into two categories: the standard one $(\omega, S)$ and the nonstandard ones (all the rest). The only way I've seen to construct a nonstandard model is through taking an ultraproduct or, equivalently, using the compactness theorem. My question is wether or not these are all the models there are? There are continuum many ultrafilters and continuum many nonstandard, countable models, but I don't know if there's a surjective correspondence.

share|improve this question
    
The number of ultrafilters on a countable index set is not continuum, but $2^{2^{\aleph_0}}$ (though not all of them give rise to nonisomorphic ultrapowers). –  Emil Jeřábek Feb 4 '13 at 17:34
add comment

2 Answers 2

up vote 19 down vote accepted

An ultrapower will never yield a countable nonstandard model of PA --- either you will recover the standard model or the result will be uncountable.

As far as the construction of a model is concerned, due to Tennenbaum's theorem (see http://en.wikipedia.org/wiki/Tennenbaum's_theorem) you will never see a recursive nonstandard model of PA. Hence, in some sense, you will never construct a countable model of PA other than the standard model.

On the other hand, if you consider the Henkin construction to be constructive enough for you, then by running his construction relative to the theory in ${\mathcal L}(+,\times,0,1,c,<)$ consisting of PA together with all the assertions $c > n$ for each $n \in {\mathbb N}$, then you would obtain a nonstandard model of PA.

share|improve this answer
    
Fixed the broken link –  David Roberts Sep 4 '11 at 22:09
    
The cardinality argument is a sort of red herring: every model of true arithmetic is an elementary submodel of an ultrapower of $\mathbb N$ (and in fact, the model has an ultrapower isomorphic to an ultrapower of $\mathbb N$). What is more important is that in this way one obtains only models of true arithmetic, i.e., elementarily equivalent to $\mathbb N$. You do not get e.g. models of PA satisfying ¬Con(PA). –  Emil Jeřábek Feb 4 '13 at 17:32
add comment

It could be mentioned perhaps that Skolem's non-standard model of arithmetic (1933-1934) is countable and is a kind of a "definable" version of the ultraproduct construction. Namely, Skolem only uses definable sequences in his construction. The advantage of his model is that it is constructed without using the axiom of choice.

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.