Lobachevskii Journal of Mathematics http://ljm.ksu.ru Vol. 16, 2004, 3 – 15
© A. Bovykin
ORDER-TYPES OF MODELS OF ARITHMETIC AND A CONNECTION WITH ARITHMETIC SATURATION
(submitted by Yi Zhang)
ABSTRACT. First, we study a question we encountered while exploring order-types of models of arithmetic. We prove that if is resplendent and the lower cofinality of is uncountable then is expandable to a model of any consistent theory whose set of Gödel numbers is arithmetic. This leads to the following characterization of Scott sets closed under jump: a Scott set is closed under jump if and only if is the set of all sets of natural numbers definable in some recursively saturated model with . The paper concludes with a generalization of theorems of Kossak, Kotlarski and Kaye on automorphisms moving all nondefinable points: a countable model is arithmetically saturated if and only if there is an automorphism moving every nondefinable point and such that for all , , we have .
2000 Mathematical Subject Classification. 03H15, 03C62, 08A35.
Key words and phrases. models of Peano arithmetic, linearly ordered sets, arithmetic saturation, resplendency, automorphisms of models.
The author was supported by a grant of the Swedish Royal Academy of Sciences to stay in Institut Mittag-Leffler and, subsequently, by a NATO-PC Advanced Fellowship via the Scientific and Technical Research Council of Turkey to stay in İstanbul Bilgi University.
Peano Arithmetic () is the first-order theory in the language consisting of the following axioms: associativity and commutativity of and , their neutral elements are and respectively, distributivity, discrete linear order axioms for , adding gives a successor, and the Induction Scheme:
for every -formula .
Peano Arithmetic is an extremely powerful theory. A folklore knowledge among logicians is that all of classical analysis, number theory and combinatorics can be done within tiny subsystems of Peano Arithmetic. In pre-Gödelean era it was believed that comprises an axiomatization of the set of all “truths” about natural numbers and finite sets.
Thus, a model of Peano Arithmetic (that is, a set with operations and defined on it so that the above axioms of hold) resemble the natural numbers as much as any working mathematician would hope for (all of his concrete mathematics can be conducted inside a model of and nobody would notice the difference). As usually for such theories, there are non-isomorphic models of in every infinite cardinality .
The structure of models of first-order Peano Arithmetic (PA) has been extensively studied since the 1960s. Due to unclassifyability of the diverse mass of models (even in the countable case) and the elusive nature of completions of (especially the ‘true arithmetic’ ), models of are among the most difficult to deal with in the whole of model theory.
Certain classes of models were studied that could be to some extent tackled: countable models, -like models (for a cardinal ), models coding certain sets, realizing certain types. Among the most important notions introduced is recursive saturation. A model is recursively saturated if it realizes every type (with parameters from ) whose set of Gödel numbers is recursive. Recursively saturated models naturally occur in model theory of arithmetic. For instance, every model of obtained from a nonstandard model of by an application of the arithmetized completeness theorem is recursively saturated.
A recursively saturated model of is uniquely determined by its complete theory and the collection of subsets of definable (coded) in the model: if , are two recursively saturated models of the same completions of and code the same subsets of then .
Other notions were also introduced, isolating important subclasses of the class of all recursively saturated models: the most important being resplendency and arithmetic saturation. Resplendent models and arithmetically saturated models will be the main objects we study in this paper.
A model is resplendent if for every , and any statement containing additional relation symbols , if is consistent then there are relations on such that . Resplendency implies existence of many automorphisms of a model, recursive saturation of a model and many other pleasant properties. Resplendent models are a plentiful class of very ‘regular’ models we can deal with.
A model is arithmetically saturated if it is recursively saturated and the class of subsets of definable in is closed under jump. Thus, more subsets of are definable in than is expected from a recursively saturated model. (A recursively saturated model is only expected to code its own complete theory, see Wilmer’s theorem below.) In particular, an arithmetically saturated model codes the sets of all true -sentences for all . In addition, arithmetic saturation implies more homogeneity than just recursive saturation. Recursive saturation implies that the model is homogeneous (if then there is an automorphism such that for all , ). Arithmetic saturation gives us extra control over this automorphism. E.g., if for all then it can be ensured that this automorphism moves all nondefinable points (i.e., for all ).
Section 3 starts off with an investigation of a problem concerning order-types of resplendent models of Peano arithmetic. The connection with arithmetic saturation is studied in Section 4. Section 5 uses the methods developed in Section 4 to produce a generalization of some well-known results of Kossak, Kotlarski and Kaye.
If is a linearly ordered set then , the lower cofinality of , is , where is with the order reversed.
If then denotes the set of all elements of definable in with parameters from , that is for some and some -formula ,
A set is definable (with parameters ) if for some -formula , .
Definition 2. A Scott set is a collection of subsets of closed under , , , complement, relative recursion and such that if codes an infinite finitely branching tree then there is , which codes an infinite path through .
It is known that for every , is a Scott set. The converse is known to hold for Scott sets of cardinalities and .
It is also known (and we shall often use this fact) that a recursively saturated model realizes all types that are coded in , i.e. such that .
It follows from Fact 1 that resplendency implies recursive saturation.
A question of H. Friedman  asks whether the classes of order-types of uncountable models of are the same for all . Having embarked on this difficult question, I realized that probably there is some chance of obtaining results in the case of resplendent models. For an up-to-date account of the state of Friedman’s problem, see . Among the results is the following theorem.
The theorem is proved by writing down a -statement expressing the existence of , and noticing that it is realized in every countable submodel of containing .
Using a theorem by D.Richard and J.-F.Pabion  which says that is -saturated if and only if is -saturated, we obtain the following corollary.
The hunt for conditions weaker than -saturation implying expandability of to a model of led to the following theorem.
Proof. For any , let us introduce the set of all nonstandard definable points of defined by a -formula.
As , there is such that . Define Now, because . Also, because if for some such that there existed then would be a nonstandard -definable point less than . Hence, . is definable, hence coded in .
Suppose at stage we already know that . Let code . Consider the statement
Let us show that the last line is expressible by a -sentence. Let where means in the language . The set is a recursive set of formulas, hence, by Kleene’s Theorem, there is a -sentence such that in any , . Then is implied by the -sentence . Hence, is a -sentence.
is consistent because, by Wilmers’ Theorem, as , there is a countable model
Hence, by resplendency, is already realized in .
Denote the model by . By construction, , , .
Let . Consider
because if but then for some , , which is a -statement. Hence, as , , contradiction.
Let , where . If then is a -definable point less than . If then , which is a -statement not belonging to . Contradiction with . Hence contradicting the assumption that .
Therefore , which is coded in . As , is coded also in .
Now, by Theorem 4, is expandable to a model of for every . □
Now, let us study a corollary. A theory is called arithmetic if it has an axiomatization such that for some formula . Recursive extensions of are examples of arithmetic theories. Also, there are complete arithmetic theories by the arithmetized completeness theorem.
Since is arithmetic, is recursive in the set for some . Hence is coded in . Hence, by Theorem 4, is expandable to a model of . □
However there is a proof that is coded in different from the one above. Indeed, resplendency implies recursive saturation and for any there is such that because . Hence, is arithmetically saturated, thus, applying the machinery of arithmetic saturation (Fact 3), we can conclude that is closed under jump, hence contains for all .
In the next section we shall investigate whether recursive saturation and uncountable lower cofinality give us more information about which sets are coded in than just arithmetic saturation. The answer will be “No”.
We can also reformulate this question as follows. If is recursively saturated and then is closed under jump. Does every countable Scott set closed under jump occur in this way? The answer will be “Yes”.
Proof. Suppose, for all , is bounded below. Let code a function whose domain contains . For every , . If is such that then for all , .
Let be arithmetically saturated, . The type which says: codes a function with (where ranges over all formulas of with two variables and is the Skolem term defined by ) is recursive, hence realized. But if is unbounded below then is not separated from contradicting arithmetic saturation. □
Let there are no nonstandard definable points below . If , . By Lemma 8, and for any such that , . The following lemma establishes some homogeneity properties of which will be important in the rest of this section.
Proof. 1. Let . For an arbitrary , let us find such that Let us show that for all for unboundedly-many . Consider the two cases. If is unbounded below then for unboundedly-many by overspill. Otherwise, let , . Define . We observe that , while , which is a contradiction.
Thus for any ,
is finitely satisfied. By recursive saturation,
is coded, hence realized.
2. Analogous proof. □
A forth-argument. Let us enumerate as and build inductively a sequence with and for all and define .
is satisfied, say, by .
As , by recursive saturation, there is an elementary embedding (actually, an automorphism) such that . Put . By construction, . □
Hence, has an elementary extension , and there is such that . Since a union of an elementary chain of recursively saturated models is recursively saturated, we can repeat this extension times to obtain the following Theorem, which was promised earlier.
The countability assumption cannot be dropped yet because for Scott sets with , the existence of a model such that is still an open problem.
Now, as we are discussing arithmetic saturation, let us turn to automorphism groups where arithmetic saturation has profound consequences. We shall employ lemmas and methods of the previous section.
Fact 12. (Kaye, Kossak, Kotlarski ) If is countable and arithmetically saturated then has an automorphism which moves every nondefinable point.
Fact 13. (Kossak ) If is countable and arithmetically saturated then there exists such that for all , , i.e. moves every nonstandard point upwards.
Fact 14. (Kossak, Schmerl ) If is countable and arithmetically saturated then there is an automorphism of such that for every , .
Notice that Fact 14 generalizes Fact 13. We are going to prove a theorem generalizing Fact 13 in a different direction and at the same time fusing it somehow with Fact 12.
Recall the notation there are no nonstandard elements of below x. In general, if , there exists no such that for all , .
Proof. Let , . Then , hence , hence . □
But what we can expect is the following Theorem.
Since in the case of , we have , this Theorem generalizes Fact 13. The proof uses Kossak’s method and the following two lemmas.
then for any there is such that and for any Skolem term ,
Notice that Fact 12 follows from Lemma 16 by a back-and-forth argument.
Proof. 1) By Lemma 9, (1), there is
such that .
By recursive saturation, there is
2) Similar proof. □
Proof. We shall construct a string of points unbounded above and below in such that our future automorphism takes to which will guarantee that each point of moves upwards: if then . Also, it obviously follows that there will be no -fixed initial segment in other than and .
Let be an enumeration of the whole of . By stage we shall already have:
satisfying the following conditions:
(At stage ,
Let . Let By Lemma 16 (applied to the tuples and and the new point ), the set of formulas
i.e., every nondefinable point of moves. Let us show that if then
Having obtained the points , for all , we observe that defined as for all is an elementary isomorphism possessing the required properties. □
LABORATORY OF MATHEMATICAL LOGIC,
ST.PETERSBURG DEPARTMENT OF STEKLOV MATHEMATICAL INSTITUTE,
FONTANKA 27, ST.PETERSBURG, 191023, RUSSIA.
E-mail address: firstname.lastname@example.org
Received January 16, 2004; Revised version May 14, 2004