MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Standard techniques (no pun intended) can be used to show that countable nonstandard models of Peano Arithmetic are order isomorphic to $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$. Once we have used the compactness theorem to verify that nonstandard models of PA exist, we can appeal to the Löwenheim–Skolem theorem to ensure that we have countable ones. We can then verify that these models form unbounded dense linear orders of $\mathbb{Z}$ blocks beyond the standard portion and use a back and forth argument to confirm that the nonstandard parts must always be order isomorphic.

My questions concern the structure of uncountable nonstandard models of PA. The Löwenheim–Skolem theorem can be used to show that we have nonstandard models of arbitrarily large cardinality so:

(1) Is there an example of a set $M$ of the form $\mathbb{N} + \mathbb{Z} \cdot D$ where $D$ is a dense linear order such that $M$ is not a model of PA?

(2) Can we find arbitrarily large $\kappa$ and nonstandard models of PA of size $\kappa$ such that there will be a an unbounded well-orderable subset of size $\kappa$ respecting the ordering relation of the nonstandard model (i.e. an order isomorphism between an ordinal and a subset of the model)?

(3) If the answer to (2) is no, what types of related results can we get?

share|cite|improve this question
@Jason: First, a brief comment: In (1) you probably mean: "Is there an unbounded dense linear order set $D$ such that there is no model of PA whose underlying order is isomorphic to N+ZD?" Second, Shelah recently posted a nice (long) paper on the arXiv on questions of precisely this kind. You may find useful looking at it and at some of its references, From the abstract: "We hope to see how much for a model M of some completion T of PA (Peano Arithmetic) does M restriction {<} determine M, say up to isomorphism." (This is [Sh:924]) – Andrés E. Caicedo Dec 6 '10 at 2:57
+1: @Andres: This is useful. Thank you. – Jason Dec 6 '10 at 6:27
A trivial answer to Q1: Yes, for example $D=\mathbb Q + \mathbb R$. In M = N + Z*D there are countably infinite intervals [a,b], and there are elements c such that all [c,d] are uncountable. Now let d:= c + (b-a), then the intervals [a,b] and [c,d] should be order isomorphic. – Goldstern May 20 '11 at 9:57
up vote 5 down vote accepted

Question 2 is an immediate consequence of the compactness theorem. Let $\kappa$ be fixed, and for each $\alpha < \kappa$ add a constant symbol $c_\alpha$ to the language. Add axioms of the form $c_\alpha < c_\beta$ for every $\alpha < \beta < \kappa$. The new theory $T$ is finitely satisfiable (every finite fragment is interpretable in the standard model of PA). So $T$ it is satisfiable, and the map $\alpha \mapsto c_\alpha$ is the desired embedding.

For question 1, it is known that $D$ cannot have the order type of the reals. There is a nice survey by Bovykin and Kaye [1] that includes this fact and has a lot more information about order types of models of PA.


share|cite|improve this answer
About Question 2: In fact, using compactness, any order can be a suborder of the ordering of a model of PA. There are more general results here; for example, the Ehrenfeucht-Mostowski theorem. – Andrés E. Caicedo Dec 6 '10 at 3:48
@Carl: +1: Thanks for the answer and link. What I really wanted to ask for Question 2 was whether we could get a well order of size $\kappa$ that's unbounded in the nonstandard model. Is this possible? – Jason Dec 6 '10 at 6:33
Hmmm... what if we add to $T$ formulas that say: $\forall p_0 \dots \forall p_n [(p_1 < c_{\alpha} \wedge \dots \wedge p_n < c_{\alpha} \wedge \exists x \phi (x, p_1, \dots , p_n)) \rightarrow \exists x < c_{\beta} \phi (x, p_1, \dots , p_n)]$ for each $\alpha < \beta$ and $\phi$ a formula with n+1 free variables. Obtain a model using compactness, and then look at the cut of the model in which the $c_{\alpha}$ are unbounded. This cut will model $PA$, in fact it will be an elementary substructure since, by the formulas we added to $T$, the Tarski-Vaught criterion will be met. – Amit Kumar Gupta Dec 6 '10 at 10:35
Alternatively, to get a model of PA with a cofinal sequence of length $\kappa$, note first that, by compactness, any model of PA has an elementary extension containing a new element above all the old ones. Now iterate this for $\kappa$ steps (taking unions at limit stages). – Andreas Blass Dec 6 '10 at 13:33
Instead of downloading my paper with Kaye that is a survey of some parts of my PhD thesis, it is better to download the actual PhD thesis (written 11 years ago) from As far as I know, nothing new about order-types of models of arithmetic has been proved since then. (Well, there is another article of mine "Resplendent models and definability with an oracle" but this is about a connection between the order-type of models of arithmetic and linear orders that are interpreted in that model, so not exactly relevant to your question). – andrey bovykin Mar 29 '11 at 15:50

Your Answer


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.