Cardinalities in the projective hierarchy

Greg Hjorth 2000

Contents

1 Introduction 1 2 Outline 3 3 Notational issues 5 4 Hairy Σ ∼_{1}^{1} set forcing: P_{H} 6 5 And its amalgam: P_{H} ⊗_{S_{1},S_{2}} P_{H} 8 6 Some dense sets for P_{H} ⊗_{S_{1},S_{2}} P_{H} 11 7 Some things to do with a generic 19 8 Generalities on finding generics 22 9 Finishing up 24

1 Introduction

We show that the “effective cardinality” of the collection of Π ∼_{n+1}^{1} sets is strictly bigger than the effective cardinality of the Π ∼_{n}^{1}. The phrase effective cardinality is vague but can be made exact in the usual ways. For instance: Theorem 1.1 Assume AD^{L(ℝ)}. Then in L(ℝ) there is no injection

i : Π ∼_{n+1}^{1} ↪ Π ∼_{n}^{1}.

A few years ago Tony Martin showed a similar result, establishing the non-existence of an injection from Π ∼_{m}^{1} to Π ∼_{n}^{1} for m sufficiently larger than n. His method did not seem to work for m = n + 1.

This present paper gives level by level calculations for the projective hierarchy, but it too falls short of a complete analysis, in as much as it leaves the position of the effective cardinals in the Wadge degrees largely obscure. At the low levels it takes some time for any new cardinals to appear. Whenever Γ_{1}, Γ_{2} are non-trivial Wadge degrees strictly included in Δ ∼_{2}^{0} one has

|Γ_{1}|_{L(ℝ)} = |Γ_{2}|_{L(ℝ)}.

Beyond Δ ∼_{2}^{0} it is known from [3] that the different levels of the Borel hierarchy have distinct effective cardinalities. It is unclear whether there might be cardinals lying strictly between say Π ∼_{2}^{0} and Π ∼_{3}^{0}, though Itay Neeman has proved that there is no L(ℝ) injection from Π ∼_{α+2}^{0} to Δ ∼_{α+2}^{0}. Thus as a landmark of our ignorance:

Question Is |Π ∼_{2}^{0}|_{L(ℝ)} < |Δ ∼_{3}^{0}|_{L(ℝ)}?

[1] provides a reference for virtually every known fact about the Wadge degrees, as well as all the general theory of L(ℝ) required below. One can also refer to [5] and [6] for basic facts about scales in L(ℝ) as well as the basis theorem for Σ ∼_{1}^{2}. §9.2 of [4] overviews some of this material and along with [2] presents an introduction to the theory of cardinality for non-wellorderable sets in L(ℝ).

2 Outline

The plan is something like this. We suppose for a contradiction that there is an L(ℝ) injection from Π ∼_{2}^{1} into Π ∼_{1}^{1}. Formally speaking we are only working with the case n = 1, but it will be clear that the proof generalizes.

We then want to find some suitable forcing notion for introducing codes for Π ∼_{2}^{1} sets, P_{H}, and some suitable Polish space of codes for Π ∼_{1}^{1} sets, call it C_{1}, and we argue from uniformization(Σ ∼_{1}^{2}) that there must be an actual L(ℝ) function

θ : Filters for P_{H} → C_{1}

such that for all sufficiently generic G_{1}, G_{2} ⊂ P_{H} we have that G_{1} and G_{2} give rise to the same Π ∼_{2}^{1} sets if and only if θ(G_{1}) and θ(G_{2}) code the same Π ∼_{1}^{1} sets^{1}. Since all functions in L(ℝ) are continuous on a comeager set we obtain that

G ↦ θ(G)

will be continuous for any sufficiently generic G.

Given codes C_{1}, C_{2} for Π ∼_{2}^{1} we want to continuously assign generics

G_{1}(C_{1}, C_{2}), G_{2}(C_{1}, C_{2}) ⊂ P_{H}

such that G_{1} and G_{2} give rise to the same Π ∼_{2}^{1} sets if and only if C_{1} and C_{2} give rise to the same Π ∼_{2}^{1}. Then by composing with θ we have that

(C_{1}, C_{2}) ↦ (θ(G_{1}(C_{1}, C_{2})), θ(G_{2}(C_{1}, C_{2})))

continuously reduces equality on pairs of codes for Π ∼_{2}^{1} sets into equality on pairs of codes for Π ∼_{1}^{1} sets. Since the former is Π ∼_{3}^{1} complete and the later is only Π ∼_{2}^{1} we have a contradiction.

In §4 we present the notion of forcing P_{H} for introducing generic Σ ∼_{1}^{1} subsets of ω^{ω} × ω^{ω}, which will then in turn give us a Π ∼_{2}^{1} set by universally quantifying out the second coordinate. The point here is that the forcing gives rise to such “hairy” and unruly Σ ∼_{1}^{1} sets that for any generic G and Σ ∼_{1}^{1} set A_{S} we will have room to find many ways to hide a copy of A_{S} inside the Σ ∼_{1}^{1} set given by G.

§5 defines a method to “amalgamate” two copies of P_{H} relative to some given Σ ∼_{1}^{1} sets. Given A_{S_{1}}, A_{S_{2}} ⊂ 2^{ω} × ω^{ω}, both Σ ∼_{1}^{1}, we can continuously from some space of codes find a forcing

P_{H} ⊗_{S_{1},S_{2}} P_{H};

the generic object on this amalgamated forcing will provide a pair of generic (but not necessarily mutually generic) G_{1}, G_{2} ⊂ P_{H}, giving rise to

A_{G_{1}}, A_{G_{2}} ⊂ ω^{ω} × ω^{ω}
Φ : 2^{ω} → ω^{ω}

such that for all (x, y) ∈ 2^{ω} × ω^{ω} we have

(x, y) ∈ A_{S_{i}} ⇔ (Φ(x), y) ∈ A_{G_{i}}

i = 1, 2, and for all z not in the range of Φ

(z, y) ∈ A_{S_{1}} ⇔ (z, y) ∈ A_{S_{2}}.

1In §9 when the details are finally played out, we will use the Polish space of all downward closed subsets of {0, 1}^{<ω} × ω^{<ω} as our space C_{1} of codes; in the usual way this can be identified with a closed subset of {0, 1}^{({0,1}^{<ω}×ω^{<ω})}. P_{H} is given in section 4, and will analogously consist of finite partial attempts to build a downward closed subset of {0, 1}^{<ω} × (ω × ω)^{<ω}.

The technical part of the proof is to verify in §6 that the various open dense sets in P_{H} appropriately lift up to open dense sets in P_{H} ⊗_{S_{1},S_{2}} P_{H} and that the generic object on this amalgamated forcing will have the various properties claimed in the paragraph before. The details in this technical part of the proof are numerous. Perhaps there are too many.

3 Notational issues

Notation For us ω denotes the set of natural numbers, and we begin counting at 0:- ω = {0, 1, 2, ...}. In this controversial issue we follow the usual practice of set theorists.

We use ω^{<ω} to denote

⋃_{k∈ω} ω^{k},

where

ω^{k} = {f : {0, 1, ..., k − 1} → ω},

2^{<ω} for

⋃_{k∈ω}{0, 1}^{k},

and (ω × ω)^{<ω} for

⋃_{k∈ω} ω^{k} × ω^{k}.

We view ω^{<ω} as ordered by inclusion in the usual way. For u, v ∈ ω^{<ω} we write u^{⌢}v for the concatenation, obtained by letting the second sequence be adjoined onto the end of the first. For j ∈ ω we write u^{⌢}j, rather than u^{⌢}⟨j⟩, for the result of adjoining the sequence ⟨j⟩ of length one to u.

Cheating ever so slightly, we shall describe the natural ordering on (ω×ω)^{<ω} as inclusion and accordingly write

(u, v) ⊂ (u′, v′)

for (u, v), (u′, v′) ∈ (ω × ω)^{<ω} when u ⊂ u′, v ⊂ v′.

Very often we will use s for an arbitrary element s ∈ (ω × ω)^{<ω} of the form s = (u, v). For s = (u, v), t = (w, r) ∈ (ω × ω)^{<ω} we let

s^{⌢}t =_{df} (u^{⌢}w, v^{⌢}r).

ℓ(u) denotes the length of u, so that u ∈ ω^{ℓ(u)}.

For u ∈ ω^{<ω} of non-zero length, we let u^{−} denote its predecessor: So that u^{−} ⊂ u and ℓ(u^{−}) = ℓ(u) − 1. If s = (u, v) ∈ (ω × ω)^{<ω} then s^{−} = (u^{−}, v^{−}).

Definition A set T ⊂ ω^{<ω} × (ω × ω)^{<ω} is said to be downwards closed if whenever

(u, (v, w)) ∈ T

and u′ ⊂ u, (v′, w′) ⊂ (v, w) then

(u′, (v′, w′)) ∈ T.

Given such a T we let A_{T} be the Σ ∼_{1}^{1} set of (x, y) ∈ ω^{ω} × ω^{ω} for which there exists f ∈ ω^{ω} such that at each n, m ∈ ω

(x|_{n}, (y|_{m}, f|_{m})) ∈ S.

Note that by the assumption of being downward closed, we in fact obtain that

A_{T} = {(x, y) : ∃f∀n(x|_{n}, (y|_{n}, f|_{n})) ∈ T }.

Notation For (u, s) ∈ ω^{<ω} × (ω × ω)^{<ω} we let

T_{(u,s)} = {(u′, s′) ∈ ω^{<ω} × (ω × ω)^{<ω}|u ⊂ u′, s ⊂ s′}.

4 Hairy Σ ∼_{1}^{1} set forcing: P_{H}

We describe a forcing notion which produces a complicated Σ ∼_{1}^{1} set.

Definition We let P_{H} denote the set of pairs (T, p) such that 1.

T ⊂ ω^{<ω} × (ω × ω)^{<ω}

is finite and closed downwards; 2.

p : T → {0, 1}

has the property that if

p(u, s) = 0

and u ⊂ u′, s ⊂ s′, then

p(u′, s′) = 0;

3. p(u, (0, 0)) ≠ 0 all u ∈ ω^{<ω}.

We order P_{H} by extension, so that

(T′, p′) ≤ (T, p)

if T′ ⊃ T and p′ ⊃ p.

Lemma 4.1 (T, p), (T′, p′) ∈ P_{H} are such that

p|_{T ∩T′} = p′|_{T ∩T′}

then (T, p), (T′, p′) are compatible, in the sense that there is some (T^{∗}, p^{∗}) ∈ P_{H} with

(T^{∗}, p^{∗}) ≤ (T, p), (T′, p′).

Proof We let T^{∗} = T′ ∪ T and p^{∗} = p′ ∪ p. We need to see that this pair (T^{∗}, p^{∗}) is an element of P_{H}.

The first and last conditions in the definition of P_{H} immediately hold, and for the second we see that if (u, s) ∈ T^{∗} with p^{∗}(u, s) = 1 then we may assume without loss that (u, s) ∈ T, and so for all (u′, s′) ⊂ (u, s) we have p(u′, s′) = 1 by (T, p) ∈ P_{H}, and hence p^{∗}(u′, s′) = 1. □

Lemma 4.2 Suppose (T′, p′) ≤ (T, p), (T′, p′) ≠ (T, p). Then there is a condition (T^{∗}, p^{∗}) with

(T′, p′) ≤ (T^{∗}, p^{∗}) ≤ (T, p)

and

|T^{∗}| = |T | + 1.

Proof Choose some (u, s) ∈ T′ \ T. Choose (u_{0}, s_{0}) with lh(u_{0}) + lh(s_{0}) minimal subject to the constraint that

u_{0} ⊂ u
s_{0} ⊂ s
(u_{0}, s_{0}) ∉ T.

Thus for any other u_{1} ⊂ u_{0}, s_{1} ⊂ s_{0} with (u_{1}, s_{1}) ≠ (u_{0}, s_{0}) we have (u_{1}, s_{1}) ∈ T.

Then let T^{∗} = T ∪ {(u_{0}, s_{0})} and p^{∗} = p′|_{T^{∗}}. □

G. Hjorth 7 Definition For G ⊂ P_{H} a sufficiently generic filter we obtain a downward closed set T_{G} ⊂ ω^{<ω} × (ω × ω)^{<ω} by

T_{G} = {(u, s) : ∃p ∈ G(p(u, s) = 1)}

and a corresponding Σ ∼_{1}^{1} set A_{G} by taking the definition of A_{T_{G}} from the previous section:

A_{G} =_{df} A_{T_{G}} = {(x, y) : ∃f∀n(x|_{n}, (y|_{n}, f|_{n})) ∈ T_{G}}.

5 And its amalgam: P_{H} ⊗_{S_{1},S_{2}} P_{H}

Definition Let S_{1}, S_{2} ⊂ 2^{<ω}×(ω×ω)^{<ω} be two sets that are closed downwards. We then define P_{H}⊗_{S_{1},S_{2}}P_{H} to be the set of sequences

q = (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ)

satisfying the following conditions (for which we parenthetically provide some brief motivation along the way):

(1) (T, p_{i}) ∈ P_{H} for i = 1, 2; (ultimately the forcing will try to generate two generics in P_{H});

(2) U ⊂ 2^{<ω} is a finite non-empty subtree and

φ : U → ω^{<ω}

is an ordering preserving injection;

(3) V ⊂ (ω × ω)^{<ω} is a finite non-empty subtree and

ψ : V → (ω × ω)^{<ω}

is an order and length preserving injection, with the property that each

ψ(v, w) = (v, ψ_{0}(v, w)),

some ψ_{0}(v, w) ∈ ω^{<ω}; (φ, ψ are partial attempts to describe a copy of 2^{<ω} × (ω × ω)^{<ω} inside ω^{<ω} × (ω × ω)^{<ω});

(4) if we define

Û(q) = {u|∃u′ ∈ U(u ⊂ φ(u′))},
V̂ (q) = {s|∃s′ ∈ V (s ⊂ ψ(s′))},

then (a) Û(q) ∩ A = 0;

(b) V̂ (q) ∩ B = 0;

(c) Û(q) × V̂ (q) ⊂ T ⊂ (Û(q) ∪ A) × (V̂ (q) ∪ B), and in turn

(Û(q) ∪ A) × (V̂ (q) ∪ B) ⊂ {(u, s)|∃u′, s′((u, s′) ∈ T, (u′, s) ∈ T)},

so that in particular A and B are finite; (note that (3) actually implies V̂ (q) = ψ[V]); (A and B describe “forbidden” sets on which the copying functions φ and ψ can never extend; T in turn at (c) includes everything necessitated by A, B, and the ranges of φ and ψ);

(5) for all u ∈ U, s ∈ V we have p_{i}(φ(u), ψ(s)) = 1 if and only if (u, s) ∈ S_{i}, i = 1, 2;

(6) if we let E_{1}(q) be the set of (u, s) such that (i) u ∈ A (ii) u^{−} ∈ Û(q) (iii) p_{1}(u, s^{−}) = p_{2}(u, s^{−}) = 1 (iv) p_{1}(u, s) = 1

(v) p_{2}(u, s) = 0 (so that E_{1}(q) refers to certain nodes on which the generic below (T, p_{1}) is unable to produce any infinite branches, while the generic below (T, p_{2}) is still open to do so; ultimately we want that the generic objects should give rise to Σ ∼_{1}^{1} sets which agree outside the ranges of ψ, and hence the function σ below at (a)-(g) is intended to busily work around to even up this possible error); and if we similarly let E_{2}(q) be the set of (u, s) such that

(i) u ∈ A

(ii) u^{−} ∈ Û(q)
(iii) p_{1}(u, s^{−}) = p_{2}(u, s^{−}) = 1
(iv) p_{1}(u, s) = 0
(v) p_{2}(u, s) = 1

then we obtain that (a) Domain(σ) = ⋃{T_{(u,s)}|(u, s) ∈ E_{1}(q)} ∩ T;

(b) Range(σ) = ⋃{T_{(u,s)}|(u, s) ∈ E_{2}(q)} ∩ T;

(c) if (u, s) ∈ E_{1}(q) with s = (v, w^{⌢}j), then

σ(u, s) = (u, (v, w^{⌢}k))

some k with (u, (v, w^{⌢}k)) ∈ E_{2}(q);

(d) for each u ∈ A with u^{−} ∈ Û(q) there is a corresponding function

σ_{u} : ⋃{T_{(u,s)}|(u, s) ∈ E_{1}(q)} → ω^{<ω}

such that for all (u, (v, w)) ∈ E_{1}(q) and (u′, (v′, w^{⌢}r)) ∈ T_{(u,(v,w))} we have

σ(u′, (v′, w^{⌢}r)) = (u′, (v′, w^{⌢}σ_{u}(v′, w^{⌢}r)));

so the σ acting on some point (u′, s′) above (u, s) ∈ E_{1}(q) leaves u′ untouched, leaves the first coordinate of s′ untouched, and its value on the second coordinate of s′ is a function solely of u and s′;

(e) for each (u, s) ∈ E_{1}(q)

σ|_{T_{(u,s)}} : T_{(u,s)} ≅ T_{σ(u,s)}

is an isomorphism of partially ordered sets;

(f) for each (u, s) ∈ E_{1}(q) and u′ ⊃ u, s′ ⊃ s we have

p_{1}(u′, s′) = p_{2}(σ(u′, s′));

(g) if u ∈ A and

p_{1}(u, s) ≠ p_{2}(u, s)

then there are u′ ⊂ u, s′ ⊂ s with

(u′, s′) ∈ E_{1}(q) ∪ E_{2}(q).

We order P_{H} ⊗_{S_{1},S_{2}} P_{H} by coordinate wise extension, except on the φ coordinate where we permit on terminal nodes of U lengthening of the value of φ(u). In other words,

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ≤ (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ)

in P_{H} ⊗_{S_{1},S_{2}} P_{H} if

1. T′ ⊃ T,

2. p′_{1} ⊃ p_{1},

3. p′_{2} ⊃ p_{2}, 4. U′ ⊃ U,

5. A′ ⊃ A,

6. V′ ⊃ V,

7. B′ ⊃ B,

8. σ′ ⊃ σ,

9. ψ′ ⊃ ψ,

10. for u ∈ U not terminal we have

φ′(u) = φ(u)

while for u ∈ U terminal in U we have

φ′(u) ⊃ φ(u).

The idea of the forcing is this: On Û(q) × V̂ (q) we have p_{1} and p_{2} constrained by the sets S_{1} and S_{2} respectively. Outside of Û(q) × V̂ (q) we try to make p_{1} and p_{2} match up as far as possible. Sometimes the commitments previously made on Û(q) × V̂ (q) prevent us, and this is tracked by the sets E_{1}(q) and E_{2}(q); and so below these bad points we use the σ_{u} isomorphisms to at least ensure that the resulting Σ ∼_{1}^{1} sets defined by the generic object G will be the same outside the tree defined by projecting ⋃_{q∈G} Û(q) × V̂ (q) to the set

{(u, v) : ∃w∃q ∈ G((u, (v, w)) ∈ Û(q) × V̂ (q))}.

There is an assymetry between the requirements on φ at (2) and ψ at (3). ψ is as a matter of law length preserving; φ need not be. This shows up at 6.10 below; it is technically convenient to have the ability to extend φ so that

p_{1}(φ(u), s) = p_{2}(φ(u), s) = 0

for any s ∈ B and u terminal in U.

6 Some dense sets for P_{H} ⊗_{S_{1},S_{2}} P_{H}

For this section fix S_{1}, S_{2} ⊂ 2^{<ω} × (ω × ω)^{<ω} downward closed.

Lemma 6.1 Suppose

q = (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ)

is in P_{H} ⊗_{S_{1},S_{2}} P_{H} and that we have conditions

(T′′, p′′) ≤ (T′, p′) ≤ (T, p_{1})

with |T′| = |T | + 1.

Then there is

q^{∗} = (T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗})

with

(T^{∗}, p_{1}^{∗}) ≤ (T′, p′)

and (T^{∗}, p_{1}^{∗}) still compatible with (T′′, p′′).

Proof Let (u, s) be such that T′ = T ∪ (u, s).

Case(1) u ∈ Û(q).

In this case it follows from (u, s) ∉ T that we have s ∉ V̂ (q). So we let

T^{∗} = T′ = T ∪ {(u, s)}
p_{1}^{∗}(u, s) = p′′(u, s) = p′(u, s)
p_{2}^{∗}(u, s) = 0
p_{1}^{∗}|_{T} = p_{1}
p_{2}^{∗}|_{T} = p_{2}
U^{∗} = U
φ^{∗} = φ
V^{∗} = V
ψ^{∗} = ψ
A = A^{∗}
B^{∗} = B ∪ {s}
σ^{∗} = σ
q^{∗} = (T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}).

Since u ∈ Û(q) and s ∉ V̂ (q) we have no possibility of violating (5) and (6) in the definition of P_{H} ⊗_{S_{1},S_{2}} P_{H}. Û(q^{∗}) = Û(q) and V̂ (q^{∗}) = V̂ (q), and so we maintain (4). φ^{∗} = φ and ψ^{∗} = ψ easily give (2) and (3). We have (1) by assumption of (T′, p′) ∈ P_{H} and choice of p_{2}^{∗}; here it is important that s ≠ (0, 0) by case assumption and the part (3) of the amalgam forcing stating V ≠ ∅, and so p_{2}^{∗}(u, s) = 0 creates no conflict with the definition of P_{H}. Finally since (T^{∗}, p_{1}^{∗}) = (T′, p′) we obtain

(T′′, p′′) ≤ (T^{∗}, p_{1}^{∗}),

which is certainly enough to show these two conditions compatible.

Case(2) u^{−} ∈ Û(q), u ∉ Û(q).

Here we may as well assume that s ≠ (0, 0), since otherwise we would have p′(u, s) = 1, and we could extend q in a care free manner, with p_{1}^{∗}(u, s) = p_{2}^{∗}(u, s) = 1, A^{∗} = A ∪ {u}, B = B^{∗}, φ^{∗} = φ, ψ^{∗} = ψ, and as in case(1) the various conditions in the definition of the forcing follow easily. So we make this assumption. In particular then since T′ = T ∪ {(u, s)} is downward closed, it follows that (u, s^{−}) ∈ T, and thus from the case assumption that u ∈ A. Similarly (u^{−}, s) ∈ T so s ∈ B ∪ V̂ (q).

Subcase(2a) p_{1}(u^{−}, s) = p_{2}(u^{−}, s) and for all s^{∗} ⊂ s we have p_{1}(u, s^{∗}) = p_{2}(u, s^{∗}).

Then just let

T^{∗} = T′ = T ∪ {(u, s)}
p_{1}^{∗}(u, s) = p_{2}^{∗}(u, s) = p′′(u, s) = p′(u, s)
p_{1}^{∗}|_{T} = p_{1}|_{T}
p_{2}^{∗}|_{T} = p_{2}|_{T}
U^{∗} = U
φ^{∗} = φ
V^{∗} = V
ψ^{∗} = ψ
A^{∗} = A
B^{∗} = B
σ^{∗} = σ
q^{∗} = (T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}).

Since (u^{−}, s) ∈ T we have no trouble with clause (c) of part (4) of the definition of P_{H} ⊗_{S_{1},S_{2}} P_{H}, while (4)(a) and (4)(b) follow as in the last case. (6) is no problem, since we have added no new elements to E_{1}(q^{∗}), E_{2}(q^{∗}) nor any new elements to T^{∗} extending a point in E_{1}(q) ∪ E_{2}(q). (5) is for free since U, φ, V, ψ are left unchanged. Similarly (2) and (3) continue to hold almost vacuously. We obtain (1) by assumption on (T′, p′) along with our case hypothesis. As in the first case of the proof, we have (T^{∗}, p_{1}^{∗}) ≤ (T′′, p′′).

Subcase(2b) p_{1}(u^{−}, s) ≠ p_{2}(u^{−}, s) but for all s^{∗} ⊂ s, s^{∗} ≠ s, we have p_{1}(u, s^{∗}) = p_{2}(u, s^{∗}).

If p′(u, s) = 0 then we can go ahead and let

p_{1}^{∗}(u, s) = p_{2}^{∗}(u, s) = 0,

and the whole thing finishes up as in the earlier cases.

So suppose instead that p′(u, s) = 1. Then the definition of P_{H} and the assumptions of this subcase entail

p_{1}(u^{−}, s) = 1,
p_{2}(u^{−}, s) = 0.

Here we have s ≠ (0, 0). Thus we may write

s = (v, w^{⌢}j)

for some j ∈ ω. Choose k with

(û, (v, w^{⌢}k)) ∉ T′′

all û ∈ ω^{<ω}. We define σ^{∗} to be the extension of σ obtained by adding (u, (v, w^{⌢}j)) to its domain and setting

σ^{∗}(u, (v, w^{⌢}j)) = (u, (v, w^{⌢}k)).

We let

T^{∗} = T ∪ {(u, s)} ∪ {(û, (v, w^{⌢}k))|û ⊂ u}.

We extend p_{1} and p_{2} to p_{1}^{∗} and p_{2}^{∗} both having domain T^{∗} with

p_{1}^{∗}(u, s) = 1
p_{2}^{∗}(u, s) = 0

and for all û ⊂ u

p_{1}^{∗}(û, (v, w^{⌢}k)) = 0
p_{2}^{∗}(û, (v, w^{⌢}k)) = 1.

This clearly guarantees our q^{∗} will satisfy (1) from the definition of the forcing. As before we can let

φ^{∗} = φ
U^{∗} = U
ψ^{∗} = ψ
V^{∗} = V

and obtain (2), (3), and (5) without any work. Letting A^{∗} = A and B^{∗} = B ∪ {(v, w^{⌢}k)} we obtain (4). Our choice of σ^{∗} maintains (6). We have (T^{∗}, p_{1}^{∗}) compatible with (T′′, p′′) by 4.1.

Subcase(2c) There is some s^{∗} ⊂ s, s^{∗} ≠ s, with p_{1}(u, s^{∗}) ≠ p_{2}(u, s^{∗}).

Then by (6)(g) of the definition of P_{H} ⊗_{S_{1},S_{2}} P_{H} we have some s^{∗} ⊂ s, s^{∗} ≠ s with

(u, s^{∗}) ∈ E_{1}(q) ∪ E_{2}(q).

We us assume the (u, s^{∗}) in E_{1}(q), since the case of (u, s^{∗}) in E_{2}(q) is similar, just with σ^{−1} instead of σ.

Let s = (v, w^{⌢}j). Fix ŵ with

σ(u, (v^{−}, w)) = (u, (v^{−}, ŵ)).

We then choose k with

(û, (v̂, ŵ^{⌢}k)) ∉ T′′

for any û, v̂. By assumption on σ we must have

p_{1}(u, s^{−}) = p_{2}(σ(u, s^{−})) = p_{2}(u, (v^{−}, ŵ)) = 1
p_{2}(u, s^{−}) = 0 = p_{1}(σ(u, s^{−})).

We then let T^{∗} = T ∪ {(u, s)} ∪ {(û, (v, ŵ^{⌢}k))|û ⊂ u} and we define p_{1}^{∗}, p_{2}^{∗} to have domain T^{∗}, extending p_{1}, p_{2} by

p_{1}^{∗}(u, s) = p_{2}^{∗}(u, (v, ŵ^{⌢}k)) = p′(u, s) = 1
p_{2}^{∗}(u, s) = p_{1}^{∗}(u, (v, ŵ^{⌢}k)) = 0

and for all û ⊂ u

p_{1}^{∗}(û, (v, ŵ^{⌢}k)) = 0

p_{2}^{∗}(û, (v, ŵ^{⌢}k)) = p′(û, s) = 1.

It is pretty clear that (T^{∗}, p_{1}^{∗}) ∈ P_{H} for i = 1, 2 and

(T^{∗}, p_{1}^{∗}) ≤ (T′, p′),

and by 4.1 we have (T^{∗}, p_{1}^{∗}) and (T′′, p′′) compatible in P_{H}.

Now we can continue on in the usual way, letting ψ^{∗} = ψ, φ^{∗} = φ, U^{∗} = U, V^{∗} = V, A^{∗} = A, B^{∗} = B ∪ {(v, ŵ^{⌢}k)}, and define σ^{∗} to be the extension of σ to the domain(σ) ∪ {(u, s)} with

σ^{∗}(u, s) = (u, (v, ŵ^{⌢}k)).

Then take

q^{∗} = (T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}).

As remarked above we have (1) in the definition of P_{H} ⊗_{S_{1},S_{2}} P_{H} since we still have each (T^{∗}, p_{i}^{∗}) ∈ P_{H}. (2), (3), (4), and (5) follow more or less for free. (6) follows from our exact choice of σ^{∗} and the construction above.

Case(3) u, u^{−} ∉ Û(q).

Subcase (3a) For all û ⊂ u, ŝ ⊂ s, if û ∈ A and (û, ŝ) ∈ T then

p_{1}(û, ŝ) = p_{2}(û, ŝ).

In particular this gives first of all that

p_{1}(u^{−}, s) = p_{2}(u^{−}, s)
p_{1}(u, s^{−}) = p_{2}(u, s^{−})

and secondly that no (û, ŝ) ⊂ (u, s) is in the domain of σ. Then we proceed as in subcase(2a).

Subcase(3b) There exists (û, ŝ) with

û ⊂ u
ŝ ⊂ s
û ∈ A
p_{1}(û, ŝ) ≠ p_{2}(û, ŝ).

It follows then from the definition of q ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H} that for u_{0} ⊂ u minimal with u_{0} ∈ A we must have some s_{0} ⊂ s with

(u_{0}, s_{0}) ∈ E_{1}(q) ∪ E_{2}(q);

let us assume (u_{0}, s_{0}) ∈ E_{1}(q), since the situation with (u_{0}, s_{0}) ∈ E_{2}(q) is a mirror image of this one. Then (u^{−}, s) ∈ domain(σ), and so there is some ŵ with

σ(u^{−}, s) = (u^{−}, (v, ŵ)),

where s = (v, w). This forces onto us the definition of σ^{∗}: Its domain is domain(σ) ∪ {(u, s)} and σ^{∗}(u, s) = (u, (v, ŵ)). The assumption on σ, that it accords with (6), implies that for all û with u_{0} ⊂ û ⊂ u, û ≠ u

p_{1}(û, s) = p_{2}(û, (v, ŵ));

similarly

p_{1}(u, s^{−}) = p_{2}(u, σ(s^{−})) = p_{2}(u, (σ(s))^{−}) = p_{2}(u, (v^{−}, ŵ^{−})).

Therefore we can let T^{∗} = T ∪ {(u, s), (u, (v, ŵ))} and let p_{1}^{∗}, p_{2}^{∗} be the extensions of p_{1}, p_{2} to T^{∗} with

p_{1}^{∗}(u, s) = p′(u, s)
p_{2}^{∗}(u, (v, ŵ)) =_{df} p_{2}^{∗}(σ^{∗}(u, s)) = p′(u, s)
p_{1}^{∗}(u, (v, ŵ)) =_{df} p_{1}^{∗}(σ^{∗}(u, s)) = p_{2}(u, s) = 0.

We let φ^{∗} = φ, ψ^{∗} = ψ, U^{∗} = U, V^{∗} = V, A^{∗} = A, B^{∗} = B, and

q^{∗} = (T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}).

We obtain (1) in the definition of the amalgamated forcing notion by assumption on p′ and from σ satisfying (6) for q. (2), (3), (4), and (5) are again automatic. (6) follows from the assumption on σ and our definition of σ^{∗}, p_{i}^{∗}(u, s), p_{i}(σ^{∗}(u, s)), i = 1, 2.

Finally we need to see that (T^{∗}, p_{1}^{∗}) is still compatible with (T′′, p′′). For this we need to check that they agree on their common domain. We first obtain that p_{1}^{∗}(u, s) = p′(u, s) = p′′(u, s) by assumption on p′. On the other new element of T^{∗} we have p_{1}^{∗}(u, (v, ŵ)) = 0, and we need to see that this does not differ from p′′(u, (v, ŵ)). But by assumption σ(u_{0}, s_{0}) ⊂ (u, (v, ŵ)) we must have some w_{0} ⊂ ŵ, v_{0} ⊂ v with

p_{1}(u_{0}, (v_{0}, w_{0})) = 0

and hence by our assumption p′′ ≤ p_{1}

p′′(u_{0}, (v_{0}, w_{0})) = 0

hence

p′′(u, (v, ŵ)) = 0.
□

Corollary 6.2 If O ⊂ P_{H} is open dense, then the set (O)^{∗} of

(T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A′, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

with (T^{∗}, p_{1}^{∗}) ∈ O is again open dense in P_{H} ⊗_{S_{1},S_{2}} P_{H}.

Proof We successively apply 6.1 and 4.2 to extend (T_{1}, p_{1}) until we at last have a condition

(T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A′, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗})

with (T^{∗}, p_{1}^{∗}) actually extending some (T′′, p′′) ∈ O. □

Corollary 6.3 For each u ∈ ω^{<ω} and s ∈ (ω × ω)^{<ω} we have that the set of

(T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

with

(u, s) ∈ T^{∗}

is open dense.

Lemma 6.4 If O ⊂ P_{H} is open dense, then the set (O)_{∗} of

(T^{∗}, p_{1}^{∗}, p_{2}^{∗}, U^{∗}, A^{∗}, φ^{∗}, V^{∗}, B^{∗}, ψ^{∗}, σ^{∗}) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

with (T^{∗}, p_{2}^{∗}) ∈ O is again open dense in P_{H} ⊗_{S_{1},S_{2}} P_{H}.

Proof The proof is exactly symmetrical to 6.2. □ Lemma 6.5 For each u ∈ 2^{<ω} and j ∈ {0, 1}, the set of

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

such that if u ∈ U′ then u^{⌢}j ∈ U′ is dense. Proof Choose some

q = (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}.

If u ∉ U then we are already done, so suppose instead u ∈ U and u^{⌢}j ∉ U. Then we can simply extend φ to φ′ with

φ′(u^{⌢}j) = φ(u)^{⌢}k

for some

φ(u)^{⌢}k ∉ A ∪ Û(q).

For s ∈ V we can set p′_{i}(φ(u)^{⌢}k, ψ(s)) = 1 if (u^{⌢}j, s) ∈ S_{i} and = 0 if (u^{⌢}j, s) ∉ S_{i}. We let ψ′ = ψ, V′ = V, A′ = A, B′ = B, U′ = U ∪ {(u^{⌢}j)}. We let Û′ = {û|∃u ∈ U′(û ⊂ φ′(u)}, T′ = T ∪ Û′ × V̂ (q).

□

Corollary 6.6 For each u ∈ 2^{<ω}, the set of

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

with u ∈ U′ is open dense. Lemma 6.7 For each (v, w) ∈ (ω × ω)^{<ω} and j, k ∈ ω, the set of

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, V̂′σ′) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

such that if (v, w) ∈ V′ then (v^{⌢}j, w^{⌢}k) ∈ V′ is dense. Proof This is similar to 6.5. □ Corollary 6.8 For each s ∈ (ω × ω)^{<ω}, the set of

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

with s ∈ V′ is open dense. Lemma 6.9 For all

q = (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

and W ⊃ U a subtree of 2^{<ω}, there is

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ≤ (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ)

with U′ = W.

Proof We let U′ = W, V′ = V, ψ′ = ψ, A′ = A, B′ = B, and then let

φ′ : W → ω^{<ω}

be any one to one order preserving function extending φ such that for all u ∈ W \ U we have

φ′(u) ∉ Û(q) ∪ A.

We define

Û′ = {û|∃u ∈ W (φ(u) ⊃ û)}

and

T′ = T ⋃ Û′ × V̂ (q),

and we require that on each (φ′(u), ψ(s)) for u ∈ W, s ∈ V, and i = 1, 2

p′_{i}(φ′(u), ψ(s)) = 1 ⇔ (u, s) ∈ S_{i},
p′_{i}(φ′(u), ψ(s)) = 0 ⇔ (u, s) ∉ S_{i}.

For other arguments (u, s) ∈ Û′ ×V̂ (q), not in T ∪(φ′[W]×ψ[V]), we go to the maximal û ⊂ u with û ∈ φ[W] and let

p′_{i}(u, s) = p′_{i}(φ^{′−1}(û), ψ^{−1}(s)).

(The properties of ψ given at (3) in the definition of the forcing notion are already enough to imply s is in the range of ψ). □

Lemma 6.10 The set of

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

such that

(1) for some ℓ,

U′ = {0, 1}^{ℓ} =_{df} {u | u : {0, 1, ...ℓ − 1} → {0, 1}},

and

(2) for all u ∈ {0, 1}^{ℓ} and s ∈ B′

p′_{1}(φ′(u), s) = p′_{2}(φ′(u), s) = 0

is dense.

Proof Fix

q = (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}.

Applying 6.9 we can assume U has the indicated form U = {0, 1}^{ℓ} for some ℓ. Let u_{1}, u_{2}, ...u_{k} (k = 2^{ℓ}) enumerate the terminal vertices in U. For each i ≤ k choose some n(i) with

φ(u_{i})^{⌢}n(i) ∉ A.

Then let

φ′(u_{i}) = φ(u_{i})^{⌢}n(i)

and

φ′(u) = φ(u)

G. Hjorth 18 for u ∈ U not terminal. Let

T′ = T ∪ {(φ(u_{i})^{⌢}n(i), s) | i ≤ k, s ∈ B ∪ V̂ (q)}.

We let A′ = A and B′ = B. For (u, s) ∈ T we of course let p′_{i}(u, s) = p_{i}(u, s), i = 1, 2. For

(φ(u_{i})^{⌢}n(i), s) ∈ T′ \ T

we let

p′_{i}(φ(u_{i})^{⌢}n(i), s) = 0

if s ∈ B and

p′_{i}(φ(u_{i})^{⌢}n(i), t) = p_{i}(φ(u_{i}), t)

for t = V̂ (q). □ Corollary 6.11 For s ∈ (ω × ω)^{<ω}, the set of

q′ = (T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ P_{H} ⊗_{S_{1},S_{2}} P_{H}

for which there exists l ∈ ω with (1) s ∈ V̂′ ∪ B′, and

(2) U′ ⊃ {0, 1}^{l}, and
(3) and we have either s ∈ V̂ (q′) or for all u ∈ {0, 1}^{l}
p′_{1}(φ(u), s) = p′_{2}(φ(u), s) = 0

is open dense.

G. Hjorth 19

7 Some things to do with a generic

Definition For G ⊂ P_{H} ⊗_{S_{1},S_{2}} P_{H} meeting all the dense open sets from corollaries 6.6 and 6.8 we define

φ_{G} : 2^{<ω} → ω^{<ω}

by

φ_{G}(u) = û

if there exists

(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G

with φ(u) = û and u not terminal in U. Similarly,

ψ_{G} : (ω × ω)^{<ω} → (ω × ω)^{<ω}

is given by

ψ_{G}(s) = ŝ

if

∃(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G[ψ(s) = ŝ].

We then define

Φ_{G} : 2^{ω} → ω^{ω}

Φ_{G} : x ↦ ⋃_{n∈ω} φ_{G}(x|_{n})

and

Ψ_{G} : ω^{ω} × ω^{ω} → ω^{ω} × ω^{ω}

Ψ_{G} : (y, f) ↦ ⋃_{m∈ω} ψ_{G}(y|_{m}, f|_{m}).

We let

A_{G} = ⋃{x ∈ ω^{ω} | ∃(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G∃n ∈ ω(x|_{n} ∈ A)}.

We then let π_{1}(G) ⊂ P_{H} be the set

{(T′, p′) ∈ P_{H} | ∃(T, p_{1}, p_{2}, U′, A, V, B, ψ, σ) ∈ G(T′ ⊂ T, p′ ⊂ p_{1})},

and we let π_{2}(G) ⊂ P_{H} be the set

{(T′, p′) ∈ P_{H} | ∃(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G(T′ ⊂ T, p′ ⊂ p_{2})}.

We let

T_{π_{1}(G)}, T_{π_{2}(G)} ⊂ ω^{<ω} × (ω × ω)^{<ω}

be the subtrees indicated in section 4, from which we then obtain the corresponding Σ ∼_{1}^{1} sets

A_{π_{i}(G)} =_{df} A_{T_{π_{i}(G)}} = {(x, y) | ∃f∀n∀(T, p) ∈ π_{i}(G)(p(x|_{n}, (y|_{n}, f|_{n})) ≠ 0)}.

Lemma 7.1 For all G ⊂ P_{H} ⊗_{S_{1},S_{2}} P_{H} meeting the dense sets of 6.3, 6.6, 6.8, 6.11, and all x ∈ A_{G}, and all y ∈ ω^{ω}, if

(x, y) ∈ A_{π_{1}(G)}

then

(x, y) ∈ A_{π_{2}(G)}.

Proof Choose f ∈ ω^{ω} with

(x|_{n}, (y|_{m}, f|_{m})) ∈ T_{π_{1}(G)}

all n, m. If every such (x|_{n}, (y|_{m}, f|_{m})) ∈ T_{π_{2}(G)} then we are done, so instead suppose that there is some

(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G

with p_{2}(x|_{n}, (y|_{m}, f|_{m})) = 0 while that p_{1}(x|_{n}, (y|_{m}, f|_{m})) = 1 by assumption on T_{π_{1}(G)}. By clause (6)(g) of the definition of P_{H} ⊗_{S_{1},S_{2}} P_{H} we may assume that n is least with x|_{n} ∈ A and m is then least with p_{2}(x|_{n}, (y|_{m}, f|_{m})) = 0.

It then follows from clauses (6)(a) and (6)(b) of the definition of P_{H} ⊗_{S_{1},S_{2}} P_{H} that (x|_{n}, (y|_{m}, f|_{m})) is in the domain of σ,

σ(x|_{n}, (y|_{m}, f|_{m})) = (x|_{n}, (y|_{m}, w_{0}))

for some w_{0} ∈ ω^{m}, and for all

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ≤ (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ)

and (x|_{n}^{⌢}u_{1}, (y|_{m}^{⌢}v_{1}, f|_{m}^{⌢}w_{1})) ∈ T′ we have

p′_{1}(x|_{n}^{⌢}u_{1}, (y|_{m}^{⌢}v_{1}, f|_{m}^{⌢}w_{1})) = p′_{2}(σ′(x|_{n}^{⌢}u_{1}, (y|_{m}^{⌢}v_{1}, f|_{m}^{⌢}w_{1}))
= p′_{2}(x|_{n}^{⌢}u_{1}, (y|_{m}^{⌢}v_{1}, σ′_{x|_{n}}(y|_{m}^{⌢}v_{1}, f|_{m}^{⌢}w_{1}))).

In particular if we define h ∈ ω^{ω} by

h|_{k} = ŵ

if and only if there is some

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ G

with

σ′_{x|_{n}}(y|_{k}, f|_{k}) = ŵ

then

(x|_{n}, (y|_{m}, h|_{m})) ∈ T_{π_{2}(G)}

all n, m.

□

Lemma 7.2 For all G ⊂ P_{H} ⊗_{S_{1},S_{2}} P_{H} meeting the dense sets of 6.3, 6.6, 6.8, 6.11, and all x ∈ A_{G}, and all y ∈ ω^{ω}, if

(x, y) ∈ A_{π_{2}(G)}

then

(x, y) ∈ A_{π_{1}(G)}.

Proof Exactly symmetrical to the proof of 7.1, but with σ^{−1} taking up the part of σ. □

Lemma 7.3 For all G ⊂ P_{H} ⊗_{S_{1},S_{2}} P_{H} meeting the dense sets of 6.3, 6.6, 6.8, 6.11, and for all x ∈ ω^{ω},

x ∈ A_{G}

if and only if

x ∉ Φ_{G}[2^{ω}].

Proof If x ∉ A_{G} then by 6.3 we may successively find

q = (T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G

and longer and longer u ∈ U such that for any

q′ = (T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ≤ p

we must have φ′(u) ⊂ x. Since any such φ′ must be one to one, we can obtain a unique x̂ ∈ 2^{ω} which is the union of all the u’s as above, and hence satisfies Φ_{G}(x̂) = x.

Conversely if x ∈ A_{G} then from (4)(a) of the definition of the amalgamated forcing we have x ∉ Φ_{G}[2^{ω}]. □

Lemma 7.4 For i = 1, 2, and G ⊂ P_{H} ⊗_{S_{1},S_{2}} P_{H} meeting the dense sets of 6.3, 6.6, 6.8, 6.11, and x, y, f ∈ ω^{ω}, if

∀n, m ∈ ω((Φ(x)|_{n}, (y|_{m}, f|_{m})) ∈ T_{π_{i}(G)})

then

(y, f) = Ψ(y, f′)

for some f′ ∈ ω^{ω}.

Proof For this we need an observation. Claim: f is in the image of Ψ if and only if whenever m ∈ ω and

(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G

then

(y|_{m}, f|_{m}) ∉ B.

Proof of claim: This equivalence follows the argument of 7.3. (Claim□) This claim granted, we apply 6.11 to see that if s = (y|_{m}, f|_{m}) ∈ B for some

(T, p_{1}, p_{2}, U, A, φ, V, B, ψ, σ) ∈ G

then there would be some l ∈ ω and

(T′, p′_{1}, p′_{2}, U′, A′, φ′, V′, B′, ψ′, σ′) ∈ G

with

p′_{i}(φ(x|_{l}), s) = 0.
□

Putting together the last few claims we finally have:-

Proposition 7.5 There is a countable collection (D_{i})_{i} of open dense subsets of P_{H} ⊗_{S_{1},S_{2}} P_{H} such that for any filter G meeting all these dense open sets we have:-

(1) For all z ∈ ω^{ω} \ Φ_{G}[2^{ω}] and for all y ∈ ω^{ω}

(z, y) ∈ A_{π_{1}(G)} ⇔ (z, y) ∈ A_{π_{2}(G)}.

(2) If z = Φ_{G}(x) ∈ Φ_{G}[2^{ω}] then for all y ∈ ω^{ω} we have

(Φ_{G}(x), y) ∈ A_{π_{1}(G)} ⇔ (x, y) ∈ A_{S_{1}}
(Φ_{G}(x), y) ∈ A_{π_{2}(G)} ⇔ (x, y) ∈ A_{S_{2}}.

8 Generalities on finding generics

There are no proofs in this section. The various assertions should not need them. Notation Let PO be the set of x ∈ 2^{ω×ω} such that ≤_{x} defined by

n ≤_{x} m

if and only if

x(n, m) = 1

provides a partial order on ω. For y ∈ 2^{ω×ω} and n ∈ ω let

D_{y,n} = {m|y(n, m) = 1}.

Then let DP O be the set of (x, y) ∈ PO×2^{ω×ω} such that for all n we have D_{y,n} dense in the partially ordered set

(ω; ≤_{x}).

Lemma 8.1 DPO is a Π ∼_{2}^{0} subset of 2^{ω×ω} × 2^{ω×ω}. Lemma 8.2 There is a continuous function

γ_{ω} : DPO → 2^{ω}

such that for all (x, y) ∈ DPO the set

{n ∈ ω|(γ(x, y))(n) = 1}

provides a filter on (ω; ≤_{x}) meeting each A_{y,n}. Notation Let S(P_{H}) be the set of y ∈ 2^{2^{<ω}×(ω×ω)^{<ω}} such that the set

S(y) =_{df} {(u, s)|y(u, s) = 1}

is closed downwards. Let F(P_{H}) be the set of z ∈ 2^{P_{H}} such that

G(z) = {(T, p)|z(T, p) = 1}

provides a filter on P_{H}. We view 2^{P_{H}} as having the product topology, under which it is homeomorphic to the Cantor space 2^{ω}.

S(P_{H}) can be viewed as a closed subset of the space

({0, 1})^{2^{<ω}×(ω×ω)^{<ω}}.

F(P_{H}) is a Π ∼_{2}^{0} subset of 2^{P_{H}}. Hence both these subspaces are Polish in their own right.

To each y_{1}, y_{2} ∈ S(P_{H}) we can continuously associate a partial order on ω isomorphic to P_{H} ⊗_{S(y_{1}),S(y_{2})} P_{H}, and thus by lemma 8.2:

Lemma 8.3 Let (O_{i})_{i∈ω} be a sequence of dense open subsets of P_{H}. Then we may find a continuous function

γ_{P_{H}×P_{H}} : S(P_{H}) × S(P_{H}) → F(P_{H}) × F(P_{H})

such that for all (y_{1}, y_{2}) ∈ S(P_{H}) × S(P_{H}), if

(z_{1}, z_{2}) = γ_{P_{H}×P_{H}}(y_{1}, y_{2})

then (1) G(z_{1}) ∩ O_{i} ≠ 0 all i ∈ ω;

(2) G(z_{2}) ∩ O_{i} ≠ 0 all i ∈ ω;

(3) there is a corresponding filter G_{y_{1},y_{2}} ⊂ P_{H} ⊗_{S(y_{1}),S(y_{2})} P_{H} meeting all the dense open sets of section 6 with

π_{1}(G_{y_{1},y_{2}}) = G(z_{1})
π_{2}(G_{y_{1},y_{2}}) = G(z_{2}).

Observe that we can reorganize γ_{P_{H}×P_{H}} into its coordinate functions and find a pair

γ_{1} : S(P_{H}) × S(P_{H}) → F(P_{H}),
γ_{2} : S(P_{H}) × S(P_{H}) → F(P_{H}),

such that if

(z_{1}, z_{2}) = gamma_{P_{H}×P_{H}}(y_{1}, y_{2})

then for i ∈ {1, 2} we have z_{i} = γ_{i}(y_{1}, y_{2}). We implicitly use this reorganization in the next section.

9 Finishing up

I understand the next lemma to be folklore.

Lemma 9.1 Equality of Π ∼_{n}^{1} sets is Π ∼_{n+1}^{1} complete in the codes.

Proof For notational simplicity we assume n = 1. Then given any Π ∼_{2}^{1} set P ⊂ 2^{ω} we can appeal to the tree representation for Σ ∼_{1}^{1} sets and continuously assign

x ↦ T_{x}

to each point in 2^{ω} a tree T_{x} ⊂ (ω × ω)^{<ω} such that x ∈ P if and only if

∀y ∈ ω^{ω}∃f ∈ ω^{ω}∀n((y|_{n}, f|_{n}) ∈ T_{x}).

Thus if we assign to each x the Π ∼_{1}^{1} set

A_{x} = {y ∈ ω^{ω} : ∀f ∈ ω^{ω}∃n((y|_{n}, f|_{n}) ∉ T_{x})}

then we have

x ∈ P

if and only if

A_{x} = ∅.

Thus we have reduced membership in P to equality of a corresponding Π ∼_{1}^{1} set with the empty set. It is easily checked that the assignment

x ↦ A_{x}

is continuous in the codes. □

Theorem 9.2 Assume AD^{L(ℝ)}. Then there is no injection in L(ℝ) from Π ∼_{n+1}^{1} into Π ∼_{n}^{1}.

Proof Suppose instead we have

Θ : Π ∼_{n+1}^{1} ↪ Π ∼_{n}^{1}

inside L(ℝ). For the sake of concreteness let us assume n = 1.

Then by the basis theorem for Σ ∼_{1}^{2} we may assume that Θ is itself Σ ∼_{1}^{2}, and hence by the uniformization theorem that there is a function in L(ℝ)

θ : F(P_{H}) → 2^{2^{<ω}×ω^{<ω}}

such that for all z_{1}, z_{2} ∈ F(P_{H}) we have

{x ∈ 2^{ω} : ∀y((x, y) ∈ A_{G(z_{1})})} = {x ∈ 2^{ω} : ∀y((x, y) ∈ A_{G(z_{2})})}

if and only if

{x ∈ 2^{ω}|∀y ∈ ω^{ω}∃n((x|_{n}, y|_{n}) ∉ θ(z_{1}))} = {x ∈ 2^{ω}|∀y ∈ ω^{ω}∃n((x|_{n}, y|_{n}) ∉ θ(z_{2}))}.

Since AD implies that all functions on Polish spaces are Baire measurable, we may find a comeager set on which θ is continuous. This means that there is a countable collection (O_{i})_{i∈ω} of open dense subsets of P_{H} such that θ is continuous on the Π ∼_{2}^{0} subset D of F(P_{H}) consisting of {z ∈ F(P_{H})} such that

∀i(G(z) ∩ O_{i} ≠ 0).

But now applying 8.3 we may find continuous functions

Γ_{1}, Γ_{2} : S(P_{H}) × S(P_{H}) → D

such that for all (y_{1}, y_{2}) ∈ S(P_{H}) × S(P_{H}) we have that if Γ_{i}(y_{1}, y_{2}) = z_{i} (i = 1, 2) then there is G_{y_{1},y_{2}} ⊂ P_{H} ⊗_{S_{1},S_{2}} P_{H} meeting all the dense sets of §6 with π_{1}(G_{y_{1},y_{2}}) = G(z_{1}) and π_{2}(G_{y_{1},y_{2}}) = G(z_{2}) (where π_{1}, π_{2} are defined as at the start of section 7). Claim: If Γ_{1}(y_{1}, y_{2}) = z_{1}, Γ_{2}(y_{1}, y_{2}) = z_{2}, then

{x ∈ ω^{ω} : ∀r((x, r) ∈ A_{G(z_{1})})} = {x ∈ ω^{ω} : ∀r((x, r) ∈ A_{G(z_{2})})}

if and only if

{x ∈ 2^{ω} : ∀r((x, r) ∈ A_{S(y_{1})})} = {x ∈ 2^{ω} : ∀r((x, r) ∈ A_{S(y_{2})})}.

Proof of claim: We will use 7.5 several times in this proof. For this we need to keep in mind that

A_{π_{1}(G_{y_{1},y_{2}} )} = A_{G(z_{1})},
A_{π_{2}(G_{y_{1},y_{2}} )} = A_{G(z_{2})}.

Suppose first that

{x ∈ ω^{ω} : ∀r((x, r) ∈ A_{G(z_{1})})} ≠ {x ∈ ω^{ω} : ∀r((x, r) ∈ A_{G(z_{2})})}.

Without loss we may assume there is some x_{0}, r_{0} with x_{0} ∈ {x ∈ ω^{ω} : ∀r((x, r) ∈ A_{G(z_{1})})} but

(x, r_{0}) ∉ A_{G(z_{2})}.

Then by the statement of 7.5(1) we must have some x̂ with

Φ_{G_{y_{1},y_{2}}} (x̂) = x_{0}.

By 7.5(2) we have for all r ∈ ω^{ω}

(x_{0}, r) ∈ A_{G(z_{1})} ⇔ (x̂, r) ∈ A_{S(y_{1})}
(x_{0}, r) ∈ A_{G(z_{2})} ⇔ (x̂, r) ∈ A_{S(y_{2})}

and thus

(x̂, r_{0}) ∉ A_{S(y_{2})}

while

∀r((x̂, r) ∈ A_{S(y_{1})}).

Thus

{x ∈ 2^{ω} : ∀r((x, r) ∈ A_{S(y_{1})})} ≠ {x ∈ 2^{ω} : ∀r((x, r) ∈ A_{S(y_{2})})}.

So now for the other direction. Let us assume x_{0}, r_{0} have been chosen so that ∀r((x_{0}, r) ∈ A_{S(y_{1})}) but ((x_{0}, r_{0}) ∉ A_{S(y_{2})}); the other case, with y_{1} and y_{2} interchanged, is essentially identical. Let x̂ = Φ_{G(y_{1},y_{2})}(x_{0}). Then by 7.5(2) we have for all r that

(x̂, r) ∈ A_{G(z_{1})}

but

(x̂, r_{0}) ∉ A_{G(z_{2})}.
(Claim□)

But then the composition

(y_{1}, y_{2}) ↦ (θ(Γ_{1}(y_{1}, y_{2})), θ(Γ_{2}(y_{1}, y_{2})))

gives a continuous reduction of the equivalence relation of coding the same Π ∼_{2}^{1} set to the equivalence relation of coding the same Π ∼_{1}^{1} set. Since the former is Π ∼_{3}^{1} complete while the later is only Π ∼_{2}^{1}, we have our desired contradiction.

□

References

[1] A. Andretta, Notes on descriptive set theory, unpublished manuscript, University of Turino, 2000.

[2] G. Hjorth, A dichotomy for the definable universe, Journal of Symbolic Logic, vol. 60(1995), pp. 1199-1207.

[3] G. Hjorth, An absoluteness principle for Borel sets, Journal of Symbolic Logic, vol. 63(1998), pp. 663–693.

[4] G. Hjorth, Classification and Orbit Equivalence Relations, American Mathematical Society Mathematical Surveys and Monographs Series, Rhode Island, 2000.

[5] D.A. Martin, Y.N. Moschovakis, J.R. Steel, The extent of definable scales, Bulletin of the American Mathematical Society, vol. 6(1982), pp. 435–440.

[6] D.A. Martin, J.R. Steel, The extent of scales in L(ℝ), Cabal Seminar 79-81, (eds. A.S. Kechris, D.A. Martin, J.R. Steel), vol. 1019, pp.86–96.

[7] Y.N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam, 1980.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555