9
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ @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]) $\endgroup$ – Andrés E. Caicedo Dec 6 '10 at 2:57
  • $\begingroup$ +1: @Andres: This is useful. Thank you. $\endgroup$ – Jason Dec 6 '10 at 6:27
  • $\begingroup$ 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. $\endgroup$ – Goldstern May 20 '11 at 9:57
11
$\begingroup$

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. In the comments below, Andrey Bovykin suggests downloading his thesis from his homepage [2]; the paper is a summary of parts of the thesis.

1: Bovykin, Andrey; Kaye, Richard. Order-types of models of Peano arithmetic. (2002) Logic and algebra, 275--285, Contemp. Math., 302; MR1928396, DOI: 10.1090/conm/302/05055, http://www.maths.bris.ac.uk/~maaib/orders.ps

2: https://logic.pdmi.ras.ru/~andrey/research.html

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Dec 6 '10 at 3:48
  • 2
    $\begingroup$ 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. $\endgroup$ – Amit Kumar Gupta Dec 6 '10 at 10:35
  • 4
    $\begingroup$ 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). $\endgroup$ – Andreas Blass Dec 6 '10 at 13:33
  • 1
    $\begingroup$ @Carl: Andreas is taking a union of a chain of elementary extensions, not just of elementarily equivalent models. $\endgroup$ – Andrés E. Caicedo Dec 6 '10 at 15:28
  • 3
    $\begingroup$ 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 logic.pdmi.ras.ru/~andrey/research.html 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). $\endgroup$ – andrey bovykin Mar 29 '11 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.