11
$\begingroup$

Let $N$ be a model of first-order Peano arithmetic, and let $\sigma$ be its order-type. Does it follow that there is a (non-transitive, expect when $M$ is the standard model) $ZFC$-model $M$ such that $\omega^{M}=\sigma$? What if $PA$ is strengthened to true arithmetic (i.e. the theory of $(\mathbb{N},+,\cdot)$ or weakened to a subtheory such as $I\Sigma_{1}$, $I\Delta_{0}+EXP$, $I\Delta_{0}$ or $IOpen$? Or when we replace $ZFC$ with something weaker like $KP$?

$\endgroup$

2 Answers 2

13
$\begingroup$

For countable models, the answer is yes, since all nonstandard such models have the same order type. (For the standard model $N=\mathbb{N}$, assume there is an $\omega$-standard model of ZFC, and in general we must assume Con(ZFC).) Namely, if $N\models\text{PA}$ is nonstandard, then its order type is $\omega+\mathbb{Z}\cdot\mathbb{Q}$, and this is also the order type appearing as the $\omega$ of any $\omega$-nonstandard countable model of ZFC.

It seems to me that this argument would also work for saturated models in larger cardinalities, but I'm unsure of the general case.

A related question would be: which models of PA arise as the full standard structure of arithmetic $\langle\mathbb{N},+,\cdot,0,1,<\rangle^M$ of a model $M\models\text{ZFC}$? In other words, we ask for the full structure, rather than merely the order type as you have. These are known as the ZFC-standard models of PA, and in the countable case they are exactly the standard model of PA (provided there is an $\omega$-model of ZFC), together with the computably saturated models of the arithmetic consequences of ZFC, a theory denoted $\text{Th}(\mathbb{N})^{\text{ZFC}}$. For a discussion of this and applications, see proposition 3 of Satisfaction is not absolute, as well as a 2009 report of Ali Enayat on the topic for the Mittlag-Lefflar institute.

Meanwhile, I was able to get the following, which works even for uncountable models. (Update: I made this an equivalence.)

Theorem. The following are equivalent for any $N\models\text{PA}$.

  1. For any finitely many axioms $\varphi_0,\ldots,\varphi_n$ of ZFC, the model $N$ thinks they are consistent.
  2. As a model of arithmetic, $N$ is isomorphic to an initial segment of the standard model $\mathbb{N}^M$ of some $M\models\text{ZFC}$.
  3. $N$ satisfies all the $\Pi_1^0$ consequences of ZFC.

Proof. ($2\to 3$) If $N$ is an initial segment of $\mathbb{N}^M$ for some $M\models\text{ZFC}$, then $N$ must satisfy all the $\Pi_1^0$ arithmetic statements true in $M$.

($3\to 1$) Those consistency statements are amongst the $\Pi_1^0$ consequences of ZFC, which proves the consistency of any particular of its finite fragments.

($1\to 2$) Suppose that $N$ is a model of PA in which every standard finite fragment of standard ZFC is consistent. (This follows from $N\models\text{Con}(\text{ZFC})$, but it is a strictly weaker hypothesis.) In particular, this hypothesis implies that ZFC is consistent, and so we may assume without loss that $N$ is nonstandard. Consider $N$'s version of the theory ZFC. We may enumerate what it thinks are the axioms, which of course includes many nonstandard axioms. Since we have assumed that $N$ thinks all the standard-finite initial segments of this enumeration are consistent, by overspill there is some nonstandard finite theory $t$ in $N$ which $N$ thinks is consistent, and which includes every standard axiom of ZFC.

Inside $N$, we may now build the usual Henkin completion $T$ of $t$. That is, we add Henkin constants and add every sentence $\sigma$ or its negation $\neg\sigma$ in the new language, in such a way that $N$ thinks $T$ extends $t$ and remains consistent, while having the Henkin property. The theory $T$ is a definable class in $N$, and $N$ is also able to define the corresponding Henkin model $M$.

By meta-theoretic induction, we can show that $M\models\sigma$ just in case $\sigma\in T$, for every standard finite sentence $\sigma$ in the expanded language. In particular, it follows that $M$ is a model of ZFC.

Finally, I claim that $N$ is isomorphic to an initial segment of the $\mathbb{N}^M$, and indeed, $N$ is able to construct this isomorphism. For every $a\in N$, the model $N$ is able to construct the term $\overbrace{1+\cdots+1}^a$, and it has added a Henkin constant $\hat a$ and the assertion $\hat a=\overbrace{1+\cdots+1}^a$ to the theory $T$. Furthermore, $N$ believes that it is able to prove (by induction) that $x<\hat a$ implies $x=\hat b$ for some $b<a$. It also must believe things like $\hat{(a+b)}=\hat a+\hat b$ and $\hat{(a\cdot b)}=\hat a\cdot\hat b$, since these kind of manipulations of terms are provable in PA. Thus, the map $$a\mapsto (\hat a)^M$$ is an isomorphism of $\langle N,+,\cdot,0,1,<\rangle$ to an initial segment of $\mathbb{N}^M$, as desired. QED

Corollary. If ZFC is consistent, then every model of true arithmetic, and indeed every model of $\text{PA}+\text{Con}(\text{ZFC})$, arises as an initial segment of the standard model $\mathbb{N}^M$ of some model $M\models\text{ZFC}$ of set theory.

One can replace ZFC in this argument with other set theories, such as KP or ZFC + large cardinals, and get an equivalence for other theories.

Basically, in the implication ($1\to 2$) of the theorem, the model $N$ thinks it has constructed an $\omega$-nonstandard model of the theory $t$, and it naturally believes that what it thinks is the standard model, itself, is an initial segment of that model.

$\endgroup$
3
  • $\begingroup$ Joel: thanks for the reference to my 2009 report. A revised draft of that report now appears in the following volume, on pages 55-64: flov.gu.se/digitalAssets/1497/1497175_ideesfixes.pdf $\endgroup$
    – Ali Enayat
    Oct 15, 2014 at 16:36
  • $\begingroup$ Great! I was hoping you'd come through with a link. $\endgroup$ Oct 15, 2014 at 16:37
  • $\begingroup$ Joel: your theorem remains true with $PA$ weakened to $I\Sigma_1$ because is known that the arithmetized completeness theorem can be implemented in $I\Sigma_1$ (this is a nontrivial result, the first proof of it was given by a forcing argument of Harrington that shows that every countable model of $I\Sigma_1$ has an expansion to a model of $WKL_0$). Also, in the theorem, one can replace $ZFC$ with any of its r.e. extensions (indeed, with any r.e. extension of a very weak fragment of $ZF$, a fragment that proves that $(\omega, \in)$ is a discrete linear order). $\endgroup$
    – Ali Enayat
    Oct 19, 2014 at 13:09
10
$\begingroup$

Joel Hamkins has already answered the question in the positive for countable models of PA; indeed PA can be relaxed to IOpen in his argument.

In the uncountable case, as far as I know, the problem is wide open.

My reason: a closely related question is still (wide) open, namely, is it possible to have distinct consistent completions $T_1$ and $T_2$ of PA such that the collection of order-types of uncountable models of $T_1$ differs from the collection of order-types of uncountable models of $T_2$ ?

This open question was first brought to world attention by Harvey Friedman in his 1975-paper "One hundred and two problems in mathematical logic" (in Journal of Symbolic Logic).

For the state of the art (in relation to order-types of models of PA) see Chapter 11 of the Kossak-Schmerl graduate text on on models of arithmetic. Friedman's problem is mentioned there both in Chapter 11, and also in Chapter 12 (List of 20 open questions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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