Lobachevskii Journal of Mathematics

http://ljm.ksu.ru

Vol. 16, 2004, 3 – 15 \begin{matrix}c \\ ◯ \end{matrix} A. Bovykin

Andrey 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 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.

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.

1. Introduction

Peano Arithmetic (PA) is the first-order theory in the language L_{PA} = {+, ×, <, 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:

∀\overline{y}[ φ(0, \overline{y}) ∧ ∀x(φ(x, \overline{y}) → φ(x + 1, \overline{y})) → ∀xφ(x, \overline{y}) ]

for every L_{PA}-formula φ(x, \overline{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 ℕ = {φ | φ ∈ L_{PA}, ℕ ⊨ φ}), 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 \overline{a} ∈ M, and any statement φ(\overline{a}) containing additional relation symbols R_{1}, …, R_{n}, if Th(M, \overline{a}) + φ(\overline{a}) is consistent then there are relations R_{1}, …, R_{n} on M such that (M, R_{1}, …, R_{n}) ⊨ φ(\overline{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(a_{1}, …, a_{n}) = tp(b_{1}, …, b_{n}) then there is an automorphism h: M → M such that for all i = 1, 2, …, n, h(a_{i}) = b_{i}). Arithmetic saturation gives us extra control over this automorphism. E.g., if a_{i} ≠ b_{i} 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 ordertypes 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 Cl_{M}(B) denotes the set of all elements of M definable in M with parameters from B, that is a ∈ Cl_{M}(B) ⇔ for some \overline{b} ∈ B and some L_{PA}-formula φ(x, \overline{y}),

M ⊨ φ(a, \overline{b}) ∧ ∃!xφ(x, \overline{b}).

A set Y ⊆ M is definable (with parameters \overline{b} ∈ M) if for some L_{PA}- formula φ(x, \overline{y}), Y = \{y ∈ M | M ⊨ φ(y, \overline{b})\}.

Definition 1. Let M ⊨ PA. We define the Standard System of M as SSy(M) = {X ⊆ ℕ | there is a definable (with parameters) Y ⊆ M such that X = Y ∩ ℕ}. We say that a subset A of ℕ is coded in M if A ∈ SSy(M).

Definition 2. A Scott set X is a collection of subsets of ℕ closed under ⋃, ⋂, ∖, complement, relative recursion and such that if T ∈ X codes an infinite finitely branching tree then there is B ∈ X, B ⊆ T which codes an infinite path through T.

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}.

Definition 3. A model M ⊨ PA is called resplendent if for every Σ_{1}^{1}- statement Φ(\overline{a}), \overline{a} ∈ M, consistent with Th(M, \overline{a}), we have M ⊨ Φ(\overline{a}).

Definition 4. A model M ⊨ PA is called recursively saturated if every recursive type p(x, \overline{a}) (that is, \{⌜φ(x, \overline{y})⌝) | φ(x, \overline{y}) ∈ p\} is recursive) is realized.

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, \overline{y})⌝ | φ(x, \overline{a}) ∈ p(x, \overline{a})\} ∈ SSy(M).

Fact 1. (Kleene). Let L be a finite language and \{φ_{n}(\overline{x})\}_{n∈ℕ} be a recursive set of formulas of L. Then there is a Σ_{1}^{1}-formula Φ(\overline{x}) such that in all infinite L-structures M, M ⊨ ∀\overline{x} (Φ(\overline{x}) ↔ ⋀_{i∈ℕ} φ_{n}(\overline{x})).

It follows from Fact 1 that resplendency implies recursive saturation.

Fact 2. (Wilmers). Let X be a countable Scott set, T ⊇ PA be a consistent theory, T ∈ X. Then there is a countable recursively saturated M ⊨ T such that SSy(M) = X.

Fact 3. ([4][7][5]). Let M ⊨ PA be recursively saturated. Then the following are equivalent.

(1) M is arithmetically saturated, i.e., SSy(M) is closed under jump;

(2) for any f ∈ M coding a set of pairs determining a function f: ℕ → M, there is c ∈ M ∖ ℕ such that for all n ∈ ℕ, f(n) > ℕ ⇔ f(n) > c;

(3) for every a ∈ M, {⌜θ(x, y)⌝ | θ(x, y) is an L_{PA}-formula in two variables and min x θ(x, a) ∉ Cl∅} ∈ SSy(M);

(4) there is g ∈ Aut(M) such that g(a) ≠ a for every a ∈ Cl∅.

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.

Theorem 4. If M ⊨ PA is resplendent and c ∈ M codes a consistent theory T ⊇ PA then (M, <) can be expanded to a model of T.

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.

Corollary 5. If M ⊨ PA is resplendent and ω_{1}-saturated then (M, <) can be expanded to a model of any consistent extension of PA.

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

Theorem 6. If M ⊨ PA is resplendent and lcf(M ∖ ℕ) > ω then for all n ∈ ω, (M, <) is expandable to a model of PA + Π_{n} Th ℕ.

Proof. For any n ∈ ω, let us introduce Σ_{n}Def = the set of all nonstandard definable points of M defined by a Σ_{n}-formula.

As lcf(M ∖ ℕ) > ω, there is a > ℕ such that Σ_{1}Def > a. Define A_{1} = {⌜∀xφ(x)⌝ | φ ∈ Δ_{0}, M ⊨ ∀x < a φ(x)}. Now, A_{1} ⊆ Π_{1} Th ℕ because ℕ ≺_{Δ_{0}} M. Also, Π_{1} Th ℕ ⊆ A_{1} because if for some φ ∈ Δ_{0} such that ℕ ⊨ ∀xφ(x) there existed x < a ¬φ(x) then min x¬φ(x) would be a nonstandard Σ_{1}-definable point less than a. Hence, A_{1} = Π_{1} Th ℕ. A_{1} is definable, hence coded in M.

Suppose at stage n we already know that Π_{n} Th ℕ ∈ SSy(M). Let b ∈ M code Π_{n} Th ℕ. Consider the statement

Φ_{n}(b) = ∃⊕_{n}, ⊗_{n}, ≪_{n}, 𝕆_{n}, 𝕊_{n}
∀xy (x ≪_{n} y ⟷ x < y) ⋀

⋀ “(⊕_{n}, ⊗_{n}, ≪_{n}, 𝕆_{n}, 𝕊_{n}) ⊨ PA + Π_{n} Th ℕ” ⋀
⋀ “SSy(M, ⊕_{n}, ⊗_{n}, ≪_{n}, 𝕆_{n}, 𝕊_{n}) ⊆ SSy(M)”.

Let us show that the last line is expressible by a Σ_{1}^{1}-sentence. Let φ_{m}(x) = (x > m) & ∀ z ∃ y ∀ i < x ((z))_{i} = (y)_{i}, where ((z))_{i} means (z)_{i} in the language {⊕_{n}, ⊗_{n}, ≪_{n}, 𝕆_{n}, 𝕊_{n}}. The set {φ_{m}(x)}_{m∈ℕ} is a recursive set of formulas, hence, by Kleene’s Theorem, there is a Σ_{1}^{1}-sentence Θ(x) such that in any K ⊨ PA, K ⊨ ∀ x (⋀_{m∈ℕ} φ_{m}(x) ↔ Θ(x)). Then SSy(M, ⊕_{n}, ⊗_{n}, ≪_{n}, 𝕆_{n}, 𝕊_{n}) ⊆ SSy(M) is implied by the Σ_{1}^{1}-sentence ∃ x Θ(x). Hence, Φ_{n}(b) is a Σ_{1}^{1}-sentence.

Φ_{n}(b) is consistent because, by Wilmers’ Theorem, as (PA+Π_{n} Th ℕ) ∈ SSy(M), there is a countable model

N ⊨ PA + Π_{n} Th ℕ, SSy(N) = SSy(Cl_{M}(b)).

Hence, by resplendency, Φ_{n}(b) is already realized in M.

Denote the model (M, ⊕_{n}, ⊗_{n}, ≪_{n}, 𝕆_{n}, 𝕊_{n}) by M_{n}. By construction, M_{n} ⊨ PA + Π_{n} Th ℕ, (M_{n}, <) ≅ (M, <), SSy(M_{n}) ⊆ SSy(M).

Let (Σ_{n}Def)_{M_{n}} > a > ℕ. Consider

A_{n+1} = {⌜∀xφ(x)⌝ | φ ∈ Σ_{n}, M_{n} ⊨ ∀x < a φ(x)}.

A_{n+1} ⊆ Π_{n+1} Th ℕ because if M_{n} ⊨ ∀x < a φ(x) but ℕ ⊨ ∃x ¬φ(x) then for some k ∈ ℕ, ℕ ⊨ ¬φ(k), which is a Π_{n}-statement. Hence, as M_{n} ⊨ Π_{n} Th ℕ, M_{n} ⊨ ¬φ(k), contradiction.

Π_{n+1} Th ℕ ⊆ A_{n+1}. Let ℕ ⊨ ∀xφ(x), where φ(x) ∈ Σ_{n}. If M_{n} ⊨ ∃x < a ¬φ(x) then c =: min x¬φ(x) is a Σ_{n}-definable point less than a. If c ∈ ℕ then M_{n} ⊨ ¬φ(c), which is a Π_{n}-statement not belonging to Π_{n} Th ℕ. Contradiction with M_{n} ⊨ Π_{n} Th ℕ. Hence ℕ < c < a contradicting the assumption that (Σ_{n}Def) > a.

Therefore Π_{n+1} Th ℕ = A_{n+1}, which is coded in M_{n}. As SSy(M_{n}) ⊆ SSy(M), Π_{n+1} Th ℕ is coded also in M.

Now, by Theorem 4, (M, <) is expandable to a model of PA+Π_{n} Th ℕ for every n ∈ ω. □

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) ∈ L_{PA}. Recursive extensions of PA are examples of arithmetic theories. Also, there are complete arithmetic theories by the arithmetized completeness theorem.

Corollary 7. For any consistent arithmetic theory T ⊇ PA, if M ⊨ PA is resplendent and lcf(M ∖ ℕ) > ω then there is N ⊨ T such that (N, <) ≅ (M, <).

Proof. Since T is arithmetic, T is recursive in the set Π_{n} Th ℕ for some n. Hence T is coded in M. Hence, by Theorem 4, (M, <) is expandable to a model of T. □

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?

Lemma 8. Let M ⊨ PA be recursively saturated. Then M is arithmetically saturated if and only if for all a ∈ M , Cl(a) ∖ ℕ is bounded below in M ∖ ℕ.

Proof. Suppose, for all a ∈ M, Cl(a) ∖ ℕ is bounded below. Let f ∈ M code a function whose domain contains ℕ. For every n ∈ ℕ, f(n) ∈ Cl(f). If b ∈ M ∖ ℕ is such that Cl(f) > b then for all n ∈ ℕ, (f(n) > ℕ ⇔ f(n) > b).

Let M be arithmetically saturated, c > ℕ. The type which says: F ∈ M codes a function F: [0, c] ⟶ M with F (⌜θ⌝) = t_{θ}(a) (where θ ranges over all formulas of L_{PA} with two variables and t_{θ} is the Skolem term defined by θ) is recursive, hence realized. But if Cl(a) ∖ ℕ is unbounded below then {F (⌜θ⌝)} ∩ (M ∖ ℕ) is not separated from ℕ contradicting arithmetic saturation. □

Let E = {x ∈ M | there are no nonstandard definable points below x}. If a ∈ M ∖ Cl∅, E_{a} = {x ∈ M | for all c ∈ Cl∅, c < x ↔ c < a }.

By Lemma 8, E ≠ ∅ and for any a such that ℕ < a < Cl∅ ∖ ℕ, E_{a} = E. The following lemma establishes some homogeneity properties of E_{a} which will be important in the rest of this section.

Lemma 9. Let M be recursively saturated, a ∈ M ∖ Cl∅.

(1) If p(x, \overline{b}) is realized by c ∈ E_{a}, c > Cl(\overline{b}) ∩ E_{a} then for all x ∈ E_{a} there is y > x such that p(y, \overline{b}).

(2) If p(x, \overline{b}) is realized by c ∈ E_{a}, c < Cl(\overline{b}) ∩ E_{a} then for all x ∈ E_{a} there is y < x such that p(y, \overline{b}).

Proof. 1. Let A_{upper} = {x ∈ M | ∃ y ∈ Cl∅, a < y < x}. For an arbitrary e ∈ E_{a}, let us find d > e such that p(d, \overline{b}). Let us show that for all θ(x, \overline{b}) ∈ p(x, \overline{b}), M ⊨ θ(y, \overline{b}) for unboundedly-many y ∈ E_{a}. Consider the two cases. If A = \{x ∈ A_{upper} | M ⊨ θ(x, \overline{b})\} is unbounded below then M ⊨ θ(y, \overline{b}) for unboundedly-many y ∈ E_{a} by overspill. Otherwise, let k ∈ Cl∅, a < k < A. Define g = max x < k θ(x, \overline{b}). We observe that g ∈ Cl(\overline{b}), while c ≤ g < A_{upper}, which is a contradiction.

Thus for any e ∈ E, p(x, \overline{b}) ∪ \{x > e\} is finitely satisfied. By recursive saturation, p(x, \overline{b}) ∪ \{x > e\} is coded, hence realized.

2. Analogous proof. □

Lemma 10. Let M ⊨ PA be a countable arithmetically saturated model, ℕ < e < Cl∅ ∖ ℕ. Then there is an elementary embedding h : M → M such that for all x > ℕ, h(x) > e.

Proof. A forth-argument. Let us enumerate M as {a_{1}, a_{2}, …, a_{i}, …}_{i<ω} and build inductively a sequence {b_{1}, b_{2}, …, b_{i}, …}_{i<ω} with tp(b_{1}, …, b_{i}) = tp(a_{1}, …, a_{i}) and b_{i} > e ⇔ b_{i} > ℕ for all i and define h(a_{i}) = b_{i}.

Suppose at stage i we already have tp(a_{1}, …, a_{i}) = tp(b_{1}, … b_{i}), e < Cl(b_{1}, …, b_{i}) ∖ ℕ. By Lemma 8, Cl(a_{1}, …, a_{i+1}) ∖ ℕ is bounded below. Let c < Cl(a_{1}, …, a_{i+1}) ∖ ℕ. By Lemma 9 (2),

p(x, a_{1}, …, a_{i}, c) = {θ(a_{1}, …, a_{i}, x) | M ⊨ θ(b_{1}, …, b_{i}, e)} ∪ {x < c}

is satisfied, say, by e^{∗} ∈ E.

As tp(a_{1}, …, a_{i}, e^{∗}) = tp(b_{1}, …, b_{i}, e), by recursive saturation, there is an elementary embedding (actually, an automorphism) h: M → M such that h(a_{1}) = b_{1}, …, h(a_{i}) = b_{i}, h(e^{∗}) = e. Put b_{i+1} = h(a_{i+1}). By construction, e < Cl(b_{1}, …, b_{i+1}). □

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.

Theorem 11. Let X be a countable Scott Set. Then X is closed under jump if and only if there is a recursively saturated M ⊨ PA, lcf(M ∖ℕ) > ω, SSy(M) = X.

The countability assumption cannot be dropped yet because for Scott sets X with card X > ω_{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.

Fact 12. (Kaye, Kossak, Kotlarski [3]) If M ⊨ PA is countable and arithmetically saturated then M has an automorphism which moves every nondefinable point.

Fact 13. (Kossak [6]) If M ⊨ Th ℕ is countable and arithmetically saturated then there exists h ∈ Aut(M) such that for all x > ℕ, h(x) > x, i.e. h moves every nonstandard point upwards.

Fact 14. (Kossak, Schmerl [7]) If M is countable and arithmetically saturated then there is an automorphism f of M such that for every x > Cl∅, f(x) < x.

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.

Proof. Let a < b < e, e ∈ Cl∅ ∖ ℕ, h(a) = b. Then e − a > e − b, hence h(e − a) > h(e − b), hence e − b > h(e − b). □

But what we can expect is the following Theorem.

Theorem 15. If M ⊨ PA is countable and arithmetically saturated then there is h ∈ Aut(M) such that for all x ∈ E, h(x) > x and h moves every nondefinable point.

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.

Lemma 16. (Kaye, Kotlarski) If M is arithmetically saturated, tp(\overline{a}) = tp(\overline{b}) and for any Skolem term t,

t(\overline{a}) = t(\overline{b}) ⇒ t(\overline{a}) ∈ Cl∅

then for any c ∈ M there is d such that tp(\overline{a}, c) = tp(\overline{b}, d) and for any Skolem term t,

t(\overline{a}, c) = t(\overline{b}, d) ⇒ t(\overline{a}, c) ∈ Cl∅.

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

Lemma 17. Let M ⊨ PA be recursively saturated.

(1) If c < Cl(\overline{a}) ∖ ℕ then for any b there is b′ such that tp(\overline{a}, b) = tp(\overline{a}, b′), c < Cl(\overline{a}, b′) ∖ ℕ.

(2) If c > Cl(\overline{a}) ∩ E then for any b there is b′ such that tp(\overline{a}, b) = tp(\overline{a}, b′), c > Cl(\overline{a}, b′) ∩ E.

Proof. 1) By Lemma 9, (1), there is d < Cl(\overline{a}, b) such that tp(\overline{a}, c) = tp(\overline{a}, d). By recursive saturation, there is h : M → M, h(\overline{a}) = \overline{a}, h(d) = c. Denote h(b) by b′. As h is elementary, tp(\overline{a}, b) = tp(\overline{a}, b′). As d < Cl(\overline{a}, b), c < Cl(\overline{a}, b′).

2) Similar proof. □

Proof. We shall construct a string of points {d_{i}}_{i∈ℤ} unbounded above and below in E such that our future automorphism h takes d_{i} to d_{i+1} which will guarantee that each point of E moves upwards: if a ∈ (d_{i}, d_{i+1}) then h(a) ∈ (hd_{i}, hd_{i+1}) = (d_{i+1}, d_{i+2}). Also, it obviously follows that there will be no h-fixed initial segment in E other than sup E and ℕ.

By Lemma 16 there are c_{0}, c_{1} ∈ E such that tp(c_{0}) = tp(c_{1}) and (t(c_{0}) = t(c_{1}) ⇒ t(c_{0}) ∈ Cl∅), hence, considering the type {φ(x) | M ⊨ φ(c_{1})} ∪ {t(x) ≠ t(c_{1}) | t(c_{1}) ∉ Cl∅}, we deduce, using Lemma 9, that there are d_{0}, d_{1} ∈ E such that

tp(d_{0}) = tp(d_{1}),
t(d_{0}) = t(d_{1}) ⇒ t(d_{0}) ∈ Cl∅,
Cl(d_{0}) ∩ E < d_{1},

Cl(d_{1}) ∖ ℕ > d_{0}.

Let {s_{i}}_{i∈ω} be an enumeration of the whole of M ∖ Cl∅. By stage n we shall already have:

\overline{a} = a_{0}, …, a_{2n−1},
\overline{b} = b_{0}, …, b_{2n−1},
\overline{d} = d_{−n}, d_{−n+1}, …, d_{n}, d_{n+1}

satisfying the following conditions:

tp(\overline{a}, d_{−n}, …, d_{n}) = tp(\overline{b}, d_{−n+1}, …, d_{n+1}),
d_{−n} < Cl(\overline{b}, d_{−n+1}, …, d_{n+1}) ∩ E,
d_{n+1} > Cl(\overline{a}, d_{−n}, …, d_{n}) ∩ E,

t(\overline{a}, d_{−n}, …, d_{n}) = t(\overline{b}, d_{−n+1}, …, d_{n+1}) ⇒ t(\overline{a}, d_{−n}, …, d_{n}) ∈ Cl∅. (At stage n = 0, \overline{a} and \overline{b} are empty.) Back Let b_{2n} = s_{n}. Let e < Cl(b_{2n}, \overline{b}, d_{−n}, …, d_{n+1}). By Lemma 16 (applied to the tuples (\overline{b}, d_{−n+1}, …, d_{n+1}) and (\overline{a}, d_{−n}, …, d_{n}) and the new point d_{−n}), the set of formulas

p(x) = \{φ(\overline{a}, x, d_{−n}, …, d_{n}) | M ⊨ φ(\overline{b}, d_{−n}, d_{−n+1}, …, d_{n+1})\} ∪

∪ \{t(\overline{a}, x, d_{−n}, …, d_{n}) ≠ t(\overline{b}, d_{−n}, d_{−n+1}, …, d_{n+1}) |

| t(\overline{b}, d_{−n}, d_{−n+1}, …, d_{n+1}) ∉ Cl∅\}

is realized, hence, by Lemma 9 (2), is realized by a point less than e, hence, by Lemma 17 (2), is realized by a point d_{−n−1} < e such that

Cl(\overline{a}, d_{−n−1}, …, d_{n}) ∩ E < d_{n+1}.

Let q(x) = \{φ(\overline{a}, d_{−n−1}, …, d_{n}, x) | M ⊨ φ(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}\} ∪

∪ \{t(\overline{a}, d_{−n−1}, …, d_{n}, x) ≠ t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) |
| t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) ∉ Cl∅\}.

By Lemma 16, q(x) is realized, hence, by Lemma 17 (2), is realized by some point a_{2n} such that

Cl(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) ∩ E < d_{n+1}.

By construction,

t(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) = t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) ⇒
⇒ t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) ∈ Cl∅,

i.e., every nondefinable point of Cl(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) moves. Let us show that if t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) ∈ E then

t(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) < t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}).

If t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) > d_{n+1} then t(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) ∈ (d_{n}, d_{n+1}) because Cl(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) ∩ E < d_{n+1}. If t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) ∈ (d_{i}, d_{i+1}), i = −n, …, n, then t(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) ∈ (d_{i−1}, d_{i}). If t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) < d_{−n} then, by construction of d_{−n−1}, t(\overline{b}, d_{−n}, …, d_{n+1}, b_{2n}) ∈ (d_{−n−1}, d_{−n}), hence t(\overline{a}, d_{−n−1}, …, d_{n}, a_{2n}) < d_{−n−1}. Forth Let a_{2n+1} = s_{n}. Using Lemmas 16, 9 (1), 17 (1), we choose d_{n+2} such that

tp(\overline{b}, b_{2n}, d_{−n}, …, d_{n+2}) = tp(\overline{a}, a_{2n}, d_{−n−1}, …, d_{n+1}),
t(\overline{b}, b_{2n}, d_{−n}, …, d_{n+2}) = t(\overline{a}, a_{2n}, d_{−n−1}, …, d_{n+1}) ⇒
⇒ t(\overline{a}, a_{2n}, d_{−n−1}, …, d_{n+1} ∈ Cl∅,
d_{n+2} > Cl(\overline{a}, a_{2n}, a_{2n+1}, d_{−n−1}, …, d_{n+1}) ∩ E,
d_{−n−1} < Cl(\overline{b}, b_{2n}, d_{−n}, …, d_{n+2}) ∩ E.

Now, using Lemmas 16 and 17 (1), we choose b_{2n+1} such that

tp(\overline{b}, b_{2n}, b_{2n+1}, d_{−n}, …, d_{n+2}) = tp(\overline{a}, a_{2n}, a_{2n+1}, d_{−n−1}, …, d_{n+1}),

t(\overline{b}, b_{2n}, b_{2n+1}, d_{−n}, …, d_{n+2}) = t(\overline{a}, a_{2n}, a_{2n+1}, d_{−n−1}, …, d_{n+1}) ⇒

⇒ t(\overline{a}, a_{2n}, a_{2n+1}, d_{−n−1}, …, d_{n+1}) ∈ Cl∅,
and d_{−n−1} < Cl(\overline{b}, b_{2n}, b_{2n+1}, d_{−n}, …, d_{n+2}).

Having obtained the points a_{i}, b_{i} for all i ∈ ω, we observe that h: M → M defined as h(a_{i}) = b_{i} for all i ∈ ω is an elementary isomorphism possessing the required properties. □

References

[1] Bovykin, A. I. (2000). On order-types of models of arithmetic. Ph.D. Thesis, University of Birmingham.

[2] Friedman H. (1975). One hundred and two problems in mathematical logic. Journal of Symbolic Logic, 40, pp. 113-129.

[3] Automorphisms of First-Order Structures. (1994). Ed. Kaye and Macpherson, Oxford University Press.

[4] Kirby, L.A.S. and Paris, J.B. (1977). Initial segments of models of Peano’s axioms. Set Theory and Hierarchy Theory, V. Bierutowice, Poland.

[5] Kaye, R., Kossak, R., Kotlarski, H. (1991). Automorphisms of recursively saturated models of arithmetic. Annals of Pure and Applied Logic, 55 pp. 67-91.

ORDER-TYPES AND ARITHMETIC SATURATION 15

[6] Kossak, R. (1991). Exercises in ‘back-and-forth’. Proceedings of the Nineth Easter Conference on Model Theory, Gosen.

[7] Kossak, R., Schmerl, J. (1995). Arithmetically saturated models of arithmetic. Notre Dame Journal of Formal Logic, 36.

[8] Pabion, J.F. (1982). Saturated models of Peano Arithmetic. Journal of Symbolic Logic, 47, pp. 625-637.

Laboratory of Mathematical Logic, St.Petersburg Department of Steklov Mathematical Institute, Fontanka 27, St.Petersburg, 191023, Russia. E-mail address: andrey@logic.pdmi.ras.ru

Received January 16, 2004; Revised version May 14, 2004