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.
[Math] Are all countable, nonstandard models of arithmetic given by ultrapowers
lo.logicmodel-theorynonstandard-analysisultrafilters
Related Solutions
Under a not unreasonable assumption about cardinal arithmetic, namely $2^{<c}=c$ (which follows from the continuum hypothesis, or Martin's Axiom, or the cardinal characteristic equation t=c), the number of non-isomorphic possibilities for *R of cardinality c is exactly 2^c. To see this, the first step is to deduce, from $2^{<c} = c$, that there is a family X of 2^c functions from R to R such that any two of them agree at strictly fewer than c places. (Proof: Consider the complete binary tree of height (the initial ordinal of cardinality) c. By assumption, it has only c nodes, so label the nodes by real numbers in a one-to-one fashion. Then each of the 2^c paths through the tree determines a function f:c \to R, and any two of these functions agree only at those ordinals $\alpha\in c$ below the level where the associated paths branch apart. Compose with your favorite bijection R\to c and you get the claimed maps g:R \to R.) Now consider any non-standard model *R of R (where, as in the question, R is viewed as a structure with all possible functions and predicates) of cardinality c, and consider any element z in *R. If we apply to z all the functions *g for g in X, we get what appear to be 2^c elements of *R. But *R was assumed to have cardinality only c, so lots of these elements must coincide. That is, we have some (in fact many) g and g' in X such that *g(z) = *g'(z). We arranged X so that, in R, g and g' agree only on a set A of size $<c$, and now we have (by elementarity) that z is in *A. It follows that the 1-type realized by z, i.e., the set of all subsets B of R such that z is in *B, is completely determined by the following information: A and the collection of subsets B of A such that z is in *B. The number of possibilities for A is $c^{<c} = 2^{<c} = c$ by our cardinal arithmetic assumption, and for each A there are only c possibilities for B and therefore only 2^c possibilities for the type of z. The same goes for the n-types realized by n-tuples of elements of *R; there are only 2^c n-types for any finite n. (Proof for n-types: Either repeat the preceding argument for n-tuples, or use that the structures have pairing functions so you can reduce n-types to 1-types.) Finally, since any *R of size c is isomorphic to one with universe c, its isomorphism type is determined if we know, for each finite tuple (of which there are c), the type that it realizes (of which there are 2^c), so the number of non-isomorphic models is at most (2^c)^c = 2^c.
To get from "at most" to "exactly" it suffices to observe that (1) every non-principal ultrafilter U on the set N of natural numbers produces a *R of the desired sort as an ultrapower, (2) that two such ultrapowers are isomorphic if and only if the ultrafilters producing them are isomorphic (via a permutation of N), and (3) that there are 2^c non-isomorphic ultrafilters on N.
If we drop the assumption that $2^{<c}=c$, then I don't have a complete answer, but here's some partial information. Let \kappa be the first cardinal with 2^\kappa > c; so we're now considering the situation where \kappa < c. For each element z of any *R as above, let m(z) be the smallest cardinal of any set A of reals with z in *A. The argument above generalizes to show that m(z) is never \kappa and that if m(z) is always < \kappa then we get the same number 2^c of possibilities for *R as above. The difficulty is that m(z) might now be strictly larger than \kappa. In this case, the 1-type realized by z would amount to an ultrafilter U on m(z) > \kappa such that its image, under any map m(z) \to \kappa, concentrates on a set of size < \kappa. Furthermore, U could not be regular (i.e., (\omega,m(z))-regular in the sense defined by Keisler long ago). It is (I believe) known that either of these properties of U implies the existence of inner models with large cardinals (but I don't remember how large). If all this is right, then it would not be possible to prove the consistency, relative to only ZFC, of the existence of more than 2^c non-isomorphic *R's.
Finally, Joel asked about a structure theory for such *R's. Quite generally, without constraining the cardinality of *R to be only c, one can describe such models as direct limits of ultrapowers of R with respect to ultrafilters on R. The embeddings involved in such a direct system are the elementary embeddings given by Rudin-Keisler order relations between the ultrafilters. (For the large cardinal folks here: This is just like what happens in the "ultrapowers" with respect to extenders, except that here we don't have any well-foundedness.) And this last paragraph has nothing particularly to do with R; the analog holds for elementary extensions of any structure of the form (S, all predicates and functions on S) for any set S.
Unfortunately, nonstandard models will survive any such attempt. This is guaranteed by the Löwenheim-Skolem Theorem which says that if a countable first-order theory T has an infinite model then it has one of every infinite cardinality. Since an uncountable model necessarily has nonstandard elements, this guarantees that there is a nonstandard model of T (and even countable ones).
Actually, in your case you need a "two-cardinal" version of Löwenheim-Skolem. In your ZFC example, you move to a theory which interprets arithmetic inside a definable substructure (the set ω). The definable substructure of such a model which might still be countable even if the model itself is uncountable. Nevertheless, one can still blow up the size of the natural number substructure via the ultrapower construction, for example.
To evade the Löwenheim-Skolem Theorem, one has to move beyond first-order logic. For example, in infinitary logic one allows infinite disjunctions such as $$\forall x(x = 0 \lor x = S0 \lor x = SS0 \lor \cdots)$$ which ensures that the model is standard. Also, second-order allows quantification over arbitrary sets under the standard interpretation, which again prohibits non-standard models. (See this related question.) This is the characterization of N most commonly used by working mathematicians.
Related Question
- [Math] Uncountable nonstandard models of PA
- [Math] Fulfilling Pythagoras’ Dream using Nonstandard Models of Arithmetic and/or Surreal Numbers
- [Math] How many models of Peano arithmetic are isomorphic to the standard model and how many models of Peano arithmetic are non-standard
- [Math] Illustrating Edward Nelson’s Worldview with Nonstandard Models of Arithmetic
- [Math] nonstandard model of arithmetic having precisely one inductive truth predicate
Best Answer
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.