Glimm-Effros for coanalytic equivalence relations

Greg Hjorth

November 17, 2006

Abstract

Assuming every real has a sharp, we prove that for any Π ∼_{1}^{1} equivalence relation either Borel reduces E_{0} or in a Δ ∼_{3}^{1} manner allows the assignment of bounded subsets of ω_{1} as complete invariants.

1 Summary

The study of equivalence relations has become a topical area in descriptive set theory.

Within this area certain directions have been emphasized ahead of others. Perhaps the majority of the papers concern themselves solely with Borel equivalence relations, and naturally enough since the study of Borel equivalence relations connects with areas of concern entirely outside logic. Here one overwhelming theorem casts its shadow across the entire field.

Theorem 1.1 (Harrington-Kechris-Louveau) Let E be a Borel equivalence relation. Then exactly one of the following two options hold:

(I) E_{0} ≤_{B} E – in other words there is a Borel function f from 2^{ℕ} to the space on which E is defined such that for all x, y ∈ 2^{ℕ}

∃N∀m > N(x(m) = y(m)) ⇔ f(x)Ef(y);

(II) E ≤_{B} id(ℝ) – in other words there is a Borel function from the space on which E is defined to ℝ such that

xEy ⇔ f(x) = f(y).

This is sometimes known as the Glimm-Effros dichotomy on account precursors being proved by Glimm and then later Effros.

Among the study of non-Borel equivalence relations, two dichotomy theorems are especially note worthy:

Theorem 1.2 (Silver) Let E be a Π ∼_{1}^{1} equivalence relation. Then either E has countably many equivalence classes or there is a perfect set of E-inequivalent points.

Theorem 1.3 (Burgess) Let E be a Σ ∼_{1}^{1} equivalence relation. Then either E has at most ℵ_{1} many equivalence classes or there is a perfect set of E-inequivalent reals.

As one moves up the projective hierarchy, the analogues of these theorems have been intensively investigated under determinacy assumptions. Kechris showed that appropriate bound for Σ ∼_{2}^{1} equivalence relations is ℵ_{1}, and it follows from [5] that for Π ∼_{2}^{1} we get the same. The results for the first two levels of the projective heirarchy then generalize in line with the periodicity theorems of [11]. This all echoes the computations of the projective ordinals in L(ℝ) , as found in [8], [11], and therefore is hardly discordant with the concerns of modern set theory.

Little serious concern has been directed towards the appropriate versions of Glimm-Effros at higher levels of the projective hierarchy. Even granting the close connections of higher versions of Silver’s theorem with the traditional concerns of set theorists, this should be viewed as surprising.

For the purpose of discussion let us assume that AD, the axiom of determinacy, holds inside L(ℝ). Let us write |A|_{L(ℝ)} for the ZF-cardinality of the set A inside L(ℝ) – thus |A|_{L(ℝ)} ≤ |B|_{L(ℝ)} if there is an injection inside L(ℝ) from A to B.

Here it turns out that Harrington-Kechris-Louveau provides a theorem about the cardinal structure of L(ℝ).

Theorem 1.4 (Harrington-Kechris-Louveau, in effect; assume AD^{L(ℝ)}) Let E be a Borel equivalence relation on ℝ. Then exactly one of:

(I) |P(ℕ)/Fin|_{L(ℝ)} ≤ |ℝ/E|_{L(ℝ)};

(II) |ℝ/E|_{L(ℝ)} ≤ |ℝ|_{L(ℝ)}.

There is an analog for the pure cardinal theory of L(ℝ):

Theorem 1.5 (Hjorth; assume AD^{L(ℝ)}). Let A ∈ L(ℝ). Then exactly one of:

(I) |P(ℕ)/Fin|_{L(ℝ)} ≤ |A|_{L(ℝ)};

(II) for some ordinal α, |A|_{L(ℝ)} ≤ |P(α)|_{L(ℝ)}.

The purpose of this paper is to take one step towards filling in the gaps between these two extremes. Given a Wadge class Γ, we would like to know the version of (II) which serves for equivalence relations E ∈ Γ. The contribution of this paper is towards understanding Π ∼_{1}^{1}.

Theorem 1.6 Assume every real has a sharp. Let E be a Π ∼_{1}^{1} equivalence relation. Then either: (I) E_{0} ≤_{B} E; or (II) there is a Δ ∼_{3}^{1} in the codes assignment of bounded subsets of ω_{1} as complete invariants to the

equivalence classes.

As a key step along the way we prove a general dichotomy theorem using the ideas of [5] to adapt the basic argument of [4]. This hitherto overlooked results can be used to prove the Glimm-Effros dichotomy theorems of [2] and [3]. Note that this theorem is proved without appeal to the axiom of choice.

Theorem 1.7 (ZF) Let κ be an infinite cardinal. Let T, T̄ ⊂ (κ × ω × ω)^{<ω} be trees. Assume: (i) p[T] = (ω^{ω} × ω^{ω}) \ p[T̄] = E; (ii) p[T̄] continues to define the complement of an equivalence relation even after we add a Cohen real.

Then either:

(I) E_{0} ≤_{B} E; or, (II) there is

U : ω^{ω} → P(κ)

such that for all x, y ∈ ω^{ω},

xEy ⇔ U(x) = U(y).

It should be mentioned that [6] proves an identical theorem to 1.6 for Σ ∼_{1}^{1} equivalence relations under the assumption of sharps, or equivalently, Σ ∼_{1}^{1} determinacy. In all honesty I should say that I have more cause for sorrow here than triumph, since it seems plausible that a result along these lines should be true for Δ ∼_{2}^{1} equivalence relations under suitable determinacy assumptions, and I have no inkling how this could be proved.

2 Definitions and background

We assume the reader is familiar with the basic set theoretical notions forcing and constructibility, as can be found in [9], along with some of the touch stones of modern descriptive set theory, such as tree, as can be found in [11]. We recall some of the concepts from the descriptive set theory of equivalence relations. Infinitary logic, admissible sets, and Barwise compactness provide a driving force through much of the arguments; while [10] provides an excellent reference, these notions fall slightly outside the traditional purview of set theory and are therefore summarized below.

2.1 The descriptive set theory of equivalence relations

Although this paper is more properly considered a work of higher set theory than the classical set theory of say [7], the notion of Borel reducibility is still salient.

Definition Given E, F on Polish spaces X, Y, we say that E is Borel reducible to F,

E ≤_{B} F,

if there is a Borel function

f : X → Y

such that for all x_{1}, x_{2} ∈ X

x_{1}Ex_{2} ⇔ f(x_{1})F f(x_{2}).

Definition For X a Polish space we use id(X) to denote the identity equivalence relation on X – {(x, x) : x ∈ X}. E_{0} denotes the equivalence relation of eventual agreement on infinite binary sequences:

xE_{0}y ⇔ ∀^{∞}n(x(n) = y(n)).

Here we have id(2^{ω}) <_{B} E_{0} – that is to say, there is a Borel reduction from the first to the second, but not the other way.

Definition For E an equivalence relation on a set X and x ∈ X we use [x]_{E} to denote the E-equivalence class of x. We use X/E to denote the collection of all E-equivalence classes.

Definition Let Γ be a point class, in the sense of [11]. We say that an equivalence relation E on a space X admits a Γ in the codes assignment of elements of 2^{<ω_{1}} as complete invariants if there is a function

f : X → (2^{ω×ω}, 2^{ω})

in Γ along with an injection

f̂: X/E ↪ 2^{<ω_{1}}

such that for all x ∈ X with h = f̂([x]_{E}) ∈ 2^{α} and (a, b) = f(x) we have

(α; {β : h(β) = 1}, ∈) ≅ (ω; {n : b(n) = 1}, {(n, m) : a(n, m) = 1}).

2.2 Infinitary logic

The reader should consult [10] or [1]. This subsection is the skeleton sketch.

Definition Given a propositional language L we use L_{∞,0} to to denote the result of closing the class of propositions under negation as well as conjunctions and disjunctions of arbitrary size.

Infinitary logic differs from traditional first order logic in that the notions of proof theoretical and semantical consistency diverge. We clarify the meaning that consistency will take for this paper.

Definition A proposition ψ ∈ L_{∞,0} is consistent if in some generic extension there exists a model for ψ.

It is an easy absoluteness argument to see that any two transitive models satisfying a sufficiently large fragment of ZFC in which ψ is hereditarily countable will agree as to whether it has a model. Thus consistency is Δ_{1} in the Levy hierarchy.

For later purposes we need a sharper result: Consistency in our sense is uniformly Π_{1} over any admissible structure containing ψ. This involves a game theoretical explication, where we have in mind the kind of infinite length games found in [11].

Definition For ψ ∈ L_{∞,0} let F_{ψ} ⊂ L_{∞,0} be the fragment generated by ψ. Let G_{ψ} be the following closed^{1} game of length ω: I and II alternate playing elements of F_{ψ}. II can play any element at all of F_{ψ}, but I’s moves are tightly constrained, and if I is ever unable to make a legal move then II wins.

(0) I must begin with the move ψ;

(i) if II plays ϕ ∨ ¬ϕ, then I must at the next turn play ϕ or ¬ϕ;

(ii) if I has previously played ⋀_{α} ϕ_{α} and II plays some ϕ_{β}, then I must immediately respond with ϕ_{β}; (iii) if I has previously played ⋁_{α} ϕ_{α} and II plays ⋁_{α} ϕ_{α} then I must respond with some ϕ_{β}; (iv) if I has previously played ¬ ⋀_{α} ϕ_{α} and II plays ¬ ⋀_{α} ϕ_{α} then I must respond with ⋁_{α} ¬ϕ_{α};

(v) if I has previously played ¬ ⋁_{α} ϕ_{α} and II plays ¬ ⋁_{α} ϕ_{α} then I must respond with ⋀_{α} ¬ϕ_{α}; (vi) if I has previously played ¬¬ϕ and II plays ¬¬ϕ, then I must play ϕ; (vi) at no stage can two of I’s previous moves consist at one move in ϕ and at another move ¬ϕ.

II wins if I is ever unable to make a next move in accordance with these requirements. I wins if the game keeps going for infinitely many turns.

One should think of this game as a interrogation between II and I. I begins by asserting ψ, and then II steadily asks questions about how I might imagine a model of this proposition to be formed. I wins if the story continues indefinitely without contradiction; II wins if I’s account is shown at some stage to be absurd.

The next couple of lemmas are well known and standard.

Lemma 2.1 Let ψ, G_{ψ} be as above. Assume ψ is hereditarily countable.

Then ψ has a model if and only if I wins G_{ψ}.

Proof (Sketch) First assume that ψ has a model. Then I wins by simply by responding to each of II’s “questions” with the answer found in the model.

Conversely, let I have a winning strategy in G_{ψ}. Our assumptions give that F_{ψ} is countable, and so we can let II make a maximal play which mentions every element of F_{ψ} infinitely often. We take the model which consists of the collection of atomic propositions asserted at some stage by I. It is then a routine induction on logical complexity to show that this model satisfies some ϕ ∈ F_{ψ} if and only if I has at some point played ψ. □

Lemma 2.2 Let P_{ψ} be the collection of legal positions in the game G_{ψ}. Then I wins if and only if there is no

π : P_{ψ} → γ ∪ {∞},

for some ordinal γ, such that at each position p ∈ P:

(i) if I is to move then π(p) = sup{π(p^{⌢}ϕ) : p^{⌢}ϕ ∈ P_{ψ}};

(ii) if II is to move then π(p) = inf{π(p^{⌢}ϕ) + 1 : ϕ ∈ F_{ψ}};
(iii) π(⟨ϕ⟩) ≠ ∞.

Proof (Sketch) First suppose we have such function π : P_{ψ} → γ. Note that our assumptions (i) and (ii) give π(p) = 0 if and only if it is I’s turn to move and there is no legal move to be made. Thus II can fashion a winning strategy by driving the ordinal down until it hits zero.

Conversely, let us just attempt to define by induction π with the initial requirement that π(p) = 0 if it is I’s move and there is no legal response, and then recursively continuing with

(i) if I is to move then π(p) = sup{π(p^{⌢}ϕ) : P^{⌢}ϕ ∈ P_{ψ}} provided all such π(p^{⌢}ϕ) have been given ordinal values; (ii) if II is to move then π(p) = inf{π(p^{⌢}ϕ) + 1 : ϕ ∈ F_{ψ}} provided at least one such π(p^{⌢}ϕ) has been given an ordinal value.

We spare the reader the details of how one formalizes such a transfinite recursion. It is a standard set theoretical construction; at stage α we will have defined π^{−1}[α + 1] = {p : π(p) ≤ α}.

Once this has been continued as far as it will permit, we set π(p) = ∞ if p has not previously been assigned an ordinal value. By assumption, π(⟨ψ⟩) = ∞, and I’s winning strategy is to always play to keep π(p) = ∞. □

1Here closed is in the sense of [11]

Lemma 2.3 There is a Π_{1} formula Φ such that for any ψ ∈ L_{∞,0} and admissible M containing ψ,

M ⊧ Φ(ψ)

if and only if ψ is consistent.

Proof (Sketch) By 2.1, it suffices to see I winning G_{ψ} is uniformly Π_{1} over M, and this in turn follows from the proof of 2.2. Inside the admissible we can recursively define

α ↦ π^{−1}[α + 1]

using the description from before. This will be a Δ_{1} recursion, and hence defined by a Δ_{1} formula over M, and hence total and calculated the same in M as in V. It is a routine application of admissibility to see that π(p) = ∞ if and only if there is no α ∈ M with π(p) = α, and this statement itself is Π_{1} over M. □

Notation A set is Σ ∼_{1} over a structure M if there is some Σ_{0} formula Ψ and some a ∈ M such that A equals the set of b ∈ M such that

M ⊧ ∃x_{1}∃x_{2}...∃x_{n}Ψ(a, b, x_{1}, ...x_{n}).

Lemma 2.4 Let M be admissible and T ⊂ L_{∞,0} ∩ M be Σ ∼_{1} over M. Suppose that every X ∈ M with X ⊂ T is consistent.

Then T is consistent.

Proof Since our definition of consistency is absolute between generic extensions, we may assume M countable; then the lemma just reduces to the usual statement of Barwise compactness.

Alternately we can give a direct game theoretic proof, where the strategy of the first player is to always maintain that the run of moves so far along with T preserves the property that any subset inside M is consistent in our sense. Using that inconsistency is Σ_{1}, the usual proof of Barwise carries through without tearing. □

Lemma 2.5 Let L, L′, L′′ be non-empty languages with L = L′ ∩ L′′. Let ϕ′ ∈ L′_{∞,0}, ϕ′′ ∈ L′′_{∞,0} with ϕ′ ⇒ ϕ′′. Then there is ϕ ∈ L_{∞,0} with

ϕ′ ⇒ ϕ ⇒ ϕ′′

(i.e. ϕ′ ∧ ¬ϕ and ϕ ∧ ¬ϕ′′ are both inconsistent).

Proof (Sketch) Suppose instead there is no such interpolant.

We define a game G_{ϕ′,¬ϕ′′}, a variant of G_{ψ} given earlier. At each turn II can plays some τ′ ∈ L′_{∞,0} and some τ′′ ∈ L′′_{∞,0}. I then responds with some σ′ ∈ L′_{∞,0} and some σ′′ ∈ L′′_{∞,0}. Again we stay inside the fragments generated by ϕ′, ϕ′′. In analogy to before, I begins with ϕ′, ¬ϕ′′. The conditions (i)-(vi) are transplanted in the obvious way:-

(i’) if τ′ = ϕ ∨ ¬ϕ, then I must at the next turn play ϕ or ¬ϕ;

(ii’) if I has previously played ⋀_{α} ϕ_{α} and τ′ = ϕ_{β}, then I must immediately respond with σ′ = ϕ_{β}; (iii’) if I has previously played ⋁_{α} ϕ_{α} and τ′ = ⋁_{α} ϕ_{α} then I must respond with some ϕ_{β} = σ′; (iv’) if I has previously played ¬ ⋀_{α} ϕ_{α} andτ′ = ¬ ⋀_{α} ϕ_{α} then I must respond with σ′ = ⋁_{α} ¬ϕ_{α}; (v’) if I has previously played ¬ ⋁_{α} ϕ_{α} and τ′ = ¬ ⋁_{α} ϕ_{α} then I must respond with σ′ ⋀_{α} ¬ϕ_{α}; (vi’) if I has previously played ¬¬ϕ and II plays τ′ = ¬¬ϕ, then I must play σ′ = ϕ.

Similarly there will conditions (i”)-(vi”) which have τ′′ for τ′ and σ′′ for σ′.

(vii) now becomes the requirement that in the union of all the moves played by I, all the τ′’s and τ′′’s, there is no outright contradiction.

Here one can adapt the usual proof of the Craig interpolation theorem to show the existence of a winning strategy for the first player: I just maintains that if ρ′ is the conjunction of the propositions in L′_{∞,0} asserted by I and ρ′′ is the conjunction of the propositions in L′′_{∞,0} asserted by I, then there is no ρ ∈ L_{∞,0} such that

ρ′ ⇒ ρ ⇒ ¬ρ′′.

We then go to a generic extension in which ϕ′, ϕ′′ are hereditarily countable. We let II run the complete play, asking every question in the respective fragments infinitely often. We get a model of L′ ∪ L′′, since there is no disagreement on the common parts of the language, by setting M ⊧ ψ, for ψ an atomic proposition, if at some point in I’s play ψ appears. Following the proof of 2.1 we get

M ⊧ ϕ′, ¬ϕ′′,

with a contradiction to the hypotheses of the lemma. □

Note for future references that the proof of the last lemma actually gives an interpolant in any admissible structure M containing ϕ′ and ϕ′′: The point is that we can adapt (vii) to be the requirement that there be no interpolant in M. Note moreover from 2.3 we have that there is a Σ_{1} formula, Ψ, such that

M ⊧ Ψ(ϕ′, ϕ′′, ϕ)

if and only if ϕ is an interpolant between ϕ′ and ϕ′′.

3 Adapting Harrington-Shelah

We adapt the framework of [5] to the combinatorics of [4].

Definition We let L^{x} be the propositional language consisting of basic propositions {p_{n}^{x} : n ∈ ω}. For a ∈ 2^{ω} we define the L^{x} model M_{a} by setting

M_{a} ⊧ p_{n}^{x}

if and only if a(n) = 1. The natural extension then is for φ ∈ L_{∞,0}^{x} we set

a ⊧ φ

if M_{a} ⊧ φ.

There are similar definitions to come, building on this kind of methodology in a way that is initially confusing to describe formally. We can at least pause to state the main result in a way that is completely precise, and much more revealing than the statement at 1.7:

Theorem 3.1 (ZF) Let κ be an infinite cardinal. Let T, T̄ ⊂ (ω × ω × κ)^{<ω} be trees. Let γ > κ be such that L_{γ}[T, T̄] is admissible. Assume:

(i) p[T] = (ω^{ω} × ω^{ω}) \ p[T̄] = E;

(ii) p[T̄] continues to define the complement of an equivalence relation even after we add a Cohen real.

Then either:

(I) E_{0} ≤_{B} E; or,

(II) in every generic extension and every a, b ∈ 2^{ω} which are E-inequivalent there is some

φ ∈ L_{0,∞}^{x} ∩ L_{γ}[T, T̄]

such that

a ⊧ φ,
b ⊧ ¬φ,

and in no other generic extension does there exist c, d ∈ 2^{ω}, f ∈ κ^{ω} with

c ⊧ φ,

d ⊧ ¬φ,

(a, b, f) ∈ [T].

In other words, if E_{0} does not embed into E, then we may find find infinitary formulas in the least admissible containing the trees T and T̄ which are in some absolute sense E-invariant and serve to separate distinct E classes.

1.7 follows 3.1 as a corollary: We can take γ to have the same size as κ, so that there are only κ many infinitary formulas in the admissible. We let (ϕ_{α})_{α∈κ} be L_{∞,0}^{x} ∩ L_{γ}[T, T̄]. We let U(a) be the set of all α < κ such that

a ⊧ ϕ_{α}

and {b : b ⊧ ϕ_{α}} is E-invariant.

More definitions. More of the same. We will need other propositional languages to talk about more than one real simultaneously and more than one attempt to witness a pair of reals is in p[T] or p[T̄].

Definition We let L^{y}, L^{z} be the propositional languages consisting of basic propositions {p_{n}^{y} : n ∈ ω}, {p_{n}^{z} : n ∈ ω} respectively. For a ∈ 2^{ω} we define the L^{y} model M_{a}^{y} by setting

M_{a} ⊧ p_{n}^{y}

if and only if a(n) = 1. The natural extension then is for φ ∈ L_{∞,0}^{y} we set

a ⊧ φ

if M_{a}^{y} ⊧ φ. Similarly for M_{a}^{z} and φ ∈ L_{∞,0}^{z}. Given φ ∈ L_{∞,0}^{x} we define φ(y) and φ(z) by replacing all appearances of p_{n}^{x} by p_{n}^{y} and p_{n}^{z} respectively. We then go on and make the same kinds of substitutions for φ ∈ L_{∞,0}^{y} and φ(x) and φ(z) or φ ∈ L_{∞,0}^{z} and φ(x) and φ(y).

So much for the reals themselves. We also need to ground a similar notation for witnesses to being in E and its complement. From now on fix T T̄ as in the statement of the 3.1. Let γ > κ be such that

L_{γ}[T, T̄]

is admissible. We can also make a helpful technical assumption on T, with the consequence that it projects to an equivalence relation in all generic extensions.

Note first of all that given T there are canonical trees T^{2} and rT which project to the sets {(a_{1}, a_{3}) : ∃a_{2}((a_{1}, a_{2}), (a_{2}, a_{3}) ∈ p[T]} and {(b, a) : (a, b) ∈ p[T]}. I will assume that these canonical trees appear as isomorphic copies inside T.

First one defines rT to be {(u, v, w) : (v, u, w) ∈ T }, and then we replace T by the disjoint union of T and rT.

Then we define T^{m} to be the set of (u, v, w) ∈ 2^{n} × 2^{n} × κ^{n}, n ∈ ω, such that

(u, ⟨(w)_{0,0,0}, (w)_{0,0,1}, ..(w)_{0,0,n−1}⟩, ⟨(w)_{0,1,0}, ...(w)_{0,1,n−1}⟩) ∈ T,
(⟨(w)_{0,0,0}, (w)_{0,0,1}, ..(w)_{0,0,n−1}⟩, ⟨(w)_{1,0,0}, ...(w)_{1,1,n−1}⟩, ⟨(w)_{1,1,0}, ...(w)_{1,1,n−1}⟩) ∈ T,
...
(⟨(w)_{m−1,0,0}, ..(w)_{m−1,0,n−1}⟩, v, ⟨(w)_{m−1,1,0}, ...v_{m−1,1,n−1}⟩) ∈ T,

where

(α, i, j, k) → (α)_{i,j,k}
κ × ω × ω × ω ↪ κ

is an injection provided by Gödel coding. Then we replace T by the disjoint union of the T^{m}’s.

We may similarly assume that in all generic extensions p[T̄] is symmetric. We may also fold in to T̄ suitable concatenations of T and T̄ so that in any extension if (a, b) ∈ p[T] and (b, c) ∈ p[T̄], then (a, c) ∈ p[T̄].

Definition We let L^{x,z,r} be the propositional language with

{p_{n}^{x} : n ∈ ω}, {p_{n}^{z} : n ∈ ω}, {p_{r(n)=α} : n ∈ ω, α ∈ κ}.

For a, b ∈ 2^{ω}, f ∈ κ^{ω} we define

M_{a,b,f}^{x,z,r}

by setting p_{n}^{x} true if a(n) = 1, p_{n}^{z} true if b(n) = 1, and p_{r(n)=α} if f(n) = α. As before,

(a, b, f) ⊧ φ

if

M_{a,b,f}^{x,z,r} ⊧ φ.

Similarly we let L^{y,z,s} be the propositional language with

{p_{n}^{y} : n ∈ ω}, {p_{n}^{z} : n ∈ ω}, {p_{s(n)=α} : n ∈ ω, α ∈ κ}.

For a, b ∈ 2^{ω}, f ∈ κ^{ω} we define

M_{a,b,f}^{y,z,s}

by setting p_{n}^{y} if a(n) = 1, p_{n}^{z} if b(n) = 1, and p_{s(n)=α} if f(n) = α. Again,

(a, b, f) ⊧ φ

if

M_{a,b,f}^{y,z,s} ⊧ φ.

For φ ∈ L^{x,z,r} we define φ(y, z, s) by replacing appearances of p_{n}^{x} by p_{n}^{y}, p_{r(n)=α} by p_{s(n)=α}.

The next two lemmas are routine consequences of the definitions. Lemma 3.2 There are ψ_{T}^{r} ∈ L_{∞,0}^{x,z,r}, ψ_{T}^{s} ∈ L_{∞,0}^{y,z,s} such that in all generic extensions

(a, b, f) ⊧ ψ_{T}^{r}

if and only if

(a, b, f) ⊧ ψ_{T}^{s}

if and only if

(a, b, f) ∈ [T].

Lemma 3.3 There are ψr ; T̄ ∈ L_{∞,0}^{x,z,r}, ψs ; T̄ ∈ L_{∞,0}^{y,z,s} such that in all generic extensions

(a, b, f) ⊧ ψr ; T̄

if and only if

(a, b, f) ⊧ ψs ; T̄

if and only if

(a, b, f) ∈ [T̄].

Definition Let S_{0} be the set of all θ ∈ L_{∞,0}^{x} ∩ L_{γ}[T, T̄] such that

θ ∧ ψ_{T}^{r} ∧ ¬θ(z)

is inconsistent.

Since our notion of consistency coincides with the existence of a model for sentences in L_{ω_{1},0}^{x}, S_{0} is the set of θ ∈ L_{∞,0}^{x} ∩ L_{γ}[T, T̄] for which in no generic extension do there exist a, b ∈ 2^{ω}, f ∈ κ^{ω} with

a ⊧ θ,

b ⊧ ¬θ,
(a, b, f) ∈ p[T].

We may therefore think of S_{0} as the absolutely E-invariant propositions.

Lemma 3.4 S_{0} is Σ_{1} over L_{γ}[T, T̄].

Proof By 2.3. □

Lemma 3.5 Let θ_{0}, θ_{1} ∈ L_{∞,0}^{x} ∩ L_{γ}[T, T̄] and suppose

θ_{0} ∧ ψ_{T}^{r} ∧ θ_{1}(z)

is inconsistent.

Then there is θ ∈ S_{0} such that

θ_{0} ∧ ¬θ

and

θ ∧ θ_{1}

are both inconsistent.

(More intuitively, θ_{0} implies θ and θ implies ¬θ_{1}; thus θ is an absolutely E-invariant interpolant between these two formulas. )

Proof Applying 2.3 we can find a Σ_{0} formula Φ such that ϕ ∈ L_{γ}[T, T̄] is an interpolant between ψ_{0}, ψ_{1} ∈ L_{γ}[T, T̄] if and only

L_{γ}[T, T̄] ⊧ ∃AΦ(A, ϕ, ψ_{0}, ψ_{1}).

Using T^{2} appearing as an isomorphic copy inside T we have

θ_{0} ∧ ψ_{T}^{r}

is inconsistent with

θ_{1}(y) ∧ ψ_{T}^{s} ,

and applying 2.5 inside the admissible we can certainly find some A, ϕ ∈ L_{γ}[T, T̄] ∩ L_{∞,0}^{z} with

L_{γ}[T, T̄] ⊧ Φ(A, ϕ, θ_{0} ∧ ψ_{T}^{r} , ψ_{T}^{s} ∧ θ_{1}(y)).

Let (A_{0}, ϕ_{0}) be the least pair in the canonical well ordering of L_{γ}[T, T̄].

At this stage, using T^{2} appearing as an isomorphic copies inside T, we have ϕ_{0}(x)∧ψ_{T} is inconsistent with ψ_{T} ∧ θ_{1}(y) So again we can take (A_{1}, ϕ_{1}) to be the first pair with A_{1} witnessing ϕ_{1}’s role as interpolant.

Continuing we obtain a function with Σ_{0} graph over L_{γ}[T, T̄],

n ↦ (A_{n}, ϕ_{n}),

such that at each n > 0 we have

L_{γ}[T, T̄] ⊧ Φ(A_{n}, ϕ_{n}, ϕ_{n−1}(x) ∧ ψ_{T}^{r} , ψ_{T}^{s} ∧ θ_{1}(y).

In particular the E-saturations of {a : a ⊧ ϕ_{n}(x)} and {b : b ⊧ θ_{1}} are disjoint and the E-saturation of {a : a ⊧ ϕ_{n−1}(x)} is included inside {a : a ⊧ ϕ_{n}(x)}.

The characteristic property of admissible sets is Σ_{1} replacement, so the set {ϕ_{n} : n ∈ ω} exists inside L_{γ}[T, T̄]. We then take

θ = ⋁_{n∈ω} ϕ_{n}.

□

Definition Let S_{1} be the set of all θ ∈ L_{∞,0}^{x} ∩ L_{γ}[T, T̄] such that the theory

{θ} ∪ {ϕ ⇔ ϕ(z) : ϕ ∈ S_{0}} ∪ {ψr ; T̄}

is inconsistent.

Lemma 3.6 S_{1} is Σ_{1} over L_{γ}[T, T̄].

Proof By 2.4, θ is in S_{1} if and only if there exists some X ∈ L_{γ}[T, T̄], X ⊂ S_{0} with

{θ} ∪ X ∪ {ψr ; T̄}

inconsistent. Then the result follows routinely by manipulation of quantifiers. □

Now we have a divide, exactly corresponding to the same step in [4].

Definition We let W be the set {¬θ : θ ∈ S_{1}}.

Intuitively, W is a theory about a real x for which there is an E-inequivalent y which cannot be separated by an E-invariant formula.

On the one hand W may be inconsistent. Then in particular every a ∈ 2^{ω} satisfies some formula in S_{1}, and it is inconsistent for there to be an E-inequivalent b which cannot be separated by a formula in S_{0}. Thus we have case (II).

Instead suppose W is consistent. We will work towards a Borel reduction of E_{0}.

Let M be a countable elementary submodel of L_{γ}[T, T̄].

Definition Let P be the set of V ⊂ L_{γ}[T, T̄] ∩ L_{∞,0}^{x} such that:

(i) V is Σ ∼_{1} over M; (ii) V ⊃ W; (iii) V is consistent.

We set V ≤ U if V ⊃ U.

Let P ×_{T} P be the set of pairs (V_{1}, V_{2}) ∈ P × P such that

V_{1} ∪ {θ(z) : θ ∈ V_{2}} ∪ {ψ_{T}^{r} }

is consistent. (Note: This amounts to the {Π_{1} \atop ∼} over M assertion that every X included in this Σ ∼_{1} set satisfies ⋀ X is consistent.) In rough terms, we are asking for it to be consistent that the real described by V_{1} be E-equivalent to the real described by V_{2}. We set (V_{1}, V_{2}) ≤ (U_{1}, U_{2}) if each V_{i} ⊃ U_{i}.

For G ⊂ P a filter we define a(G) ∈ 2^{ω} with a(G)(n) = 1 if p_{n}^{x} ∈ G. For G ⊂ P ×_{T} P a filter we define a_{ℓ}(G) and a_{r}(G) by

a_{ℓ}(G)(n) = 1 ⇔ ∃(V, W) ∈ G(p_{n}^{x} ∈ V),
a_{r}(G)(n) = 1 ⇔ ∃(V, W) ∈ G(p_{n}^{x} ∈ W).

Note that since M is countable, both these forcing notions are countable. Thus a forcing extension by either one over the universe is either trivial or equivalent to the result of adding a Cohen real.

Lemma 3.7 (W, W) ⊩_{P×_{T} P} (a_{ℓ}(G), a_{r}(G)) ∈ p[T̄].

Proof Let (V_{1}, V_{2}) ≤ (W, W) force otherwise. Let V_{1}^{∗} ⊂ L_{∞,0}^{y,z,s} ∩ M be the set

{ψ(y) : ψ ∈ V_{1}} ∪ {ψ(z) : ψ ∈ V_{1}} ∪ ψs ; T̄ ∪ {θ(y) ⇔ θ(z) : θ ∈ S_{0} ∩ M}.

V_{1}^{∗} is Σ ∼_{1} over M

Notation For A ⊂ L_{∞,0}^{x} we define A(y) to be {ψ(y) : ψ ∈ A}, A(z) to be {ψ(z) : ψ ∈ A}.

Claim: V_{1}^{∗} ∪ V_{2} ∪ {ψ_{T}^{r} } is consistent.

Proof of claim: Let V̂_{1} be set of ψ ∈ L_{∞,0}^{x} ∩ L_{γ}[T, T̄] such that

V_{1} ∪ V_{2}(z) ∪ {ψ_{T}^{r} } ∪ {¬ψ}

is inconsistent – in other words, asserting V_{1} about x, V_{2} about z, along with T witnessing xEz, entails ψ about x.

V̂_{1} is consistent, just because our assumption on (V_{1}, V_{2}) ∈ P ×_{T} P entails V_{1}∪V_{2}(z)∪{ψ_{T}^{r} } consistent.

V̂_{1} ⊃ V_{1} ⊃ W,

and so

V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄}

is consistent. We then let U_{1} be the set of ψ ∈ L_{∞,0}^{z} ∩ L_{γ}[T, T̄] such that

V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄} ∪ {¬ψ}

is inconsistent – in other words, U_{1} is the set of consequences for z of asserting V̂_{1} along with the existence of an x which is witnessed by T̄ to be E-inequivalent but cannot be separated from z by a formula in S_{0}.

Subclaim: U_{1} ∪ V_{1} ∪ {ψ_{T}^{r} } is consistent.

Proof of subclaim: Otherwise by 2.4 there are Z ⊂ U_{1}, X ⊂ V_{1}, Z, X ∈ L_{γ}[T, T̄], such that if we let

ψ_{x} = ⋀ X,
ψ_{z} = ⋀ Z,

then

ψ_{x} ∧ ψ_{T}^{r} ∧ ψ_{z}

is inconsistent. But then by 3.5 there is θ_{0} ∈ S_{0} such that

ψ_{x} ⇒ θ_{0},
ψ_{z} ⇒ ¬θ_{0},

with a contradiction to the consistency of U_{1}. (The point is that if (a, b, f) ⊧ V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄}, then a ⊧ ψ_{x}, hence a ⊧ θ_{0}, while b ⊧ U_{1}, and hence b ⊧ ψ_{z}, hence b ⊧ ¬θ_{0}, which brutally contradicts θ_{0} ∈ S_{0}.) (Subclaim□)

Subclaim: V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄} ∪ V_{1}(y) ∪ {ψ_{T}^{s} } is consistent.

Proof of subclaim: Or else by 2.5 there would be ψ ∈ L_{∞,0}^{z} ∩ L_{γ}[T, T̄] which is a consequence of

V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄},

and hence by definition of U_{1} has ψ in U_{1}, but also has ¬ψ a consequence of

V_{1}(y) ∪ {ψ_{T}^{s} }.

Changing variables, y to x, we get

V_{1} ∪ {ψ_{T}^{r} }

entailing ¬ψ. Thus ψ provides a stark point at which V_{1} ∪ {ψ_{T}^{r} } and U_{1} disagree, with a contradiction to the last subclaim. (Subclaim□)

Subclaim: V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄} ∪ V_{1}(z) is consistent.

Proof of subclaim: Go to some generic extension in which we have a model for

V̂_{1} ∪ {θ ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψr ; T̄} ∪ V_{1}(y) ∪ {ψ_{T}^{s} },

with a ∈ 2^{ω} serving for x, b ∈ 2^{ω} for y, c ∈ 2^{ω} for z.

Then we would have

(c, b) ∈ p[T],

and so for all θ ∈ S_{0}

b ⊧ θ ⇔ c ⊧ θ.

On the other hand we have for all θ ∈ S_{0}

a ⊧ θ ⇔ c ⊧ θ,

and so for all θ ∈ S_{0}

b ⊧ θ ⇔ a ⊧ θ.

Combining (c, b) ∈ p[T] and (a, c) ∈ p[T̄] we obtain

(a, b) ∈ p[T̄],

and thus for some f ∈ κ^{ω} we have (a, b, f) a model of V̂_{1}∪{θ ⇔ θ(z) : θ ∈ S_{0}}∪{ψr ; T̄}∪V_{1}(z). (Subclaim□)

After simply changing variables we have

V̂_{1}(z) ∪ {θ(y) ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψs ; T̄} ∪ V_{1}(y)

consistent. Since V̂_{1}(z) is closed under all the consequences in L_{∞,0}^{z} ∩ L_{γ}[T, T̄] of

V_{1}(z) ∪ V_{2} ∪ {ψ_{T}^{r} }

we can appeal to 2.5 to obtain the consistency of

V̂_{1}(z) ∪ {θ(y) ⇔ θ(z) : θ ∈ S_{0}} ∪ {ψs ; T̄} ∪ V_{1}(y) ∪ V_{2} ∪ {ψ_{T}^{r} },

as required. (Claim□)

Let Q be the set of (U_{1}, U_{2}) such that (i) U_{1} is a Σ ∼_{1} over M subset of L_{∞,0}^{y,z,s};

(ii) U_{1} ⊃ V_{1}^{∗};
(iii) U_{2} is a Σ ∼_{1} over M subset of L_{∞,0}^{x} ∩ L_{γ}[T, T̄];
(iv) U_{1} ∪ U_{2} ∪ {ψ_{T}^{r} } is consistent.

For (U_{1}, U_{2}) ∈ Q we let

p_{1}(U_{1}) = {ψ(x) : ψ ∈ L_{∞,0}^{y} ∩ L_{γ}[T, T̄], U_{1} ∪ {¬ψ} inconsistent};

in otherwords, p_{1}(U_{1}) is the set of consequences for y entailed by the theory U_{1}. Similarly we let

p_{2}(u_{1}) = {ψ(x) : ψ ∈ L_{∞,0}^{z} ∩ L_{γ}[T, T̄], U_{1} ∪ {¬ψ} inconsistent},

the consequences for z.

It follows immediately from the definitions that if (U_{1}, U_{2}) ∈ Q then (p_{1}(U_{1}), U_{2}) ∈ P ×_{T} P.

Claim: If (U_{1}, U_{2}) ∈ Q, then (p_{2}(U_{1}), U_{2}) ∈ P ×_{T} P.

Proof of claim: If p_{2}(U_{1}) ∪ U_{2}(z) ∪ {ψ_{T}^{r} } is inconsistent, then by 2.4 we get ψ_{x} ∈ L_{∞,0}^{x} ∩ L_{γ}[T, T̄], ψ_{z} ∈ L_{∞,0}^{z} ∩ L_{γ}[T, T̄] with

ψ_{x} ∧ ψ_{T}^{r} ∧ ψ_{z}

inconsistent, ψ_{x} a consequence of U_{2}, ψ_{z} a consequence of p_{2}(U_{1}). Then by 3.5 there is some θ_{0} ∈ S_{0} with

ψ_{x} ⇒ θ_{0},
ψ_{z}(x) ⇒ ¬θ_{0}.

However this contradicts the assumption of (U_{1}, U_{2}) ∈ Q, since a, b, c, f, g were to have

(a, b, f) ⊧ U_{1} ∪ {θ(y) ⇔ θ(z) : θ ∈ S_{0}} ∧ ψs ; T̄,

(c, b, g) ⊧ U_{2} ∧ ψ_{T}^{r} ,

then aEc and θ_{0} ∈ S_{0} gives

a ⊧ θ_{0} ⇔ c ⊧ θ_{0},

while the assumption on (a, b, f) yields

a ⊧ θ_{0} ⇔ b ⊧ S_{0},

and hence

b ⊧ θ_{0} ⇔ c ⊧ S_{0}.

This contradicts b ⊧ p_{2}(U_{1}), c ⊧ U_{2} and ¬θ_{0}(z) being a consequence of p_{2}(U_{1}), θ being a consequence of U_{2}. (Claim□)

Note further that if (W_{1}, W_{2}) ≤ (p_{1}(U_{1}), U_{2}) in P ×_{T} P, then we can let U′_{1} = {ψ(y) : ψ ∈ W_{1}} ∪ U_{1} to obtain (U′_{1}, W_{2}) ∈ Q below (U_{1}, U_{2}) with (p_{1}(U′_{1}), V_{2}) = (W_{1}, W_{2}). Similarly on the other side, if (W_{1}, W_{2}) ≤ (p_{2}(U_{2}), U_{2}) we can obtain (U′_{1}, W_{2}) ∈ Q with p_{2}(U′_{1}) = W_{1}. From these observations one has that for any open dense D ⊂ P ×_{T} P the sets

{(U_{1}, U_{2}) : (p_{1}(U_{1}), U_{2}) ∈ D},
{(U_{1}, U_{2}) : (p_{2}(U_{1}), U_{2}) ∈ D}

are open dense. In this sense we have a kind of transfer property for open dense sets.

Let G ⊂ Q be V -generic. Let G^{1} = {(p_{1}(U_{1}), U_{2}) : (U_{1}, U_{2}) ∈ G} and G^{2} = {(p_{2}(U_{1}), U_{2}) : (U_{1}, U_{2}) ∈ G}. By the transfer property for open dense sets, G^{1} and G^{2} are both V -generic below the condition (V_{1}, V_{2}), and hence by our assumption that the claim fails

(a_{ℓ}(G^{1}), a_{r}(G^{1})) ∉ p[T̄],
(a_{ℓ}(G^{2}), a_{r}(G^{2})) ∉ p[T̄].

However it is direct consequence of the definitions that a_{r}(G^{1}) = a_{r}(G^{2}). Moreover it is an easy consequence of the definition of the forcing notion Q that

(a_{ℓ}(G^{1}), a_{ℓ}(G^{2})) ∈ p[T̄],

with a contradiction to p[T̄] defining the complement of an equivalence relation in the generic extension. □

True to our promises, the next lemma is proved without choice.

Lemma 3.8 There exists a countable collection (D_{n})_{n∈ω} of dense open sets in P ×_{T} P such that if G ⊂ P ×_{T} P is a filter meeting every D_{n}, then

(a_{ℓ}(G), a_{r}(G)) ∈ p[T̄].

Proof The previous lemma will hold true in L[T, T̄] as well as it does in V, so appealing to reflection go to a δ > κ with L_{δ}[T, T̄] which also satisfies this claim along with a large fragment of ZFC. Let N be a countable elementary substructure of L_{δ}[T, T̄]. If G is N-generic, then there will be f ∈ (κ ∩ N)^{ω} having

N[G] ⊧ (a_{ℓ}(G), a_{r}(G), f) ∈ [T̄].

Since T̄ ∩ N is certainly a subset of T̄, we are done. □

At this stage it will be momentarily convenient to build elaborations of our propositional languages.

Definition For t, t′ ∈ 2^{n}, n ∈ ω, we let L^{t,t′,r} be the language with propositions

{p_{n}^{t} : n ∈ ω}, {p_{n}^{t′} : n ∈ ω}, {p_{r(n)=α}^{t,t′} : n ∈ ω, α ∈ κ}.

For a, b ∈ 2^{ω}, f ∈ κ^{ω} we define

M_{a,b,f}^{t,t′,r}

by setting p_{n}^{t} true if a(n) = 1, p_{n}^{t′} true if b(n) = 1, and p_{r(n)=α}^{t,t′} if f(n) = α. As before,

(a, b, f) ⊧ φ

if the resulting M_{a,b,f}^{t,t′,r} satisfies it. We define L^{t} and substitutions of one formula across into the language of another just as before. Again we can define

ψ_{T}^{t,t′,r} ∈ L_{∞,0}^{t,t′,r} ∩ L_{γ}[T, T̄]

so that (a, b, f) satisfies this formula if and only if (a, b, f) ∈ [T], and similarly with

ψt,t′,r ; T̄ ∈ L_{∞,0}^{t,t′,r} ∩ L_{γ}[T, T̄]

and T̄.

We now build by induction on n, (w_{s})_{s∈2^{n}} in P, (σ_{s_{1},s_{2}})_{s_{1},s_{2}∈2^{n}} in κ^{n} ∩ M, (h_{s})_{s∈2^{n}} in ω^{n} with the following conditions:-

(i) at each s_{1}, s_{2} ∈ 2^{n}

(h_{s_{1}}, h_{s_{2}}, σ_{s_{1},s_{2}}) ∈ T ∩ N;

(ii) at each s_{1} ≠ s_{2} ∈ 2^{n} we have

(w_{s_{1}}, w_{s_{2}}) ∈ P ×_{T} P;

(iii) at each s_{1}, s_{2} ∈ 2^{n} with s_{1}(n − 1) ≠ s_{2}(n − 1) we have

(w_{s_{1}}, w_{s_{2}}) ∈ D_{0} ∩ D_{1} ∩ ... ∩ D_{n};

(iv) if s_{1}(n − 1) = s_{2}(n − 1) then σ_{s_{1},s_{2}} ⊃ σ_{s_{1}|_{n−1},s_{2}|_{n−2}};

(v) h_{s} ⊃ h_{s|_{n−1}};

(vi) at each s ≠ t we let v_{s,t} be the theory

w_{s}(s) ∪ w_{t}(t)
∪{p_{m}^{s} : m < n, h_{s}(m) = 1} ∪ {¬p_{m}^{s} : m < n, h_{s}(m) = 0}∪
∪{p_{m}^{t} : m < n, h_{t}(m) = 1} ∪ {¬p_{m}^{t} : m < n, h_{t}(m) = 0}∪

∪{p_{r(m)=α}^{s,t} : m < n, σ_{s,t}(m) = α} ∪ {¬p_{r(m)=α}^{s,t} : m < n, σ_{s,t}(m) ≠ α} ∪ {ψ_{T}^{r} };

we then require that for each w_{s} includes every ϕ(x) ∈ L_{γ}[T, T̄] which is a consequences of

⋃_{t≠t′∈2^{n}} v_{t,t′}.

As is commonly the case with these constructions, when written out in detail the clauses are fearsome. (vi) in particular requires an apology.

The idea is that at stage n we have built a partial story about 2^{n} many reals. We are requiring if we pair the stories for any two reals, gaining (w_{s}, w_{t}), then the condition is in P ×_{T} P – which is like saying they could be inequivalent, but not in a way that can be separated by one of the invariant sets in S_{0}. (i) says not only might they be equivalent, but here is some partial, finite, information about the witness that could do the job. (iv) states that if s and t in 2^{n} agree on their final term, then the witness at this level is consistent with what we saw just for the restriction of s and t to the previous lemma; this condition is diametrically opposed to (iii), which states that if whenever s and t disagree on a term we immediately ask that (w_{s}, w_{t}) flies off and meets the first n + 1 many dense open sets.

(vi) is a bit more subtle. This condition states that if we collect all the information together about all 2^{n} many reals we have in mind at stage n, then each w_{s} includes all the entailments of that theory. There is a terrifying typographical massacre in expressing this simple idea, just because we need to play around with the subscripts to make each w_{s} refer to a different real. But this is the idea.

The possibility of completing this construction follows just as in [4]. Assume we have built the relevant (w_{s})_{s∈2^{n}}, (σ_{s_{1},s_{2}})_{s_{1},s_{2}∈2^{n}}, (h_{s})_{s∈2^{n}}, and attempt to ratchet up one more level.

Let 0^{n} be the element of 2^{n} such that each entry is 0. For each s we can extend w_{0^{n}} and w_{s} to a pair (w′, w′′) ∈ P ×_{T} P which meets

D_{0} ∩ D_{1} ∩ ... ∩ D_{n} ∩ D_{n+1}.

Doing this over several times we can at last assume that we have w^{∗} including w_{0^{n}} and v_{s^{⌢}1} extending each w_{s} so that at every s

(w^{∗}, v_{s^{⌢}1}) ∈ D_{0} ∩ ...D_{n+1}.

Nothing has really changed in this situation so we can repeated adinfinitum, creating (u_{s^{⌢}i})_{s∈2^{n},i∈{0,1}} so that at each i ≠ j, s, t ∈ 2^{n}

(u_{s^{⌢}i}, u_{t^{⌢}j}) ∈ D_{0} ∩ ...D_{n+1}.

Now again we are confronted with this massive theory, concerning 2^{n+1}. For s, t ∈ 2^{n+1} we define v′_{s,t} to be

v_{s}(s) ∪ v_{t}(t)
∪{p_{m}^{s} : m < n, h_{s|_{n}}(m) = 1} ∪ {¬p_{m}^{s} : m < n, h_{s|_{n}}(m) = 0}∪
∪{p_{m}^{t} : m < n, h_{t|_{n}}(m) = 1} ∪ {¬p_{m}^{t} : m < n, h_{t|_{n}}(m) = 0}∪
∪{p_{r(m)=α}^{s,t} : m < n, σ_{s|_{n},t|_{n}}(m) = α} ∪ {¬p_{r(m)=α}^{s,t} : m < n, σ_{s|_{n},t|_{n}}(m) ≠ α} ∪ {ψ_{T}^{r} },

and we again go on to take the union of the various v′_{s,t} as s, t range over distinct elements of 2^{n+1}. The construction of the various w′, w′′, w^{∗} and so on can be done so that we maintain the consistency of the unions from (vi) above, and so that in the end

⋃_{s≠t,s,t∈2^{n+1}} v′_{s,t}

is consistent. We can appropriately extend the values of the various h_{s}’s and σ_{s,t}’s by simply filing in further information in this giant theory.

With this all in place we can at least define the reduction of E_{0}. Given b ∈ 2^{ω} we let G_{b} ⊂ P be the set of v such that some w_{s} ⊂ v. We let f(b) be the resulting real

a(G_{b}) ∈ 2^{ω}.

Note that this also equals ⋃_{n} h_{b|_{n}}.

If bE_{0}c then we choose some N with b(n) = c(n) all n ≥ N and let s = b|_{N}, t = b|_{N}. We then appeal to (iv) to obtain an increasing sequence

σ_{s,t} ⊂ σ_{b|_{N+1},c|_{N+1}} ⊂ σ_{b|_{N+2},c|_{N+2}}...

with each

(h_{b|_{n}}, h_{c|_{n}}, σ_{b|_{n},c|_{n}}) ∈ T,

and hence

⋃_{n>N} σ_{b|_{n},c|_{n}}

witnesses (f(b), f(c)) ∈ p[T], and hence f(b)Ef(c).

Conversely if there are infinitely many n with b(n) ≠ c(n) then we have appeal to (iii) to get

G_{b} × G_{c} ∈ ⋂_{n∈ω} D_{n},

and hence, but the assumption on the D_{n}’s, f(b) and f(c) are E-inequivalent.

We do obtain as a consequence of this result a theorem originally proved by totally different means in [3] and [2].

Corollary 3.9 (Foreman-Magidor, Ditzen) Assume ZF + AD^{ℝ}. Then for every equivalence E on 2^{ω} we have either

(I) E_{0} ≤ E, or

(II) there is an ordinal α and

f : 2^{ω} → P(α)

such that f(x) = f(y) if and only if xEy.

Proof Fix E. First of all we obtain the trees. Woodin has shown in unpublished work that AD^{ℝ} implies every set of reals has a scale, and so we can certainly find trees T, T̄ on some κ projecting to E and its complement.

Secondly we need to verify the condition regarding Cohen forcing. Given terms τ_{1}, τ_{2}, τ_{2} we can find some x ∈ 2^{ω} with each τ_{i} in L[x]. Then since AD implies the non-existence of an ω_{1} sequence of reals we have ω_{1} inaccessible in L[x, T, T̄]. Thus we can find an L[x, T, T̄] generic for Cohen forcing, G. Since the calculation of p[T̄] is absolute between well founded models, we have p[T̄] continues to define the complement of an equivalence relation in L[x, T, T̄, G]. Since this argument holds for any triple of terms in Cohen forcing, we are done. □

4 Π ∼_{1}^{1} equivalence relations

The argument consists in capturing a certain moment in the proof of 1.7. It was for this purpose that 3.1 was isolated.

Theorem 4.1 Assume every real has a sharp. Let E be a Π ∼_{1}^{1} equivalence relation. Then either (I) E_{0} ≤_{B} E; or (II) there is a Δ ∼_{3}^{1} in the codes assignment of bounded subsets of ω_{1} as complete invariants to the

equivalence classes.

Proof For notational convenience assume E is lightfaced Π_{1}^{1}. Let

T̄ ⊂ 2^{<ω} × 2^{<ω} × ω^{<ω}

be canonically chosen to project to the complement of E and let

T ⊂ 2^{<ω} × 2^{<ω} × ω_{1}^{<ω}

be equally chosen to project to E. Both these trees will exist in L; in fact T̄ will be recursive and T will be Σ_{0}. Let γ > ω_{1} be the least ordinal such that L_{γ} is admissible.

Assume that E_{0} does not Borel reduce to E.

Let S_{0} be the set of φ ∈ L_{∞,0}^{x} ∩ L_{γ} such that in no generic extension does there exist b_{1}, b_{2}, f with (b_{1}, b_{2}, f) ∈ [T] with b_{1} ⊧ φ, b_{2} ⊧ ¬φ. Following 3.1 we have that for any b ∈ 2^{ω} there is no generic extension with (b, c) ∈ p[T̄] but for all φ ∈ L_{∞,0}^{x} ∩ L_{γ}

b ⊧ φ ⇔ c ⊧ φ.

Let κ > γ be the least ordinal for which L_{κ} satisfies ZFC without powerset. Note then that L_{κ} is the Skolem hull of ω_{1} + 1. At each α < ω_{1} let M_{α} be the Skolem hull of α ∪ ω_{1} in L_{κ}. Let C be the ordinals α less than ω_{1} such that

α ∩ M_{α} = α.

For each α in C let κ(α) be such that the transitive collapse of M_{α} is isomorphic to L_{κ(α)}. Let

i_{α} : L_{κ(α)} → L_{γ}

be the inverse of the collapsing map for M_{α}. Let S_{0}^{α} = i^{−1}(S_{0}), T^{α} = i^{−1}(T), T̄^{α} = i^{−1}(T̄). Define

U_{α} : 2^{ω} → P(S_{0}^{α})
a ↦ {θ ∈ S_{0}^{α} : a ⊧ θ}.

Claim: For all α ∈ C, a, b ∈ 2^{ω}, U_{α}(a) = U_{α}(b) ⇒ xEy.

Proof of claim: Note that i_{α}[T̄] = T̄. Moreover L_{κ}^{Coll(ω,ω_{1})} calculates that there is no pair a, b in p[T̄] but having

a ⊧ θ ⇔ b ⊧ θ

all θ ∈ S_{0}. Thus the same fact goes down to L_{κ(α)}^{Coll(ω,α)}, with S_{0}^{α} replacing S_{0}. But this fact is Σ_{1}^{1}(c) for any parameter c encoding S_{0}^{α}, and hence absolute. (Claim□)

Claim: For all a ∈ 2^{ω} there is some α ∈ C with

a ⊧ θ ⇔ a ⊧ i_{α}(θ).

Proof of claim: Just choose α so that the Skolem hull of α in L_{κ}[a], M^{a}, has M^{a} ∩ ω_{1} = α. Let L_{δ}[a] be the transitive collapse, and

i^{a} : L_{δ}[a] → L_{κ}[a].

It follows from L_{κ} being the Skolem hull of ω_{1} that M^{a} ∩ κ = M_{α} ∩ κ and i^{a} and i_{α} agree on L_{δ}. Thus by elementarity of i^{a}, for all θ ∈ S_{0}^{α}

a ⊧ θ ⇔ a ⊧ i^{a}(θ) ⇔ a ⊧ i_{α}(θ).
(Claim□)

For each a ∈ 2^{ω} let α(a) be least α ∈ C such that there exists some bEa with

b ⊧ θ ⇔ b ⊧ i_{α}(θ).

Claim: α(a) is uniformly definable over L[a] from any ω_{1}^{V}.

Proof of claim: Given ω_{1}^{V} as a parameter, L[a] can define C and the corresponding i_{α}, S_{0}^{α} just as in V. Then for each α ∈ C the existence of bEa having

b ⊧ θ ⇔ b ⊧ i_{α}(θ)

will be uniformly Σ_{2}^{1}(a, g) for any parameter g encoding the collapse of {θ ∈ S_{0}^{α} : a ⊧ i_{α}(θ)}, and hence absolute between L[a]^{Coll(ω,α)} and V. (Claim□)

It is then a routine application of our assumption that every real has a sharp to verify the function

a ↦ α(a)

is Δ_{3}^{1}. Let π : ω_{1} → S_{0} be the canonical bijection induced by L_{γ} being the Skolem hull of ω_{1}. We finish by letting

U : 2^{ω} → 2^{<ω_{1}}
a ↦ {β < α(a) : a ⊧ i_{α(a)}(β)}.
□

I do not know if the function U can be taken to be Δ ∼_{2}^{1} in option (II) of the theorem. I also do not know if the assumption of sharps is necessary – the reduction procedure described works even without sharps, but it is not clear why it would projective.

References

[1] J. Barwise, Admissible sets and structures, Springer-Verlag, Berlin New York, 1975.

[2] A. Ditzen, PhD, Caltech, 1992.

[3] M. Foreman, M. Magidor, Large cardinals and definable counterexamples to the continuum hypothesis, Annals of Pure and Applied Logic, vol. 76 (1995), 47–97.

[4] L. Harrington, A.S. Kechris, A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, Journal of the American Mathematical Society, vol. 3 (1990), 903–928.

[5] L. Harrington, S. Shelah, Counting equivalence classes for co-κ-Souslin equivalence relations, Logic Colloquium ’80 (Prague, 1980), 147–152, Stud. Logic Foundations Math., 108, North-Holland, Amsterdam-New York, 1982.

[6] G. Hjorth, A.S. Kechris, Analytic equivalence relations and Ulm-type classifications, Journal of Symbolic Logic, 60 (1995), 1273–1300.

[7] G. Hjorth, A.S. Kechris, New dichotomies for Borel equivalence relations, Bulletin of Symbolic Logic, vol. 3 (1997), 329–346.

[8] S. Jackson, A computation of δ_{∼}_{5}^{1}, Memoirs of the American Mathematical Society, vol. 140 (1999).

[9] T. Jech, Set Theory, Pure and Applied Mathematics. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978.

[10] H.J. Keisler, Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers, Studies in Logic and the Foundations of Mathematics, Vol. 62. North-Holland Publishing Co., Amsterdam-London

[11] Y.N. Moschovakis, Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics, 100. North-Holland Publishing Co., Amsterdam-New York, 1980.