Lobachevskii Journal of Mathematics http://ljm.ksu.ru Vol. 16, 2004, 3 – 15

© A. Bovykin

ABSTRACT. First, we study a question we encountered while exploring order-types of models of arithmetic. We prove that if M⊧PA is resplendent and the lower cofinality of M \ ℕ is uncountable then (M,<) is expandable to a model of any consistent theory T ⊇PA whose set of Gödel numbers is arithmetic. This leads to the following characterization of Scott sets closed under jump: a Scott set X is closed under jump if and only if X is the set of all sets of natural numbers definable in some recursively saturated model M⊧PA with lcf(M \ ℕ) > ω. The paper concludes with a generalization of theorems of Kossak, Kotlarski and Kaye on automorphisms moving all nondefinable points: a countable model M⊧PA is arithmetically saturated if and only if there is an automorphism h: M → M moving every nondefinable point and such that for all x ∈ M, ℕ < x < Cl∅ \ ℕ, we have h(x) > x.

1. Introduction

Peano Arithmetic (PA) is the first-order theory in the language LPA = {+,×,<, 0, 1} consisting of the following axioms: associativity and commutativity of + and ×, their neutral elements are 0 and 1 respectively, distributivity, discrete linear order axioms for <, adding 1 gives a successor, and the Induction Scheme:

for every LPA-formula ϕ(x,y¯).

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 PA 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 PA 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 PA and nobody would notice the difference). As usually for such theories, there are 2λ non-isomorphic models of PA 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 PA (especially the ‘true arithmetic’ Th ℕ = {ϕ∣ϕ ∈LPA,ℕ⊧ϕ}), models of PA 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 M is recursively saturated if it realizes every type (with parameters from M) whose set of Gödel numbers is recursive. Recursively saturated models naturally occur in model theory of arithmetic. For instance, every model of PA obtained from a nonstandard model of PA by an application of the arithmetized completeness theorem is recursively saturated.

A recursively saturated model of PA is uniquely determined by its complete theory and the collection of subsets of ℕ definable (coded) in the model: if M⊧PA, N⊧PA are two recursively saturated models of the same completions of PA and code the same subsets of ℕ then M≅N.

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 M is resplendent if for every a¯ ∈ M, and any statement ϕ(a¯) containing additional relation symbols R1,…,Rn, if Th(M,a¯) + ϕ(a¯) is consistent then there are relations R1,…,Rn on M such that (M,R1,…,Rn)⊧ϕ(a¯). 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 M⊧PA is arithmetically saturated if it is recursively saturated and the class of subsets of ℕ definable in M is closed under jump. Thus, more subsets of ℕ are definable in M 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 Πn Th ℕ of all true Πn -sentences for all n ∈ ℕ. In addition, arithmetic saturation implies more homogeneity than just recursive saturation. Recursive saturation implies that the model is homogeneous (if tp(a1,…,an) = tp(b1,…,bn) then there is an automorphism h: M → M such that for all i = 1, 2,…,n, h(ai) = bi). Arithmetic saturation gives us extra control over this automorphism. E.g., if ai ⁄= bi for all i = 1, 2,…n then it can be ensured that this automorphism moves all nondefinable points (i.e., h(x) ⁄= x for all x ⁄∈Cl∅).

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.

2. Definitions

If A is a linearly ordered set then lcf(A), the lower cofinality of A, is cf(A∗), where A∗ is A with the order reversed.

If B ⊆ M⊧PA then ClM(B) denotes the set of all elements of M definable in M with parameters from B, that is a ∈ClM(B) ⇔ for some b¯ ∈ B and some LPA-formula ϕ(x,y¯),

A set Y ⊆ M is definable (with parameters b¯ ∈ M) if for some LPA-formula ϕ(x,y¯), Y = {y ∈ M∣M⊧ϕ(y,b¯)}.

It is known that for every M⊧PA, SSy(M) is a Scott set. The converse is known to hold for Scott sets of cardinalities ω and ω1 .

It is also known (and we shall often use this fact) that a recursively saturated model M realizes all types that are coded in M, i.e. such that {⌜ϕ(x,y¯)⌝∣ϕ(x,a¯) ∈ p(x,a¯)}∈SSy(M).

It follows from Fact 1 that resplendency implies recursive saturation.

3. A question about expanding order-types of resplendent models to models of other theories

A question of H. Friedman [2] asks whether the classes of order-types of uncountable models of T are the same for all T ⊇PA. 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 [1]. Among the results is the following theorem.

The theorem is proved by writing down a Σ1 1-statement expressing the existence of N⊧T, (N,<)≅(M,<) and noticing that it is realized in every countable submodel of M containing c.

Using a theorem by D.Richard and J.-F.Pabion [8] which says that M⊧PA is ω1 -saturated if and only if (M,<) is ω1 -saturated, we obtain the following corollary.

The hunt for conditions weaker than ω1 -saturation implying expandability of (M,<) to a model of T ⊃PA led to the following theorem.

Now, let us study a corollary. A theory T is called arithmetic if it has an axiomatization S such that S = {n ∈ ℕ∣ℕ⊧θ(n)} for some formula θ(x) ∈LPA. Recursive extensions of PA are examples of arithmetic theories. Also, there are complete arithmetic theories by the arithmetized completeness theorem.

However there is a proof that Πn Th ℕ is coded in M different from the one above. Indeed, resplendency implies recursive saturation and for any f : ℕ → M there is a ∈ M such that ∀n ∈ ℕ(f(n) > ℕ ⇒ f(n) > a) because lcf(M \ ℕ) > ω. Hence, M is arithmetically saturated, thus, applying the machinery of arithmetic saturation (Fact 3), we can conclude that SSy(M) is closed under jump, hence contains Πn Th ℕ for all n ∈ ω.

In the next section we shall investigate whether recursive saturation and uncountable lower cofinality give us more information about which sets are coded in M than just arithmetic saturation. The answer will be “No”.

We can also reformulate this question as follows. If M is recursively saturated and lcf(M \ ℕ) > ω then SSy(M) is closed under jump. Does every countable Scott set closed under jump occur in this way? The answer will be “Yes”.

4. Do recursive saturation and uncountable lower cofinality say more about coding than arithmetic saturation?

Let E = {x ∈ M∣ there are no nonstandard definable points below x}. If a ∈ M \ Cl∅, Ea = {x ∈ M∣ for all c ∈Cl∅,c < x ↔ c < a}. By Lemma 8, E ⁄= ∅ and for any a such that ℕ < a < Cl∅ \ ℕ, Ea = E. The following lemma establishes some homogeneity properties of Ea which will be important in the rest of this section.

Hence, M has an elementary extension N ≻ M, N≅M and there is a ∈ N \ M such that ℕ < a < M. Since a union of an elementary chain of recursively saturated models is recursively saturated, we can repeat this extension ω1 times to obtain the following Theorem, which was promised earlier.

The countability assumption cannot be dropped yet because for Scott sets X with cardX > ω1, the existence of a model M⊧PA such that SSy(M) = X is still an open problem.

5. Automorphisms moving all nondefinable points

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.

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 E = {x ∈ M∣ there are no nonstandard elements of Cl∅ below x}. In general, if Th(M) ⁄= Th ℕ, there exists no h ∈Aut(M) such that for all x ⁄∈Cl∅, h(x) > x.

But what we can expect is the following Theorem.

Since in the case of Th(M) = Th ℕ, we have E = M \ ℕ, this Theorem generalizes Fact 13. The proof uses Kossak’s method and the following two lemmas.

Notice that Fact 12 follows from Lemma 16 by a back-and-forth argument.