It is immediate that J0 = ∈ M. If δ > 0, then π−1(δ)< β. Then 〈Jβ, ∈〉 ⊨ (∃x) (∃s)φ(x, π−1(δ), s) and so 〈M, ∈〉 ⊨ (∃x)(∃s)φ(x, δ, s). Let x ∈ M and let s ∈ M such that 〈M, ∈〉 ⊨ φ(x, δ, s). By the absoluteness of φ(x, δ, s), any admissible structure containing x, s and δ satisfies φ(x, δ, s). By Proposition 3.3.3, Jδ = x ∈ M.

Furthermore, for any x ∈ M, there exists a δ < β such that π−1(x)∈ Jδ. Hence 〈Jβ, ∈〉 ⊨ (∃δ)(∃y)(∃s)(π−1(x)∈ y ∧ φ(y, δ, s)). Then 〈M, ∈〉 ⊨ (∃δ)(∃y)(∃s)(x ∈ y ∧ φ(y, δ, s)). By Proposition 3.3.3 again, x ∈ Jδʹ for some δʹ < γ. We conclude that Jγ ⊇ M

Suppose x <Jβ π(x) for some x ∈ X. Take x0 to be the <Jβ-least such set. Then x0 ∈ Jγ since π(x0)∈ Jγ and so there is an x1 ∈ X such that π(x1)= x0. If x0 <Jβ x1, then π(x0)<Jα π(x1)= x0 which contradicts the assumption that x0 <Jβ π(x0). So x1 <Jβ π(x1)= x0 which contradicts the choice of x0 to be the Jβ-least counterexample.

An immediate consequence of the Condensation Theorem (3.3.7) is that V = L implies the Continuum Hypothesis. We leave the proof as an exercise.

Corollary 3.3.8. 2ω ∩ L = 2ω ∩ Lω1.

Another important tool in the theory of constructibility is the use of Skolem functions. A relation or function is Σn()-definable if it is Σn-definable over (possibly with parameters).

Definition 3.3.9. Given a structure , a Σn-Skolem function for is a Σn()-definable function h : ω × M → M with parameter p ∈ M such that for any A ⊆ M which is Σn-definable over with parameters p, x ∈ M, there is an i ∈ ω satisfying h(i, x)∈ A.

Thus a Σn-Skolem function is a Σn-definable choice function for Σn-sets.

Proposition 3.3.10. Suppose that α > 0 is admissible and h is a Σn-Skolem function for 〈Jα, ∈〉. Then

(i)for any x ∈ Jα, x ∈ Range(h(ω ×{x})) and 〈Range(h(ω ×{x})), ∈〉 ≺Σn 〈Jα, ∈〉;

(ii)if q ∈ Jα and X ⊆ Jα is closed under ordered pairs, then X ∪{q} ⊆ Range(h(ω ×(X ∪ {q})) and 〈Range(h(ω ×(X ∪{q})), ∈〉 ≺Σn 〈Jα, ∈〉.

Proof. Note that (i) is straightforward to verify and is a standard fact in model theory.

For (ii), since X is closed under ordered pairs, any finite sequence from X used to define a finite sequence in Range(h(ω ×(X ∪{q})) may be coded by a single parameter. Hence it is routine to show 〈Range(h(ω ×(X ∪{q})), ∈〉 ≺Σn 〈Jα, ∈〉.

We remark that the existence of a Σn-Skolem function is not atrivial fact. Inmodel theory, defining a Skolem function for a structure requires a well-ordering of . In the constructible universe L, however, there is a uniformly Σ1-definable Skolem function.

Proposition 3.3.11. There is a Σ1-formula φ(x, y, i, z) such that for any ordinal α, the function

is a Σ1-Skolem function for 〈Jα, ∈〉.

Proof. By Proposition 3.3.3, there is a Σ1-formula φ<(u, v) defining a well-ordering <J of Jα for any admissible α. Clearly there is a Σ1-enumeration {φi(u, v, w)} of all Σ0-formulas. In other words, there is a Σ1-formula φ(x, y, i, z) so that 〈Jα, ∈〉 ⊨ φ(x, y, i, z) ⇔ 〈Jα, ∈〉 ⊨ φi(x, y, z). Define hα(i, x) to be y0 such that (y0, y1) is the <J-least pair with 〈Jα, ∈〉 ⊨ φi(y0, y1, x). By Proposition 3.3.3, hα(i, x) is Σ1-definable.

By the admissibility of α, using some tedious coding argument which may be found in [22], one can show that the relation “〈Jα, ∈〉 ⊨ φi(y0, y1, x)” is uniformly Δ1. Let hα(i, x)= y0 if and only if there exists a y1 such that 〈Jα, ∈〉 ⊨ φi(y0, y1, x) and there exists a z ={(z0, z1)|(z0, z1)<J (y0, y1)} such that for any pair (z0, z1)∈ z, 〈Jα, ∈〉 ⊨ ¬φi(y0, y1, x). Since z is uniformly Δ1-definable for any admissible α, we have hα(i, x) to be uniformly Σ1-definable for any admissible α.

If α is admissible, we call the Σ1-Skolem function hα the canonical Σ1-Skolem function for α.

Proposition 3.3.12. If α > ω is admissible, then α ≥ .

Proof. Suppose α is admissible and ω < . By Theorem 3.3.6, Lα is admissible. By Theorem 1.3.4, there is a recursive function f such that for each n ∈ , Wf(n) = {〈i, j〉| i <o j <o n}. Fix a number n ∈ with |n|= α. Then the order type of Wf(n) is α and Wf(n) ∈ Lω+1 ⊆ Lα by Theorem 3.2.5. By Σ-induction there is a Σ1 order-preserving bijection g : Wf(n) → α. Since Wf(n) ∈ Lα, α ∈ Lα by the admissibility of α. This is a contradiction.

3.3.3 Exercises

Exercise 3.3.1. Prove that 〈Lω1, ∈〉 ⊨ KP + “V = L”.

Exercise 3.3.2. Prove Corollary 3.3.8.

Exercise 3.3.3 (Putnam [115]). Prove that for any countable ordinal α, there is a countable ordinal β such that Lβ+α Lβ ∩ 2ω =0.

3.4 Projecta and master codes

In the interest of keeping the chapter within reasonable length and the proofs simpler, we present weaker versions of results in Jensen [55]. Nevertheless, the key ideas are extracted from [55] and the results are sufficient for recursion-theoretic applications.

3.4.1 Projecta

Definition 3.4.1. Let α > 0 and n ≥ 1. The Σn-projectum , of α is the least ordinal ρ for which there is a Σn(Jα)-definable function f mapping a subset of Jρ onto Jα

Clearly exists for any n ≥ 1. One may replace Jρ with ωρ in the above definition. To prove this, we need the following lemma whose proof is left to the reader:

Lemma 3.4.2. Let α > 0. For each 1 ≤ γ ≤ ωα, there is a Σ1(Jα)-definable bijection between ωα and γ × ωα.

Proposition 3.4.3. Let α > 0. There Is A Σ1(Jα)-definable function from ωα onto Jα.

Proof. Let f0 = (f 0, f 1) be a bijection between ωα and (ωα)2 guaranteed by Lemma 3.4.2 (setting γ = ωα) defined via the <Jα -least parameter p ∈ Jα). Define fn+1(γ)= (f 0(γ), fn(f 1(γ))) for γ < ωα. It is easy to verify that fn is Σ1(Jα)-definable with parameter p and is a bijection between ωα and (ωα)n+2. Let hα be the canonical Σ1-Skolem function for Jα. Set X = hα(ω ×(ωα ×{p})). Note that for each n < ω and γ < ωα, there is an in such that fn(γ)= hα(in, (γ, p)). Thus γ ∈ X for every γ < ωα.

By Proposition 3.3.10, 〈X, ∈〉 ≺Σ1 〈Jα, ∈〉. By Theorem 3.3.7, there is a β ≤ α and an isomorphism π : 〈X, ∈〉 ≅ 〈Jβ, ∈〉. Moreover, π(p) ≤Jα p. Since γ ∈ X for every γ < ωα, we have β = α and π(γ)= γ for every γ < ωα. Hence π−1 : 〈Jα, ∈〉 ≺Σ1 〈Jα, ∈〉 and π−1(f0)= f0. Thus f0 is also defined by π(p) in 〈Jα, ∈〉. By the assumption on p, p ≤Jα π(p) and so p = π(p). Then for any x ∈ X, there are i < ω and γ < ωα such that

x = hα(i, (γ, p)) = hα(π(i), (π(γ), π(p))) = π(x),

implying that X = Jα.

Note that hα is not necessarily total. Let φ(u, v, w, s) be a Σ0-formula such that hα(i, γ, p)= x if and only if 〈Jα, ∈〉 ⊨ (∃y)φ(i, γ, p, y). Then by the proof of Proposition 3.3.11, there is a total Σ1-function

Let h(γ)= hʹ(f1(γ)) for γ < ωα.

Applying Proposition 3.4.3, we have:

Proposition 3.4.4. α is admissible if and only if there is no Σ1(Jα)-definable function mapping a γ < ωα onto ωα.

The next lemma is a characterization of .

Lemma 3.4.5. Suppose that α > 0 and ρ = . Then A ∈ Jρ for any γ < ρ and any Σ1(Jα)-definable A ⊆ Jγ.

Proof. If ρ = 1 then the conclusion is immediate. Suppose ρ > 1. Then ρ is a limit ordinal. Let γ < ρ and A ⊆ Jγ. Let hα be the canonical Σ1-Skolem function for Jα. Fix p ∈ Jα such that A is Σ1(Jα)-definable with parameter p. Let X = hα(ω×(Jγ×{p})). Then 〈X, ∈〉 ≺Σ1 〈Jα, ∈〉. By Theorem 3.3.7, there is a β ≤ α such that π : 〈X, ∈〉 ≅ 〈Jβ, ∈〉 is an isomorphism. Note that π(x)= x for all x ∈ Jγ since Jγ is transitive. Hence π(x)= x for x ∈ A. Thus A is also Σ1-definable in Jβ with parameter π(p)∈ Jβ. We claim that β < ρ. Otherwise, let f be Σ1(Jα) mapping a subset of Jρ onto Jα. Then f ∘ π ∘ hα is Σ1(Jα) and maps a subset of ω ×(Jγ ×{p}) onto Jα. But ω × Jγ ∈ Jγ+2 ∈ Jρ, and so it maps a subset of Jγ+2 onto Jα, contradicting the choice of ρ.

Lemma 3.4.6. Let α > 0 and ρ = . Then there is an A ⊆ Jρ which is Σ1(Jα)-definable and A ∉ Jα.

Proof. Let f be Σ1(Jα)-definable mapping a subset of Jρ onto Jα. Then the domain of f restricted to Jρ is Σ1(Jα) and not an element of Jα by admissibility.

Lemma 3.4.5 and Lemma 3.4.6 yield the following characterization of :

Theorem 3.4.7. Let α > 0. Then is the least ordinal ρ for which there is a Σ1(Jα) set A ⊆ Jρ not in Jα.

Now suppose that x ⊆ ω is Σ1(Jα)-definable with parameter p and x ∉ Jα. Let X = hα(ω ×(J1 ×{p}))). We may identify ω × J1 with J1. Hence X = h(J1 ×{p})) for some Σ1-function h. Then 〈X, ∈〉 ≺Σ1 〈Jα, ∈〉. By transitive collapse there is a β ≤ α such that π : 〈X, ∈〉 ≅ 〈Jβ, ∈〉. Since x ⊆ J1, π(n)= n for all n ∈ ω. Thus x is Σ1(Jβ)-definable with parameter π(p). If β < α, then x ∈ Jα which is a contradiction. Thus β = α. Now π is Σ1(Jα)-definable and so π ∘ h is Σ1(Jα)-definable and maps a set y ⊆ J1 onto Jα. Since J1 = HF, by Proposition 3.2.6, we may assume that y is a real. Hence for any admissible α, if Jα+1 Jα contains a Σ1(Jα)-definable real, then it contains a real “coding Jα”.

Remark 3.4.8. Theorem 3.4.7 remains valid for n ≥ 1. However, the proof requires more than a straightforward generalization of what was presented above. The major difficulty is that there is no canonical Σn-Skolem function for n ≥ 2. To overcome this difficulty, a finer analysis of Jα is introduced. See Jensen [55] for details.

3.4.2 Master codes

Definition 3.4.9. Given an ordinal α and n ≥ 0, a Σn-master code for Jα is a Σn(Jα)-definable set A ⊆ such that for any m ≥ 1, any set B ⊆ , that is Σn+m(Jα)-definable is Σm-definable in 〈, ∈, A〉.

There is an interpretation of the notion of a master code in the context of recursion theory. First suppose α = 1 and hence = 1. Then Jα = Jρ = HF. Let A ⊆ HF be a Σ1-master code. By Proposition 3.2.6, there is a real x such that x is Δ1-definable in 〈HF, ∈, A〉 and A is Δ1-definable in 〈HF, ∈, x〉. By Theorem 3.2.5, every Σ1-definable real in 〈HF, ∈, x〉 is r.e. in x. Hence every real Σ2-definable in 〈HF, ∈〉 is Σ1-definable in 〈HF, ∈, A〉 and so r.e. in x. Thus the Σ1-master codes are precisely the reals that are r.e. and complete (hence Turing equivalent to ʹ). In general, a real which is a Σn-master code in 〈J1, ∈〉 is Σn-complete and hence Turing equivalent to (n). We may therefore consider master codes to be Turing jumps in the set-theoretic sense. Second, suppose that = 1. A Σ1-master code for 〈Jα, ∈〉 is a set A ⊆ HF such that every Σ2(Jα)-definable real is Σ1 in 〈HF, ∈, A〉. Again by Proposition 3.2.6 and Theorem 3.2.5, every Σ2(Jα)-definable real is r.e. in some real x which is Σ1(Jα)-definable. In particular, every real z ∈ Jα is recursive in x. Thus if α is much larger than , the real x must be remarkably strong in computational power. Historically, the notion of a master code for ρ = 1 was first introduced by Boolos and Putnam [8] when they studied the Turing degrees of reals in the constructible universe. We now show that Σ1-master codes exist for any admissible ordinal α.

Theorem 3.4.10. Let α > 0. There is a Σ1-master code for 〈Jα, ∈〉, i.e. a Σ1(Jα)-definable A ⊆ such that for any B ⊆ if B is Σm+1(Jα)-definable, then it is Σm-definable in 〈, ∈, A〉.

Proof. We only prove the case m = 1 for simplicity. Suppose that f is Σ1(Jα)-definable with parameter p mapping a subset of onto α. Fix a Δ1-enumeration {φi(x, p)}i<ω of Σ1-formulas with parameter p. Let

It is obvious that A is Σ1-definable over 〈Jα, ∈〉. Now suppose that B ⊆ is Σ2-definable over 〈Jα, ∈〉. Then there is a Σ1(Jα)-formula φ(u, v, w) such that

where s is a parameter in Jα. Since f is onto, there is an s0 ∈ such that f(s0)= s.

Then

Since f is Σ1(Jα)-definable with parameter p, there is an index i such that for x, y ∈

Thus

Hence B is Σ1-definable over 〈, ∈, A〉.

As an example, ʹ is a Σ1(J1)-master code since it satisfies the property described in Theorem 3.4.10. Jensen [55] proved the following general result:

Theorem 3.4.11. For any ordinal α > 0 and n > 0, there is a Σn(Jα)-master code A ⊂ . Moreover, is the least ordinal γ for which there is a Σn(Jα) A ⊆ ωγ not in Jα.

A Σn-master code corresponds to (n) in recursion theory. The equality (n+m) =(n)(m) has a natural analog in fine structure theory. See [55] for details.

3.4.3 Exercises

Exercise 3.4.1. Prove Lemma 3.4.2.

Exercise 3.4.2. Prove Proposition 3.4.4.

Exercise 3.4.3. Prove that there is a countable admissible ordinal α > ωsuch that = α.

3.5 ω-models

Definition 3.5.1. A structure is an ω-model if ωM = ω.

ω-models are widely used in recursion theory and descriptive set theory. A major point of interest in an ω-model is its standard part.

Definition 3.5.2. Let =〈M, E〉 be a structure and M1 ⊆ M. Then M1 is E-closed if for every x ∈ M1, yEx and y ∈ M implies y ∈ M1. The standard part of is the maximal E-closed wellfounded subset of M.

Obviously if M1 ⊆ M is E-closed, then for any Σ0-formula φ(v) and x ∈ M1, 〈M, E〉 ⊨ φ(x) if and only if 〈M1, E〉 ⊨ φ(x).

Lemma 3.5.3. Suppose that ⊨ KP. Then x belongs to the standard part of M if and only if rk(x), the rank of x, belongs to the standard part of .

Proof. Since ⊨ KP, by the Σ-induction Theorem (3.1.8) the rank function rk is Δ1-definable.

If x belongs to the standard part of M, then by induction on the rank of x, it is straightforward to verify that rk(x) also belongs to the standard part.

If x does not belong to the standard part of M, then there is a descending sequence {xn}n<ω in M so that xn+1Exn for every n and x0Ex. Then rk(xn+1)Erk(xn) for every n and rk(x0)Erk(x). So rk(x) does not belong to the standard part of M either.

Lemma 3.5.4. Suppose that ⊨ KP and M1 ⊆ M is the standard part of M. Then 〈M1, E〉 ⊨ KP.

Proof. Since M1 ⊆ M is E-closed, the extensionality axiom holds in 1 =〈M1, E〉. 1 satisfies the foundation axiom since M1 is the standard part of M. Similarly it is straightforward to verify that pairing, union and the Δ0-comprehension axioms hold in 1. We prove 1 ⊨ Δ0-collection.

Suppose that φ(u, v) is a Δ0-formula and a ∈ M1 such that

〈M1, E〉⊨(∀xEa)(∃y)φ(x, y).

Since φ(u, v) is Δ0 and M1 is an E-closed subset of M, we have

〈M, E〉⊨(∀xEa)(∃y)φ(x, y).

Now 〈M, E〉 ⊨ KP implies that there is a b ∈ M such that

〈M, E〉⊨(∀xEa)(∃yEb)φ(x, y).

By Lemma 3.5.3, there is a b0 such that rk(b0)= α0 is the least ordinal in to satisfy the collection axiom for φ. If α0 ∈ M1, then by Lemma 3.5.3, b0 ∈ M1 and we are done. Otherwise, α0 ∈ M M1. But then there is a nonstandard α1Eα0 such that for every xEa, there is a yEb0 in M1 with rk(y)Eα1 and 〈M, E〉 ⊨ φ(x, y). Note that φ(x, y)∧ rk(y)Eα1 is a Σ-formula and

〈M, E〉⊨(∀xEa)(∃y)(φ(x, y)∧ rk(y)Eα1).

By the Σ-collection Theorem (3.1.6), there is a b1 ∈ M such that

〈M, E〉⊨(∀xEa)(∃yEb1)φ(x, y)∧ rk(y)Eα1).

Define

c ={y | yEb1 ∧〈M, E〉 ⊨ rk(y)Eα1 ∧∃xEa(φ(x, y))}.

By Theorem 3.1.6, c ∈ M.

Then rk(c)Eα0 and α0 = rk(b0). Since α0 is the least ordinal in to satisfy the collection axiom for φ, we have a contradiction.

Proposition 3.5.5. Let ⊨ KP be an ω-model. Then .

Proof. Let M1 ⊆ M be the standard part of M. By Lemma 3.5.4, 〈M1, E〉 ⊨ KP. Hence 〈M1, E〉 is also an ω-model of KP. Since ω∪{ω}⊆ M1, by Δ0-separation every recursive set belongs to 〈M1, E〉. By Σ-induction, ⊆ M1. Let π : 〈M1, E〉→〈N, ∈〉 be the collapsing map. Then 〈N, ∈〉 is admissible so that ⊆ N. By Theorem 3.3.4, ⊆ N. We prove by induction on β < that π−1 ↾ is the identity map.

Note that by Proposition 3.3.3 there exists a Δ1-formula φ(u, v) such that for any ordinal β < , 〈N, ∈〉 ⊨ φ(β, x) if and only if x = Jβ. Moreover,

〈N, ∈〉 ⊨ φ(β, Jβ)∧(∀x ∈ Jβ)(∃γ ∈ β)(∃y)(x ∈ y ∧ φ(γ, y)).

We prove by induction that π−1(Jγ)= Jγ for every γ < .

Since ⊆ M1, we have π(β)= β for any β < . Thus π(x)= x for x ∈ J1. Since 〈N, ∈〉 ⊨ φ(1, x) if and only if x = J1, we have 〈M1, E〉 ⊨ φ(1, x) if and only if x = J1. So π−1(J1)= J1.

For a successor ordinal β + 1. π clearly preserves the Gödel primitive recursive operators. Hence Range(π−1 ↾ Jβ+1)= Jβ+1. Since 〈N, ∈〉 ⊨ φ(β + 1, x) if and only if x = Jβ+1, we have 〈M1, E〉 ⊨ φ(β + 1, x) if and only if x = Jβ+1. So π−1(Jβ+1)= Jβ+1.

Now suppose β < is a limit ordinal. By induction, if γ < β then 〈M1, E〉 ⊨ φ(γ, x) if and only if x = Jγ. Let z = π−1(Jβ). Since π−1(β)= β, we have

〈M1, E〉 ⊨ φ(β, z)∧(∀xEz)(∃γEβ)(∃y(xEy)∧ φ(γ, y)).

Thus z = Jβ. By the transitivity of , we conclude that π−1 ↾ is the identity map so that ⊆ M

3.5.1 Exercise

Exercise 3.5.1. Prove that if 〈M, E〉 ⊨ KP is a nonstandard ω-model, then for any nonstandard ordinal α ∈ M, there is a set A ⊆ {β | 〈M, E〉 ⊨ βEα} such that (, <) is isomorphic to 〈A, E〉, where is the set of rational numbers.

3.6 Coding structures

The method of coding a language or a structure by a set of natural numbers was introduced by Gödel in the proof of the Incompleteness Theorem. Coding is widely used today in mathematical logic. In this section, we will not discuss the formalism of coding. Instead, we present a general description of how the method works.

3.6.1 Coding a language

Given a countable language , there are many ways of coding it by a set of numbers. What we want is a “nice” coding scheme. In many cases, one may code a language by a recursive set ⊆ ω. A language that may be thus coded is called a recursive language. For example, both the first order language of arithmetic and the language of Zermelo–Fraenkel set theory are recursive. Moreover, in a recursive language, the set of well-formed formulas and the set of sentences are recursive. We may effectively associate each formula φ with its Gödel number ⌜φ⌝. We say that a theory T is recursive if its corresponding set of Gödel numbers is recursive. The theories considered in this book, such as KP, ZFC, are recursive.

Under coding with Gödel numbers, a proof sequence is identified with a finite sequence of numbers, and may therefore be considered as a finite subset of ω. Moreover, if both and T are recursive, then so is the set of proofs in T. It follows that the set of sentences which are theorems of T is r.e.

3.6.2 Coding a structure

Given a recursive language , one may associate with it a recursive set and code a countable structure in by the set of natural numbers ω with relations in defined over ω, so that the resulting structure is isomorphic to the original structure. If = 〈M, R0, …, Rn〉 is countable, a coding of is a structure such that ≅ . If all the relations are recursive, then the structure is said to be recursive. However, very few structures are recursive.

Let be a recursive language and a structure coded by . For a formula ̂φ(u) in corresponding to the formula φ(u) in , we may compute the complexity of the set . The procedure to calculate the complexity goes as follows: Recursively decode to obtain the formula φ(u). Then the complexity of A is the complexity of φ(u). For example, suppose is the language of set theory and corresponds to the formula φ(w): (∀u)(∀v)(u ∈ v ∧ v ∈ w → u ∈ w) (“w is transitive”). Then the set

is .

In general, given a language with relation symbols R0,…, Rn, a structure and a formula φ ∈ , the set {m ∈ ω | ⊨ ̂φ(m)} is arithmetical in ̂R0 ⊕ … ⊕ ̂Rn. Moreover, this calculation is uniform. Hence if {φi}i<ω is recursive, then the set {(i, m)| ⊨ ̂φi(m)} is Turing computable in ( ̂R0 ⊕ … ⊕ ̂Rn)(ω) via an algorithm with index e. In particular, there is an e such that if {φi}i<ω is a recursive set of sentences, then ⊨ ̂φi if and only if Φ(̂R0⊕…⊕ ̂Rn)(ω) (i)= 1. As a consequence, we have the following:

Proposition 3.6.1. Given a recursive theory T, the set {|(∀φ)(φ ∈ T ⇒ ⊨ ̂φ)} is .

For example, {| ⊨ KP + “V = L”} is (where for simplicity we make no distinction between KP+“V = L” and the corresponding sentences interpreted in ).