A version of the Jensen – Johnsbråten coding at arbitraly level n ≥ 3

Vladimir Kanovei ^{∗}^{†}^{‡}

December 1997

Abstract

Theorem 1 Let n ≥ 2. There is a CCC (in L ) forcing notion P = P_{n} ∈ L such that P -generic extensions of L are of the form L[a], where a ⊆ ω and

(A) a is Δ_{n+1}^{1} in L[a] ;

(B) if b ∈ L[a], b ⊆ ω is Σ_{n}^{1} in L[a] then b ∈ L and b is Σ_{n}^{1} in L .

In addition, if a model ℳ extends L and contains two different P -generic sets

a, a′ ⊆ ω, then ωℳ_{1} > ω_{1}^{L} .

For n = 2, this is the result of Jensen and Johnsbråten [4] (in this case, (B) is a corollary of the Shoenfield absoluteness theorem).

In the absense of the additional requirement, the result was proved by Harrington [1] (using a version of the almost disjoint coding of Jensen and Solovay [3]) and, independently, by the author [5, 6] (using a version of the Jensen “minimal Δ_{3}^{1} ” coding [2]). Our proof is a similar modification of the construction in [4].

Recall that the forcing notion in [4] is the union of a certain increasing ω_{1}- sequence of its countable initial segments. We choose another such a sequence, which is more complicated (leading to a ∈ Δ_{n+1}^{1} instead of a ∈ Δ_{3}^{1} in L[a] ), but bears an appropriate amount of “symmetry”, sufficient for (B).

Acknowledgements I am thankful to Peter Koepke and other members of the Bonn set theoretic group for useful discussions and hospitality during my stay at Bonn in Fall 1997.

∗ Moscow Transport Engineering Institute

† kanovei@math.uni-wuppertal.de and kanovei@mech.math.msu.su

‡ Partially supported by MPI (Bonn) in Fall 1997.

1 Preliminaries

By a normal tree we shall understand a tree T, which consists of sequences (so

normal tree

that every t ∈ T is a function with dom t ∈ Ord and the order <_{T} is the extension order ⊂) and satisfies conditions i) – iv):

i) the empty sequence Λ does not belong to T ; Λ

ii) if t ∈ T and 1 ≤ α < dom t then t↾α ∈ T .

Let |t| = dom t for any sequence t. It follows from i), ii) that, for any α ≥ 1, |t| T (α) = {t ∈ T : |t| = α} is just the α-th level of T. (We start counting levels with level 1; the missed, for the sake of convenience, level 0 would consist of Λ .)

Let |T | be the least ordinal > 0 and > all |t|, t ∈ T (the height of T ). |T | For α < |T |, let T ↾_{<α} = ⋃_{γ<α} T (γ) (the restriction).

T ↾_{<α}

iii) each non-maximal t ∈ T has \underline{infinitely many} immediate successors;

iv) each level T (α) is at most countable.

Let 1 ≤ λ ≤ ω_{1}. A normal λ-tree is a normal tree T satisfying

normal ; λ-tree

v) |T | = λ, and, if t ∈ T and |t| < α < λ then t has successors in T (α) .

(Thus the only normal 1-tree is the empty tree. Normal 0-trees do not exist.)

1.1 Iterated sequence of Souslin trees

We are going to define, in L, a sequence of normal ω_{1}-trees T_{n}, and, for all n and T_{n}, T_{(t)} t ∈ T_{n}, a subtree T_{(t)} ⊆ T_{n+1}, satisfying the following requirements (1) through (8), and some extra conditions, to be formulated later.

Fix once and for all a recursive partition ℚ^{+} = ⋃_{n} Q_{n} of the set ℚ^{+} of all Q_{n} positive rationals onto countably many countable topologically dense sets Q_{n}.

(1) T_{n}(α) ⊆ (ℚ^{+})^{α} for all n and 1 ≤ α < ω_{1} .

(2) T_{n}(1) = {⟨q⟩ : q ∈ Q_{n}} for all n.

(3) If t ∈ T_{n}(α) and q ∈ ℚ^{+} then t^{∧}q ∈ T_{n}(α + 1) .

( t^{∧}q denotes the extension of a sequence t by q as the rightmost term.) Thus t^{∧}q any element t ∈ T_{n}(α) is a sequence t = ⟨t_{γ}⟩_{γ<α} of positive rationals, and the trees T_{n} do not intersect each other.

(4) If t ∈ T_{n}(α) then T_{(t)} ⊆ T_{n+1} is a normal α-tree, and T_{n+1} = ⋃_{t∈T_{n}} T_{(t)} .

(5) If t, t_{1} ∈ T_{n} and t < t_{1} then T_{(t)} = T_{(t_{1})}↾_{<|t|}.

(6) Suppose that t ∈ T_{n}(α), α ≥ 1, and q_{1} ≠ q_{2} ∈ ℚ^{+}. Then T_{(t_{1})} ∩T_{(t_{2})} = T_{(t)} .

We observe that T_{(t)} = ∅ whenever t ∈ T_{n}(1) .

It follows that for any s ∈ T_{n+1}(α) (here α ≥ 1 ) there is unique s ∈ T_{n}(α +1) such that s ∈ T_{(t)}. This t will be denoted by t = 𝔣(s). We have 𝔣

⟨∗⟩ if t, t′ ∈ T_{n+1} and t ⊂ t′ then 𝔣(t) ⊂ 𝔣(t′) .

The next requirement will imply that every T_{n} is a Souslin tree in L .

(7) Suppose that λ < ω_{1} is a limit ordinal. Let ϑ < ω_{1} be the least ordinal such that L_{ϑ} models ZFC^{−} (minus the power set axiom), λ is countable in L_{ϑ}, and both the sequence ⟨T_{n}↾_{<λ}⟩_{n∈ω} and the map which sends every t ∈ ⋃_{n} T_{n}↾_{<λ} to T_{(t)} belong to L_{ϑ}. We require that every t ∈ T_{n}(λ) satisfies ∃ s ∈ D (s ⊂ t) whenever D ∈ L_{ϑ} is a pre-dense subset of T_{n}↾_{<λ}.

1.2 Coding idea of the construction of Jensen and Johnsbråten

Now suppose that, in a generic extension of L, for n ∈ ω, C_{n} is a branch in T_{n}, so that C_{n} ∈ (ℚ^{+})^{ω_{1}} and C_{n}↾α ∈ T_{n} for all 1 ≤ α < ω_{1}. Suppose further that

⟨†⟩ 𝔣(C_{n+1}↾α) ⊂ C_{n} for all n ∈ ω and 1 ≤ α < ω_{1}, or, in other words, if 1 ≤ α < ω_{1} then C_{n+1}↾α ∈ T_{(C_{n} ↾(α+1))}.

In this case there is a straightforward procedure of “decoding” the branches C_{n} from the sequence ⟨q_{n}⟩_{n∈ω} ∈ (ℚ^{+})^{ω}, where q_{n} = C_{n}(0) ∈ ℚ^{+} :

⟨‡⟩ We begin with the values C_{n}↾1 = ⟨q_{n}⟩, put C_{n}↾α + 1 = 𝔣(C_{n+1}↾α) (by induction on α simultaneously for all n), and take unions at all limit steps.

Thus ⟨C_{n}⟩_{n∈ω} is constructible from ⟨q_{n}⟩_{n∈ω}!

We are going to define such an extension of the universe, in which there exists only one sequence q⃗ = ⟨q_{n}⟩_{n∈ω} ∈ (ℚ^{+})^{ω} for which the procedure “converges” in the sense that C_{n}↾α is an extension of C_{n}↾β whenever 1 ≤ β < α < ω_{1}. Note that the meaning the “convergence” is

⟨§⟩ First, every q_{n} must be the 1st term of the 2-term sequence 𝔣(⟨q_{n+1}⟩). Second, the unions at limit steps, in the inductive computation of C_{n}↾α, must remain in the trees T_{n}.

1.3 The uniqueness in the construction of Jensen and Johnsbråten

The principal idea of [4] is to arrange things so that in any extension of L, if there are two different sequences of rationals for which the procedure ⟨‡⟩ “converges” then ω_{1}^{L} < ω_{1}. Technically, the collapse will be realised in the form of an increasing ω_{1}^{L}-sequence of rationals.

Assume that {q_{γ}}_{γ<α} is a sequence of non-negative rationals. Set ∑_{γ<α} q_{γ} to be the supremum of finite partial sums (including the case of +∞).

If s, t ∈ T_{n}(α) then define ∑(s, t) = ∑_{γ<α} |s_{γ} − t_{γ}|. We require the following: ∑(s, t)

(8) Suppose that T is T_{0} or T_{(t)} for some t ∈ T_{n} ( n ∈ ω), α < λ < |T |, λ is limit, and s, t ∈ T (λ). Then ∑(s↾α, t↾α) < ∑(s, t) < +∞.

(It can be easily shown that there must be s ∈ T_{0} – as well as in any T_{n} – satisfying ∑ s = ∞, so that some “series” diverge to infinity. However by (8) they diverge in “almost parallel” fascion.)

1.4 The “limit” generic extension

To summarize the consideration, suppose that, in L, we have a system 𝔗 = 𝔗 ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ satisfying (1) – (8) in L .

Define 𝔣 as above. 𝔣 Define ℙ_{𝔗} = lim T_{n} to be the “limit” of the sequence, that is, the set of all

“tuples” t⃗ = ⟨t_{0}, …, t_{n}⟩, where n ∈ ω, and t_{i} ∈ T_{i} and t_{i} = 𝔣(t_{i+1}) for all i ≤ n. ℙ_{𝔗} = lim T_{n} We order ℙ_{𝔗} as follows: t⃗ = ⟨t_{0}, …, t_{n}⟩ ≤ s⃗ = ⟨s_{0}, …, s_{m}⟩ ( s⃗ is stronger than t⃗) iff n ≤ m and t_{i} ⊂ s_{i} in T_{i} for all i.

Theorem 2 [4] 1) ℙ_{𝔗} is a CCC forcing in L. Each T_{n} is a Souslin tree in L .

2) In a ℙ_{𝔗}-generic extension of L, there is a sequence ⟨q_{n}⟩_{n∈ω} ∈ (ℚ^{+})^{ω} for

which the procedure ⟨‡⟩ “converges” in the sense of ⟨§⟩.

3) In any extension of L, if there are two different sequences ⟨q_{n}⟩_{n∈ω} for which the procedure ⟨‡⟩ “converges” in the sense of ⟨§⟩, then ω_{1}^{L} is countable.

Proof 1) Follow classical patterns, with the help of (7).

2) It is clear that any ℙ_{𝔗}-generic extension of L has the form L[⟨C_{n}⟩_{n∈ω}], where C_{n} = ⋃_{⟨t_{0},...,t_{n}⟩∈ℙ_{𝔗}} t_{n} is an ω_{1}^{L}-branch in T_{n}. Moreover, the branches C_{n} C_{n} satisfy ⟨†⟩, hence each C_{n+1} is a branch in the subtree ^{∗}T_{n+1} = ⋃_{1≤α<ω_{1}} T_{(C_{n} ↾α)} ∈ L[C_{n}] of T_{n}. (By the way C_{n} ∈ L[C_{n+1}] because C_{n} = ⋃_{α<ω_{1}^{L}} 𝔣(C_{n+1}↾α) by ⟨†⟩.) ^{∗}T_{n}

Now the procedure ⟨‡⟩ “converges” (just to the chains C_{n}) for the sequence of the rationals q_{n} = C_{n}(0) . q_{n}

3) Suppose that ⟨q_{n}⟩_{n∈ω} and ⟨q′_{n}⟩_{n∈ω} are two different sequences of positive

q_{n}, q′_{n}

rationals for which the procedure ⟨‡⟩ “converges”, to resp. branches C_{n} and C′_{n}

C_{n}, C′_{n}

in T_{n} ( n ∈ ω). Now either C_{0} ≠ C′_{0} or there is n such that C_{n+1} ≠ C′_{n+1} but C_{k} = C′_{k} for all k ≤ n. (Otherwise q_{n} = q′_{n} for all n.)

In the “either” case C_{0} and C′_{0} are two different branches in T_{0}, which implies, by (8), that there exists a strictly increasing ω_{1}^{L}-sequence of rationals, namely the sequence of sums ∑(C_{0}↾α, C′_{0}↾α), α < ω_{1}^{L}, hence ω_{1}^{L} is countable.

Consider the “or” case. Define the subtrees ^{∗}T_{k+1} = ⋃_{α<ω_{1}} T_{(C_{k} ↾α)} and ^{∗}T′_{k+1} = ⋃_{α<ω_{1}} T_{(C′_{k} ↾α)} of T_{k+1} for all k. Then ^{∗}T′_{k+1} = ^{∗}T_{k+1} for all k ≤ n, in particular, ^{∗}T_{n}, ^{∗}T′_{n} ∗T′_{n+1} = ^{∗}T_{n+1}. Thus C_{n+1} and C′_{n+1} are two different ω_{1}^{L}-branches in ^{∗}T_{n+1}, which, as above, implies that ω_{1}^{L} is countable. □

2 Construction of the trees

Let us now describe how a collection of trees and a map t ⟼ T_{(t)} satisfying (1) through (8) can be constructed in L .

The following requirement will facilitate the construction.

(9) Suppose that T = T_{0} or T = T_{(t)} for some t ∈ T_{n} and n ∈ ω. Let further r ∈ ℚ^{+}, t, t′ ∈ T (β), and s ∈ T (α), β < α < |T |, t ⊂ s. Then there exists s′ ∈ T (α) such that t′ ⊂ s′ and ∑(s, s′) − ∑(t, t′) < r.

This looks weaker than (9) in [4], but implies the latter by the triangle inequality.

Definition 3 An embrion of height λ ( λ ≤ ω_{1} ) is a system 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ of embrion normal λ-trees T_{n} and a map t ⟼ T_{(t)} which satisfy (1) through (8) of Section 1 plus (9) below λ.

An embrion 𝔗′ extends 𝔗, symbolically 𝔗 ⪯ 𝔗′, when λ ≤ λ′, T_{n} = T′_{n}↾_{<λ},

{extends \atop ⪯}

and T_{(·)} is the restriction of T′_{(·)} on ⋃_{n} T_{n}.

|𝔗| denotes the height of the embrion 𝔗. Emb is the set of all embrions of

|𝔗|

\underline{countable} height.

                                                                           Emb

If 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ is an embrion and λ < |𝔗| then we define the restriction 𝔗↾λ = ⟨⟨T_{n}↾_{<λ}⟩_{n∈ω}, T_{(·)}↾λ⟩, where T_{(·)}↾λ is the restriction of T_{(·)} on the domain 𝔗↾λ ⋃_{n} T_{n}↾_{<λ}. Obviously 𝔗↾λ is an embrion of height λ. □

Lemma 4 Let 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ be an embrion of a countable height λ. There is an embrion 𝔗′ = ⟨⟨T′_{n}⟩_{n∈ω}, T′_{(·)}⟩ of height λ + 1 extending 𝔗.

Proof ^{1} We have to define the levels T_{n}(λ), m ∈ ω, and extend the map t ⟼ T_{(t)} on ⋃_{n} T_{n}(λ). This depends on the form of the ordinal λ.

1 A brief form of the proof in [4].

Case 1 : λ is a limit ordinal. Note that possible elements of T_{n}(λ) are sequences s ∈ (ℚ^{+})^{λ} such that s↾α ∈ T_{n}(α) for all α < λ. So the problem is to choose countably many of them for any n.

Let ϑ be defined as in (7), and ℳ = L_{ϑ}. ϑ, ℳ Let us start with T_{0}(λ). Thus we have to define a countable set T_{0}(λ) = S ⊆

(ℚ^{+})^{λ} satisfying

(i) if s ∈ S and γ < λ then s↾γ ∈ T_{0}(γ) ;

(ii) if s ∈ S and D ∈ ℳ is a dense subset of T_{0} then ∃ γ < λ (s↾γ ∈ D) ;

(iii) if s, s′ ∈ S then ∑(s↾α, s′↾α) < ∑(s, s′) < +∞ for all α < λ;

(iv) if r ∈ ℚ^{+}, α < λ, t, t′ ∈ T_{0}(α), s ∈ S, and t ⊂ s, then there is s′ ∈ S such that t′ ⊂ s′ and ∑_{α}(s, s′) < r.

The construction can be carried out by a rather cumbersome forcing over ℳ, described in [4]. To present the idea but avoid most of technicalities, let us conduct a simpler construction. Namely, suppose that r ∈ ℚ^{+}, α < λ, t and t′ belong to T_{0}(α), and a sequence s ∈ (ℚ^{+})^{λ} satisfies t ⊂ s, (i), and (ii). Find a sequence s′ ∈ (ℚ^{+})^{λ} satisfying t′ ⊂ s′, (i), (ii), and ∑_{α}(s, s′) < r.

Since λ and ℳ are countable, the following is sufficient:

Claim Assume that ε ∈ ℚ^{+}, γ < λ, t ∈ T_{0}(γ), and D ∈ ℳ is dense in T_{0}. There exist an ordinal γ′, γ < γ′ < λ, and t′ ∈ T_{0}(γ′) ∩ D, such that t ⊂ t′ and ∑_{γ}(σ, t′) < ε, where σ = s↾γ′.

Proof The set D′ = {σ ∈ T_{0} : ∃ t′ ∈ T_{0} ∩ D [ t ⊆ t′ & |t′| = |σ| & ∑_{γ}(σ, t′) < ε]} belongs to ℳ and is dense in T_{0} by (9), therefore there is an ordinal γ′, γ < γ′ < λ, such that σ = s↾γ′ ∈ D′. ⊣

Now suppose that S_{n} = T_{n}(λ) has been defined, and define S_{n+1} = T_{n+1}(λ). S_{n}, S_{n+1} We assume that S_{n} satisfies (i) and (ii) (for T_{n} rather than T_{0}, of course).

Define T_{(s)} = ⋃_{γ<λ} T_{(s↾γ)} for all s ∈ S_{n}. Thus T_{(s)} is a subtree of T_{n}.

Claim If D ∈ ℳ is a dense subset of T_{n+1} then, for any s ∈ T_{n}(λ), the intersection D ∩ T_{(s)} is dense in T_{(s)} .

Proof Let us fix t_{0} ∈ T_{(s)}. Then |t| = γ < λ and σ_{0} = 𝔣(t_{0}) ∈ T_{n}(γ + 1). Now

D′ = {σ ∈ T_{n} : |σ| > γ & [ σ_{0} ⊆ σ ⟹ ∃ t ∈ T_{(σ)} (t ∈ D & t_{0} ⊆ t) ]}

belongs to ℳ and is dense in T_{n}, so σ = s↾γ′ ∈ D′ for some γ′ < λ. ⊣

This allows to define S_{n+1} as the union of separate parts, each part being defined within T_{(s)} for some s ∈ S_{n} in the same way as S = T′_{0}(λ) above.

This completes the definition of T′_{n}(λ) for all n and T_{(s)} for all s ∈ ⋃_{n} T′_{n}(λ) . Case 2 : 𝔗 is an embrion of height λ + 1, λ < ω_{1} still being a limit ordinal.

Thus T_{n}(λ) is defined (and is the maximal level in each T_{n}). Then T_{n}(λ + 1) = {s^{∧}q : s ∈ T_{n}(λ) & q ∈ ℚ^{+}} by (3), so the task is to define T_{(σ)} for σ ∈ T_{n}(λ+1) .

Let S_{n+1}^{t} = {s ∈ T_{n}(λ) : ∀ γ < λ (s↾γ ∈ T_{(t)})}. By the construction the tree T_{(t)} ∪ S_{n+1}^{t} is a normal (λ + 1)-tree satisfying (9). Moreover we can divide S_{n+1}^{t} onto countably many infinite pairwise disjoint parts, S_{n+1}^{t} = ⋃_{k} S_{n+1, k}^{t}, so that still each T_{(t)} ∪ S_{n+1, k}^{t} is a normal (λ + 1)-tree satisfying (9). Now fix a recursive enumeration ℚ^{+} = {q_{k} : k ∈ ω} and set T_{(t^{∧}q_{k})} = T_{(t)} ∪ S_{n+1, k}^{t} for all k.

enumera- ; tion q_{k}

Case 3 : 𝔗 is an embrion of height λ + j + 1, λ < ω_{1} being limit or 0, and j ≥ 1. Put T_{n}(λ + j + 1) = {s^{∧}q : s ∈ T_{n}(λ + j) & q ∈ ℚ^{+}}, as above. Now define T_{(σ)} for σ = s^{∧}q ∈ T_{n}(λ + j + 1). The tree T_{(s)} is a normal (λ + j)-tree, hence it has the maximal level T = T_{(s)}(λ + j − 1). Now set T_{(s^{∧}q_{k})} = T_{(s)} ∪ {t^{∧}q : t ∈ T & q ∈ Q_{k}} for all k, where Q_{k} are the sets introduced in Subsection 1.1. □

Note that there exists an embrion of height 2 : put T_{n}(1) = {⟨q⟩ : q ∈ Q_{n}} for all n, according to (2). (Obviously this is the only embrion of height 2.)

Corollary 5 [4] (assuming V = L ) There exists an increasing Δ_{1}^{HC} sequence ⟨𝔗_{α}⟩_{2≤α<ω_{1}} such that each 𝔗_{α} is an embrion of height α and 𝔗_{β} extends 𝔗_{α} whenever α < β < ω_{1} . □

Set T_{n} = ⋃_{2≤α<ω_{1}} T_{n}(α) for all n and define the map t ⟼ T_{(t)} accordingly. Then both the map T_{(·)} and the trees T_{n} uniformly on n belong to Δ_{1}^{HC}. Put 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ and define the forcing ℙ_{𝔗} as in Subsection 1.4.

Theorem 6 [4] Any ℙ_{𝔗}-generic extension of L has the form L[a], where a is a Δ_{3}^{1} real in L[a] .

Proof The extension has the form L[⟨C_{n}⟩_{n∈ω}, where each C_{n} is an ω_{1}^{L}-branch in T_{n}. Let q_{n} = C_{n}(0). Then, the sequence of positive rationals ⟨q_{n}⟩_{n∈ω} is, in the extension, the only sequence in (ℚ^{+})^{ω} such that the procedure ⟨‡⟩ “converges” in the sense of ⟨§⟩, by Theorem 2. It remains to demonstrate that the condition ⟨§⟩ can be expressed by a Π_{1} formula in HC. But this is rather clear: the formula says that any sequence of α < ω_{1}^{L} steps in the “procedure” ⟨‡⟩ starting from ⟨q_{n}⟩_{n} and satisfying ⟨§⟩ can be extended by one more step so that ⟨§⟩ is not violated. □

3 Proof of the theorem: part 1

Theorem 6 is equal to the main theorem (Theorem 1) for n = 2. The proof of the general case, presented in this section, follows the scheme of Jensen and Johnsbråten, but contains one more idea: the final ω_{1}-trees and the map T_{(·)} (or, what is equivalent, the increasing ω_{1}-sequence of embrions which generates the former) must be “generic” in a sense relevant to the level Δ_{n+1}^{1} : roughly, it will intersect all dense subsets in the collection Emb of all (countable) embrions.

3.1 Formulas

We argue in L .

Let 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ be an embrion of height λ < ω_{1}. Define and order ℙ_{𝔗} = lim T_{n} as in Subsection 1.4.

ℙ_{𝔗}

Let ℳ(𝔗) = L_{ϑ}, where ϑ < ω_{1}, as in (7), is the least ordinal such that L_{ϑ}

ℳ(𝔗)

models ZFC^{−}, λ is countable in L_{ϑ}, and 𝔗 ∈ L_{ϑ}. We observe that T ∈ ℳ(𝔗) .

Define Trm(𝔗) to be the set of all 𝔗-terms for subsets of ω, that is, all Trm(𝔗) countable sets τ ⊆ ℙ_{𝔗} × ω. Put Trm^{∗}(𝔗) = Trm(𝔗) ∩ ℳ(𝔗) .

Trm^{∗}(𝔗)

We use a special language to facilitate the study of analytic phenomena in T - generic extensions. Let L be the language containing variables l, m, i, j of type L 0 (for natural numbers) and x, y, z of type 1 (for subsets of ω), arithmetical predicates for type 0 and the membership i ∈ x.

Let a 𝔗-formula be a formula of L some (or all) free variables of which, of 𝔗-formula types 0 and 1, are substituted by resp. natural numbers and elements of Trm^{∗}(𝔗) .

If φ is a 𝔗-formula and G ⊆ ℙ_{𝔗} then φ[G] will denote the formula obtained φ[G] by substitution, in φ, of each term τ ∈ Trm^{∗}(𝔗) by the set τ[G] = {l ∈ ω : ∃ t⃗ ∈ G (⟨t⃗, l⟩ ∈ τ)}. Thus φ[G] is a formula of L containing subsets of ω as parameters.

Let 𝔗Σ_{∞}^{0}-formula be any 𝔗-formula which does not contain quantifiers over 𝔗Σ_{∞}^{0}-formula variables of type 1. Formulas of the form

∃ x_{1} ∀ x_{2} ∃ x_{3} … ∀ (∃) x_{k} ψ , ∀ x_{1} ∃ x_{2} ∀ x_{3} … ∃ (∀) x_{k} ψ , where ψ ∈ 𝔗Σ_{∞}^{0} ,

will be called resp. 𝔗Σ_{k}^{1}-formulas and 𝔗Π_{k}^{1}-formulas. 𝔗Σ_{k}^{1}-formula

𝔗Π_{k}^{1}-formula

3.2 “Approximations” of the forcing

We introduce the relation t⃗ forc_{𝔗} φ. Here it is assumed that 𝔗 ∈ Emb, t⃗ ∈ ℙ_{𝔗}, and φ is a closed 𝔗-formula of one of the classes 𝔗Σ_{k}^{1}, 𝔗Π_{k}^{1} . The definition goes on by induction on k.

(F1) If φ ∈ 𝔗Σ_{∞}^{0} ∪ 𝔗Σ_{1}^{1} ∪ 𝔗Π_{1}^{1} then t⃗ forc_{𝔗} φ iff ( 𝔗, t⃗, φ are as above and) t⃗ ||−_{𝔗} φ, where ||−_{𝔗} is the ordinary forcing in the sense of ℳ(𝔗) as the initial model and ℙ_{𝔗} as the notion of forcing.

(F2) Let k ≥ 1, φ(x) ∈ 𝔗Π_{k}^{1}. Define t⃗ forc_{𝔗} ∃ x φ(x), iff there is a term τ ∈ Trm^{∗}(𝔗) such that t⃗ forc_{𝔗} φ(τ) .

(F3) Let k ≥ 2, φ is a closed 𝔗Π_{k}^{1} formula. Put t⃗ forc_{𝔗} φ if ¬ s⃗ forc_{𝔖} φ^{−} for any countable embrion 𝔖 ∈ Emb which extends 𝔗 and any s⃗ ∈ ℙ_{𝔖}, s⃗ ≥ t⃗, where φ^{−} is the result of the transformation of ¬ φ to the 𝔗Σ_{k}^{1} form.

The following statements are true for the usual forcing, hence true for the relation forc restricted on formulas φ in 𝔗Σ_{∞}^{0} ∪ 𝔗Σ_{1}^{1} ∪ 𝔗Π_{1}^{1}, while the extension on more complicated formulas is easily carried out by induction.

(a) If t⃗ forc_{𝔗} φ and 𝔖 ∈ Emb extends 𝔗, s⃗ ∈ ℙ_{𝔖}, s⃗ ≥ t⃗, then s⃗ forc_{𝔖} φ.

(b) t⃗ forc_{𝔗} φ and t⃗ forc_{𝔗} φ^{−} are incompatible.

Now consider the complexity of the relation forc .

Suppose that φ(x_{1}, …, x_{m}, l_{1}, …, l_{μ}) is a parameter–free formula of L. Put

Forc(φ) = {⟨𝔗, t⃗, τ_{1}, …, τ_{m}, l_{1}, …, l_{μ}⟩ : 𝔗 ∈ Emb & τ_{1}, …, τ_{m} ∈ Trm^{∗}(𝔗) & t⃗ ∈ ℙ_{𝔗} & l_{1}, …, l_{μ} ∈ ω & t⃗ forc_{𝔗} φ(τ_{1}, …, τ_{m}, l_{1}, …, l_{μ})} .

Theorem 7 If φ is a formula of one of the classes Σ_{∞}^{0}, Σ_{1}^{1}, Π_{1}^{1}, then Forc(φ) ∈ Δ_{1}^{HC}. If k ≥ 2 and φ ∈ Π_{k}^{1}, then Forc(φ) ∈ Σ_{k−1}^{HC}. Esli k ≥ 2 i φ ∈ Σ_{k}^{1}, to Forc(φ) ∈ Π_{k−1}^{HC} .

Proof The result for φ ∈ Σ_{∞}^{0} ∪Σ_{1}^{1} ∪Π_{1}^{1} follows from the definability of the usual forcing ||−_{𝔗} in the model ℳ(𝔗), which is uniformly Δ_{1}^{HC}(𝔗). The induction step is clear. □

We now formulate a theorem which states that the relation t⃗ forc_{𝔗} φ actually does not depend on the choice of t⃗ and 𝔗, provided φ is a parameter–free formula.

Theorem 8 Let φ be a closed 𝔗Σ_{k}^{1}-formula, which does not contain parameters of type 1, 𝔗, 𝔗′ ∈ Emb, and t⃗ ∈ ℙ_{𝔗}, t⃗′ ∈ ℙ_{𝔗}′. Then t⃗ forc_{𝔗} φ is inconsistent with t⃗′ forc_{𝔗}′ φ^{−}.

The proof (see below) is based on a system of automorphisms of Emb .

3.3 Isomorphisms between the embrions

Suppose that 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ and 𝔗′ = ⟨⟨T′_{n}⟩_{n∈ω}, T′_{(·)}⟩ are two embrions, of equal heigth λ < ω_{1}. An isomorphism of 𝔗 onto 𝔗′ is a collection h = ⟨h_{n}⟩_{n∈ω}

isomorphism of embrions

of order isomorphisms h_{n} : T_{n} onto T′_{n} such that, for all n and t ∈ T_{n}, the map h_{n+1} restricted on T_{(t)} is an order isomorphism of T_{(t)} onto T′_{(h(t))} . ^{2}

In this case, if t⃗ = ⟨t_{0}, …, t_{n}⟩ ∈ ℙ_{𝔗} (so that t_{i} ∈ T_{i} and t_{i} = 𝔣(t_{i+1}) for all i), then we put ht⃗ = ⟨h_{0}(t_{0}), …, h_{n}(t_{m})⟩; then ht⃗ ∈ ℙ_{𝔗}′ . ht⃗

Let Isom(𝔗, 𝔗′) denote the set of all isomorphisms of 𝔗 onto 𝔗′. Isom(𝔗, 𝔗′)

Theorem 9 Suppose that λ < ω_{1} is a limit ordinal and 𝔗, 𝔗′ are embrions of

height λ + 1, t⃗ = ⟨t_{0}, …, t_{n}⟩ ∈ ℙ_{𝔗}, t⃗′ = ⟨t_{0}, …, t_{n}⟩ ∈ ℙ𝔗^{′}, and |t_{0}| = |t′_{0}|. (Then

|t_{k}| = |t′_{k}| = |t_{0}| − k for all k.) Then there is an isomorphism h ∈ Isom(𝔗, 𝔗′) such that ht⃗ = t⃗′.

Proof Let us define an order isomorphism h_{0} : T_{0} onto T′_{0} such that h_{0}(t_{0}) = t′_{0} . Fix σ_{0} ∈ T_{0}(λ) and σ′_{0} ∈ T′_{0}(λ) such that t_{0} ⊂ σ_{0} and t′_{0} ⊂ σ′_{0}. A function H will be called a correct map if dom H and ran H are subsets of correct map

(ℚ^{+})^{λ}, H is 1 − 1, and, for all s ≠ t ∈ dom H, if s′ = g(s) and t′ = g(t), then the maximal α < λ such that s↾α = t↾α is equal to the maximal α < λ such that s′↾α = t′↾α.

Since all elements of T and T′, except for those of the maximal levels T (λ) and T′(λ), have infinitely (countably) many successors, there is a correct map g : T (λ) onto T′(λ) such that H(σ_{0}) = σ′_{0}. Set h_{0}(t) = g(t) for t ∈ T_{0}(λ). If s ∈ T_{0}↾_{<λ} then pick any t ∈ T_{0}(λ) satisfying s ⊂ t, and put h_{0}(s) = g(t)↾|s|.

Let us demonstrate how to get h_{1} .

We observe that, for any t ∈ T_{0}(λ), S_{t} = T_{(t)} is a normal λ-tree, a subtree of T_{1}↾_{<λ}. Let L_{t} = \{t_{1} ∈ T_{1}(λ) : ∀ α < λ (t_{1}↾α ∈ S_{t})\}. Then \overline{S}_{t} = S_{t} ∪ L_{t} is normal (λ + 1)-tree, a subtree of T_{1}, having L_{t} as its λ-th (and the upper) level, and T_{1}(λ) is a pairwise disjoint union of L_{t}.

Using the same construction, we define S′_{t′}, L′_{t′}, \overline{S′}_{t′} for all t′ ∈ T′_{0}(λ). Then, similarly to the case of T_{0} and T′_{0} above, we cad define a correct map g : T_{1}(λ) onto T′_{1}(λ) which maps each \overline{S}_{t} onto \overline{S′}_{h_{0}(t)}. This leads to an order isomorphism h_{1} : T_{1} onto T′_{1}, as above. A separate point is to guarantee that h_{1}(t_{1}) = t′_{1}. Pick σ_{1} ∈ L_{σ_{0}} and σ′_{1} ∈ L′_{σ′_{0}} so that t_{1} ⊂ σ_{1} and t′_{1} ⊂ σ′_{1}. Now it suffices to arrange the action of g on L_{t} so that g(σ_{1}) = σ′_{1} .

The same argument allows to obtain, by induction, all other order isomorphisms h_{n} : T_{n} onto T′_{n} satisfying h_{n}(t_{n}) = t′_{n}. □

2 The definition contains nothing to match the “metric” properties (8) and (9).

3.4 Extensions of isomorphisms on higher embrions

Let 𝔗 = ⟨⟨T_{n}⟩_{n∈ω}, T_{(·)}⟩ and 𝔗′ = ⟨⟨T′_{n}⟩_{n∈ω}, T′_{(·)}⟩ be embrions of one and the same height η + 1, η < ω_{1}, and h = ⟨h_{n}⟩_{n∈ω} ∈ Isom(𝔗, 𝔗′) . η

In this case, the action of h can be correctly defined for any embrion 𝔖 = ⟨⟨S_{n}⟩_{n∈ω}, S_{(·)}⟩ ∈ Emb which extends 𝔗. Indeed suppose that n ∈ ω and s ∈ S_{n}(γ). If γ ≤ η then s ∈ T_{n}(γ), and we put h_{n}^{+}(s) = h_{n}(s). If η < γ < |𝔖| then s↾η ∈ T_{n}(η) (the maximal level of T_{n}), so that h_{n}(s↾η) ∈ T′_{n}(η) is defined. Define s′ = h_{n}^{+}(s) ∈ (ℚ^{+})^{γ} so that s′↾η = h_{n}(s↾η) while s′(α) = s(α) for all h^{+} η ≤ α < |𝔖|. Thus h_{n}^{+}(s) is defined for all n and s ∈ S_{n}.

We let S′_{n} = {h^{+}(s) : s ∈ S_{n}} for each n. Now define the associated map S′_{(·)}. Suppose that s′ = h^{+}(s) ∈ S′_{n}, so that s ∈ S_{n}. Put S′_{(s′)} = {h_{n+1}^{+}(t) : t ∈ S_{(s)}}.

This ends the definition of 𝔖′ = ⟨⟨S′_{n}⟩_{n∈ω}, S_{(·)}⟩. We shall write 𝔖′ = h𝔖. h𝔖

Lemma 10 In this case, if ℳ(𝔖′) ⊆ ℳ(𝔖) and h ∈ ℳ(𝔖) then 𝔖′ is an embrion extending 𝔗′ and h^{+} ∈ Isom(𝔖, 𝔖′) .

Proof It suffices to check only (7), (8), and (9) for 𝔖′ below η + 1; the rest of requirements is quite obvious.

Consider (7). Let λ < |𝔖| = |𝔖′| be a limit ordinal, ℳ′ = ℳ(𝔖′↾λ), and D′ ∈ ℳ′ be a pre-dense subset of S′_{n}↾λ. Prove that any s′ = h^{+}(s) ∈ S′_{n}(λ) satisfies ∃ α < λ (s′↾α ∈ D). The case λ ≤ η is clear: apply (7) for 𝔗′. Thus we assume that η < λ < |𝔖′|. Then ℳ(𝔖′↾λ) ⊆ ℳ(𝔖↾λ) because h ∈ ℳ(𝔗) and ℳ(𝔗′) ⊆ ℳ(𝔗). It follows that D = {t ∈ S_{n}↾_{<λ} : h^{+}(t) ∈ D′} belongs to ℳ(𝔖↾λ). Moreover, D is a pre-dense subset of S_{n}↾_{<λ}. Therefore s↾α ∈ D for some α < λ. Then s′↾α ∈ D′, as required.

Consider (8). Suppose that S′ is S′_{0} or S′_{(s′)} for some s′ = h^{+}(s) ∈ S′_{n}, α < λ < |𝔖′|, λ is limit, and s′_{1} = h(s_{1}), s′_{2} = h(s_{2}) belong to S′(λ). (Then s_{1} and s_{2} belong to S = S_{(s)} .) Prove that ∑(s′_{1}↾α, s′_{2}↾α) < ∑(s′_{1}, s′_{2}) < +∞. Assume η < λ (the nontrivial case). To prove the right inequality note that

∑(s′_{1}, s′_{2}) = ∑(s′_{1}↾λ, s′_{2}↾λ) +_{∑λ≤γ<|𝔖|}|s_{1}(γ) − s_{2}(γ)| ,

by definition, so the result follows from the fact that 𝔖 and 𝔗′ are embrions. The left inequality is demonstrated similarly.

Finally prove (9). Suppose that S′ is S′_{0} or S′_{(s′)} for some s′ = h^{+}(s) ∈ S′_{n}, r ∈ ℚ^{+}, β < η < α < |S′| (the nontrivial case), and t′_{1} = h(t_{1}), t′_{2} = h(t_{2}) belong to S′(β), and s′_{1} = h(s_{1}) ∈ S′(α), t′_{1} ⊂ s′_{1}. We have to find s′_{2} ∈ S′(α) such that t′_{2} ⊂ s′_{2} and ∑(s′_{1}, s′_{2}) − ∑(t′_{1}, t′_{2}) < r.

Let σ′_{1} = s′_{1}↾η, so that σ′_{1} = h(σ_{1}) ∈ S′(η), where σ_{1} ∈ S(η) while either S = S_{0} or S = S_{(s)}. Since 𝔗′ is an embrion, there exists σ′_{2} = h(σ_{2}) ∈ S′(η)

(where σ_{2} ∈ S(η) ) such that t′_{2} ⊂ σ′_{2} and ∑(σ′_{1}, σ′_{2})−∑(t′_{1}, t′_{2}) < r/2. Since 𝔖 is an embrion, there is s_{2} ∈ S(α) such that σ_{2} ⊂ s_{2} and ∑(s_{1}, s_{2})−∑(σ_{1}, σ_{2}) < r/2. Now s′_{2} = h(s_{2}) is as required because by definition

∑(s′_{1}, s′_{2}) − ∑(σ′_{1}, σ′_{2}) = ∑(s_{1}, s_{2}) − ∑(σ_{1}, σ_{2}) .  □

3.5 Extensions of isomorphisms on terms and formulas

Suppose that h ∈ Isom(𝔗, 𝔗′). Then h induces an order isomorphism t⃗ ⟼ ht⃗ from ℙ = ℙ_{𝔗} onto ℙ′ = ℙ_{𝔗}′, hence if τ ∈ Trm(𝔗) then hτ

hτ = {⟨ht⃗, l⟩ : ⟨t⃗, l⟩ ∈ τ } ∈ Trm(𝔗′) ,

We shall assume that

⟨∗∗⟩ 𝔐(𝔗) = 𝔐(𝔗′) and h ∈ 𝔐(𝔗) .

Then hτ ∈ Trm^{∗}(𝔗′) whenever τ ∈ Trm^{∗}(𝔗). Furthermore, if, assuming ⟨∗∗⟩, Φ is a 𝔗-formula then the formula hΦ, obtained by changing of every term τ ∈ Trm^{∗}(𝔗) in Φ by hτ, is a 𝔗′-formula.

Note finally that h^{−1} ∈ Isom(𝔗′, 𝔗), and the consecutive action of h and h^{−1} on conditions, terms, and formulas, is idempotent.

Lemma 11 Let 𝔗 and 𝔗′ be embrions of equal height λ < ω_{1}. Suppose that h ∈ Isom(𝔗, 𝔗′) and ⟨∗∗⟩ holds. Assume finally that t⃗ ∈ ℙ_{𝔗} and Φ is a 𝔗formula. Then t⃗ forc_{𝔗} Φ iff ht⃗ forc_{𝔗}′ hΦ .

Proof is carried out by induction on the complexity of Φ .

Let Φ be a formula in 𝔗Σ_{∞}^{0} ∪ 𝔗Σ_{1}^{1} ∪ 𝔗Π_{1}^{1} (case (F1) in the definition). Then h defines, in ℳ(𝔗) = ℳ(𝔗′), an order isomorphism ℙ_{𝔗} onto ℙ_{𝔗}′, such that φ[G] is equal to (hφ)[h”G] for any set G ⊆ ℙ_{𝔗} and any 𝔗-formula φ. This implies the result by the ordinary forcing theorems. ( p”G is the p-image of G.)

The induction steps (F2) and (F3) do not cause any problem. (However Lemma 10 participates in the induction step (F3).) □

3.6 Proof of Theorem 8

Suppose, towards the contrary, that t⃗ forc_{𝔗} φ but t⃗′ forc_{𝔗}′ φ^{−}. We may assume that 𝔗 and 𝔗′ are embrions of one and the same length η + 1, η < ω_{1} being a limit ordinal. Moreover we can suppose that t⃗ = ⟨t_{0}, …, t_{n}⟩ and t⃗′ = ⟨t′_{0}, …, t′_{n}⟩ for one and the same n, and |t_{0}| = |t′_{0}| (then |t_{k}| = |t′_{k}| for all k).

We observe that by definition ℳ(𝔗) = L_{ϑ} and ℳ(𝔗′) = L_{ϑ′}, where ϑ and ϑ′ are countable (limit) ordinals. Let, for instance, ϑ′ ≤ ϑ. Then, in ℳ = ℳ(𝔗), 𝔗 and 𝔗′ remain embrions of length η + 1, countable in ℳ. Moreover, applying Theorem 9 in ℳ, we get an isomorphism h ∈ Isom(𝔗, 𝔗′)∩ℳ, satisfying ht⃗ = t⃗′.

Since we do not assume ℳ(𝔗) = ℳ(𝔗′), Lemma 11 cannot be applied directly. However take any embrion 𝔖 of length ϑ, extending 𝔗. Then, by Theorem 10, 𝔖′ = h𝔖 is an embrion of the same length ϑ and ℳ(𝔖) = ℳ(𝔖′). Furthermore there is an extension h^{+} ∈ ℳ(𝔖) ∩ Isom(𝔖, 𝔖′) of h.

To complete the proof note that t⃗ forc_{𝔖} φ and t⃗′ forc_{𝔖}′ φ^{−} by (a) . Applying Lemma 11 to the first statement, we obtain t⃗′ forc_{𝔖}′ hφ. However hφ coincides with φ, because φ does not contain terms. Thus t⃗′ forc_{𝔗}′ φ, which is a contradiction with the assumption t⃗′ forc_{𝔗}′ φ^{−} by (b) .

References

[1] L. Harrington. The constructible reals can be anything. A preprint dated May 1974 with several addendums dated up to October 1975.

[2] R. B. Jensen. Definable sets of minimal degree. Mathematical logic and foundations of set theory, Amsterdam, North-Holland, 1970, pp. 122 – 128.

[3] R. B. Jensen and R. M. Solovay. Some applications of almost disjoint sets. Mathematical logic and foundations of set theory, Amsterdam, North-Holland, 1970, pp. 84 – 104.

[4] R. B. Jensen and H. Johnsbråten. A new construction of a non-constructible Δ_{3}^{1} subset of ω. Fund. Math. 1974, 81, pp. 280 – 290.

[5] V. Kanovei. The independence of some propositions of descriptive set theory and second order arithmetic. Soviet Math. Dokl. 1975, 16, 4, pp. 937 – 940.

[6] V. Kanovei. On the nonemptiness of classes in axiomatic set theory. Math. USSR Izv. 1978, 12, pp. 507 – 535.