Welcome to MathOverflow

Question

5

1

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?

edited Dec 6 2010 at 6:11

asked Dec 6 2010 at 2:50

Jason
1,944●1●5●16

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 2010 at 2:57

+1: @Andres: This is useful. Thank you. – Jason Dec 6 2010 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 2011 at 9:57

Carl Mummert · Accepted Answer · 2010-12-06 03:01:18Z UTC

5

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

answered Dec 6 2010 at 3:01

Carl Mummert
4,838●1●15●27

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 2010 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 2010 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 2010 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 2010 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 2010 at 13:33

show 9 more comments

Uncountable nonstandard models of PA

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.