Handbook of Set Theory

Foreman, Kanamori, and Magidor (eds.) February 27, 2008

2

Contents

I Fine structure 5 by Ralf Schindler and Martin Zeman 1 Acceptable J-structures . . . . . . . . . . . . . . . . . . . . . . . 6 2 The first projectum . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Downward extension of embeddings . . . . . . . . . . . . . . . . 21 4 Upward extension of embeddings . . . . . . . . . . . . . . . . . . 25 5 Iterated projecta . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Standard parameters . . . . . . . . . . . . . . . . . . . . . . . . 36 7 Solidity witnesses . . . . . . . . . . . . . . . . . . . . . . . . . . 39 8 Fine ultrapowers . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 9 Applications to L . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4 CONTENTS

I. Fine structure

Ralf Schindler and Martin Zeman

Fine structure theory is an in-depth study of definability over levels of constructible hierarchies. It was invented by Ronald B. Jensen (cf. [?]), and later pursued by Jensen, Mitchell, Steel, and others (cf. for instance [?] and [?]). Our aim here is to give a self-contained introduction to this theory.

Fine structure theory is a necessary tool for a detailed analysis of Gödel’s L and of more complicated constructible models; in fact, it is unavoidable even for the construction of an important class of such models, the so-called core models. The present chapter is thus intended as an introduction to chapters [?], [?], and [?], where core model theory is developed and applied. It may also be read as an introduction to [?], [?], or [?].

An important result of [?] is the Σ_{n} uniformization theorem (cf. [?, Theorem 3.1]), which implies that for any ordinal α and for any positive integer n there is a Σ_{n} Skolem function for J_{α}, i.e., a Skolem function for Σ_{n} relations over J_{α} which is itself Σ_{n} definable over J_{α}. The naïve approach for obtaining such a Skolem function only works for n = 1; for n > 1, fine structure theory is called for.

Classical applications of the fine structure theory are to establish Jensen’s results that □_{κ} holds in L for every infinite cardinal κ (cf. [?, Theorem 5.2]) and his Covering Lemma: If 0^{#} does not exist, then every uncountable set of ordinals can be covered by a set in L of the same size (cf. [?]). We shall prove L ⊧ □_{κ} as well as a slight weakening of Jensen’s Covering Lemma in the final section of this chapter (cf. [?] on a complete proof of the Covering Lemma); they have been generalized by recent research (cf. [?] and [?]; cf. also [?]).

The present chapter will discuss the “pure” part of fine structure theory, the one which is not linked to any particular kind of constructible model one might have in mind. We shall discuss Jensen’s classical version of this theory. We shall not, however, deal with Jensen’s Σ^{∗} theory (which may be found in [?, Sections 1.6–1.8] or in [?]), and we shall also ignore other variants of the fine structure theory which have been created. What we shall deal with here is tantamount to what is presented in (parts of) [?, §§2 and 4].

The authors would like to thank Gunter Fuchs, Paul Larson, Adrian Mathias, Grigor Sargsyan, and the referee for carefully reading earlier versions of this chapter and for bringing many errors to their attention. The second author was partially supported by the NSF Grants DMS-0204728 and DMS-0500799.

1. Acceptable J-structures

An inner model is a transitive proper class model of ZF. If A is a set or a proper class, then L[A] is the least inner model which is closed under the operation x ↦ A ∩ x. An important example is L = L[∅], Gödel’s constructible universe. V itself, the universe of all sets, is of the form L[A] in a class forcing extension which does not add any new sets.^{1}

Any model of the form L[A] may be stratified in two ways: into levels of the L-hierarchy and into levels of the J-hierarchy. The former approach was Gödel’s original one, but it turned out that the latter one (which was introduced by Jensen in [?]) is more useful.

In order to define the J-hierarchy we need the concept of rudimentary functions (cf. [?, p. 233]).

1.1 Definition. Let A be a set or a proper class. A function f: V^{k} → V, where k < ω, is called rudimentary in A (or, rud_{A}) if it is generated by the following schemata:

f(⟨x_{1}, ..., x_{k}⟩) = x_{i}
f(⟨x_{1}, ..., x_{k}⟩) = x_{i} \ x_{j}
f(⟨x_{1}, ..., x_{k}⟩) = {x_{i}, x_{j}}
f(⟨x_{1}, ..., x_{k}⟩) = h(g_{1}(⟨x_{1}, ..., x_{k}⟩), ..., g_{ℓ}(⟨x_{1}, ..., x_{k}⟩))
f(⟨x_{1}, ..., x_{k}⟩) = ⋃_{y∈x_{1}} g(⟨y, x_{2}, ..., x_{k}⟩)
f(x) = x ∩ A

f is called rudimentary (or, rud) if f is rud_{∅}.

Let us write x⃗ for ⟨x_{1}, ..., x_{k}⟩. It is easy to verify that for instance the following functions are rudimentary: f(x⃗) = ⋃ x_{i}, f(x⃗) = x_{i} ∪ x_{j}, f(x⃗) = {x_{1}, ..., x_{k}}, and f(x⃗) = ⟨x_{1}, ..., x_{k}⟩. Proposition 1.3 below will provide more information.

1This class forcing extension is obtained simply by forcing with enumerations p: α → V, ordered by end-extension.

1. Acceptable J-structures 7

If U is a set and A is a set or a proper class then we shall denote by rud_{A}(U) the rud_{A} closure of U,^{2} i.e., the set

U ∪ {f(⟨x_{1}, ..., x_{k}⟩) ; f is rud_{A} and x_{1}, ..., x_{k} ∈ U}.

It is not hard to verify that if U is transitive, then so is rud_{A}(U ∪ {U}). We shall now be interested in 𝒫(U) ∩ rud_{A}(U ∪ {U}) (cf. Lemma 1.4 below).

1.2 Definition. Let A be a set or a proper class. A relation R ⊆ V^{k}, where k < ω, is called rudimentary in A (or, rud_{A}) if there is a rud_{A} function f: V^{k} → V such that R = {x⃗; f(x⃗) ≠ ∅}. R is called rudimentary (or, rud) if R is rud_{∅}.

1.3 Proposition. Let A be a set or a proper class.

(a) The relation ∉ is rud.

(b) Let f, R be rud_{A}. Let g(x⃗) = f(x⃗) if R(x⃗) holds, and g(x⃗) = ∅ if not. Then g is rud_{A}.

(c) If R, S are rud_{A}, then so is R ∩ S.

(d) Membership in A is rud_{A}.

(e) If R is rud_{A}, then so is its characteristic function χ_{R}.

(f) R is rud_{A} iff ¬R is rud_{A}.

(g) Let R be rud_{A}. Let f(⟨y, x⃗⟩) = y ∩ {z; R(⟨z, x⃗⟩)}. Then f is rud_{A}.

(h) If R(⟨y, x⃗⟩) is rud_{A} then so is ∃z ∈ yR(⟨z, x⃗⟩).

Proof. (a) x ∉ y iff {x} \ y ≠ ∅. (b) If R(x⃗) ↔ r(x⃗) ≠ ∅, where r is rud_{A}, then g(x⃗) = ⋃_{y∈r(x⃗)} f(x⃗). (c) Let R(x⃗) ↔ f(x⃗) ≠ ∅, where f is rud_{A}. Let g(x⃗) = f(x⃗) if S(x⃗) holds, and g(x⃗) = ∅ if not. g is rud_{A} by (b), and thus g witnesses that R ∩ S is rud_{A}. (d) x ∈ A iff {x} ∩ A ≠ ∅. (e): by (b). (f) χ_{¬R}(x⃗) = 1 \ χ_{R}(x⃗). (g) Let g(⟨z, x⃗⟩) = {z} if R(⟨z, x⃗⟩) holds, and g(⟨z, x⃗⟩) = ∅ if not. We have that g is rud_{A} by (b), and f(⟨y, x⃗⟩) = ⋃_{z∈y} g(z, x⃗). (h) Set f(y, x⃗) = y ∩ {z; R(⟨z, x⃗⟩)}. f is rud_{A} by (g), and thus f witnesses that ∃z ∈ yR(⟨z, x⃗⟩) is rud_{A}. ⊣

We shall be concerned here with structures of the form ⟨U, ∈, A_{0}, ..., A_{m}⟩, where U is transitive. (By ⟨U, ∈, A_{0}, ..., A_{m}⟩ we shall mean the structure ⟨U, ∈↾ U, A_{0} ∩ U, ..., A_{m} ∩ U⟩.) Each such structure comes with a language L_{Ȧ_{0},...,Ȧ_{m}} with predicates ˙∈, Ȧ_{0}, ..., Ȧ_{m}. We shall restrict ourselves to the case where m = 0 or m = 1.

If M = ⟨|M|, ...⟩ is a structure, X ⊆ |M|, and n < ω then we let Σ_{n}^{M}(X) denote the set of all relations which are Σ_{n} definable over M from parameters in X. We shall also write Σ_{n}^{M} for Σ_{n}^{M}(M), and we shall write Σ_{ω}^{M} for ⋃_{n<ω} Σ_{n}^{M}. Further, we’ll write Σ_{n}^{M} for Σ_{n}^{M}(∅), where n ≤ ω.

The following lemma says that rud_{A}(U∪{U}) is just the result of “stretching” Σ_{ω}^{⟨U,∈,A⟩} without introducing additional elements of 𝒫(U).

2This is in contrast to [?, p. 238], where rud_{A}(U) stands for the rud_{A} closure of U ∪ {U}.

1.4 Lemma. Let U be a transitive set, and let A be a set or proper class such that A∩V_{rk(U)+ω} ⊆ U. Then 𝒫(U)∩rud_{A}(U ∪{U}) = 𝒫(U)∩Σ_{ω}^{⟨U,∈,A⟩}.

Proof. Notice that 𝒫(U) ∩ Σ_{ω}^{⟨U,∈,A⟩} = 𝒫(U) ∩ Σ_{0}^{⟨U∪{U},∈,A∩U⟩}, so that we have to prove that

𝒫(U) ∩ rud_{A}(U ∪ {U}) = 𝒫(U) ∩ Σ_{0}^{⟨U∪{U},∈,A⟩}

“⊇”: By Proposition 1.3 (a) and (d), ∉ and membership in A are both rud_{A}. By Proposition 1.3 (f), (c), and (h), the collection of rud_{A} relations is closed under complement, intersection, and bounded quantification. Therefore we get inductively that every relation which is Σ_{0} in the language LȦ with ˙∈ and Ȧ is also rud_{A}.

Now let x ∈ 𝒫(U) ∩ Σ_{0}^{⟨U∪{U},∈,A⟩}. There is then some rud_{A} relation R and there are x_{1}, ..., x_{k} ∈ U ∪ {U} such that y ∈ x iff y ∈ U and R(⟨y, x_{1}, ..., x_{k}⟩) holds. But then x = U ∩ {y; R(⟨y, x_{1}, ..., x_{k}⟩)} ∈ rud_{A}(U ∪ {U}) by Proposition 1.3 (g).

“⊆”: Call a function f: V^{k} → V, where k < ω, simple iff the following holds true: if φ(v_{0}, v_{1}, ..., v_{m}) is Σ_{0} in the language LȦ with ˙∈ and Ȧ, then φ(f(v′_{1}, ..., v′_{k}), v_{1}, ..., v_{m}) is equivalent over transitive rud_{A} closed structures to a Σ_{0} formula in the same language. It is not hard to verify inductively that every rud_{A} function is simple. (Here we use the hypothesis that A ∩ V_{rk(U)+ω} ⊆ U which ensures that in this situation quantifying over A is tantamount to quantifying over A ∩ U.)

Now let x ∈ 𝒫(U) ∩ rud_{A}(U ∪ {U}), say x = f(⟨x_{1}, ..., x_{k}⟩), where x_{1}, ..., x_{k} ∈ U ∪ {U} and f is rud_{A}. Then “v_{0} ∈ f(⟨v_{1}, ..., v_{k}⟩)” is (equivalent over rud_{A}(U ∪ {U}) to) a Σ_{0} formula in the language LȦ, and hence x = {y ∈ U; y ∈ f(⟨x_{1}, ..., x_{n}⟩)} is in Σ_{0}^{⟨U∪{U},∈,A⟩}({x_{1}, ..., x_{n}}). ⊣

Of course Lemma 1.4 also holds with 𝒫(U) being replaced by the set of all relations on U. The hypothesis that A ∩ V_{rk(U)+ω} ⊆ U in Lemma 1.4 is needed to avoid pathologies; it is always met in the construction of fine structural inner models.

Let U be rud_{A} closed, and let x ∈ U be transitive. Suppose that B ∈ Σ_{0}^{⟨U,∈,A⟩}({x_{1}, ..., x_{k}}), where x_{1},...,x_{k} ∈ x. Then B ∩ x ∈ Σ_{0}^{⟨x,∈,A⟩}, and hence B ∩ x ∈ rud_{A}(x ∪ {x}) by Lemma 1.4. But rud_{A}(x ∪ {x}) ⊆ U, and therefore B ∩ x ∈ U. We have shown the following.

1.5 Lemma. Let U be a transitive set such that for every x ∈ U there is some transitive y ∈ U with x ∈ y, let A be a set or a proper class, and suppose that U is rud_{A} closed. Then ⟨U, ∈, A⟩ is a model of Σ_{0} comprehension in the sense that if B ∈ Σ_{0}^{⟨U,∈,A⟩} and x ∈ U is transitive then B ∩ x ∈ U.

In the next section we shall start with studying possible failures of Σ_{1} comprehension in rud_{A} closed structures. Lemma 1.5 provides the key element for proving that (all but two of) the structures we are now about to define are models of “basic set theory” (cf. [?, p. 36]), a theory which consists of Σ_{0} comprehension together with extensionality, foundation, pairing, union, infinity, and the statement that Cartesian products exist.^{3}

We may now define the J_{α}^{A} hierarchy as follows. For later purposes it is convenient to index this hierarchy by limit ordinals.^{4}

1.6 Definition. Let A be a set or a proper class.

J_{0}^{A} = ∅
J_{α+ω}^{A} = rud_{A}(J_{α}^{A} ∪ {J_{α}^{A}})
J_{ωλ}^{A} = ⋃_{α<λ} J_{ωα}^{A} for limit λ
L[A] = ⋃_{α∈On} J_{ωα}^{A}

Every J_{α}^{A} is rud_{A} closed and transitive. We shall also denote by J_{α}^{A} the structure ⟨J_{α}^{A}, ∈↾ J_{α}^{A}, A ∩ J_{α}^{A}⟩.

An important special case is obtained by letting A = ∅ in Definition 1.6. We write J_{α} for J_{α}^{∅}, and L for L[∅]. L is Gödel’s constructible universe; it will be studied in the last section of this chapter. Other important examples are obtained by letting A code a (carefully chosen) sequence of extenders; such models are discussed in [?], [?], and [?].

The following is an immediate consequence of Lemma 1.4

1.7 Lemma. Let A be a set or proper class such that A ∩ V_{rk(U)+ω} ⊆ U,

and let α be a limit ordinal. Then 𝒫(J_{α}^{A}) ∩ J_{α+ω}^{A} = 𝒫(J_{α}^{A}) ∩ Σ_{ω}^{J_{α}^{A}}.

It is often necessary to work with the auxiliary hierarchy S_{α}^{A} of [?, p. 244] which is defined as follows:

S_{0}^{A} = ∅
S_{α+1}^{A} = S^{A}(S_{α}^{A})
S_{λ}^{A} = ⋃_{ξ<λ} S_{ξ}^{A} for limit λ

where S^{A} is an operator which, applied to a set U, adds images of members of U ∪ {U} under rud_{A} functions from a certain carefully chosen fixed finite list. We may set

S^{A}(U) = ⋃_{i=0}^{15} F_{i}“(U ∪ {U})^{2},

3Said structures will also be models of “the transitive closure of any set exists,” a statement which - despite of a claim made in [?] - is not provable even in Zermelo’s set theory.

4This is again in contrast with [?].

where

F_{0}(x, y) = {x, y}
F_{1}(x, y) = x \ y
F_{2}(x, y) = x × y
F_{3}(x, y) = {⟨u, z, v⟩; z ∈ x ∧ ⟨u, v⟩ ∈ y}
F_{4}(x, y) = {⟨u, v, z⟩; z ∈ x ∧ ⟨u, v⟩ ∈ y}
F_{5}(x, y) = ⋃ x
F_{6}(x, y) = dom(x)
F_{7}(x, y) = ∈ ∩(x × x)
F_{8}(x, y) = {x“{z}; z ∈ y}
F_{9}(x, y) = ⟨x, y⟩
F_{10}(x, y) = x“{y}
F_{11}(x, y) = ⟨left(y), x, right(y)⟩
F_{12}(x, y) = ⟨left(y), right(y), x⟩
F_{13}(x, y) = {left(y), ⟨right(y), x⟩}
F_{14}(x, y) = {left(y), ⟨x, right(y)⟩}
F_{15}(x, y) = A ∩ x.

(Here, ⟨x_{1}, x_{2}, … x_{n}⟩ = ⟨x_{1}, ⟨x_{2}, …, x_{n}⟩⟩, and left(y) = u and right(y) = v if y = ⟨u, v⟩ and left(y) = 0 = right(y) if y is not an ordered pair.) It is not difficult to show that each F_{i}, 0 ≤ i ≤ 15, is rud_{A}. A little bit more work is necessary to show that every rud_{A} function can be generated by using functions from this list. The functions F_{i}, 0 ≤ i ≤ 15, are therefore a basis for the set of rud_{A} functions (cf. [?, Lemma 1.8]).

Every S_{α}^{A} is transitive,^{5} and moreover

J_{α}^{A} = S_{α}^{A}  (I.1)

for all limit ordinals α. It is easy to see that there is only a finite jump in rank from S_{α}^{A} to S_{α+1}^{A}. A straightforward induction shows that J_{α}^{A}∩On = α for all limit ordinals α.

Recall that a structure ⟨U, ∈, A_{1}, ..., A_{m}⟩ is called amenable if and only if A_{i} ∩ x ∈ U whenever 1 ≤ i ≤ m and x ∈ U. Lemma 1.5 together with (I.1) readily gives the following.

1.8 Lemma. Let A be a set or proper class, and let α be a limit ordinal. Let B ∈ Σ_{0}^{J_{α}^{A}}. Then ⟨J_{α}^{A}, B⟩ is amenable, i.e., J_{α}^{A} is a model of Σ_{0} comprehension in the language L_{Ȧ,Ḃ} with ˙∈, Ȧ and Ḃ.

5The above list in fact contains more functions than the list from [?, Lemma 1.8]; this enlargement yields the transitivity of each S_{α}^{A}.

1.9 Definition. A J-structure is an amenable structure of the form ⟨J_{α}^{A}, B⟩ for a limit ordinal α and predicates A, B.

Here, ⟨J_{α}^{A}, B⟩ denotes the structure ⟨J_{α}^{A}, ∈↾ J_{α}^{A}, A ∩ J_{α}^{A}, B ∩ J_{α}^{A}⟩. Any J_{α}^{A} is a J-structure.

1.10 Lemma. Let J_{α}^{A} be a J-structure.

(1) For all β < α, ⟨S_{γ}^{A}; γ < β⟩ ∈ J_{α}^{A}. In particular, S_{β}^{A} ∈ J_{α}^{A} for all β < α.

(2) ⟨S_{γ}^{A}; γ < α⟩ is uniformly Σ_{1}^{J_{α}^{A}}. That is, “x = S_{γ}^{A}” is Σ_{1} over J_{α}^{A} as witnessed by a formula which does not depend on α.

Proof. (1) and (2) are shown simultaneously by induction on ⟨α, β⟩, ordered lexicographically. Fix α and β < α. If β is a limit ordinal then inductively

by (2), ⟨S_{γ}^{A}; γ < β⟩ is Σ_{1}^{J_{β}^{A}}, and hence ⟨S_{γ}^{A}; γ < β⟩ ∈ J_{α}^{A} by Lemma 1.7. If β = δ + 1 then inductively by (1), ⟨S_{γ}^{A}; γ < δ⟩ ∈ J_{α}^{A}. If δ is a limit ordinal

then S_{δ}^{A} = ⋃_{γ<δ} S_{γ}^{A} ∈ J_{α}^{A}, and if δ = δ̄ + 1 then S_{δ}^{A} = SA ; δ̄ ∪ S^{A}(SA ; δ̄) ∈ J_{α}^{A}

as well. It follows that ⟨S_{γ}^{A}; γ < β⟩ ∈ J_{α}^{A}. (2) is then not hard to verify. ⊣

We may recursively define a well-ordering <_{β}^{A} of S_{β}^{A} as follows. If β is a limit ordinal then we let <_{β}^{A}= ⋃_{γ<β} <_{γ}^{A}. Now suppose that β = β̄+ 1. The order <A ; β̄ induces a lexicographical order, call it <_{β̄,lex}^{A}, of 16 × SA ; β̄ × SA ; β̄. We may then set

x <_{β}^{A} y ⟺ \begin{cases}x, y ∈ SA ; β̄ and x <A ; β̄ y, or else \\ x ∈ SA ; β̄ ∧ y ∉ SA ; β̄, or else \\ x, y ∉ SA ; β̄ and (i, u_{x}, v_{x}) <_{β̄,lex}^{A} (j, u_{y}, v_{y}) \\ where (i, u_{x}, v_{x}) is <_{β̄,lex}^{A} −minimal with x = F_{i}(u_{x}, v_{x}) \\ and (j, u_{y}, v_{y}) is <_{β̄,lex}^{A} −minimal with y = F_{j}(u_{y}, v_{y}). \end{cases}

The following is easy to prove.

1.11 Lemma. Let J_{α}^{A} be a J-structure.

(1) For all β < α, ⟨<_{γ}^{A}; γ < β⟩ ∈ J_{α}^{A}. In particular, <_{β}^{A}∈ J_{α}^{A} for all β < α.

(2) ⟨<_{γ}^{A}; γ < α⟩ is uniformly Σ_{1}^{J_{α}^{A}}. That is, “x =<_{γ}^{A}” is Σ_{1} over J_{α}^{A} as witnessed by a formula which does not depend on α.

If M = J_{α}^{A}, then we shall also write <_{M} for <_{α}^{A}.

We shall now start working towards showing that J-structures have Σ_{1} definable Σ_{1} Skolem functions.

In what follows we shall fix a recursive enumeration ⟨φ_{i}; i ∈ ω⟩ of all Σ_{1} formulae of the language LȦ. (What we shall say easily generalizes to L_{Ȧ_{1},...,Ȧ_{m}}.) We shall denote by ⌜φ⌝ the Gödel number of φ, i.e., ⌜φ⌝ = i iff φ = φ_{i}. We may and shall assume that if φ̄ is a proper subformula of φ then ⌜φ̄⌝ < ⌜φ⌝. We shall write v(i) for the set of free variables of φ_{i}. Recall that all the relevant syntactical concepts are representable in (weak fragments of) Peano arithmetic, so that the representability of these concepts is immediate.

Let M be a structure for LȦ. We shall express by ⊧_{M}^{Σ_{1}} φ_{i}[a] the fact that a: v(i) → M, i.e., a assigns elements of M to the free variables of φ_{i}, and φ_{i} holds true in M under this assignment. We shall also write ⊧_{M}^{Σ_{1}} for the set of ⟨i, a⟩ such that ⊧_{M}^{Σ_{1}} φ_{i}[a]. We shall express by ⊧_{M}^{Σ_{0}} φ_{i}[a] the fact that ⊧_{M}^{Σ_{1}} φ_{i}[a] holds, but with φ_{i} being a Σ_{0} formula, and we shall write ⊧_{M}^{Σ_{0}} for the set of ⟨i, a⟩ such that ⊧_{M}^{Σ_{0}} φ_{i}[a].

It turns out that once we have verified that ⊧_{M}^{Σ_{0}} is uniformly Δ_{1} over J-structures M (which are structures of LȦ), we easily get that ⊧_{M}^{Σ_{1}} is Σ_{1} definable over such structures and that these structures admit Σ_{1} definable Σ_{1} Skolem functions. R on M is Δ_{1} iff R, ¬ R are both Σ_{1}.

Let us fix a J-structure M = J_{α}^{A}, a structure for LȦ.

1.12 Proposition. Let N ∈ M be transitive. For each n < ω, there is a unique f = f_{n}^{N} ∈ M such that dom(f) = n and for all i < n, if φ_{i} is not a Σ_{0} formula then f(i) = ∅, and if φ_{i} is a Σ_{0} formula then

f(i) = {a ∈ ^{v(i)}N ; ⊧_{N}^{Σ_{0}} φ_{i}[a]}.

Proof. As uniqueness is clear, let us verify inductively that f_{n}^{N} ∈ M. Well, f_{0}^{N} = ∅ ∈ M. Now suppose that f_{n}^{N} ∈ M. If φ_{n} is not Σ_{0}, then f_{n+1}^{N} = f_{n}^{N} ∪ {⟨n, ∅⟩} ∈ M. Now let φ_{i} be Σ_{0}. We have that ^{v(n)}N ∈ M, and if

T = {a ∈ ^{v(n)}N ; ⊧_{N}^{Σ_{0}} φ_{n}[a]}

then T ∈ 𝒫(^{v(n)}N) ∩ Σ_{0}^{M}, and thus T ∈ M by Lemma 1.8. Therefore,

f_{n+1}^{N} = f_{n}^{N} ∪ {⟨n, T ⟩} ∈ M.
⊣

Now let Θ(f, N, n) denote the following formula.

N is transitive ∧ f: n → N ∧ ∀i < n [
( i = ⌜v_{i_{0}} ∈ v_{i_{1}}⌝, some v_{i_{0}}, v_{i_{1}} → f(i) = {a ∈ ^{v(i)}N; a(v_{i_{0}}) ∈ a(v_{i_{1}})}) ∧
( i = ⌜Ȧ(v_{i_{0}})⌝, some v_{i_{0}} → f(i) = {a ∈ ^{v(i)}N; a(v_{i_{0}}) ∈ A}) ∧
( i = ⌜ψ_{0} ∧ ψ_{1}⌝, some ψ_{0}, ψ_{1} →

f(i) = {a ∈ ^{v(i)}N; a ↾ v(⌜ψ_{0}⌝) ∈ f(⌜ψ_{0}⌝) ∧ a ↾ v(⌜ψ_{1}⌝) ∈ f(⌜ψ_{1}⌝)}) ∧

( i = ⌜∃v_{i_{0}} ∈ v_{i_{1}}ψ⌝, some v_{i_{0}}, v_{i_{1}}, ψ, where ψ is Σ_{0} →

f(i) = {a ∈ ^{v(i)}N; ∃x ∈ a(v_{i_{1}})

(a ∪ {⟨v_{i_{0}}, x⟩}) ↾ v(⌜ψ⌝) ∈ f(⌜ψ⌝)}) ∧
( i = ⌜φ⌝, some φ, where φ is not Σ_{0} → f(i) = ∅ ].

It is straightforward to check that Θ(f, N, n) holds (in M) if and only if f = f_{n}^{N}. Now Proposition 1.12 and the fact that every element of M is contained in a transitive element of M (for instance in some S_{β}^{A}; cf. Lemma 1.10) immediately gives the following.

1.13 Proposition. Let φ_{i} be Σ_{0}, and let a: v(i) → M. Then ⊧_{M}^{Σ_{0}} φ_{i}[a] if and only if

M ⊧ ∃f ∃N (ran(a) ⊆ N ∧ Θ(f, N, i + 1) ∧ a ∈ f(i)),

if and only if

M ⊧ ∀f ∀N ((ran(a) ⊆ N ∧ Θ(f, N, i + 1)) → a ∈ f(i)).

In particular, the relation ⊧_{M}^{Σ_{0}} is Δ_{1}^{M}.

We are now ready to prove two important results.

1.14 Theorem. Let M = J_{α}^{A} be a J-structure. The Σ_{1}-satisfaction relation ⊧_{M}^{Σ_{1}} is then uniformly Σ_{1}^{M}.

If M is a structure then h is a Σ_{1} Skolem function for M if

h: ⋃_{i<ω}{i} ×^{v(i)}|M| → |M|,

where h may be partial, and whenever φ_{i} = ∃v_{i_{0}}φ_{j} and a: v(i) → |M| then

∃y ∈ |M| ⊧_{M}^{Σ_{1}} φ_{j}[a ∪ {⟨v_{i_{0}}, y⟩} ↾ v(j)]
⟹ ⊧_{M}^{Σ_{1}} φ_{j}[a ∪ {⟨v_{i_{0}}, h(i, a)⟩} ↾ v(j)].

1.15 Theorem. Let M be a J-structure. There is a Σ_{1} Skolem function h_{M} which is uniformly Σ_{1}^{M}.

The above two theorems are to be understood as follows. There are Σ_{1}-formulae Φ, Ψ such that whenever M is a J-structure,

a) Φ defines ⊧_{M}^{Σ_{1}}, i.e. ⊧_{M}^{Σ_{1}} φ_{i}[a] ↔ M ⊧ Φ(i, a), and

b) Ψ defines h_{M}, i.e. y = h_{M}(i, a) ↔ M ⊧ Ψ(i, a, y).

Proof of Theorem 1.14. We have that ⊧_{M}^{Σ_{1}} φ_{i}[a] iff

∃b ∈ M ∃⟨v_{i_{0}}, ..., v_{i_{k}}, j⟩, some v_{i_{0}}, ..., v_{i_{k}}, j [ i = ⌜∃v_{i_{0}} ⋯ ∃v_{i_{k}}φ_{j}⌝ ∧
φ_{j} is Σ_{0} ∧ a, b are functions ∧ dom(a) = v(i) ∧
dom(b) = v(j) ∧ a = b ↾ v(i) ∧ ⊧_{M}^{Σ_{0}} φ_{j}[b] ].

Here, ⊧_{M}^{Σ_{0}} is uniformly Δ_{1}^{M} by Proposition 1.13. The rest follows. ⊣

Proof of Theorem 1.15. The idea here is to let y = h_{M}(i, a) be the “first component” of a minimal witness to the Σ_{1} statement in question (rather than letting y be minimal itself). We may let y = h_{M}(i, a) iff

∃N ∃β ∃R ∃b, all in M, ∃⟨v_{i_{0}}, ..., v_{i_{k}}, j⟩, some v_{i_{0}}, ..., v_{i_{k}}, j [

N = S_{β}^{A} ∧ R =<_{β}^{A} ∧i = ⌜∃v_{i_{0}} ⋯ ∃v_{i_{k}}φ_{j}⌝ ∧ φ_{j} is Σ_{0} ∧ a, b are functions ∧

dom(a) = v(i) ∧ dom(b) = v(j) ∧ a = b ↾ v(i) ∧ ran(b) ⊆ N ∧ ⊧_{M}^{Σ_{0}} φ_{j}[b] ∧ ∀b̄ ∈ N((b̄ is a function ∧ dom(b̄) = v(j) ∧

a = b̄ ↾ v(i) ∧ ran(b̄) ⊆ N ∧ b̄ R b) → ¬ ⊧_{M}^{Σ_{0}} φ_{j}[b̄])∧ y = b(v_{i_{0}}) ].

Here, “N = S_{β}^{A}” and “R =<_{β}^{A}” are uniformly Σ_{1}^{M} by Lemmata 1.10 (2) and 1.11 (2), and ⊧_{M}^{Σ_{0}} is uniformly Δ_{1}^{M} by Proposition 1.13. Therefore, the rest follows. ⊣

If we were to define a Σ_{2} Skolem function for M in the same manner then we would end up with a Σ_{3} definition. Jensen solved this problem by showing that under favourable circumstances Σ_{n} over M can be viewed as Σ_{1} over a “reduct” of M. Reducts will be introduced in the fifth section of this chapter.

Another useful fact is the so-called condensation lemma.^{6}

1.16 Theorem. Let M = ⟨J_{α}^{A}, B⟩ be a J-structure, and let π: M̄ ⟶_{Σ_{1}} M

where M̄ is transitive. Then M̄ is a J-structure, i.e., there are ᾱ ≤ α, Ā, and B̄ such that M̄ = ⟨J Ā ; ᾱ, B̄⟩.

Proof. Set ᾱ = On ∩ M̄ ≤ α, Ā = π^{−1}”A, and B̄ = π^{−1}”B. We claim that

M̄ = ⟨J Ā ; ᾱ, B̄⟩.

Well, Lemma 1.10 easily gives that SĀ ; β ∈ M̄ whenever β < ᾱ. Therefore, J A ; ᾱ ⊆ M̄. On the other hand, let x ∈ M̄. Then π(x) ∈ S_{β}^{A} for some β < α, and hence x ∈ SĀ ; β for some β < ᾱ. ⊣

6For n < ω, X ≺_{Σ_{n}} M means that Σ_{n} formulae with parameters taken from X are absolute between X and M. To have π: M̄ ⟶_{Σ_{n}} M means that ran(π) ≺_{Σ_{n}} M.

We also want to write h_{M}(X) for the closure of X under h_{M}, more precisely:

Convention. Let M = J_{α}^{A} be a J-structure, and let X ⊆ |M|. We shall write h_{M}(X) for h_{M}”(⋃_{i<ω}({i} ×^{v(i)}X)).

Using Theorem 1.15, it is easy to verify that h_{M}(X) ≺_{Σ_{1}} M. There will be no danger of confusing the two usages of “h_{M}.” [X]^{<ω} denotes the set of all finite subsets of X.

1.17 Lemma. Let M = J_{α}^{A} be a J-structure. There is then some surjective f: [α]^{<ω} → M which is Σ_{1}^{M}.

If α is closed under the Gödel pairing function, then there is a surjection g: α → J_{α}^{A} which is Σ_{1}^{M}. For an arbitrary α, there is a surjection h: α → J_{α}^{A} which is Σ_{1}^{M}.

Proof. We have that h_{M}(α) ≺_{Σ_{1}} M, and hence h_{M}(α) = M. But it is straightforward to construct a surjective g′: [α]^{<ω} → ⋃_{i<ω}({i} × ^{v(i)}α) which is Σ_{1}^{M}. We may then set f = h_{M} ∘ g′.

As to the existence of g, let Φ: otp(<_{α}^{A}) → J_{α}^{A} denote the enumeration of J_{α}^{A} according to <_{α}^{A}. It is not hard to verify by a simultaneous induction (cf. the proof of Lemma 1.10) that for all limit ordinals β ≤ α, Φ ↾ β is

Σ_{1}^{J_{β}^{A}} and for all γ < β, Φ ↾ γ ∈ J_{β}^{A}. But now if α is closed under the Gödel pairing function then otp(<_{α}^{A}) = α.

The existence of h is established by [?, Lemma 2.10]. ⊣

In the following we describe a useful class of formulae, which lies somewhere between Σ_{1} and Π_{2}. It turns out that many notions can be expressed by statements belonging to this class.

1.18 Definition. We say that φ is a Q-formula iff φ is of the form

∀ u ∃ v ⊇ u ψ(v),

where ψ is Σ_{1} and does not contain u. Instead of ∀ u ∃ v ⊇ u we write briefly Qv. The above formula then has the form Qv ψ(v) and we read “for cofinally many v, ψ(v)”. A map π which preserves Q formulae is called Q-preserving and we write

π : M̄ ⟶_{Q} M.

A property which is characterized by a Q-formula is also called a Q-condition.

1.19 Definition. Let U, V be transitive structures. A map σ : U → V is cofinal iff for all y ∈ V there is some x ∈ U such that y ⊆ σ(x).

Let σ : U ⟶_{Σ_{1}} V, where U, V are transitive structures, and let φ be a

Q-formula. It is easy to see that

a) φ is preserved downwards,

b) if σ is cofinal, then φ is preserved upwards.

Note also that Q-formulae are closed under ∧ and ∨ (modulo the “basic set theory” of [?, p. 36]).

We now introduce the notion of acceptability which is fundamental for the general fine structure theory. As will follow from the definition, acceptability can be considered as a strong version of GCH.

1.20 Definition. A J-structure M = ⟨J_{α}^{A}, B⟩ is acceptable iff the following holds: Whenever ξ < α is a limit ordinal and 𝒫(τ) ∩ J_{ξ+ω}^{A} ⊈ J_{ξ}^{A} for some τ < ξ, there is a surjective map f : τ → ξ in J_{ξ+ω}^{A}. (This means that Card(ξ) ≤ τ in J_{ξ+ω}^{A}.)

1.21 Lemma. Being an acceptable J-structure is a Q-property. More precisely: There is a fixed Q-sentence Ψ such that for any M = ⟨|M|, A, B⟩ which is transitive and closed under pairing, M is an acceptable J-structure iff M ⊧ Ψ.

Proof. The statement ⟨|M|, A⟩ = J_{α}^{A} is a Q-condition for ⟨|M|, A⟩, as we may write this as

Qu ∃β u = S_{β}^{A}.

Here, “u = S_{β}^{A}” is the Σ_{1} formula from Lemma 1.10 (2). Amenability can be expressed by

Qu ∃ z z = B ∩ u.

It only remains to prove that the fact that we collapse ξ whenever we add a new bounded subset is expressible in a Q-fashion. We note first that a J-structure M is acceptable iff the following holds in M:

\{ \begin{matrix}∀ limit ordinals ξ ∃ n ∈ ω ∀ m ≥ n ∀ τ < ξ \\ [𝒫(τ) ∩ S_{ξ+m}^{A} ⊈ S_{ξ}^{A} ⟹ ∃ f ∈ S_{ξ+m}^{A} f : τ ⟶^{onto} ξ]. \end{matrix}  (I.2)

Denote the sentence from (I.2) by ψ. It is easy to see that if M satisfies ψ then M is acceptable. To see the converse, fix a limit ordinal ξ and suppose there is a τ < ξ such that 𝒫(τ) ∩ S_{ξ+ω}^{A} ⊈ S_{ξ}^{A}. Let τ be minimal with this property. By acceptability of M, there is an n ∈ ω such that S_{ξ+n}^{A} contains a function f mapping τ onto ξ. Using f, it is easy to construct a surjective map f_{τ′} : τ′ → ξ for any τ′ < ξ whose power set in S_{ξ+ω}^{A} is larger than that in S_{ξ}^{A} (since τ′ ≥ τ) and it follows immediately that f_{τ′} ∈ S_{ξ+n+k}^{A} for some k < ω; so we have a uniform bound for all such functions.

If the height of M is ωα for some limit α, then acceptability is equivalent to the statement

Qξ S_{ξ}^{A} ⊧ ψ.

Otherwise we have to state (I.2) explicitly for the last level. Hence, the desired condition is then

\{ \begin{matrix}⟨|M|, A, B⟩ is an amenable J-structure ∧ \\ Qζ (lim(ζ) ⟹ S_{ζ}^{A} ⊧ ψ) ∧ [Qζ (ζ is a limit) ∨ φ] \end{matrix}  (I.3)

where φ is the sentence

Qζ ∃ β < ζ [lim(β) ∧ ∀ η < ζ (η > β → succ(η)) ∧ φ′(β, ζ)]

and φ′(β, ζ) is the formula

∀ τ < β [∃ u ∈ S_{ζ}^{A} (u ∉ S_{β}^{A} ∧ u ⊆ τ) ⟹ ∃ f ∈ S_{ζ}^{A} f : τ ⟶^{onto} β].

φ is clearly a Q-sentence, hence (I.3) is a Q-sentence as well. Denote this formula by Ψ. Then M is an acceptable J-structure iff M ⊧ Ψ. ⊣

1.22 Corollary. a) If π : M̄ ⟶_{Σ_{1}} M and M is acceptable, then so is M̄.

b) If π : M̄ ⟶_{Q} M and M̄ is acceptable, then so is M. This holds in

particular if π is a Σ_{0} preserving cofinal map.

1.23 Lemma. Let M = J_{α}^{A} be acceptable and let ρ ∈ M be an infinite cardinal in M. Given u ∈ J_{ρ}^{A}, any a ∈ M which is a subset of u is in fact an element of J_{ρ}^{A}.

Proof. Since u ∈ J_{ρ}^{A}, there is some τ < ρ and a surjective map g : τ → u in J_{ρ}^{A} (cf. Lemma 1.17). Set ā = g^{−1}”a. Then ā ⊆ τ and a ∈ J_{ρ}^{A} ⟺

ā ∈ J_{ρ}^{A}. But if ā ∉ J_{ρ}^{A}, then there is an f : τ ⟶^{onto} ξ, where ξ is such that ā ∈ J_{ξ+ω}^{A} \ J_{ξ}^{A}; hence ξ ≥ ρ. This contradicts the fact that ρ is a cardinal in J_{α}^{A}. Consequently, a ∈ J_{ρ}^{A}. ⊣

1.24 Lemma. Let M be as above and ρ an infinite successor cardinal in M. Let a ⊆ J_{ρ}^{A} be such that a ∈ M and Card(a) < ρ in M. Then a ∈ J_{ρ}^{A}.

Proof. Let γ < ρ and g ∈ M be such that g : γ ⟶^{onto} a. Define f : γ → ρ by

ζ = f(ξ) ⟺ g(ξ) ∈ S_{ζ+ω}^{A} \ S_{ζ}^{A}.

Then f ∈ M.

Claim. f is bounded in ρ.

Suppose this Claim to hold true. Let δ < ρ be such that rng(f) ⊆ δ. Then a ⊆ S_{δ}^{A} ∈ J_{ρ}^{A} and, by Lemma 1.23, a ∈ J_{ρ}^{A}. Hence it suffices to prove the Claim.

Suppose f is unbounded in ρ. Define G : ρ → M by

G(η) = the <_{α}^{A}-least function of γ onto η.

This is possible since ρ is a successor cardinal in M, so we can pick γ large enough that all we have done so far goes through. Clearly G is definable over J_{ρ}^{A}, hence G ∈ M. Now define F : γ × γ ⟶^{onto} ρ by

F (ξ, η) = G(f(ξ))(η).

Then F ∈ M. By Lemma 1.17, there is some surjection g: γ → γ × γ which

is Σ_{1}^{J_{γ}^{A}}; hence g ∈ M. But then F ∘g ∈ M witnesses that ρ is not a cardinal in M. This contradiction yields the Claim. ⊣

1.25 Corollary. Let M, ρ be as in Lemma 1.24. Then J_{ρ}^{A} ⊧ ZFC^{−}.

Proof. The point here is to verify the separation and replacement schemata in J_{ρ}^{A}, since the rest of the axioms hold in J_{ρ}^{A} automatically. The former follows from Lemma 1.23 and the latter from Lemma 1.24 in a straightforward way. ⊣

1.26 Corollary. Let M be as above where ρ > ω is a limit cardinal in M. Then J_{ρ}^{A} ⊧ ZC (where ZC is Zermelo set theory with choice).

Proof. We only have to verify the power set axiom; the rest goes through as before. Let a ∈ J_{ρ}^{A}. Pick γ < ρ such that γ is a cardinal in J_{ρ}^{A} and a ∈ J_{γ}^{A}. Then for every x ∈ 𝒫(a) ∩ J_{ρ}^{A}, x ∈ J_{γ}^{A}. Hence 𝒫(a) ∩ J_{ρ}^{A} ∈ J_{ρ}^{A}. ⊣

1.27 Corollary. Let M, ρ be as above. Then

|J_{ρ}^{A}| = H_{ρ}^{M} =^{def}{x ∈ M ; Card (TC(x)) < ρ in M}.

Proof. Clearly |J_{ρ}^{A}| ⊆ H_{ρ}^{M}. So it is sufficient to prove the converse. Suppose it fails. Let ρ be the least counterexample. Then ρ is a successor cardinal in M. Let x ∈ H_{ρ}^{M} be ∈-minimal such that x ∉ J_{ρ}^{A}. Then x ⊆ J_{ρ}^{A}. Since card(x) < ρ in M, x ∈ J_{ρ}^{A} by Lemma 1.23. Contradiction. ⊣

2. The first projectum

We now introduce the central notions of fine structure theory – the notions projectum, standard code and good parameter. We stress that we are working with arbitrary J-structures and that these structures have, in general, very few closure properties. This means that there might be bounded definable subsets of these structures (in a precise sense) failing to be elements. However, each J-structure has an initial segment which is “firm” in the sense that it does contain all sets reasonably definable over the whole structure. The height of this “firm” segment is called the projectum. Standard codes are (boldface) definable relations computing truth and good parameters are parameters which occur in the definitions of standard codes.

2.1 Definition. The Σ_{1}-projectum (or, first projectum) ρ(M) of an acceptable J-structure M = J_{α}^{A} is defined by

ρ(M) = the least ρ ∈ On such that 𝒫(ρ) ∩ Σ_{1}^{M} ⊈ M.

2.2 Lemma. Let M be as above. If ρ(M) ∈ M, then ρ(M) is a cardinal in M.

Proof. Suppose not. Set ρ = ρ(M). Let f ∈ M be such that f : γ ⟶^{onto} ρ for some γ < ρ and A ∈ Σ_{1}^{M} be such that a = A ∩ ρ ∉ M. Let ā = f^{−1}′′a. Then ā ∉ M, since otherwise a = f”ā ∈ M. On the other hand, ā ∈ M by the definition of ρ, since ā ⊆ γ and ā ∈ Σ_{1}^{M}. Contradiction. ⊣

2.3 Lemma. Let M be as above and ρ = ρ(M). Then ρ is a Σ_{1}-cardinal in M (i.e. there is no Σ_{1}^{M} partial map from some γ < ρ onto ρ).

Proof. Suppose there is such a map, say f : γ ⟶^{onto} ρ. We know that there

is a Σ_{1}^{J_{ρ}^{A}} map of ρ onto J_{ρ}^{A} (cf. Lemma 1.17). Hence there is a Σ_{1}^{M} map

g : γ ⟶^{onto} J_{ρ}^{A}. Define a set b by

ξ ∈ b ⟺ ξ ∉ g(ξ).

Then b is clearly Σ_{1}^{M} and b ⊆ γ. Moreover, b ∉ J_{ρ}^{A} by a diagonal argument: if b ∈ J_{ρ}^{A} then b = g(ξ_{0}) for some ξ_{0} < γ which would give ξ_{0} ∈ b = g(ξ_{0}) iff ξ_{0} ∉ g(ξ_{0}). Hence b ∉ M: this follows from Lemma 1.23 if ρ ∈ M and is immediate otherwise. On the other hand, γ < ρ, and therefore b ∈ M. Contradiction! ⊣

Lemma 1.17 and Lemma 1.23 now immediately give the following.

2.4 Corollary. Let M be acceptable and ρ = ρ(M).

(a) If B ⊆ J_{ρ}^{A} is Σ_{1}^{M}, then ⟨J_{ρ}^{A}, B⟩ is amenable.

(b) |J_{ρ}^{A}| = H_{ρ}^{M}.

Recall that we fixed a recursive enumeration ⟨φ_{i}; i < ω⟩ of all Σ_{1} formulae. In what follows it will be convenient to pretend that each φ_{i} has exactly one free variable. For instance, if φ_{i} = φ_{i}(v_{i_{1}}, ..., v_{i_{ℓ}}) with all free variables shown then we might confuse φ_{i} with

∃v_{i_{1}}...∃v_{i_{ℓ}}(u = ⟨v_{i_{1}}, ..., v_{i_{ℓ}}⟩ ∧ φ_{i}(v_{i_{1}}, ..., v_{i_{ℓ}})).

To make things even worse, we shall nevertheless frequently write φ_{i}(x_{1}, ..., x_{ℓ}) instead of φ_{i}(⟨x_{1}, ..., x_{ℓ}⟩). If a: v(i) → V assigns values to the free variable(s) v_{i_{1}}, ..., v_{i_{ℓ}} of φ_{i} then, setting x_{1} = a(v_{i_{1}}), ..., x_{ℓ} = a(v_{i_{ℓ}}) we shall use the more suggestive M ⊧ φ_{i}(x_{1}, ..., x_{ℓ}) rather than ⊧_{M}^{Σ_{1}} φ_{i}[a] in what follows. We shall also write h_{M}(i, x⃗) instead of h_{M}(i, a).

2.5 Definition. Let M = ⟨J_{α}^{B}, D⟩ be an acceptable J-structure, ρ = ρ(M) and p ∈ M. We define

A_{M}^{p} = {⟨i, x⟩ ∈ ω × H_{ρ}^{M}; M ⊧ φ_{i}(x, p)}.

A_{M}^{p} is called the standard code determined by p. Let us stress that A_{M}^{p} is the intersection of ω × H_{ρ}^{M} with a set Ã_{M}^{p} (defined in an obvious way) which is Σ_{1}^{M}({p}). We shall often write A_{M}^{p}(i, x) instead of ⟨i, x⟩ ∈ A_{M}^{p}. The structure

M^{p} = ⟨J_{ρ}^{B}, A_{M}^{p}⟩

is called the reduct determined by p. If δ = ρ or δ < ρ where δ is a cardinal in M, we also set

A_{M}^{p,δ} = A^{p} ∩ J_{δ}^{B}
M^{p,δ} = ⟨J_{δ}^{B}, A_{M}^{p,δ}⟩.

We shall omit the subscript _{M} whenever there is no danger of confusion.

2.6 Definition. Let M be acceptable and ρ = ρ(M).

P_{M} =  the set of all p ∈ [ρ(M), On ∩ M)^{<ω} for which
there is a B ∈ Σ_{1}^{M}({p}) such that B ∩ ρ ∉ M.

The elements of P_{M} are called good parameters.

2.7 Lemma. Let M be as before, p ∈ M and A = A_{M}^{p}. Then

p ∈ P_{M} ↔ A ∩ (ω × ρ(M)) ∉ M.

Proof. (→) Pick B which witnesses that p ∈ P_{M}. Suppose B is defined by φ_{i}. Hence B(ξ) ↔ ⟨i, ξ⟩ ∈ A, which means that if A ∩ (ω × ρ(M)) is in M, then so is B ∩ ρ(M). Hence the former is not an element of M.

(←) Suppose A ∩ (ω × ρ(M)) ∉ M. Let f : ω × ρ(M) ⟶ ρ(M) be defined by f(i, ωξ + j) = ωξ + 2^{i} · 3^{j}. Clearly f is Σ_{1}^{M} uniformly and if ρ(M) ∈ M then f ∈ M. Let B = f”A. Then B is Σ_{1}^{M}({p}) and B ∩ ρ(M) ∉ M: if ρ(M) ∈ M, this follows from the fact that f ∈ M and A ∩ (ω × ρ(M)) = f^{−1}”(B ∩ ρ(M)); if ρ(M) ∉ M, it follows from the fact that B is cofinal in ρ(M). ⊣

2.8 Definition. Let M be acceptable and ρ = ρ(M). We set

R_{M} = the set of all r ∈ [ρ(M), On ∩ M)^{<ω}such that h_{M}(ρ ∪ {r}) = |M|.

The elements of R_{M} are called very good parameters.

2.9 Lemma. R_{M} ⊆ P_{M} ≠ ∅.

Proof. By the proof of Lemma 1.17, h_{M}(On ∩ M) = M for any J-structure M. Given an acceptable structure M, if A is a relation which is Σ_{1}^{M}({p}) for some p ∈ M then A is therefore also Σ_{1}^{M}({q}) for some q ∈ [On∩M]^{<ω}. As ρ(M) is closed under the Gödel pairing function (if ρ(M) < On ∩ M), the inequality easily follows. As to the inclusion, define the set a ⊆ ω ×On∩M by

⟨i, ξ⟩ ∈ a ⟺ ⟨i, ξ⟩ ∉ h_{M}(i, ⟨ξ, p⟩)

for a p ∈ R_{M}. By a diagonal argument, a ∩ ω × ρ(M) ∉ M and a is Σ_{1}(M) in p. Using the map f from the proof of Lemma 2.7 it is easy to turn the set a into some b ⊆ On ∩ M such that b is Σ_{1}^{M} in p and b ∩ ρ(M) ∉ M. ⊣

We remark that P_{M} and R_{M} are often defined differently so as to include arbitrary elements of M rather than just finite sequences of ordinals in the half-open interval [ρ(M), On ∩ M).

3. Downward extension of embeddings

Given a Σ_{0} preserving map between the reducts of two acceptable structures, the question naturally arises whether the map can be extended to a map between the original structures. It turns out that this is possible. The conjunction of the following three lemmas is called the downward extension of embeddings lemma.

3.1 Lemma. Let π : M̄ p̄ ⟶_{Σ_{0}} M^{p}, where p̄ ∈ RM̄. Then there is a unique

π̃ : M̄ ⟶_{Σ_{0}} M such that π̃ ⊇ π and π̃(p̄) = p. Moreover, π̃ : M̄ ⟶_{Σ_{1}} M.

Proof. Uniqueness: Assume that π̃ has the above properties. Let x ∈ M̄. Then x = hM̄(i, ⟨ξ, p̄⟩) for some i ∈ ω and ξ < ρ(M). Let H̄ be ΣM̄ ; 0 such that ∃ z H̄(z, x, i, ξ, p̄) defines the Skolem function hM̄ (this involves a slight abuse of notation). H̄ has a uniform definition, so let H have the same definition over M. Pick z such that H̄(z, x, i, ξ, p̄). Since π̃ is Σ_{0} preserving, we have H(π̃(z), π̃(x), i, π̃(ξ), p), i.e. π̃(x) = h_{M}(i, ⟨π̃(ξ), p⟩) = h_{M}(i, ⟨π(ξ), p⟩). Hence, there is at most one such π̃.

Existence: The above proof of uniqueness suggests how to define the extension π̃. Here we show that such a definition is correct. We first observe:

Claim. Suppose that φ(v_{1}, …, v_{ℓ}) is a Σ_{1}-formula. Let x̄_{i} = hM̄(j_{i}, ⟨ξ̄_{i}, p̄⟩) for some j_{i} ∈ ω, ξ̄_{i} < ρ(M) and x_{i} = h_{M}(j_{i}, ⟨ξ_{i}, p⟩) where ξ_{i} = π(ξ̄_{i}) (i = 1, …, ℓ). Then

M̄ ⊧ φ(x̄_{1}, …, x̄_{ℓ}) iff M ⊧ φ(x_{1}, …, x_{ℓ}).

Proof. M̄ ⊧ φ(x̄_{1}, …, x̄_{ℓ}) is equivalent to

M̄ ⊧ φ(hM̄(j_{1}, ⟨ξ̄_{1}, p̄⟩), …, hM̄(j_{ℓ}, ⟨ξ̄_{ℓ}, p̄⟩)).

Since hM̄ has a uniform Σ_{1}-definition over M̄, there is a Σ_{1}-formula ψ such that the above is equivalent to

M̄ ⊧ ψ(ξ̄_{1}, …, ξ̄_{ℓ}, p̄).  (I.4)

The formula ψ clearly does not depend on the actual structure in question, so the statement M ⊧ φ(x_{1}, …, x_{ℓ}) is equivalent to

M ⊧ ψ(ξ_{1}, …, ξ_{ℓ}, p).  (I.5)

Now suppose ψ(ξ_{1}, …, ξ_{ℓ}, p) ⟺ φ_{k}(⟨ξ_{1}, …, ξ_{ℓ}⟩, p) in our fixed recursive enumeration of Σ_{1} formulae, hence (I.4) is equivalent to

Ap̄ ; M̄(k, ⟨ξ̄_{1}, …, ξ̄_{ℓ}⟩)  (I.6)

and (I.5) is equivalent to

A_{M}^{p}(k, ⟨ξ_{1}, …, ξ_{ℓ}⟩).  (I.7)

Since π is Σ_{0} preserving, (I.6) and (I.7) are equivalent. ⊣

Now define π̃ by

π̃(hM̄(i, ⟨ξ, p̄⟩)) ≃ h_{M}(i, ⟨π(ξ), p⟩)

for i ∈ ω and ξ < ρ(M̄). We have to verify several facts:

– π̃ is well defined. Let hM̄(j_{1}, ⟨ξ̄_{1}, p̄⟩) = hM̄(j_{2}, ⟨ξ̄_{2}, p̄⟩) for some j_{1}, j_{2} ∈ ω and ξ̄_{1}, ξ̄_{2} < ρ(M̄). We have to show that h_{M}(j_{1}, ⟨ξ_{1}, p⟩) = h_{M}(j_{2}, ⟨ξ_{2}, p⟩), where ξ_{i} = π(ξ̄_{i}) (i = 1, 2). By the above claim, this follows immediately.

– π̃ is Σ_{1} preserving. Since π̃ is a well defined map, this follows immediately from the above claim.

– π̃ ⊇ π.

There is an i ∈ ω such that the equality x = h_{M}(i, ⟨x, q⟩) holds uniformly and independently of q. In particular, for ξ < ρ(M̄) we have ξ = hM̄(i, ⟨ξ, p̄⟩), so

π̃(ξ) = h_{M}(i, ⟨π(ξ), p⟩) = π(ξ).

– π̃(p̄) = p.

Similarly as above, there is an i ∈ ω such that q = h(i, ⟨x, q⟩) uniformly. Hence p̄ = hM̄(i, ⟨0, p̄⟩) and π̃(p̄) = h_{M}(i, ⟨0, p⟩) = p.

⊣

3.2 Lemma. Let M̄, M, p̄, p, π, π̃ be as above. Suppose moreover that

p ∈ R_{M}. Let π : M̄ p̄ ⟶_{Σ_{n}} M^{p}. Then

π̃ : M̄ ⟶_{Σ_{n+1}} M.

Proof. We shall proceed by induction. Suppose the lemma holds for n. Suppose we have a Σ_{n+1} formula φ which is of the form

∃ z_{1} ∀ z_{2} … ∃/∀ z_{n+1} φ̄(z_{1}, …, z_{n+1}, x_{1}, …, x_{ℓ}),  (I.8)

where φ̄ is Σ_{0}. For notational simplicity, assume that n = 2 and ℓ = 1. Given a J-structure N and an arbitrary q ∈ R_{N}, the structure N satisfies (I.8) iff it satisfies the formula

\{ \begin{matrix}∃ξ_{1} < ρ(N) ∃i_{1} ∀ξ_{2} < ρ(N) ∀i_{2} [∃y y = h_{N}(i_{2}, ⟨ξ_{2}, q⟩) ⟹ \\ ∃y_{1} ∃y_{2} ∃x ∃z_{3} (y_{1} = h_{N}(i_{1}, ⟨ξ_{1}, q⟩) ∧ y_{2} = h_{N}(i_{2}, ⟨ξ_{2}, q⟩)∧ \\ x = h_{N}(j_{1}, ⟨ζ_{1}, q⟩) ∧ φ̄(y_{1}, y_{2}, z_{3}, x) ] \end{matrix}  (I.9)

where x_{1} = h_{N}(j_{1}, ⟨ζ_{1}, q⟩). (For an arbitrary n, the analogous fact can be verified by a straightforward induction on n using that q is a very good parameter.) Notice that the matrix in (I.9) is of the form ψ_{1} → ψ_{2}, where both ψ_{1} and ψ_{2} are Σ_{1} via a uniform transformation, i.e., there are k_{1}, k_{2} ∈ ω depending only on φ̄ such that (I.9) can be expressed in a Σ_{2}-fashion over N^{q} in the following way:

∃ξ_{1} ∃i_{1} ∀ξ_{2} ∀i_{2} [ A_{N}^{q}(k_{1}, ⟨ξ_{1}, i_{1}, ξ_{2}, i_{2}, ζ_{1}, j_{1}⟩) ⟹ A_{N}^{q}(k_{2}, ⟨ξ_{1}, i_{1}, ξ_{2}, i_{2}, ζ_{1}, j_{1}⟩) ].

Then, if in fact x_{1} = hM̄(j_{1}, ⟨ζ_{1}, p̄⟩),

M̄ ⊧ φ(x_{1}) ⟺

∃ ξ_{1} ∃i_{1} ∀ ξ_{2} ∀i_{2} [ Ap̄ ; M̄(k_{1}, ⟨ξ_{1}, i_{1}, ξ_{2}, i_{2}, ζ_{1}, j_{1}⟩) ⟹

Ap̄ ; M̄(k_{2}, ⟨ξ_{1}, i_{1}, ξ_{2}, i_{2}, ζ_{1}, j_{1}⟩) ] ⟺

∃ ξ_{1} ∃i_{1} ∀ ξ_{2} ∀i_{2} [ A_{M}^{p}(k_{1}, ⟨ξ_{1}, i_{1}, ξ_{2}, i_{2}, π(ζ_{1}), j_{1}⟩) ⟹

A_{M}^{p}(k_{2}, ⟨ξ_{1}, i_{1}, ξ_{2}, i_{2}, π(ζ_{1}), j_{1}⟩) ]

⟺ M ⊧ φ(π̃(x_{1})).

Similar, but slightly more complicated reductions can be done for arbitrary n; we leave this to the reader. ⊣

3.3 Lemma. Let π : N ⟶_{Σ_{0}} M^{p}, where N is a J-structure and p ∈ R_{M}.

Then there are unique M̄, p̄ such that p̄ ∈ RM̄ and N = M̄^{p}.

Proof. Let M = ⟨J_{α}^{B}, D⟩, M^{p} = ⟨J_{ρ}^{B}, A⟩ and N = ⟨J B̄′ ; ρ̄, Ā⟩. (In particular, A = A_{M}^{p}.) Let also X = rng(π), Y = h_{M}(X ∪ {p}), let M̄ be the transitive collapse of Y and let π̃ : M̄ → Y be the inverse of the Mostowski collapse. The map π̃ is clearly Σ_{1}-preserving, hence M̄ is of the form ⟨J B̄ ; ᾱ, D̄⟩. We shall show that M̄ is the desired structure. We prove first

π̃ ⊇ π and J B̄′ ; ρ̄ = J B̄ ; ρ̄,  (I.10)

which follows immediately from

if x ∈ X, y ∈ Y and y ∈ x, then y ∈ X  (I.11)

since the latter tells us that the collapsing map for Y restricted to X coincides with π^{−1}.

So suppose y = h_{M}(i, ⟨z, p⟩) for some z ∈ X. Since both y, z ∈ M^{p}, this can be equivalently expressed in the form A(k, ⟨y, z⟩) for some k ∈ ω. Thus we have

∃ v ∈ x A(k, ⟨v, z⟩)

which is preserved by a Σ_{0} map, so

∃ v ∈ x̄ Ā(k, ⟨v, z̄⟩)

where (x̄, z̄) = π^{−1}(x, z). Let ȳ ∈ x̄ be such that A(k, ⟨ȳ, z̄⟩). Such a ȳ is uniquely determined: if ȳ_{1} were another one, we would have

A(k, ⟨π(ȳ), z⟩) ∧ A(k, ⟨π(ȳ_{1}), z⟩),

which means that π(ȳ) = h_{M}(i, ⟨z, p⟩) = π(ȳ_{1}), hence ȳ = ȳ_{1}. This argument also shows π(ȳ) = y. Hence y ∈ X.

We have shown I.10 and I.11.

Now let

p̄ = π̃^{−1}(p).

Note that there is a ΣM̄ ; 1 map of ρ̄ onto M̄; this follows immediately from the fact that M̄ = hM̄(J B̄ ; ρ̄ ∪ {p̄}) and that there is a ΣM̄ ; 1 map of ρ̄ onto J B̄ ; ρ̄. So we have

ρ(M̄) ≤ ρ̄.  (I.12)

Note also that if i ∈ ω and x ∈ N, then

Ā(i, x) ⟺ A(i, π̃(x)) ⟺ M ⊧ φ_{i}(π̃(x), p) ⟺ M̄ ⊧ φ_{i}(x, p̄) (I.13)

where ⟨φ_{i}⟩_{i} is the fixed recursive enumeration of the Σ_{1}-formulae. Our aim is to show

ρ(M̄) = ρ̄  (I.14)

which reduces to proving the inequality ρ̄ ≤ ρ(M̄). Let P be ΣM̄ ; 1({q̄}). By the fact that hM̄(J B̄ ; ρ̄ ∪ {p̄}) = M̄ we can find an R which is ΣM̄ ; 1 and such that

P (z) ⟺ R(z, x, p̄)

for some fixed x ∈ N. By (I.13), there is an i ∈ ω such that

P (z) ⟺ Ā(i, ⟨z, x⟩).

Hence if γ < ρ̄ then P ∩ γ is a projection of Ā ∩ ({i} × γ × {x}) ∈ N ⊆ M̄, thus it is itself in M̄. This proves (I.14).

As an immediate consequence of (I.13) and (I.14) we get

Ā = Ap̄ ; M̄.  (I.15)

It only remains to prove that

p̄ ∈ RM̄.  (I.16)

If M̄ = N this is trivial. Otherwise there is a Σ_{1}^{M} map of ρ̄ onto J B̄ ; ρ̄. Since hM̄(J B̄ ; ρ̄ ∪ {p̄}) = M̄, the proof is complete. ⊣

4. Upward extension of embeddings

In this section we present a method which gives a solution to the problem dual to that from the previous section, where we formed the extension of an embedding from the reduct of a J-structure to the whole structure: namely, we now aim to build a target model which can serve as the codomain of an extended embedding. This problem is a bit more delicate than the previous one, since such an extension need not always exist; therefore we have to strengthen our requirements on the embeddings we intend to extend. The difference between forming downward and upward extensions lies in the fact that the former ones are related to taking hulls and collapsing them, which is always possible, whilst the latter ones are related to forming ultrapowers, which have transitive isomorphs only if they are well-founded.

4.1 Definition. π : M̄ → M is a strong embedding iff

a) π : M̄ ⟶_{Σ_{1}} M

b) For any R̄, R such that R̄ is rudimentary over M̄ and R is rudimentary over M by the same definition the following holds:

If R̄ is well-founded, then so is R.

The upward extension of embeddings lemma is the conjunction of the following lemma together with Lemmata 3.1 and 3.2.

4.2 Lemma. Let π : M̄ p̄ → N be a strong embedding, where N is acceptable and p̄ ∈ RM̄. Then there are unique M, p such that N = M^{p} and p ∈ R_{M}. Moreover, π̃ is strong, where π̃ ⊇ π, π̃ : M̄ ⟶_{Σ_{1}} M and π̃(p̄) = p.

Proof. Uniqueness. Suppose π̃_{1} : M̄ → M_{1} and π̃_{2} : M̄ → M_{2} are two extensions of π satisfying the conclusions of the lemma and that p_{1}, p_{2} are the corresponding parameters. Then A_{M_{1}}^{p_{1}} = A_{M_{2}}^{p_{2}}, call it A, and every x ∈ M_{k} is of the form h_{M_{k}}(i, ⟨ξ, p_{k}⟩) for some i ∈ ω and ξ ∈ On ∩ N (k = 1, 2). Let σ : M_{1} → M_{2} be the map sending h_{M_{1}}(i, ⟨ξ, p_{1}⟩) to h_{M_{2}}(i, ⟨ξ, p_{2}⟩). Then σ is well defined since

∃z z = h_{M_{1}}(i, ⟨ξ, p_{1}⟩) ⟺ A(j, ⟨i, ξ⟩) ⟺ ∃z z = h_{M_{2}}(i, ⟨ξ, p_{2}⟩) (I.17)

for an appropriate j (i.e., j is such that ∃z z = h_{M_{k}}(i, ⟨ξ, p_{k}⟩) can be expressed as M_{k} ⊧ φ_{j}(⟨i, ξ⟩) for k = 1, 2). Also, σ is Σ_{1}-preserving, since given any Σ_{1}-formula ψ(v_{1}, …, v_{ℓ}) and x_{s} = h_{M_{1}}(i_{s}, ⟨ξ_{s}, p_{1}⟩) (s = 1, …, ℓ),

M_{1} ⊧ ψ(x_{1}, …, x_{ℓ}) ⟺ M_{1} ⊧ ψ(h_{M_{1}}(i_{1}, ⟨ξ_{1}, p_{1}⟩), …, h_{M_{1}}(i_{ℓ}, ⟨ξ_{ℓ}, p_{1}⟩))
⟺ A(j, ⟨⟨i_{1}, ξ_{1}⟩, …, ⟨i_{ℓ}, ξ_{ℓ}⟩⟩)
⟺ M_{2} ⊧ ψ(h_{M_{2}}(i_{1}, ⟨ξ_{1}, p_{2}⟩), …, h_{M_{2}}(i_{ℓ}, ⟨ξ_{ℓ}, p_{2}⟩))
⟺ M_{2} ⊧ ψ(σ(x_{1}), …, σ(x_{ℓ}))

for a suitable j (which only depends on ψ). It is then easy to see that σ is structure preserving and σ ∘ π̃_{1} = π̃_{2}. Furthemore, (I.17) implies that ran(σ) = M_{2}. Thus, M_{1} = M_{2}, π̃_{1} = π̃_{2} and p_{1} = p_{2}.

Existence. The idea of the construction is simple: using the fact that p̄ ∈ RM̄, we encode the whole structure M̄ and its satisfaction relation in a rudimentary fashion over M̄ p̄. The preservation properties of π then guarantee that the corresponding relations with the same rudimentary definitions over N encode the required structure M; the process of decoding will also yield the extension π̃. However, the verification of all details is somewhat technical.

Suppose M̄ = ⟨J B̄ ; ᾱ, D̄⟩. Let k̄(⟨i, z⟩) ≃ hM̄(i, ⟨z, p̄⟩) and d̄ = dom(k̄).

Then membership in d̄ is expressible by a Σ_{1}-statement over M̄ in p̄ as

x ∈ d̄⟺ ∃i ∃z (i ∈ ω ∧ x = ⟨i, z⟩ ∧ ∃y y = hM̄(i, ⟨z, p̄⟩).

So there is an i_{0} ∈ ω such that for every x ∈ M̄ p̄ we have x ∈ d̄iff Ap̄ ; M̄(i_{0}, x). Note that the latter is a rudimentary relation over M̄ p̄. Similarly, the identity and membership relations as well as the membership in B̄ and D̄ can be expressed in a Σ_{1}-fashion over M̄ in p̄, and therefore in a rudimentary fashion over M̄ p̄. More precisely, we introduce relations Ī, Ē, B̄^{∗} and D̄^{∗} over d̄ as follows

xĪy ⟺ k̄(x) = k̄(y)
xĒy ⟺ k̄(x) ∈ k̄(y)
B̄^{∗}(x) ⟺ B̄(k̄(x))
D̄^{∗}(x) ⟺ D̄(k̄(x))

and set

𝔻̄ = ⟨d̄, Ī, Ē, B̄^{∗}, D̄^{∗}⟩.

The symbol for = is interpreted in 𝔻̄ as Ī, the symbol for ∈ as Ē, and the symbols for B̄, D̄ as B̄^{∗} and D̄^{∗}, respectively. Thus 𝔻̄ encodes the structure M̄: Ī is a congruence relation on 𝔻̄, Ē represents the membership relation and k̄ is the Mostowski collapsing isomorphism between 𝔻̄/Ī and M̄. We denote the Σ_{1}-satisfaction relation for 𝔻̄ by T̄. More precisely, for x_{1}, …, x_{ℓ} ∈ d̄ and i ∈ ω we have

T̄(i, ⟨x_{1}, …, x_{ℓ}⟩) ⟺ 𝔻̄ ⊧ φ_{i}(x_{1}, …, x_{ℓ})

where ⟨φ_{i}; i ∈ ω⟩ is our fixed recursive enumeration of Σ_{1} formulae (remember that ⟨x_{1}, …, x_{ℓ}⟩ = ⟨x_{1}, ⟨x_{2} …, x_{ℓ}⟩⟩ and that we write φ_{i}(x_{1}, …, x_{ℓ}) instead of φ_{i}(⟨x_{1}, …, x_{ℓ}⟩)). One can easily show the following equivalence by induction:

T̄(i, ⟨x_{1}, …, x_{ℓ}⟩) ⟺ M̄ ⊧ φ_{i}(k̄(x_{1}), …, k̄(x_{ℓ})).

For atomic formulae this follows immediately from the definitions of the relations Ī, Ē, B̄^{∗} and D̄^{∗}. To illustrate how the induction steps go we show the induction step for the formula φ_{j}(v) of the form ∃z ∈ left(v) φ_{i}(z, v) (recall that left(v) = v_{1} and right(v) = v_{2} if v = ⟨v_{1}, v_{2}⟩ and undefined otherwise). Then

𝔻̄ ⊧ φ_{j}(x_{1}, …, x_{ℓ}) ⟺ ∃w ∈ d̄ [wĒx_{1} ∧ 𝔻̄ ⊧ φ_{i}(w, x_{1}, x_{2}, …, x_{ℓ})]
⟺ ∃w [k̄(w) ∈ k̄(x_{1}) ∧
∧ M̄ ⊧ φ_{i}(k̄(w), k̄(x_{1}), k̄(x_{2}), …, k̄(x_{ℓ}))]
⟺ M̄ ⊧ φ_{j}(k̄(x_{1}), …, k̄(x_{ℓ})).

The middle equivalence follows by the induction hypothesis, the last one by the fact that if there is a z witnessing the bottom formula, then such a z is always of the form k̄(w) for some w.

Let d, I, E, B^{∗} and D^{∗} be rudimentary over N by the same rudimentary definitions as their counterparts over M̄ p̄. It follows from the above that T̄ is ΣM̄ ; 1 in p̄ and therefore rudimentary over M̄ p̄. Let

𝔻 = ⟨d, I, E, B^{∗}, D^{∗}⟩

and T be a relation which is rudimentary over N by the same rudimentary definition as T̄. We show that T is the Σ_{1}-satisfaction predicate for 𝔻. Strictly speaking, we must show that the following equivalences hold, where φ_{i}(v) has the form indicated on the left hand side:

left(v) = right(v)  T (i, ⟨x, y⟩) ⟺ xIy
left(v) ∈ right(v)  T (i, ⟨x, y⟩) ⟺ xEy
B(v)  T (i, x) ⟺ B^{∗}(x)
D(v)  T (i, x) ⟺ D^{∗}(x)
φ_{i_{1}}(v) ∧ φ_{i_{2}}(v)  T (i, x⃗) ⟺ T (i_{1}, x⃗) ∧ T (i_{2}, x⃗)
¬φ_{j}(v)  T (i, x⃗) ⟺ ¬T (j, x⃗)
∃z ∈ left(v) φ_{j}(z, v)  T (i, ⟨x, y⃗⟩) ⟺ ∃z ∈ d (zEx ∧ T (j, ⟨z, x, y⃗⟩))
∀z ∈ left(v) φ_{j}(z, v)  T (i, ⟨x, y⃗⟩) ⟺ ∀z ∈ d (zEx ∧ T (j, ⟨z, x, y⃗⟩))
∃z φ_{j}(z, v)  T (i, x⃗) ⟺ ∃z ∈ d T (j, ⟨z, x⃗⟩).

Here x⃗ stands for ⟨x_{1}, …, x_{ℓ}⟩. We again proceed by induction on formulae. Suppose first that φ_{i} is an atomic formula, say the formula left(v) = right(v). Then

∀x, y ∈ d̄ (T̄(i, ⟨x, y⟩) ⟺ xĪy).

This is a Π_{1} statement over M̄ p̄, since the predicates d̄, T̄ and Ī are rudimentary. Since π is Σ_{1} preserving, T (i, ⟨x, y⟩) iff xIy iff 𝔻 ⊧ φ_{i}(x, y) for all x, y ∈ d.

Now suppose φ_{i}(v) is the formula φ_{i_{1}}(v) ∧ φ_{i_{2}}(v). Then

∀x_{1}, …, x_{ℓ} ∈ d̄[T̄(i, ⟨x_{1}, …, x_{ℓ}⟩) ⟺ T̄(i_{1}, ⟨x_{1}, …, x_{ℓ}⟩) ∧ T̄(i_{2}, ⟨x_{1}, …, x_{ℓ}⟩)].

This is again a Π_{1}-statement over M̄ p̄, so we obtain

T (i, ⟨x_{1}, …, x_{ℓ}⟩) ⟺ T (i_{1}, ⟨x_{1}, …, x_{ℓ}⟩) ∧ T (i_{2}, ⟨x_{1}, …, x_{ℓ}⟩)
⟺ 𝔻 ⊧ φ_{i_{1}}(x_{1}, …, x_{ℓ}) ∧ φ_{i_{2}}(x_{1}, …, x_{ℓ})
⟺ 𝔻 ⊧ φ_{i}(x_{1}, …, x_{ℓ});

the second equivalence follows from the induction hypothesis. We proceed similarly if φ_{i}(v) is of the form ¬φ_{j}(v).

Finally, suppose that φ_{i}(v) introduces a quantifier; say φ_{i}(v) is of the form ∃z ∈ left(v) φ_{j}(z, v). The implication (⟸) follows easily: Since T̄ is a satisfaction relation for 𝔻̄, we have

∀x, y [∃z (zĒx ∧ T̄(j, ⟨z, x, y⟩)) ⟹ T̄(i, ⟨x, y⟩)].

This is a Π_{1}-statement over M̄ p̄ and is therefore preserved upwards by π. To see the converse, let ḡ be a ΣM̄ ; 1-function in p̄ uniformizing the relation

z ∈ k̄(x) ∧ φ_{j}(z, k̄(x), k̄(y)).

Then ḡ(u) ≃ hM̄(m, ⟨u, p̄⟩) ≃ k̄(⟨m, u⟩) for an appropriate m ∈ ω, hence

φ_{i}(k̄(x), k̄(y)) ⟹ ⟨m, x, y⟩ ∈ dom(k̄) ∧ k̄(⟨m, x, y⟩) ∈ k̄(x) ∧
∧ φ_{j}(k̄(⟨m, x, y⟩), k̄(x), k̄(y))

holds in 𝔻̄ for all x, y in M̄ p̄. Translating this into the language of 𝔻̄ we obtain

∀x, y [T̄(i, ⟨x, y⟩) ⟹ ⟨m, x, y⟩ ∈ d̄ ∧ ⟨m, x, y⟩Ēx ∧ T̄(j, ⟨⟨m, x, y⟩, x, y⟩)],

which is again a Π_{1}-statement over M̄ p̄. The required implication for 𝔻 then follows immediately.

One consequence of the fact that T is a satisfaction relation for 𝔻 is:

π : 𝔻̄ ⟶_{Σ_{2}} 𝔻,

as follows immediately by the fact that T̄, T are rudimentary over M̄ p̄, N respectively by the same rudimentary definition. This implies that I is a congruence relation on 𝔻 and E is extensional modulo this congruence relation; the map π simply carries both properties from 𝔻̄ over to 𝔻 (extensionality being Π_{2}). Note also that Ē is well-founded modulo the congruence relation Ī (in other words, the relation xĒy ∧ ¬(xĪy) is well-founded). Hence E is well-founded modulo the congruence relation I by the strongness of π.

Let M be the transitive collapse of 𝔻 and k be the collapsing map. Define π̃ : M̄ → M by

π̃(k̄(x)) = k(π(x)) for all x ∈ d̄.

It follows immediately that

π̃ : M̄ ⟶_{Σ_{2}} M.

In the following we show that M has all the required properties. Note first that M is a J-structure, say M = ⟨J_{α}^{B}, D⟩. For the rest of the proof fix i, i^{∗} ∈ ω so that

x = h_{Q}(i, ⟨x, q⟩) holds uniformly over any J-structure Q
p̄ = hM̄(i^{∗}, ⟨0, p̄⟩).

Then

x = k̄(⟨i, x⟩) for all x ∈ M̄ p̄ and p̄ = k̄(⟨i^{∗}, 0⟩).

We first observe that |N| ⊆ M. Given any x ∈ M̄ p̄, k̄(⟨j, z⟩) ∈ x = k̄(⟨i, x⟩) iff k̄(⟨j, z⟩) = w = k̄(⟨i, w⟩) for some w ∈ x; in other words,

⟨j, z⟩ ∈ d̄ ⟹ [⟨j, z⟩Ē⟨i, x⟩ ⟺ ∃w ∈ x (⟨j, z⟩Ī⟨i, w⟩)]

holds for all x, y ∈ M̄ p̄ and j ∈ ω. Quantifying over M̄ p̄ we obtain a Π_{1}-statement, which is preserved under π. This allows us to conclude: Whenever x ∈ N (note: ⟨i, x⟩ ∈ d by the fact that π is Σ_{1}-preserving and the “same” holds for M̄ p̄),

k(⟨i, x⟩) = {k(⟨i, w⟩); w ∈ x}.

It follows by ∈-induction that k(⟨i, x⟩) = x for all x ∈ N. Furthermore, given any x ∈ M̄ p̄,

π̃(x) = π̃(k̄(⟨i, x⟩)) = k(π(⟨i, x⟩)) = k(⟨i, π(x)⟩) = π(x),

and hence π̃ ⊇ π.

Let B′, A and ρ be such that N = ⟨J_{ρ}^{B′}, A⟩ (recall that, by our assumption, N is an acceptable structure). Set p = k(⟨i^{∗}, 0⟩). It is easy to check that π̃(p̄) = p. We now prove that A = A_{M}^{p}. Given an x ∈ M̄ p̄ and j ∈ ω,

we have Ap̄ ; M̄(j, x) ⟺ M̄ ⊧ φ_{j}(x, p̄) ⟺ M̄ ⊧ φ_{j}(k̄(⟨i, x⟩), k̄(⟨i^{∗}, 0⟩)) ⟺

T̄(j, ⟨⟨i, x⟩, ⟨i^{∗}, 0⟩⟩). Hence, the Π_{1}-statement

∀x ∀j ∈ ω [Ap̄ ; M̄(j, x) ⟺ T̄(j, ⟨⟨i, x⟩, ⟨i^{∗}, 0⟩⟩)]

is preserved by π, which means that

A(j, x) ⟺ T (j, ⟨⟨i, x⟩, ⟨i^{∗}, 0⟩⟩) ⟺ M ⊧ φ_{j}(x, p)  (I.18)

for every x ∈ N and j ∈ ω.

This equivalence easily yields that B′ = B ∩ N and N = ⟨J_{ρ}^{B}, A⟩ for ρ as above. Pick a j such that φ_{j}(u, v) is the formula “B^{∗}(u)” for any acceptable structure of the form ⟨J_{α^{∗}}^{B^{∗}}, D^{∗}⟩. Since B̄(x) ⟺ Ap̄ ; M̄(j, x) holds for every x ∈ M̄ p̄, the preservation properties of π guarantee that A(j, x) ⟺ B′(x). However, A(j, x) is equivalent to B(x) for all x ∈ N, as follows from (I.18).

To see that A = A_{M}^{p} it suffices to show that ρ = ρ(M), as |N| = H_{ρ}^{M} then follows immediately (recall that ρ = On ∩ N). The computation below will also yield that p ∈ R_{M}. Notice that

k̄(⟨j, x⟩) = hM̄(j, ⟨x, p̄⟩) = hM̄(k̄(⟨i, j⟩), ⟨k̄(⟨i, x⟩), k̄(⟨i^{∗}, 0⟩)⟩),

where the left equality is simply the definition of k̄. Leaving out the middle term we obtain a Σ_{1}-statement, so it can be represented by some m ∈ ω. More precisely, T̄(m, ⟨⟨j, x⟩, ⟨i, j⟩, ⟨i, x⟩, ⟨i^{∗}, 0⟩⟩) holds for all x ∈ M̄ p̄ and j ∈ ω. As above we apply π to obtain the corresponding statement for T and all x ∈ N. Using the fact that the Σ_{1}-Skolem functions have uniform definitions we infer that k(⟨j, x⟩) = h_{M}(k(⟨i, j⟩, ⟨k(⟨i, x⟩), k(⟨i^{∗}, 0⟩)⟩) = h_{M}(j, ⟨x, p⟩). Note that there is a lightface Σ_{1}^{M} map^{7} from ρ onto |N|; since the values k(⟨j, x⟩) range over all of M, we have

M = h_{M}(ρ ∪ {p}) and ρ(M) ≤ ρ.

The latter is obviously a consequence of the former. On the other hand, given any r ∈ M we can pick a ξ ∈ On ∩ N such that r = h_{M}(j, ⟨ξ, p⟩) for some j. For any Σ_{1} formula ψ, M ⊧ ψ(η, r) iff M ⊧ φ_{m}(η, ξ, p) for a suitable m; the latter is equivalent to A(m, ⟨η, ξ⟩) by (I.18). Taken together, M ⊧ ψ(η, r) can be expressed in a rudimentary fashion over N. Since N is amenable, every bounded Σ_{1}^{M} subset of ρ is an element of N, which means that ρ ≤ ρ(M). Thus,

ρ = ρ(M) and p ∈ R_{M}.

It only remains to show that π̃ is strong. Let R̄, R be binary relations which are rudimentary over M̄, M respectively by the same rudimentary definition. Define R̄^{∗}, R^{∗} as follows

xR̄^{∗}y ⟺ x, y ∈ d̄ ∧ k̄(x)R̄k̄(y)
xR^{∗}y ⟺ x, y ∈ d ∧ k(x)Rk(y).

Then R̄^{∗} is well-founded since R̄ is – any decreasing chain x_{0}, x_{1}, …, x_{n}, … in R̄^{∗} yields a decreasing chain k̄(x_{0}), k̄(x_{1}), …, k̄(x_{n}), … in R̄, hence no such chain can be infinite. Furthermore, R̄^{∗}, R^{∗} are rudimentary over M̄ p̄, N respectively by the same rudimentary definition. As π is strong, R^{∗} must be well-founded. Hence R must be well-founded as well, since every infinite decreasing chain x_{0}, x_{1}, …, x_{n}, … in R is of the form k(z_{0}), k(z_{1}), …, k(z_{n}), … for some z_{0}, z_{1}, …, z_{n}, … and the latter would be an infinite decreasing chain in R^{∗}. ⊣

7“Lightface” means that no parameters are needed in the definition of such a function.

5. Iterated projecta

In this chapter we shall show how to iterate the process of defining a projectum and forming a standard code, and we shall introduce the notion of n-th projectum, n-th standard code, and n-th reduct.

5.1 Definition. Let M = ⟨J_{β}^{B}, D⟩ be an acceptable J-structure. For n < ω we recursively define the n-th projectum ρ_{n}(M), the n-th standard code A_{M}^{n,p} and the n-th reduct M^{n,p} as follows:

ρ_{0}(M) = β,  Γ_{M}^{0} = {∅},  A_{M}^{0,∅} = ∅,  M^{0,∅} = M,

ρ_{n+1}(M) = min{ρ(M^{n,p}); p ∈ Γ_{M}^{n}},

Γ_{M}^{n+1} = ∏_{i∈n+1}[ρ_{i+1}(M), ρ_{i}(M))^{<ω},

and for p ∈ Γ_{M}^{n+1},

A_{M}^{n+1,p} = A_{M^{n,p↾n}}^{p(n),ρ_{n+1}(M)} and
M^{n+1,p} = (M^{n,p↾n})^{p(n),ρ_{n+1}(M)}.

We also set ρ_{ω}(M) = min{ρ_{n}(M); n < ω}. The ordinal ρ_{ω}(M) is called the ultimate projectum of M.

The reader will gladly verify that ρ_{1}(M) = ρ(M). On the other hand, if M is not 1-sound (cf. Definition 5.7 below) then it need not be the case that ρ_{2}(M) is the least ρ such that 𝒫(ρ) ∩ Σ_{2}^{M} ⊈ M.

Supposing that we know ρ_{n}(M) ≤ ⋯ ≤ ρ_{1}(M) we may identify p = ⟨p(0), …, p(n)⟩ ∈ Γ_{M}^{n+1} with the (finite) set ⋃ ran(p) of ordinals; this will play a rôle in the next section.

5.2 Definition. We define P_{M}^{n}, R_{M}^{n} ⊆ Γ_{M}^{n} as follows:

P_{M}^{0} = {∅}
P_{M}^{n+1} = {p ∈ Γ_{M}^{n+1}; p ↾ n ∈ P_{M}^{n} ∧
ρ(M^{n,p↾n}) = ρ_{n+1}(M) ∧ p(n) ∈ P_{M^{n,p↾n}}}

R_{M}^{n} is defined in the same way but with R_{M^{n,p↾n}} in place of P_{M^{n,p↾n}}.

As before, we call the elements of P_{M}^{n} good parameters and the elements of R_{M}^{n} very good parameters.

5.3 Lemma. Let M be acceptable.

(a) R_{M}^{n} ⊆ P_{M}^{n} ≠ ∅

(b) Let p ∈ R_{M}^{n}. If q ∈ Γ_{M}^{n} then A^{n,q} is rud_{M^{n,p}} in parameters from M^{n,p}.

(c) Let p ∈ R_{M}^{n}. Then ρ(M^{n,p}) = ρ_{n+1}(M).

(d) p ∈ P_{M}^{n} ⟹ ∀ i ∈ n p(i) ∈ P_{M^{i,p↾i}}, and similarly for R_{M}^{n}. Moreover, if p ↾ (n − 1) ∈ R_{M}^{n−1} then equivalence holds.

Proof. (a) This is easily shown inductively by using Lemma 2.9 and by amalgamating parameters.

(b) By induction on n < ω. The case n = 0 is trivial. Now let n > 0, and suppose (b) holds for n − 1. Write m = n − 1. Let p ∈ R_{M}^{n} and q ∈ Γ_{M}^{n}. We have to show that A_{M^{m,q↾m}}^{q(m),ρ_{n}(M)} is rud_{M^{n,p}} in parameters from M^{n,p}. Inductively, M^{m,q↾m} is rud_{M^{m,p↾m}} in a parameter t ∈ M^{n,p}. As p(m) ∈ R_{M^{m,p↾m}}, there are e_{0} and e_{1} and z ∈ M^{n,p} such that

q(m) = h_{M^{m,p↾m}}(e_{0}, ⟨z, p(m)⟩)

and

t = h_{M^{m,p↾m}}(e_{1}, ⟨z, p(m)⟩).

For i < ω and x ∈ M^{n,p}, we have that

⟨i, x⟩ ∈ A_{M^{m,q↾m}}^{q(m),ρ_{n}(M)} ⟺ M^{m,q↾m} ⊧ φ_{i}(x, q(m))
⟺ M^{m,q↾m} ⊧ φ_{i}(x, h_{M^{m,p↾m}}(e_{0}, ⟨z, p(m)⟩))
⟺ M^{m,p↾m} ⊧ φ_{j}(⟨x, z⟩, p(m))
⟺ ⟨j, ⟨x, z⟩⟩ ∈ A_{M^{m,p↾m}}^{p(m)},

for some j which is recursively computable from i, as M^{m,q↾m} is rud_{M^{m,p↾m}} in the parameter t = h_{M^{m,p↾m}}(e_{1}, ⟨z, p(m)⟩). Therefore, A_{M^{m,q↾m}}^{q(m),ρ_{n}(M)} is rud_{A_{M^{m,p↾m}}^{p(m)}} in the parameter z.

(c) Let ρ_{n+1}(M) = ρ(M^{n,q}), where q ∈ Γ_{M}^{n}. By (b), M^{n,q} is rud_{M^{n,p}} in parameters from M^{n,p}, which implies that Σ_{1}^{M^{n,q}} ⊆ Σ_{1}^{M^{n,p}}. But then ρ(M^{n,p}) ≤ ρ(M^{n,q}) = ρ_{n+1}(M), and hence ρ(M^{n,p}) = ρ_{n+1}(M).

(d) This is shown inductively by using (c). ⊣

The following is given just by the definition of R_{M}^{n+1}. Let M be acceptable, and let p ∈ R_{M}^{n+1}. Then

M = h_{M}(h_{M^{1,p↾1}}(⋯ h_{M^{n,p↾n}}(ρ_{n+1}(M) ∪ {p(n)}) ⋯) ∪ {p(0)}).

We thus can, uniformly over M, define a function h_{M}^{n+1} basically as the iterated composition of the Σ_{1} Skolem functions of the i^{th} reducts of M, 0 ≤ i ≤ n, such that M is the h_{M}^{n+1}-hull of ρ_{n+1}(M) ∪ {p} whenever p ∈ R_{M}^{n+1}. The precise definition of the (partial) function h_{M}^{n+1} : ^{<ω}ω ×^{<ω}|M^{n+1,p}| → |M| is by recursion on n < ω; we set h_{M}^{1} = h_{M} and

h_{M}^{n+1}(⟨i⃗, i_{0}, ⋯ i_{k}⟩, ⟨x⃗_{i_{0}}, ⋯ x⃗_{i_{k}}⟩) =
h_{M}^{n}(i⃗, ⟨h_{M^{n,p↾n}}(i_{0}, x⃗_{i_{0}}), ⋯, h_{M^{n,p↾n}}(i_{k}, x⃗_{i_{k}})⟩).

5.4 Lemma. Let n < ω, and let M be acceptable. Then h_{M}^{n+1} is in Σ_{ω}^{M}, and

M = h_{M}^{n+1}”(ρ_{n+1}(M) ∪ {p}),

whenever p ∈ R_{M}^{n+1}.

5.5 Lemma. Let 0 < n < ω. Let M be acceptable, and let p ∈ R_{M}^{n}. Then Σ_{ω}^{M} ∩ 𝒫(M^{n,p}) = Σ_{ω}^{M^{n,p}}.

Proof. It is easy to verify that Σ_{ω}^{M^{n,p}} ⊆ Σ_{ω}^{M} ∩ 𝒫(M^{n,p}). Let us prove the other direction.

It is straightforward to verify by induction on m ≤ n that if φ is Σ_{0} and x, y ∈ M^{m,p↾m}, then

φ(x, h_{M}^{m}(y)) is uniformly Δ_{1}^{M^{m−1,p↾m−1}}(x, y).  (I.19)

Now let A ∈ Σ_{ω}^{M} ∩ 𝒫(M^{n,p}), say

x ∈ A ⟺ M ⊧ ∃x_{1}∀x_{2} ⋯ ∃/∀x_{k} φ(x, y, x_{1}, x_{2}, ⋯, x_{k}),

where φ is Σ_{0} and y ∈ M. By Lemma 5.4, we may write

x ∈ A ⟺ ∃x′_{1} ∈ M^{n,p} ∀x′_{2} ∈ M^{n,p} ⋯ ∃/∀x_{k} ∈ M^{n,p}
φ(x, h_{M}^{n}(y′), h_{M}^{n}(x′_{1}), h_{M}^{n}(x′_{2}), ⋯ h_{M}^{n}(x′_{k})),

where y′ ∈ M^{n,p}. But then A ∈ Σ_{ω}^{M^{n,p}}, with the help of (I.19) for m = n. ⊣

A more careful look at the proofs of Lemmata 5.4 and 5.5 shows the following.

5.6 Lemma. Let n < ω. Let M be acceptable and p ∈ R_{M}^{n}. Let A ⊆ M^{n,p} be Σ_{n+1}^{M}. Then A is Σ_{1}^{M^{n,p}}.

5.7 Definition. M is n-sound iff R_{M}^{n} = P_{M}^{n}. M is sound iff M is n-sound for all n < ω.

We shall prove later (cf. Lemma 9.2) that every J_{α} is sound. In fact, a key requirement on initial segments of a core model is that they be sound.

We can now formulate a general downward extension of embeddings lemma as the conjunction of the following three lemmata which, in turn, are immediate consequences of the corresponding lemmata for the first projectum.

5.8 Lemma. Let M̄, M be acceptable and π : M̄^{n,p̄} ⟶_{Σ_{0}} M^{n,p}, where p̄ ∈

Rn ; M̄. Then there is a unique map π̃ ⊇ π such that dom(π̃) = M̄, π̃(p̄) = p and, setting π̃_{i} = π̃ ↾ Hi ; M̄,

π̃_{i} : M̄^{i,p̄↾i} ⟶_{Σ_{0}} M^{i,p↾i} for i ≤ n.

The map π̃_{i} is in fact Σ_{1}-preserving for i ∈ n.

5.9 Lemma. Suppose that M̄, M, p̄, p, π, π̃, π̃_{i}, i ≤ n, are as above and

p ∈ R_{M}^{n}. Let π : M̄^{n,p̄} ⟶_{Σ_{ℓ}} M^{n,p} where ℓ ∈ ω. Then

π̃_{i} : M̄^{i,p̄↾i} ⟶_{Σ_{ℓ+n−i}} M^{i,p↾i} for i ≤ n.

Hence, π̃_{0} : M̄ ⟶_{Σ_{ℓ+n}} M.

5.10 Lemma. Let π : N ⟶_{Σ_{0}} M^{n,p}, where M is as above. Then there are

unique M̄, p̄ such that p̄ ∈ Rn ; M̄ and N = M̄^{n,p̄}.

The general upward extension of embeddings lemma is the conjunction of the following lemma together with Lemmata 5.8 and 5.9.

5.11 Lemma. Let π : M̄^{n,p̄} → N be strong, where M̄ is an acceptable J-structure and p̄ ∈ Rn ; M̄. Then there are unique M, p such that M is acceptable, p ∈ R_{M}^{n} and M^{n,p} = N. Moreover, if π̃ is as in Lemma 5.8, then π̃ is strong.

If π and π̃ are as in Lemma 5.8 then π̃ is often called the n-completion of π.

If we take π : M̄^{n,p̄} → M^{n,p} as in Lemma 5.8 and form the corresponding extension π̃, we can in fact do better than stated there. It is easy to see that for every appropriate q̄ and q = π̃(q̄),

π̃_{i} : M̄^{i,q̄↾i} ⟶_{Σ_{1}} M^{i,q↾i} for i ∈ n.  (I.20)

This suggests the general notion of a Σ_{ℓ}^{(n)}-preserving embedding, where n indicates preservation at the n-th level, i.e. if π̃(q̄) = q then (I.20) and

π̃_{n} : M̄^{n,q̄} ⟶_{Σ_{ℓ}} M^{n,q}.  (I.21)

It turns out that there is a canonical class of formulae, the so called Σ_{ℓ}^{(n)}-formulae, such that the above embeddings are exactly those which are elementary with respect to this class. This idea leads towards Jensen’s elegant Σ^{∗} theory which is dealt with in [?, Sections 1.6 ff.].

Following [?, §2], though, we shall call Σ_{1}^{(n)} elementary maps rΣ_{n+1} elementary. Here is our official definition, which presupposes that the structures involved possess very good parameters; it will play a rôle in the last two sections.

5.12 Definition. Let M, N be acceptable, let π: M → N, and let n < ω. Then π is called rΣ_{n+1} elementary provided that there is p ∈ R_{M}^{n} with π(p) ∈ R_{N}^{n}, and for all i ≤ n,

π ↾ H_{ρ_{i}(M)}^{M}: M^{i,p↾i} ⟶_{Σ_{1}} N^{i,π(p)↾i}.  (I.22)

The map π is called weakly rΣ_{n+1} elementary provided that there is p ∈ R_{M}^{n} with π(p) ∈ R_{N}^{n}, and for all i < n, (I.22) holds, and

π ↾ H_{ρ_{n}(M)}^{M}: M^{n,p} ⟶_{Σ_{0}} N^{n,π(p)}.

If π: M → N is (weakly) rΣ_{n+1} elementary then typically both M and N will be n-sound; however, neither M nor N has to be (n + 1)-sound. It is possible to generalize this definition so as to not assume that very good parameters exist (cf. [?, §2]).

Lemma 5.8 therefore says that the map π can be extended to its ncompletion π̃ which is weakly rΣ_{n+1} elementary, and Lemma 5.9 says that if π is Σ_{1} elementary to begin with then the n-completion π̃ will end up being rΣ_{n+1} elementary.

Moreover, if a map π: M → N is rΣ_{n+1} elementary then it respects h^{n+1} by Theorem 1.15, i.e.:

5.13 Lemma. Let n < ω, and let M, N be acceptable. Let π: M → N be rΣ_{n+1} elementary. Then for all appropriate x,

π(h_{M}^{n+1}(x)) = h_{N}^{n+1}(π(x)).

6. Standard parameters

Finite sets of ordinals are well-ordered in a simple canonical way.

6.1 Definition. Let a, b ∈ [On]^{<ω}. Set

a <^{∗} b ⟺ ∃ α ∈ b (a \ (α + 1) = b \ (α + 1) ∧ α ∉ a).^{8}

8I.e., max(a△b) ∈ b.

The ordering <^{∗} has a rudimentary definition, therefore it is absolute for transitive rudimentarily closed structures and is also preserved under embeddings which are Σ_{0} elementary. If we view finite sets of ordinals as finite decreasing sequences, a <^{∗} b precisely when a precedes b lexicographically. Moreover, we easily get the following.

6.2 Lemma. [On]^{<ω} is well-ordered by <^{∗}.

Let M be acceptable, and n < ω. The well-ordering <^{∗} induces a wellordering of Γ_{M}^{n} by confusing p ∈ Γ_{M}^{n} with ⋃ ran(p) (i.e., by identifying p with the obvious set of ordinals; cf. above). We shall denote this latter well-ordering also by <^{∗}.

6.3 Definition. Let M be acceptable. The <^{∗}-least p ∈ P_{M}^{n} is called the n^{th} standard parameter of M and is denoted by p_{n}(M). We shall write M^{n} for M^{n,p_{n}(M)}; M^{n} is called the n^{th} standard reduct of M.

6.4 Lemma. Let p ∈ R_{M}^{n}. Then p can be lengthened to some p′ ∈ P_{M}^{n+1}, i.e., there is some p′ ∈ P_{M}^{n+1} with p′ ↾ n = p.

Proof. This follows immediately from Lemma 5.3 (c). ⊣

6.5 Corollary. Let n > 0. Let M be n-sound. Then p_{n−1}(M) = p_{n}(M) ↾ (n − 1).

Proof. By Lemma 6.4. ⊣

6.6 Definition. Let M be acceptable. Suppose that for all n < ω, p_{n}(M) = p_{n+1}(M) ↾ n. Then we set p(M) = ⋃_{n<ω} p_{n}(M). p(M) is called the standard parameter of M.

We shall often confuse p(M) with ⋃ ran(p(M)).

6.7 Corollary. Let M be sound. Then p(M) exists, i.e., for all n < ω, p_{n}(M) = p_{n+1}(M) ↾ n.

Proof. By Corollary 6.5. ⊣

6.8 Lemma. M is sound iff p_{n}(M) ∈ R_{M}^{n} for all n ∈ ω.

Proof. We shall prove the non-trivial direction (⇐). For each n > 0 we shall prove

p_{n}(M) ∈ R_{M}^{n} ⟹ R_{M}^{n} = P_{M}^{n}.  (I.23)

This holds trivially for n = 0. Now suppose n > 0 is least such that the statement (I.23) fails. Hence P_{M}^{n} \R_{M}^{n} ≠ ∅ (cf. Lemma 5.3 (a)). Let q be the <^{∗}-least element of P_{M}^{n} \ R_{M}^{n}. This means that p <^{∗} q, where p = p_{n}(M). By Lemma 5.3, we may let i < n be least such that q(i) ∉ R_{M^{i,q↾i}}.

Let us first consider the case n = 1.

Then, of course, p(0) <^{∗} q(0). Using the downward extension of embeddings lemma, we may let M̄, q̄, π be unique such that

\{ \begin{matrix}q̄ ∈ RM̄ \\ π : M̄ → M is Σ_{1} elementary \\ π(q̄) = q(0) \\ π ↾ H_{ρ_{1}(M)}^{M} = id. \end{matrix}  (I.24)

As q(0) ∉ R_{M}, π ≠ id. Because p(0) ∈ R_{M}, there are e and z ∈ [ρ_{1}(M), M ∩ On)^{<ω} such that

q(0) = h_{M}(e, ⟨z, p(0)⟩).

As p(0) <^{∗} q(0), by elementarity we get that

M̄ ⊧ ∃p′ <^{∗} q̄ (q̄ = h(e, ⟨z, p′⟩)).

Letting p^{∗} be a witness, we may conclude that by elementarity again

π(p^{∗}) <^{∗} q(0) ∧ q(0) = h_{M}(e, ⟨z, π(p^{∗})⟩,  (I.25)

where we may and shall assume that π(p^{∗}) ∈ [ρ_{1}(M), M ∩ On)^{<ω}. We have that π(p^{∗}) ∈ P_{M} by I.25. But π(p^{∗}) ∈ ran(π) and π ≠ id, so that we must also have that π(p^{∗}) ∉ R_{M}. Because π(p^{∗}) <^{∗} q(0), we have a contradiction to the choice of q.

Now let us consider the case n > 1.

If p ↾ n − 1 = q ↾ n − 1 then we may apply the above argument to the reduct M^{n−1,p↾n−1}. We may thus assume that p ↾ n − 1 <^{∗} q ↾ n − 1. Let i < n be least such that p ↾ i <^{∗} q ↾ i. We shall assume that i = 1 and n = 2 for notational convenience. The general case is similar to this special case and is left to the reader.

As p_{2}(M) ∈ R_{M}^{2}, Lemma 5.3 (d) yields that P_{M}^{1} = R_{M}^{1}. As p(0) <^{∗} q(0), there is some j ∈ ω and z ∈ [ρ_{1}(M), M ∩ On)^{<ω} such that

∃p′(p′ <^{∗} q(0) ∧ q(0) = h_{M}(j, ⟨z, p′⟩)).

If i is the Gödel number of this Σ_{1} formula, we thus have that A_{M}^{q(0)}(i, z) holds true. Let X be the smallest Σ_{1} submodel of the (first) reduct M^{q(0)}. There is then some z_{0} ∈ X such that A_{M}^{q(0)}(i, z_{0}) holds true. Therefore,

∃p′(p′ <^{∗} q(0) ∧ q(0) = h_{M}(j, ⟨z_{0}, p′⟩)).  (I.26)

So there is some p′, call it q̄(0), witnessing I.26 which is an element of the smallest Σ_{1} substructure of M which contains both q(0) and z_{0}. There is then also some k with q̄(0) = h_{M}(k, ⟨z_{0}, q(0)⟩).

Now set q̄ = q̄(0) ∪ q(1). Then q̄ ∈ P_{M}^{2}, because q(0) = h_{M}(j, ⟨z_{0}, q̄(0)⟩) and q ∈ P_{M}^{2}. We’ll now show that q̄ ∉ R_{M}^{2}. As q̄(0) <^{∗} q(0) (and hence q̄ <^{∗} q) this will contradict the choice of q and finish the proof.

Well, to see that q̄ ∉ R_{M}^{2} it suffices to verify that if

Y = h_{M^{q̄(0)}}(ρ_{2}(M) ∪ {q(1)})

then Y ≠ M^{q̄(0)}. As q̄(0) = h_{M}(k, ⟨z_{0}, q(0)⟩), we can find a recursive f: ω → ω such that for all ℓ ∈ ω and for all x,

A_{M}^{q̄(0)}(ℓ, x) ⟺ A_{M}^{q(0)}(f(ℓ), ⟨x, z_{0}⟩).

Therefore, as z_{0} ∈ X,

Y ⊆ h_{M^{q(0)}}(ρ_{2}(M) ∪ {q(1)}).

But q(1) ∉ R^{M^{q(0)}}, and so Y ≠ M^{q̄(0)}. ⊣

There is a class of structures, for which the above characterization of soundness has a particularly nice form. This class comprises all of the structures J_{α} where α is a limit ordinal. Moreover, the same applies to sufficiently iterable premice, which are the building blocks of core models.

7. Solidity witnesses

Solidity witnesses are witnesses to the fact that a given ordinal is a member of the standard parameter. The key fact will be that being a witness is preserved under Σ_{1} elementary maps, so that witnesses can be used for showing that standard parameters are mapped to standard parameters.

Whereas the pure theory of witnesses is easy to grasp, it is one of the deepest results of inner model theory that the structures considered there (viz., iterable premice) do contain witnesses.

7.1 Definition. Let M be an acceptable structure, let p ∈ [On ∩ M]^{<ω}, and let ν ∈ p. Let W be another acceptable structure with ν ⊆ W, and let r ∈ [On ∩ W]^{<ω}. We say that (W, r) is a witness for ν ∈ p w.r.t. M, p iff for every Σ_{1} formula φ(v_{0}, ..., v_{l+1}) and for all ξ_{0}, ..., ξ_{l} < ν

M ⊧ φ(ξ_{0}, ..., ξ_{l}, p \ (ν + 1)) ⟹ W ⊧ φ(ξ_{0}, ..., ξ_{l}, r).  (I.27)

In this situation, we shall often suppress r and call W a witness. The proof of Lemma 7.2 will show that if a witness exists then there is also one where ⟹ may be replaced by ⟺ in I.27.

7.2 Lemma. Let M be an acceptable structure, and let p ∈ P_{M}. Suppose that for each ν ∈ p there is a witness W for ν ∈ p w.r.t. M, p such that W ∈ M. Then p = p_{1}(M).

Proof. Suppose not. Then p_{1}(M) <^{∗} p, and we may let ν ∈ p \ p_{1}(M) be such that p \ (ν + 1) = p_{1}(M) \ (ν + 1). Let us write q for p \ (ν + 1) = p_{1}(M) \ (ν + 1). Let (W, r) ∈ M be a witness for ν ∈ p w.r.t. M, p. Let A ∈ Σ_{1}^{M}({p_{1}(M)}) be such that A ∩ ρ_{1}(M) ∉ M.

Let k be the number of elements of p∩ν, and if k > 0 then let ξ_{1} < ... < ξ_{k} be such that p_{1}(M) ∩ ν = {ξ_{1}, ..., ξ_{k}}. There is a Σ_{1} formula φ(v_{0}, ..., v_{k+1}) such that

ξ ∈ A ⟺ M ⊧ φ(ξ, ξ_{1}, ..., ξ_{k}, q).

Because (W, r) ∈ M is a witness for ν ∈ p w.r.t. M, p, we have that

M ⊧ φ̄(ξ, ξ_{1}, ..., ξ_{k}, q) ⟹ W ⊧ φ̄(ξ, ξ_{1}, ..., ξ_{k}, r)

for every ξ < ρ_{1}(M) ≤ ν and every φ̄ which is Σ_{1}.

Let α = sup(h_{W} (ν ∪ {r}) ∩ On), and let W̄ = J_{α}^{B} (where W = J_{β}^{B}, some β ≥ α). By looking at the canonical elementary embedding from h_{M}(ν ∪ {q}) into W̄, which is Σ_{0} elementary and cofinal (and hence Σ_{1} elementary) we get that

M ⊧ φ̄(ξ, ξ_{1}, ..., ξ_{k}, q) ⟺ W̄ ⊧ φ̄(ξ, ξ_{1}, ..., ξ_{k}, r)  (I.28)

for every ξ < ρ_{1}(M) ≤ ν and every φ̄ which is Σ_{1}. In particular, I.28 holds with φ̄ replaced by φ and every ξ < ρ_{1}(M) ≤ ν. As W̄ ∈ M, this shows that in fact A ∩ ρ_{1}(M) ∈ M. Contradiction! ⊣

7.3 Definition. Let M be acceptable, let p ∈ [On ∩ M]^{<ω}, and let ν ∈ p. We denote by W_{M}^{ν,p} the transitive collapse of h_{M}(ν ∪ (p \ (ν + 1))). We call W_{M}^{ν,p} the standard witness for ν ∈ p w.r.t. M, p.

7.4 Lemma. Let M be acceptable, and let ν ∈ p ∈ P_{M}. The following are equivalent.

(1) W_{M}^{ν,p} ∈ M.

(2) There is a witness W for ν ∈ p w.r.t. M, p such that W ∈ M.

Proof. We have to show (2) ⟹ (1). Let σ: W_{M}^{ν,p} → M be the inverse of the transitive collapse. We may also let σ^{∗}: W_{M}^{ν,p} → W be defined by h_{W_{M}^{ν,p}}(ξ, σ^{−1}(p \ ν + 1)) ↦ h_{W} (ξ, r), ξ < ν. Set α = sup(h_{W} (ν ∪ {r}) ∩ On), and let W̄ = J_{α}^{A} (where W = J_{β}^{A}, some β ≥ α). Again, σ^{∗}: W_{M}^{ν,p} → W̄ is Σ_{1} elementary.

Let us assume w.l.o.g. that W_{M}^{ν,p} is not an initial segment of M.

Now if σ(ν) = ν then a witness to ρ_{1}(M) is definable over W_{M}^{ν,p}, and hence over W̄. But as W̄ ∈ M, this witness to ρ_{1}(M) would then be in M. Contradiction!

We thus have that ν is the critical point of σ. Thus, if M = J_{γ}^{B}, we know that σ(ν) is regular in M and so J_{σ(ν)}^{B} ⊧ ZFC^{−}. We may code W_{M}^{ν,p} by some a ⊆ ν, Σ_{1}-definably over W_{M}^{ν,p}. Using σ^{∗}, a is definable over W̄, so that a ∈ M. In fact, a ∈ J_{σ(ν)}^{B} by acceptability. We can thus decode a in J_{σ(ν)}^{B}, which gives W_{M}^{ν,p} ∈ J_{σ(ν)}^{B} ⊆ M. ⊣

7.5 Definition. Let M be an acceptable structure. We say that M is 1-solid iff

W_{M}^{ν,p_{1}(M)} ∈ M

for every ν ∈ p_{1}(M).

7.6 Lemma. Let M̄, M be acceptable structures, and let π: M̄ ⟶_{Σ_{1}} M. Let

ν̄ ∈ p̄ ∈ [On∩M̄]^{<ω}, and set ν = π(ν̄) and p = π(p̄). Let (W̄ , r̄) be a witness for ν̄ w.r.t. M̄, p̄ such that W̄ ∈ M̄, and set W = π(W̄) and r = π(r̄). Then (W, r) is a witness for ν w.r.t. M, p.

Proof. Let φ(v_{0}, ..., v_{l+1}) be an arbitrary Σ_{1} formula. We know that

M̄ ⊧ ∀ξ_{0}...ξ_{l} < ν̄[φ(ξ_{0}, ..., ξ_{l}, p̄ \ (ν̄ + 1)) → W̄ ⊧ φ(ξ_{0}, ..., ξ_{l}, r̄)].

As π is Π_{1} elementary, this yields that

M ⊧ ∀ξ_{0}...ξ_{l} < ν[φ(ξ_{0}, ..., ξ_{l}, p \ (ν + 1)) → W ⊧ φ(ξ_{0}, ..., ξ_{l}, r)].

We thus conclude that (W, r) is a witness for ν w.r.t. M, p. ⊣

7.7 Corollary. Let M̄, M be acceptable structures, and let π: M̄ ⟶_{Σ_{1}} M.

Suppose that M̄ is 1-solid and π(p_{1}(M̄)) ∈ P_{M}. Then p_{1}(M) = π(p_{1}(M̄)), and M is 1-solid.

The proof of the following lemma is virtually the same as the proof of Lemma 7.6.

7.8 Lemma. Let M̄, M be acceptable structures, and let π: M̄ ⟶_{Σ_{1}} M. Let

ν̄ ∈ p̄ ∈ [On ∩ M̄]^{<ω}, and set ν = π(ν̄) and p = π(p̄). Let (W̄ , r̄) ∈ M̄ be such that, setting W = π(W̄) and r = π(r̄), (W, r) is a witness for ν w.r.t. M, p. Then (W̄ , r̄) is a witness for ν̄ ∈ p̄ w.r.t. M̄, p̄.

7.9 Corollary. Let M̄, M be acceptable structures, and let π: M̄ ⟶_{Σ_{1}} M.

Suppose that M is 1-solid, and that in fact W_{M}^{ν,p_{1}(M)} ∈ ran(π) for every ν ∈ p_{1}(M). Then p_{1}(M̄) = π^{−1}(p_{1}(M)), and M̄ is 1-solid.

The following definition just extends Definition 7.5.

7.10 Definition. Let M be an acceptable structure. If 0 < n < ω then we say that M is n-solid if for every k < n, p_{1}(M^{k}) = p_{k+1}(M)(k) = p_{n}(M)(k) and M^{k} is 1-solid, i.e., if

W_{M^{k}}^{ν,p_{1}(M^{k})} ∈ M^{k}

for every ν ∈ p_{1}(M^{k}).

7.11 Lemma. Let M̄, M be acceptable, let n > 0, and let π: M̄ → M be rΣ_{n} elementary as being witnessed by p_{n−1}(M). If M̄ is n-solid and π(p_{1}(M̄^{n−1})) ∈ P_{M^{n−1}} then p_{n}(M) = π(p_{n}(M̄)) and M is n-solid.

7.12 Lemma. Let M̄, M be acceptable, let n > 0, and let π: M̄ → M be rΣ_{n} elementary as being witnessed by π^{−1}(p_{n−1}(M)). Suppose that M is nsolid, and in fact W_{M^{k}}^{ν,p_{1}(M^{k})} ∈ ran(π) for every k < n. If π^{−1}(p_{n−1}(M)) ∈ P n−1 ; M̄ then p_{n}(M̄) = π^{−1}(p_{n}(M̄)) and M̄ is n-solid.

The ultrapower maps we shall construct in the next section shall be elementary in the sense of the following definition. (Cf. [?, Definition 2.8.4].)

7.13 Definition. Let both M and N be acceptable, let π: M → N, and let n < ω. Then π is called an n-embedding if the following hold true.

(1) Both M and N are n-sound,

(2) π is rΣ_{n+1} elementary,

(3) π(p_{k}(M)) = p_{k}(N) for every k ≤ n, and

(4) π(ρ_{k}(M)) = ρ_{k}(N) for every k < n and ρ_{n}(N) = sup(π”ρ_{n}(M)).

Other examples for n-embeddings are typically obtained as follows. Let M be acceptable, and let, for n ∈ ω, ℭ_{n}(M) denote the transitive collapse of h_{M}^{n}”(ρ_{n}(M)∪{p_{n}(M)}). ℭ_{n}(M) is called the n^{th} core of M. The natural map from ℭ_{n+1}(M) to ℭ_{n}(M) will be an n-embedding under favourable circumstances.

8. Fine ultrapowers

This section deals with the construction of “fine structure preserving” embeddings. Inner model theory is in need of such maps in two main contexts: first, in “lift up arguments” which are crucial for instance in the proof of the Covering Lemma for L or higher core models and in the proof of □_{κ} in such models (cf. [?] and the next section), and second, in performing iterations of premice (cf. [?], [?], and [?]). This section will deal with the construction of such embeddings from an abstract point of view. The combinatorial objects which are used for defining such maps are called “extenders.”

The following definition makes use of notational conventions which are stated right after it.

8.1 Definition. Let M be acceptable. Then E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ is called a (κ, ν)-extender over M with critical points ⟨μ_{a}; a ∈ [ν]^{<ω}⟩ provided the following hold true.

(1) (Ultrafilter property) For a ∈ [ν]^{<ω} we have that E_{a} is an ultrafilter on the set 𝒫([μ_{a}]^{Card(a)}) ∩ M which is κ-complete w.r.t. sequences in M; moreover, μ_{a} is the least μ such that [μ]^{Card(a)} ∈ E_{a}.

(2) (Coherency) For a, b ∈ [ν]^{<ω} with a ⊆ b and for X ∈ 𝒫([μ_{a}]^{Card(a)}) ∩ M we have that X ∈ E_{a} ⇔ X^{ab} ∈ E_{b}.

(3) (Uniformity) μ_{{κ}} = κ.

(4) (Normality) Let a ∈ [ν]^{<ω} and f: [μ_{a}]^{Card(a)} → μ_{a} with f ∈ M. If

{u ∈ [μ_{a}]^{Card(a)}; f(u) < max(u)} ∈ E_{a}

then there is some β < max(a) such that

{u ∈ [μ_{a}]^{Card(a∪{β})}; f^{a,a∪{β}}(u) = u_{β}^{a∪{β}}} ∈ E_{a∪{β}}.

We write σ(E) = sup{μ_{a} + 1; a ∈ [ν]^{<ω}}. The extender E is called short if σ(E) = κ + 1; otherwise E is called long.

Let b = {β_{1} < ... < β_{n}}, and let a = {β_{j_{1}} < ... < β_{j_{m}}} ⊆ b. If u = {ξ_{1} < ... < ξ_{n}} then we write u_{a}^{b} for {ξ_{j_{1}} < ... < ξ_{j_{m}}}; we also write u_{β_{i}}^{b} for ξ_{i}. If X ∈ 𝒫([μ_{a}]^{Card(a)}), then we write X^{ab} for {u ∈ [μ_{b}]^{Card(b)}; u_{a}^{b} ∈ X}. Finally, if f has domain [μ_{a}]^{Card(a)} then we write f^{a,b} for that g with domain [μ_{b}]^{Card(b)} such that g(u) = f(u_{a}^{b}). Finally, we write pr for the function which maps {β} to β (i.e., pr = ⋃).

Notice that if E is a (κ, ν)-extender over the acceptable J-model M with critical points μ_{a}, and if N is another acceptable J-model with 𝒫(μ_{a})∩N = 𝒫(μ_{a}) ∩ M for all a ∈ [ν]^{<ω}, then E is also an extender over N.

The currently known core models are built with just short extenders on their sequence (cf. [?], [?], [?]). On the other hand, already the proof of the Covering Lemma for L has to make use of long extenders.

The following is easy to verify.

8.2 Theorem. Let M and N be acceptable, and let π: M ⟶_{Σ_{0}} N cofinally

with critical point κ. Let ν ≤ N ∩ On. For each a ∈ [ν]^{<ω} let μ_{a} be the least μ ≤ M ∩ On such that a ⊆ π(μ), and set

E_{a} = {X ∈ 𝒫([μ_{a}]^{Card(a)}) ∩ M; a ∈ π(X)}.

Then E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ is a (κ, ν)-extender over M.

8.3 Definition. If π: M → N, E, κ , and ν are as in the statement of Theorem 8.2 then E is called the (κ, ν)-extender derived from π.

8.4 Theorem. Let M = ⟨J_{α}^{A}, B⟩ be acceptable, and let E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ be a (κ, ν)-extender over M. There are then N and π such that the following hold true.

(a) π: M ⟶_{Σ_{0}} N cofinally with critical point κ,

(b) the well-founded part wfp(N) of N is transitive and ν ⊆ wfp(N),

(c) N = {π(f)(a); a ∈ [ν]^{<ω}, f: [μ_{a}]^{Card(a)} → M, f ∈ M}, and

(d) for a ∈ [ν]^{<ω} we have that X ∈ E_{a} if and only if X ∈ 𝒫([μ_{a}]^{Card(a)})∩ M and a ∈ π(X).

Moreover, N and π are unique up to isomorphism.

Proof. We do not construe (c) in the statement of this Theorem to presuppose that N be well-founded; in fact, this statement makes perfect sense even if N is not well-founded.

Let us first argue that N and π are unique up to isomorphism. Suppose that N, π and N′, π′ are both as in the statement of the Theorem. We claim that

π(f)(a) ↦ π′(f)(a)

defines an isomorphism between N and N′. Notice for example that π(f)(a) ∈ π(g)(b) if and only if, setting c = a ∪ b,

c ∈ π({u ∈ [μ_{c}]^{Card(c)}; f^{a,c}(u) ∈ g^{b,c}(u)}),

which by (d) yields that

{u ∈ [μ_{c}]^{Card(c)}; f^{a,c}(u) ∈ g^{b,c}(u)} ∈ E_{c},

and hence by (d) once more that

c ∈ π′({u ∈ [μ_{c}]^{Card(c)}; f^{a,c}(u) ∈ g^{b,c}(u)},

i.e., π′(f)(a) ∈ π′(g)(b).

The existence is shown by an ultrapower construction. Let us set

D = {⟨a, f⟩; a ∈ [ν]^{<ω}, f: [μ_{a}]^{Card(a)} → M, f ∈ M}.

For ⟨a, f⟩, ⟨b, g⟩ ∈ D let us write

⟨a, f⟩ ∼ ⟨b, g⟩ ⟺ {u ∈ [μ_{c}]^{Card(c)}; f^{a,c}(u) = g^{b,c}(u)} ∈ E_{c}, for c = a ∪ b.

We may easily use (1) and (2) of Definition 8.1 to see that ∼ is an equivalence relation on D. If ⟨a, f⟩ ∈ D then let us write [a, f] = [a, f]_{E}^{M} for the equivalence class {⟨b, g⟩ ∈ D; ⟨a, f⟩ ∼ ⟨b, g⟩}, and let us set

D̃ = {[a, f]; ⟨a, f⟩ ∈ D}.

Let us also define, for [a, f], [b, g] ∈ D̃,

[a, f] ˜∈ [b, g] ⟺ {u ∈ [μ_{c}]^{Card(c)}; f^{a,c}(u) ∈ g^{b,c}(u)} ∈ E_{c}, for c = a ∪ b
Ã([a, f]) ⟺ {u ∈ [μ_{a}]^{Card(a)}; f(u) ∈ A} ∈ E_{a}
B̃([a, f]) ⟺ {u ∈ [μ_{a}]^{Card(a)}; f(u) ∈ B} ∈ E_{a}

Notice that the relevant sets are members of M, as M is rud_{A}-closed and amenable. Moreover, by (1) and (2) of Definition 8.1, ˜∈, Ã, and B̃ are well-defined. Let us set

N = ⟨D̃, ˜∈, Ã, B̃⟩.

Claim 1. (Łoś Theorem) Let φ(v_{1}, ..., v_{k}) be a Σ_{0} formula, and let ⟨a_{1}, f_{1}⟩, ..., ⟨a_{k}, f_{k}⟩ ∈ D. Then

N ⊧ φ([a_{1}, f_{1}], ..., [a_{k}, f_{k}]) ⟺

{u ∈ [μ_{c}]^{Card(c)}; M ⊧ φ(f_{1}^{a_{1},c}(u), ..., f_{k}^{a_{k},c}(u))} ∈ E_{c} for c = a_{1} ∪ ... ∪ a_{k}.

Notice again that the relevant sets are members of M. Claim 1 is shown by induction on the complexity of φ, by exploiting (1) and (2) of Definition 8.1. Let us illustrate this by verifying the direction from right to left in the case that, say, φ ≡ ∃v_{0} ∈ v_{1} ψ for some Σ_{0} formula ψ.

We assume that, setting c = a_{1} ∪ ... ∪ a_{k},

{u ∈ [μ_{c}]^{Card(c)}; M ⊧ ∃v_{0} ∈ v_{1} ψ(f_{1}^{a_{1},c}(u), ..., f_{k}^{a_{k},c}(u))} ∈ E_{c}.

Let us define f_{0} : [μ_{c}]^{Card(c)} → ran(f_{1}) as follows.

f_{0}(u) = \begin{cases}the <_{M} −smallest x ∈ ran(f_{1}) with \\ M ⊧ ψ(x, f_{1}^{a_{1},c}, ..., f_{k}^{a_{k},c}(u)) & if some such x exists, \\ ∅ & otherwise. \end{cases}

The point is that f_{0} ∈ M, because M is rud_{A}-closed and amenable. But we then have that

{u ∈ [μ_{c}]^{Card(c)}; M ⊧ f_{0}(u) ∈ f_{1}^{a_{1},c}(u) ∧ ψ(f_{1}^{a_{1},c}(u), ..., f_{k}^{a_{k},c}(u))} ∈ E_{c},

which inductively implies that

N ⊧ [c, f_{0}] ∈ [a_{1}, f_{1}] ∧ ψ([a_{1}, f_{1}], ..., [a_{k}, f_{k}]),

and hence that

N ⊧ ∃v_{0} ∈ v_{1} ψ([a_{1}, f_{1}], ..., [a_{k}, f_{k}]).

Given Claim 1, we may and shall from now on identify, via the Mostowski collapse, the well-founded part wfp(N) of N with a transitive structure. In particular, if [a, f] ∈ wfp(N) then we identify the equivalence class [a, f] with its image under the Mostowski collapse.

Let us now define π: M → N by

π(x) = [0, c_{x}], where c_{x}: [μ_{0}]^{0} → {x}.

We aim to verify that N, π satisfy (a), (b), (c), and (d) from the statement of Theorem 8.4.

Claim 2. If α < ν and [a, f] ˜∈ [{α}, pr] then [a, f] = [{β}, pr] for some β < α.

46 I. Fine structure

In order to prove Claim 2, let [a, f] ˜∈ [{α}, pr]. Set b = a ∪ {α}. By the Łoś Theorem,

{u ∈ [μ_{b}]^{Card(b)}; f^{a,b}(u) ∈ pr^{{α},b}(u)} ∈ E_{b}.

By (4) of Definition 8.1, there is some β < α such that, setting c = b ∪ {β},

{u ∈ [μ_{c}]^{Card(c)}; f^{a,c}(u) = pr^{{β},c}(u)} ∈ E_{c},

and hence, by the Łoś Theorem again,

[a, f] = [{β}, pr].

Claim 2 implies, via a straightforward induction, that

[{α}, pr] = α for α < ν.  (I.29)

In particular, (b) from the statement of Theorem 8.4 holds.

Claim 3. If a ∈ [ν]^{<ω} then [a, id] = a.

If [b, f] ˜∈ [a, id] then by the Łoś Theorem, setting c = a ∪ b,

{u ∈ [μ_{c}]^{Card(c)}; f^{b,c}(u) ∈ u_{a}^{c}} ∈ E_{c}.

However, as E_{c} is an ultrafilter, there must then be some α ∈ a such that

{u ∈ [μ_{c}]^{Card(c)}; f^{b,c}(u) = u_{α}^{c}} ∈ E_{c},

and hence by the Łoś Theorem and (I.29)

[b, f] = [{α}, pr] = α.

On the other hand, if α ∈ a then it is easy to see that α ∈ [a, id]. This shows Claim 3.

Claim 4. [a, f] = π(f)(a).

Notice that this statement makes sense even if [a, f] ∉ wfp(N).

Let b = a ∪ {0}. We have that

{u ∈ [μ_{b}]^{Card(b)}; f^{a,b}(u) = ((c_{f})^{{0},b}(u))(id^{a,b}(u))} = [μ_{b}]^{Card(b)} ∈ E_{b}, by (1) of Definition 8.1, and therefore by the Łoś Theorem and Claim 3,

[a, f] = [0, c_{f}]([a, id]) = π(f)(a).

Claim 4 readily implies (c) from the statement of Theorem 8.4.

Claim 5. κ = cr(π).

Let us first show that π ↾ κ = id. We prove that π(ξ) = ξ for all ξ < κ by induction on ξ.

Let ξ < κ. Suppose that [a, f] ˜∈ π(ξ) = [0, c_{ξ}]. Set b = a ∪ {ξ}. Then

{u ∈ [μ_{b}]^{Card(b)}; f^{a,b}(u) < ξ} ∈ E_{b}.

As E_{b} is κ-complete w.r.t. sequences in M (cf. (1) of Definition 8.1), there is hence some ξ̄ < ξ such that

{u ∈ [μ_{b}]^{Card(b)}; f^{a,b}(u) = ξ̄} ∈ E_{b},

and therefore [a, f] = π(ξ̄) which is ξ̄ by the inductive hypothesis. Hence π(ξ) ⊆ ξ. It is clear that ξ ⊆ π(ξ).

We now prove that π(κ) > κ (if π(κ) ∉ wfp(N) we mean that κ˜∈π(κ)) which will establish Claim 5. Well, μ_{{κ}} = κ, and

{u ∈ [κ]^{1}; pr(u) < κ} = [κ]^{1} ∈ E_{{κ}},

from which it follows, using the Łoś Theorem, that κ = [{κ}, pr] < [0, c_{κ}] = π(κ).

The following, together with Claim 1 and Claim 5, will establish (a) from the statement of Theorem 8.4.

Claim 6. For all [a, f] ∈ N there is some y ∈ M with [a, f] ˜∈ π(y).

To verify Claim 6, it is easy to see that we can just take y = ran(f). It remains to prove (d) from the statement of Theorem 8.4. Let X ∈ E_{a}. By (1) of Definition 8.1,

X = {u ∈ [μ_{a}]^{Card(a)}; u ∈ X} ∈ E_{a},

which, by the Łoś Theorem and Claim 3, gives that a = [a, id] ˜∈ [0, c_{X}] = π(X).

On the other hand, suppose that X ∈ 𝒫([μ_{a}]^{Card(a)}) ∩ M and a ∈ π(X). Then by Claim 3, [a, id] = a ∈ π(X) = [0, c_{X}], and thus by the Łoś Theorem

X = {u ∈ [μ_{a}]^{Card(a)}; u ∈ X} ∈ E_{a}.

We have shown Theorem 8.4. ⊣

8.5 Definition. Let M, E, N, and π be as in the statement of Theorem 8.4. We shall denote N by Ult_{0}(M; E) and call it the Σ_{0} ultrapower of M by E, and we call π: M → N the Σ_{0} ultrapower map (given by E). We shall also write π_{E} for π.

8.6 Definition. Let M be acceptable, and let E be a (κ, ν)-extender over M. Let n < ω be such that ρ_{n}(M) > σ(E). Suppose that M is n-sound, and set p = p_{n}(M). Let

π: M^{n,p} → N̄

be the Σ_{0} ultrapower map given by E. Suppose that

π̃: M → N

is as given by the proof of Lemmata 4.2 and 5.11. Then we write Ult_{n}(M; E) for N and call it the rΣ_{n+1} ultrapower of M by E, and we call π̃ the rΣ_{n+1} ultrapower map (given by E).

A comment is in order here. Lemmata 4.2 and 5.11 presupposes that π is strong (cf. Definition 4.1). However, the construction of the term model in section 4 does not require π to be strong, nor does it even require the target model N̄ to be well-founded. Consequently, we can make sense of Ult_{n}(M; E) even if π is not strong or N̄ is not well-founded. This is why we have “the proof of Lemmata 4.2 and 5.11” in the statement of Definition 8.6. We shall of course primarily be interested in situations where Ult_{n}(M; E) is well-founded after all. In any event, we shall identify the well-founded part of Ult_{n}(M; E) with its transitive collapse.

One can also construct rΣ_{n+1} ultrapower maps without assuming that the model one takes the ultrapower of is n-sound; this is done by pointwise lifting up a directed system converging to the model in question. However, the construction of Definition 8.6 seems to be broad enough for most applications.

Recall Definition 5.12. It is clear in the light of the upward extension of embeddings lemma that any rΣ_{n+1} ultrapower map is rΣ_{n+1} elementary (and hence the name). The following will give more information.

8.7 Theorem. Let M be acceptable, and let E be a (κ, ν)-extender over M. Let n < ω be such that ρ_{n}(M) > σ(E). Suppose that M is n-sound and (n + 1)-solid. Let

π: M → Ult_{n}(M; E)

be the rΣ_{n+1} ultrapower map given by E. Assume that Ult_{n}(M; E) is transitive, and that π(p_{n+1}(M)) ∈ P_{N}^{n+1}.

Then π is an n-embedding, Ult_{n}(M; E) is (n+1)-solid, and π(p_{n+1}(M)) = p_{n+1}(N).

Proof. Set N = Ult_{n}(M; E). That N is n-sound follows from the upward extension of embeddings lemma. N is (n + 1)-solid and π(p_{n+1}(M)) = p_{n+1}(N) by Lemma 7.11. By construction we have that π is the upward extension of

π ↾ M^{n}: M^{n} → Ult_{0}(M^{n}; E),

so that by the upward extension of embeddings lemma we shall now have that N^{n} = Ult_{0}(M^{n}; E), and therefore ρ_{n}(N) = N^{n} ∩ On = Ult_{0}(M^{n}; E) ∩ On; however, π ↾ M^{n} is cofinal in Ult_{0}(M^{n}; E) by Theorem 8.4, and thus ρ_{n}(N) = sup”ρ_{n}(M). The upward extension of embeddings lemma also implies that π(ρ_{k}(M)) = ρ_{k}(N) for all k < n. ⊣

The following is sometimes called the “Interpolation Lemma.” We leave the (easy) proof to the reader.

8.8 Lemma. Let n < ω. Let M̄, M be acceptable, and let

π: M̄ ⟶ M

be rΣ_{n+1} elementary. Let ν ≤ M ∩ On, and let E be the (κ, ν)-extender derived from π.

There is then a weakly rΣ_{n+1} elementary embedding

σ: Ult_{n}(M̄; E) → M

such that σ ↾ ν = id and σ ∘ π_{E} = π.

If π is as in Theorem 8.7 then it is often crucial to know that ρ_{n+1}(M) = ρ_{n+1}(Ult_{n}(M; E)). In order to be able to prove this we need that ⟨M, E⟩ satisfies additional hypotheses.

8.9 Definition. Let M be acceptable, and let E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ be a (κ, ν)-extender over M. Then E is close to M if for every a ∈ [ν]^{<ω},

(1) E_{a} is Σ_{1}^{M}({q}) for some q ∈ M, and

(2) if Y ∈ M, M ⊧ Card(Y) ≤ κ, then E_{a} ∩ Y ∈ M.

The following theorem is the key tool for proving the preservation of the standard parameter in iterations of mice.

8.10 Theorem. Let M be acceptable, and let E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ be a short (κ, ν)-extender over M which is close to M. Suppose that n < ω is such that ρ_{n+1}(M) ≤ κ < ρ_{n}(M), M is n-sound, and Ult_{n}(M; E) is transitive. Then

𝒫(κ) ∩ M =𝒫(κ) ∩ Ult_{n}(M; E), and
ρ_{n+1}(M) =ρ_{n+1}(Ult_{n}(M; E)).

In particular, if M is (n + 1)-solid then Ult_{n}(M; E) is (n + 1)-solid and π(p_{n+1}(M)) = p_{n+1}(Ult_{n}(M; E)).

Proof. Set N = Ult_{n}(M; E). Trivially, 𝒫(κ) ∩ M ⊆ 𝒫(κ) ∩ N. To show that 𝒫(κ) ∩ N ⊆ 𝒫(κ) ∩ M, let X ∈ 𝒫(κ) ∩ N. Let X = [a, f]_{E}^{M^{n}}. As E is short, μ_{a} ≤ κ; in fact, w.l.o.g., μ_{a} = κ. Hence for ξ < κ, if we set

X_{ξ} = {u ∈ [κ]^{Card(a)}; ξ ∈ f(u)}

then {X_{ξ}; ξ < κ} ∈ M^{n} ⊆ M. But ξ ∈ X ⇔ X_{ξ} ∈ E_{a} by the Łoś Theorem, and since E is close to M we get that X ∈ M.

If A ∈ Σ_{1}^{M^{n}}({q}), where q ∈ M^{n}, then A∩ρ_{n+1}(M) ∈ Σ_{1}^{N^{n}}({π(q), ρ_{n+1}(M)}). Because 𝒫(κ) ∩ N ⊆ 𝒫(κ) ∩ M, we thus have that ρ_{n+1}(N) ≤ ρ_{n+1}(M).

To show that ρ_{n+1}(M) ≤ ρ_{n+1}(N), let A ∈ Σ_{1}^{N^{n}}({q}) for some q ∈ N^{n}. Let q = [a, f]_{E}^{M^{n}}, and let

x ∈ A ⟺ N^{n} ⊧ φ(x, [a, f]),

where φ is Σ_{1}. If M^{n} = ⟨J_{α}^{B}, A⟩ and δ < α then we shall write M^{n,δ} for ⟨J_{δ}^{B}, A ∩ J_{δ}^{B}⟩. For δ < N^{n} ∩ On, N^{n,δ} is defined similarly. Because π_{E}: M^{n} → N^{n} is cofinal, we have that

x ∈ A ⟺ ∃δ < M^{n} ∩ On N^{n,π_{E}(δ)} ⊧ φ(x, [a, f]).

By the Łoś Theorem, we may deduce that for ξ < κ,

ξ ∈ A ⟺ ∃δ < M^{n} ∩ On {u ∈ [κ]^{Card(a)}; M^{n,δ} ⊧ φ(ξ, f(u))} ∈ E_{a}.

But now E is close to M, so that E_{a} is Σ_{1}^{M^{n}}({q′}) for some q′ ∈ M^{n}, which implies that A ∩ κ is Σ_{1}^{M^{n}}({q′, κ, f}).

We now finally have that π(p_{n+1}(M)) ∈ P_{M}^{n+1}. Therefore, if M is (n+1)- solid then Ult_{n}(M; E) is (n+1)-solid and π(p_{n+1}(M)) = p_{n+1}(Ult_{n}(M; E)) by Lemma 7.12. ⊣

We now turn towards criteria for Ult_{n}(M; E) being well-founded.

8.11 Definition. Let M be acceptable, and let E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ be a (κ, ν)-extender over M. Let λ < Card(κ) be an infinite cardinal (in V). Then E is called λ-complete provided the following holds true. Suppose that ⟨⟨a_{i}, X_{i}⟩; i < λ⟩ is such that X_{i} ∈ E_{a_{i}} for all i < λ. Then there is some order-preserving map τ: ⋃_{i<λ} a_{i} → σ(E) such that τ”a_{i} ∈ X_{i} for every i < λ.

8.12 Lemma. Let M be acceptable, and let E = ⟨E_{a}; a ∈ [ν]^{<ω}⟩ be a (κ, ν)-extender over M. Let λ < Card(κ) be an infinite cardinal. Then E is λ-complete if and only if for every U ≺_{Σ_{0}} Ult_{0}(M; E) of size λ there is

some φ: U ⟶_{Σ_{0}} M such that φ ∘ π_{E}(x) = x whenever π_{E}(x) ∈ U.

Proof. “⇒”: Let U ≺_{Σ_{0}} Ult_{0}(M; E) be of size λ. Write U = {[a, f]; ⟨a, f⟩ ∈

Ū} for some Ū of size λ. Let ⟨⟨a_{i}, X_{i}⟩; i < λ⟩ be an enumeration of all pairs ⟨c, X⟩ such that there is a Σ_{0} formula ψ and there are ⟨a^{1}, f_{1}⟩, ..., ⟨a^{k}, f_{k}⟩ ∈ Ū with c = a^{1} ∪ ... ∪ a^{k} and

X = {u ∈ [μ_{c}]^{Card(c)}; M ⊧ ψ(f_{1}^{a^{1},c}(u), ..., f_{k}^{a^{k},c})} ∈ E_{c}.

Let τ: ⋃_{i<λ} a_{i} → σ(E) be order-preserving such that τ”a_{i} ∈ X_{i} for every i < λ. Let us define φ: U → M by setting φ([a, f]) = f(τ”(a)) for ⟨a, f⟩ ∈ Ū.

We get that φ is well-defined and Σ_{0} elementary by the following reasoning. Let ψ(v_{1}, ..., v_{k}) be Σ_{0}, and let ⟨a^{j}, f_{j}⟩ ∈ U, 1 ≤ j ≤ k. Set c = a^{1} ∪ ... ∪ a^{k}. We then get that

U ⊧ψ([a^{1}, f_{1}], ..., [a^{k}, f_{k}])  ⟺
Ult_{0}(M; E) ⊧ψ([a^{1}, f_{1}], ..., [a^{k}, f_{k}])  ⟺
{u ∈ [μ_{c}]^{Card(c)}; M ⊧ψ(f_{1}^{a^{1},c}(u), ..., f_{k}^{a^{k},c}(u))} ∈ E_{c}  ⟺
τ”c ∈ {u ∈ [μ_{c}]^{Card(c)};M ⊧ ψ(f_{1}^{a^{1},c}(u), ..., f_{k}^{a^{k},c}(u))}  ⟺
M ⊧ψ(f_{1}(τ”a^{1}), ..., f_{k}(τ”a^{k})).

We also get that φ ∘ π_{E}(x) = φ([∅, c_{x}]) = c_{x}(∅) = x.

“⇐”: Let ⟨⟨a_{i}, X_{i}⟩; i < λ⟩ be such that X_{i} ∈ E_{a_{i}} for all i < λ. Pick U ≺_{Σ_{0}} Ult_{0}(M; E) with {a_{i}, X_{i}; i < λ} ⊆ U, Card(U) = λ, and let φ: U ⟶_{Σ_{0}} M

be such that φ∘π_{E}(x) = x whenever π_{E}(x) ∈ U. Set τ = φ ↾ ⋃_{i<λ} a_{i}. Then τ”a_{i} = φ(a_{i}) ∈ φ ∘ π_{E}(X_{i}) = X_{i} for all i < λ. Clearly, ran(τ) ⊆ σ(E). ⊣

8.13 Corollary. Let M be acceptable, and let E be an ℵ_{0}-complete (κ, ν)- extender over M. Then Ult_{0}(M; E) is well-founded. In fact, if n < ω is such that ρ_{n}(M) ≥ σ(E) then Ult_{n}(M; E) is well-founded.

The concept of ℵ_{0}-completeness is relevant for constructing inner models below the “sharp” for an inner model with a proper class of strong cardinals (cf. [?]). There are strengthenings of the concept of ℵ_{0}-completeness which are needed for the construction of inner models beyond the “sharp” for an inner model with a proper class of strong cardinals (cf. for instance [?, Definition 1.2], [?, Definition 1.6]).

8.14 Lemma. Let λ be an infinite cardinal, and let θ be regular. Let π: H̄ → H_{θ}, where H̄ is transitive and ^{λ}H̄ ⊆ H̄. Suppose that π ≠ id, and set κ = cr(π). Let M be acceptable, let ρ be regular in M, and suppose that H_{ρ}^{M} ⊆ H̄. Set ν = supπ”ρ, and let E be the (κ, ν)-extender derived from π ↾ H_{ρ}^{M}. Then E is λ-complete.

Proof. Let ⟨⟨a_{i}, X_{i}⟩; i < λ⟩ be such that X_{i} ∈ E_{a_{i}}, and hence a_{i} ∈ π(X_{i}), for all i < λ. As ^{λ}H̄ ⊆ H̄, ⟨X_{i}; i < λ⟩ ∈ H̄. Let σ: otp(⋃_{i<λ} a_{i}) ≅ γ be the transitive collapse; notice that γ < λ^{+} < κ. For each i < λ let ā_{i} = σ”a_{i}. We have that ⟨ā_{i}; i < λ⟩ ∈ H̄. But now

H_{θ} ⊧ ∃τ: γ ˜→On ∀i < λ τ”ā_{i} ∈ π(⟨X_{j}; j < λ⟩)(i),

as witnessed by σ. Therefore,

H̄ ⊧ ∃τ: γ ˜→On ∀i < λ τ”ā_{i} ∈ X_{i}.

Hence, if τ ∈ H̄ is a witness to this fact then τ ∘ σ: ⋃_{i<λ} a_{i} → On is such that τ ∘ σ”a_{i} ∈ X_{i} for every i < λ. ⊣

We leave it to the reader to find variants of this result. For instance, extenders derived from canonical ultrapower maps witnessing that a given cardinal κ is measurable are λ-complete for every λ < κ.

9. Applications to L

In this final section we shall illustrate how to use the above machinery in the simplest case – in the constructible universe L. The theory developed above is, however, general enough so that it can be used for all the currently known core models.

We shall first prove two important lemmata. Recall that we index the J-hierarchy with limit ordinals.

9.1 Lemma. For each limit ordinal α, J_{α} is acceptable.

9.2 Lemma. For each limit ordinal α, J_{α} is sound.

We shall prove these two lemmata simultaneously. The proof goes by induction on α in a zig-zag way in the sense that we use soundness of J_{α} to prove the acceptability of J_{α+ω} and then, knowing this, its soundness.

Proof. The case α = ω is trivial. Now suppose both lemmata hold for all limit ordinals β < α.

Claim 1. J_{α} is acceptable.

This is trivial for α being a limit of limit ordinals. For α = β + ω it is clear that the only thing we have to prove is the following:

If there is τ < β and a ⊆ τ such that a ∈ J_{β+ω} \ J_{β}, (I.30)
then there is an f ∈ J_{β+ω} such that f : τ ⟶^{onto} β.

We prove (I.30). Suppose there are such τ, a and take τ to be the least one such that there is a as above. Then

τ = ρ_{ω}(J_{β}).  (I.31)

To see (I.31) note first that if n is such that ρ_{n}(J_{β}) = ρ_{ω}(J_{β}), then we have a new Σ_{1}^{J_{β}^{n}} subset of ρ_{ω}(J_{β}). Such a set is Σ_{ω}^{J_{β}} by Lemma 5.5, and is hence in J_{β} + ω \ J_{β} by Lemma 1.7. Therefore, τ ≤ ρ_{ω}(J_{β}).

9. Applications to L 53

Let a ⊆ τ such that a ∈ J_{β+ω} \ J_{β}. Then a ∈ Σ_{n}^{J_{β}} for some n ∈ ω by Lemma 1.7. By the above inequality, a ⊆ ρ_{n}(J_{β}). Lemma 5.6 then

yields that a is Σ_{1}^{J_{β}^{n−1}}, since, by the induction hypothesis, J_{β} is sound. Consequently, ρ_{ω}(J_{β}) ≤ τ. This proves (I.31).

Now we use the induction hypthesis once again to verify (I.30). By the soundness of J_{β} and by Lemmata 5.4 and 5.5, there is some f ∈ Σ_{ω}^{J_{β}} such that f: ρ_{ω}(J_{β}) → J_{β} is surjective. By Lemma 1.7, f ∈ J_{β+ω}. This shows (I.30) and therefore also Claim 1.

Claim 2. J_{α} is sound.

We shall make use of Lemma 6.8 here. Hence, for n < ω we prove

p_{n}(J_{α}) ∈ R_{J_{α}}^{n}.  (I.32)

Suppose this is false. Pick the first n such that p = p_{n}(J_{α}) ∉ R_{J_{α}}^{n}. Let a

be Σ_{1}^{J_{α}^{n−1}}({p}) such that a ∩ ρ_{n}(J_{α}) ∉ J_{α}. Using the downward extension of embeddings lemma we construct unique Jᾱ, p̄, π such that

\{ \begin{matrix}p̄ ∈ R_{Jᾱ}^{n} \\ π : J n−1,p̄↾n−1 ; ᾱ → J_{α}^{n−1,p↾n−1} is Σ_{1} elementary \\ π(p̄(n − 1)) = p(n − 1) \\ π ↾ J_{ρ_{n}(J_{α})} = id. \end{matrix}  (I.33)

Hence a ∩ ρ_{n}(J_{α}) = ā ∩ ρ_{n}(Jᾱ) where ā is Σ_{1}^{J n−1 ; ᾱ}({p̄(n − 1)}) by the same definition. Hence ᾱ cannot be less than α, since otherwise a ∩ ρ_{n}(J_{α}) ∈ J_{α}. Consequently, ᾱ = α. It is also clear by the construction that p̄ ≤^{∗} p. But p ≤^{∗} p̄ since p is the standard parameter. Hence, p = p̄. But this means p ∈ R_{J_{α}}^{n}. Contradiction.

⊣

Classical applications of the fine structure theory include Jensen’s results that ♢ and □ hold in L and that L satisfies the Covering Lemma. The following is Jensen’s Covering Lemma for L.

9.3 Theorem. Suppose that 0^{#} does not exist. Let X be a set of ordinals. Then there is Y ∈ L with Y ⊇ X and Card(Y) ≤ Card(X) · ℵ_{1}.

This result is shown in [?] (cf. also [?]). In order to illustrate the fine structural techniques we have developed we shall now give a proof of a corollary to Theorem 9.3. Recall that a cardinal κ is called countably closed if λ^{ℵ_{0}} < κ whenever λ < κ.

9.4 Corollary. Let κ be a countably closed singular cardinal. If 0^{#} does not exist then κ^{+L} = κ^{+}.

Proof. We shall use the fact that the existence of 0^{#} is equivalent with the existence of a non-trivial elementary embedding π: L → L. Suppose that 0^{#} does not exist and κ is a countably closed singular cardinal such that κ^{+L} < κ^{+}. We aim to derive a contradiction.

Let X ⊆ κ^{+L} be cofinal with otp(X) < κ. We may pick an elementary embedding

π: H̄ → H_{κ^{+}}

such that H̄ is transitive, ^{ω}H̄ ⊆ H̄, X ⊆ ran(π), and Card(H̄) = otp(X)^{ℵ_{0}}. As κ is countably closed, Card(H̄) < κ, which implies that π ≠ id. Set λ = π^{−1}(κ^{+L}), and let E be the (κ, π(λ))-extender over J_{λ} derived from π ↾ J_{λ}.

By Lemma 8.14, E is ℵ_{0}-complete. By Corollary 8.13, this implies the following.

Claim. Let α ≥ λ, α ∈ On ∪ {On}. Suppose that λ is a cardinal in J_{α} (which implies that E is an extender over J_{α}). Suppose that ρ_{n}(J_{α}) ≥ λ. Then Ult_{n}(J_{α}; E) is transitive, and therefore Ult_{n}(J_{α}; E) = J_{β} for some β ∈ On ∪ {On}. (If α = On then by J_{α} we mean L, and we want n = 0; we shall then have J_{β} = L as well.)

Now because 0^{#} does not exist, we cannot have that α = On satisfies the hypothesis of the Claim. Let α ∈ On \ λ be largest such that λ is a cardinal in J_{α}. Let n < ω be such that ρ_{n+1}(J_{α}) < λ ≤ ρ_{n}(J_{α}). By Lemma 9.2, we have that

J_{α} = h_{J_{α}}^{n+1}”(ρ_{n+1}(J_{α}) ∪ {p}),

where p = p_{n+1}(J_{α}). (Cf. Lemma 5.4.) Because π_{E} is rΣ_{n+1} elementary by Theorem 8.7, Lemma 5.13 implies that

X ⊆ π”J_{α} ⊆ h_{J_{β}}^{n+1}”(π(ρ_{n+1}(J_{α})) ∪ {π(p)}).

But π(ρ_{n+1}) ≤ κ, so that in particular

J_{β+ω} ⊧ π(λ) is not a cardinal.

However, π(λ) = κ^{+L}. Contradiction! ⊣

We finally aim to prove □_{κ} in L. This is the combinatorial principle the proof of which most heavily exploits the fine structure theory.

Let κ be an infinite cardinal. Recall that we say that □_{κ} holds if and only if there is a sequence ⟨C_{ν}; ν < κ^{+}⟩ such that if ν is a limit ordinal, κ < ν < κ^{+}, then C_{ν} is a club subset of ν with otp(C_{ν}) ≤ κ and whenever ν̄ is a limit point of C_{ν} then Cν̄ = C_{ν} ∩ ν̄.

9.5 Theorem. Suppose that V = L. Let κ ≥ ℵ_{1} be a cardinal. Then □_{κ} holds.

Proof. We shall verify that there is a club C ⊆ κ^{+} and some ⟨C_{ν}; ν ∈ C ∧ cf(ν) > ω⟩ such that if ν is a limit ordinal, κ < ν < κ^{+}, then C_{ν} is a club subset of ν with otp(C_{ν}) ≤ κ and whenever ν̄ is a limit point of C_{ν} then Cν̄ = C_{ν} ∩ ν̄. It is not hard to verify that this implies □_{κ} (cf. [?, pp. 158ff.]).

Let C = {ν < κ^{+}; J_{ν} ≺_{Σ_{ω}} J_{κ^{+}}}, a closed unbounded subset of κ^{+}.

Let ν ∈ C. Obviously, κ is the largest cardinal of J_{ν}. We may let α(ν) be the largest α ≥ ν such that either α = ν or ν is a cardinal in J_{α}. By Lemma 1.7, ρ_{ω}(J_{α(ν)}) = κ. Let n(ν) be that n < ω such that κ = ρ_{n+1}(J_{α(ν)}) < ν ≤ ρ_{n}(J_{α(ν)}).

If ν ∈ C, then we define D_{ν} as follows. D_{ν} consists of all ν̄ ∈ C ∩ ν such that n(ν̄) = n(ν), and there is a weakly rΣ_{n(ν)+1} elementary embedding

σ: J_{α(ν̄)} ⟶ J_{α(ν)}.

such that σ ↾ ν̄ = id, σ(p_{n(ν̄)+1}(J_{α(ν̄)})) = p_{n(ν)+1}(J_{α(ν)}), and if ν̄ ∈ J_{α(ν̄)} then ν ∈ J_{α(ν)} and σ(ν̄) = ν. It is easy to see that if ν̄ ∈ D_{ν} then there is exactly one map σ witnessing this, namely the one with

σ(h_{J_{α(ν̄)}}^{n(ν̄)+1}(ξ, p_{n(ν̄)+1}(J_{α(ν̄)}))) = h_{J_{α(ν)}}^{n(ν)+1}(ξ, p_{n(ν)+1}(J_{α(ν)}))

ξ < κ; we shall denote this map by σ_{ν̄,ν}.

Claim 1. Let ν ∈ C. The following hold true.

(a) D_{ν} is closed.

(b) If cf(ν) > ω then D_{ν} is unbounded.

(c) If ν̄ ∈ D_{ν} then D_{ν} ∩ ν̄ = Dν̄.

Proof of Claim 1. (a) and (c) are easy. Let us show (b). Suppose that cf(ν) > ω. Set α = α(ν) and n = n(ν). Let β < ν. We aim to show that D_{ν} \ β ≠ ∅.

Let π: Jᾱ ⟶_{Σ_{n+1}} J_{α} be such that ᾱ is countable, β ∈ ran(π), and

{W_{J_{α}^{k}}^{ν,p_{1}(J_{α}^{k})}; ν ∈ p_{1}(J_{α}^{k}), k ≤ n} ⊆ ran(π).

Let ν̄ = π^{−1}(ν) (if ν = α, we mean ν̄ = ᾱ). Let

π′ = π_{E_{π↾Jν̄}} : Jᾱ ⟶_{rΣ_{n+1}} Ult_{n}(Jᾱ; E_{π↾Jν̄}).

Write J_{α′} = Ult_{n}(Jᾱ; E_{π↾Jν̄}). By Lemma 8.8, we may define a weakly rΣ_{n+1} elementary embedding

k: J_{α′} ⟶ J_{α}

with k∘π′ = π. As β ∈ ran(π), k^{−1}(ν) > β. Moreover, k^{−1}(ν) = sup π”ν̄ < ν, as cf(ν) > ω. Therefore β < k^{−1}(ν) ∈ D_{ν}. ⊣

Now let ν ∈ C. We aim to define C_{ν}. Set α = α(ν), and n = n(ν). Recursively, we define sequences ⟨ν_{i}; i ≤ θ(ν)⟩ and ⟨ξ_{i}; i < θ(ν)⟩ as follows. Set ν_{0} = min(D_{ν}). Given ν_{i} with ν_{i} < ν, we let ξ_{i} be the least ξ < κ such that

h_{J_{α}}^{n+1}(ξ, p_{n+1}(J_{α})) \ ran(σ_{ν_{i},ν}) ≠ ∅.

Given ξ_{i}, we let ν_{i+1} be the least ν̄ ∈ D_{ν} such that

h_{J_{α}}^{n+1}(ξ_{i}, p_{n+1}(J_{α})) ∈ ran(σ_{ν̄,ν}).

Finally, given ⟨ν_{i}; i < λ⟩, where λ is a limit ordinal, we set ν_{λ} = sup({ν_{i}; i < λ}. Naturally, θ(ν) will be the least i such that ν_{i} = ν. We set C_{ν} = {ν_{i}; i < θ(ν)}.

The following is now easy to verify.

Claim 3. Let ν ∈ C. The following hold true.

(a) ⟨ξ_{i}; i < θ(ν)⟩ is strictly increasing.

(b) otp(C_{ν}) = θ(ν) ≤ κ.

(c) C_{γ} is closed.

(d) If ν̄ ∈ C_{ν} then C_{ν} ∩ ν̄ = Cν̄.

(e) If D_{ν} is unbounded in ν then so is C_{ν}.

We have shown that □_{κ} holds. ⊣