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

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|improve this question
3  
@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, arxiv.org/abs/1004.3342 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]) –  Andres 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
add comment

1 Answer

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.

1: http://www.maths.bris.ac.uk/~maaib/orders.ps

share|improve this answer
4  
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. –  Andres 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
    
Jason, Carl's $c_{\alpha}$'s are that desired subset. They satisfy the axioms $c_{\alpha} < c_{\beta}$ for $\alpha < \beta < \kappa$, and that's precisely what it means for $\alpha \mapsto c_{\alpha}$ to be an order isomorphism. –  Amit Kumar Gupta Dec 6 '10 at 7:12
2  
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
1  
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
show 9 more comments

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.