A dichotomy theorem for isomorphism

Greg Hjorth December 24, 1999

Contents

1 Introduction 2 2 Set theoretical notation 7 3 Descriptive set theoretical prerequisites 10 4 Equivalence relations 14 5 Model theoretic generalities 17 6 Aside: Something about Gandy-Harrington 23 7 The central definition 31 8 Consequences of the definition 35 9 Aside: Which sentences have uncountable models? 40 10 The split in cases 47 11 Proof for case(I) 51 12 Proof for case(IIb) 72 13 Proof for case(IIa) 86 14 Variations and modifications 90

1 Introduction

This paper contains a dichotomy theorem for the isomorphism relation on a class of countable structures. The statement of the theorem is cleanest when the isomorphism relation is Borel and the class of models is defined by a sentence in L_{ω_{1},ω}, and therefore this is where we begin.

We display a canonical obstruction which must be present whenever we are unable to reduce the isomorphism relation to a countable Borel equivalence relation.

Theorem 1.1 Let Mod(L) the space of countable L structures in either the (Polish) topology generated by quantifier free formulas or the topology generated by first order logic. Let σ ∈ L_{ω_{1},ω} be such that ≅|_{Mod(σ)} is Borel and let Mod(σ) be the space of countable models of σ.

Then exactly one of the following occurs:- (I) there is a Borel function θ : Mod(σ) → X, some Polish space X, and there is a Borel equivalence relation E on X all of whose equivalence classes are countable, such that for all M_{0}, M_{1} ∈ Mod(σ)

M_{0} ≅ M_{1} ⇔ θ(M_{0})Eθ(M_{1});

(II) there is a Borel function

θ : (2^{ω})^{ω} → Mod(σ)

such that for all (x_{n})_{n∈ω}, (y_{n})_{n∈ω} with each x_{n}, y_{n} : ω → {0, 1}, we have

θ((x_{n})_{n∈ω}) ≅ θ((y_{n})_{n∈ω})

if and only if for all n ∈ ω there is K_{n} ∈ ω such that for all i > K_{n}

x_{n}(i) = y_{n}(i).

By [13] and a result by Kechris at 5.1 of [11] we obtain that (I) is equivalent to each of the following:

(I’) there is a Borel function

f : Mod(σ) → ℝ

such that (a) f has countable image on each isomorphism type: |{f(N) : N ≅ N_{0}}| ≤ ℵ_{0}

for each N_{0} ∈ Mod(σ);

(b) f assigns disjoint countable sets: for if |{f(N) : N ≅ N_{0}}|∩|{f(N) : N ≅

N_{1}}| ≠ ∅ then N_{0} ≅ N_{1}.

(I”) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ⊧ σ we have some a⃗ ∈ M with the model

⟨M; a⃗⟩

atomic over the fragment F;

(I”’) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ⊧ σ we have some a⃗ ∈ M with the F -theory of the model

⟨M; a⃗⟩

ℵ_{0}-categorical.

Very loosely one might think of (I), (I’), (I”), and (I”’) as expressing the idea that the models of σ all have “finite rank.” A specific case of this is when the models are all finitely generated, in the sense that every M ∈ Mod(σ) has

M = {t(a⃗) : t is a term},

for some a⃗ ∈ M.

On the other side, (II) may be thought of expressing that the models of σ interpret – in some very generous notion of interpretation – a canonical theory which has infinite rank. For the purposes of illustrating that let us take an example.

Consider the language L̂ with a single binary relation < and countably many unary predicates (U_{n})_{n∈ω}. Let φ ∈ L̂_{ω_{1},ω} be the sentence all of whose models are linearly ordered by < with order type equal to ℤ · ω (in the reverse lexicographic ordering); that is to say, if we start with ℤ · ω the linear ordering given by ω-many ℤ-blocks, then Mod(φ) consists in the the expansions of this structure by countably many unary predicates.

With all this in place, we can rephrase (II) as (II’) there is a Borel function

θ : Mod(φ) → Mod(σ)

such that for all N_{0}, N_{1} ∈ Mod(φ) we have

N_{0} ≅ N_{1} ⇔ θ(N_{0}) ≅ θ(N_{1}).

The method of proof allows certain modifications. We can work on Σ ∼_{1}^{1} subsets of the space of all countable models, instead of just those defined by a countably infinitary formula. Thus in particular if F is a Borel equivalence relation, on a Polish space Y, and if F allows a Borel reduction to the isomorphism relation on some space of countable structures, then we have, as in the theorem above, exactly one of the following:

(I^{∗}) there is a Borel function θ : Y → X, some Polish space X, and there is a Borel equivalence relation E on X all of whose equivalence classes are countable, such that for all y_{0}, y_{1} ∈ Y

y_{0}F y_{1} ⇔ θ(y_{0})Eθ(y_{1});

(II^{∗}) there is a Borel function

θ : (2^{ω})^{ω} → Y

such that for all (x_{n})_{n∈ω}, (y_{n})_{n∈ω} with each x_{n}, y_{n} : ω → {0, 1}, we have

θ((x_{n})_{n∈ω})F θ((y_{n})_{n∈ω})

if and only if for all n ∈ ω there is K_{n} ∈ ω such that for all i > K_{n}

x_{n}(i) = y_{n}(i).

The situation for general, not necessarily Borel, isomorphism relations is more subtle. The first point to make is that the theorem does fail in this wider context. A counter example is given by the abelian p-groups, p a prime, as discussed in [12]. Here one has an explicit bijection between the isomorphism types and 2^{<ℵ_{1}}; as may seem very plausible, and has been discussed in [6], there is no definable method of injecting 2^{<ℵ_{1}} into countable sets of reals, as would happen at (I) above; alternatively the equivalence relation described at (II) is certainly not reducible to 2^{<ℵ_{1}}, as [12] even shows the equivalence relation E_{0}, of eventual agreement just on a single copy of 2^{ω}, to refuse subsets of the ordinals as complete invariants in any kind of definable, let alone Borel or Δ ∼_{2}^{1}, manner.

With this problem noted, and bearing in mind the extrapolations past Borel appearing in earlier papers such as [12], one can find the right statement for Σ_{1}^{1} isomorphism relations. There are various ways of stating this. For instance bearing in mind (I’) above:

Theorem 1.2 Let σ ∈ L_{ω_{1},ω} and let Mod(σ) be the space of countable models of σ.

Then exactly one of the following occurs:-

(Î) there is a Δ ∼_{2}^{1} in the codes function f : Mod(σ) → 2^{<ℵ_{1}}, (a) f has countable image on each isomorphism type: |{f(N) : N ≅ N_{0}}| ≤ ℵ_{0} for each N_{0} ∈ Mod(σ);

(b) f assigns disjoint countable sets: for if |{f(N) : N ≅ N_{0}}| ∩ |{f(N) : N ≅ N_{1}}| ≠ ∅ then N_{0} ≅ N_{1}.

(II) there is a Borel function

θ : (2^{ω})^{ω} → Mod(σ)

such that for all (x_{n})_{n∈ω}, (y_{n})_{n∈ω} with each x_{n}, y_{n} : ω → {0, 1}, we have

θ((x_{n})_{n∈ω}) ≅ θ((y_{n})_{n∈ω})

if and only if for all n ∈ ω there is K_{n} ∈ ω such that for all i > K_{n}

x_{n}(i) = y_{n}(i).

The proof of the main theorem is fairly long and there are several parts. In section 7 we present the main definition which is used to define a split into cases. In some rough sense the idea here is to consider the Σ_{1}^{1} sets which a given

⟨M; a⃗⟩

falls inside, and ask when we can produce a new type, over a given fragment F, realized by some

⟨N; b⃗⟩,

where M allows a “highly elementary” embedding into N. The branching into three possibilities, at 11, 13, and 12, and the consequent rank function which appears when there is no such N, constitutes the main idea.

In 8 we step through various standard reflection arguments, many of which are similar to parallel points in [8], and show that the various sets we need to be Σ_{1}^{1} are indeed Σ_{1}^{1}.

Section 9 turns off into an aside. It uses ideas closely related to 7 to obtain a characterization of when an infinitary sentence allows a countable model; this characterization appears natural, to the author at least, given the arguments of section 10 and following. It can be viewed as the generalization of [7], which completely described when a countable model allows an uncountable model of its Scott’s sentence and has as a consequence a result by Keisler and Shelah to the effect that a set of infinitary sentences allowing an uncountable model is Σ_{1}^{1} in the codes.

10 returns to the main road. Here there is a fork into three possibilities. The first, case(I), corresponds to when we are appropriately able to add to the F -types for some suitable set of M ⊧ σ. The second and third, labeled (IIa) and (IIb), are when we are unable to add to the F -types for any countable Δ_{1}^{1} fragment F, and therefore have a kind of rank function definable over the models of σ, which ranks the tree of partial attempts corresponding to case(I); this rank function can be finite everywhere, giving us case(IIa), or somewhere it may be infinite, giving (IIb).

In 11 we show that case(I) entails that we are in (II) of the theorem:

(E_{0})^{ω} ≤_{B}≅|_{Mod(σ)}.

The rough idea is to try to build a generic sequence of models, each one elementary in the next, each one realizing many more types than the last, and squeeze in between successive models a copy of E_{0}, the equivalence relation of eventual agreement on infinite binary sequences.

Section 12 handles case(IIb), when the rank function exists and for some models it is always infinite. Here we argue that we can assume that the rank function has as its supremum some countable recursive limit ordinal. Then we can try to stratify our generic model into countably many levels, classifying a tuple b⃗ from M on the basis of its rank. Once this is set in place we mimic the argument from 11, interpreting a different copy of E_{0} on different levels.

Finally we are left with 13 and the discussion of case(IIa), which is in some ways the easiest case, or at least the most familiar, being almost identical to a parallel argument from [14]. This is the one place we use that ≅|_{Mod(σ)} is Borel. By assuming that the rank function is finite over all fragments, and iterating this observation through as many ordinal steps as the Borel complexity of the isomorphism relation, we finally obtain (I’).

There are several sections of background material. Certainly 2, 5, and 4 with their discussion of set theoretical and model theoretic prerequisites, as well as the general theory of Borel equivalence relations, are standard for this kind of paper.

On the other hand 3 is a little bit more than the usual thumbnail sketch of the well known. Here there are several short proofs on the boundary of effective descriptive set theory and admissible set theory, all of which are commonplace but strangely difficult to find precisely in the literature. In the arguments of 8, 11, 12, 13, and even 7, it will be helpful to continually pass back and forward from the descriptive set theory of Σ_{1}^{1} sets to the “inner model theory” of admissible sets, and while it would be theoretically possible to do everything just using effective descriptive set theory, the arguments would become unintuitive and hard to follow.

Given the length of the proof, the reader may already be planning how it might be possible to avoid reading most of it. This is a reasonable desire, so I should state forthrightly what is most peripheral.

Two sections which can be skipped are 9 and 6. The first, as remarked above, plays out the ideas of the proof for a result whose actual statement is unrelated; it is never referenced again.

The situation with the 6 is more ambiguous. It came about after considering arguments invoking Gandy-Harrington forcing. Often when becoming involved in calculations that use the “geometry” of Σ_{1}^{1} sets it becomes easier if we fix a kind of “generic” member of the Σ_{1}^{1}, and perform our various calculations with repeated appeals to its genericity. The main point of 6 is the somewhat philosophical one, that the entire usefulness of a generic member of a Σ_{1}^{1} set is that it is low, in the sense of having its Church-Kleene ordinal equal to ω_{1}^{ck}; for the rest of the paper we therefore refer only to reals that are low, never to reals which arise from a Gandy-Harrington generic filter. While it is true that there are isolated references back to 6, they are only made to 6.7, 6.10, and 6.11, all of which are well known.

2 Set theoretical notation

Notation For us the set of natural numbers is

ω = {0, 1, 2, 3, ...}.

We identify each natural number with its set of predecessors:

n = {0, 1, 2, ..., n − 1};

zero has no predecessors, and thus equals the empty set:

0 = ∅.

With this in hand 2 = {0, 1} and for any natural number n

2^{n} = {f| f : {0, 1, 2, ..., n − 1} → {0, 1}};

2^{ω} is the set of all functions from ω to {0, 1}, and in general given sets X and Y we let

X^{Y} = {f : Y → X}.

Given a set X and n ∈ ω, we use X^{n} for the set of all sequences of length n from X:

X^{n} = {f| f : {0, 1, 2, ..., n − 1} → X};

this may be naturally identified with the n-fold product of X:

X × X × ⋯ [n times] × X.

Then X^{<ω} is the set of all finite sequences from X:

X^{<ω} = ⋃_{n∈ω} X^{n}.

Definition Given sets X_{1}, X_{2}, ...X_{n}, tree on X_{1} × X_{2} × ...X_{k} is a subset of

⋃_{n∈ω} X_{1}^{n} × X_{2}^{n} × ...X_{k}^{n}

closed under subsequences in the natural way – so that given (u_{1}, ..., u_{k}) ∈ X_{1}^{n} × X_{2}^{n} × ...X_{k}^{n} in the tree we require that for any l < n we have that (u_{1}|_{l}, u_{2}|_{l}, ..., u_{k}|_{l}) is again in the tree.

For T a tree on X_{1}, X_{2}, ...X_{n}, an infinite branch through T is some (f_{1}, f_{2}, ..., f_{k}), each

f_{i} : ω → X_{i}

with f_{i}|_{l} ∈ T all l ∈ ω. We let [T] denote the collection of all infinite branches.

Notation Given two finite sequences s and t, we use

s^{⌢}t

to indicate the concatenation, obtained by following s by t.

Thus if s ∈ X^{k} and t ∈ X^{n} then we have s^{⌢}t ∈ X^{k+n} defined by

(s^{⌢}t)(i) = s(i)

for i < k and

(s^{⌢}t)(k + i) = t(i)

for i < n.

In the case that t = ⟨a⟩ has length 1 we may write

s^{⌢}a

instead of s^{⌢}⟨a⟩.

Notation Frequently I will write

s⃗

to indicate that s⃗ is a sequence. In this case

s_{j}

will refer to the jth term.

For s⃗ a sequence we can use lh(s⃗) to indicate the length of s. Thus if s⃗ ∈ X^{k} then lh(s⃗) = k.

Notation For R a well founded relation or < a well ordering, we let ||R|| or || < || denote the ordinal corresponding to their ranks. Thus for R a relation on a set X and assuming that there is no infinite descending chain (x_{i})_{i∈ω} such that at each i we have

x_{i}Rx_{i+1}

we let ||R|| be the least ordinal γ such that there is some

ρ : X → γ

such that whenever xRy we have ρ(y) ∈ ρ(x).

I will assume basic notions of constructibility. In particular for X a recursive Polish space and x ∈ X I need to ask that the reader can make sense the constructible hierarchy built over x – that is to say, the collection of transitive structures of the form

L_{α}[x]

where α is an ordinal.

This is easily understood when X is a space such as 2^{ω} or ω^{ω} but requires more creativity when X is a recursive space whose elements cannot be viewed as infinite subsets of the hereditarily finite sets. For these less friendly spaces we need to work out some method of coding, and since the precise details will be irrelevant, I will leave them undiscussed. Alternatively the reader may choose to view all our statements about recursive spaces as holding only for those that are rudimentarily definable subsets of

P(HF)

and whose elements are therefore subject to relative constructibility in the usual way. Indeed this would be an appropriate attitude, since we will be primarily interested in the recursive Polish spaces 2^{ω}, ω^{ω}, Mod(L) (see section 5 below) and their products; in all these cases the individual points of the space are subsets of the hereditarily finite sets.

Definition LO is the subset of 2^{ω×ω} consisting of x such that

<^{x}= {(n, m) : x(n, m) = 1}

defines a linear ordering. WO is the subset of LO consisting of x with <^{x} defining a linear ordering of ω which is a well ordering, in the sense that there is no infinite sequence (n_{i})_{i∈ω} such that at each i

n_{i+1} <^{x} n_{i}.

3 Descriptive set theoretical prerequisites

We presume a robust familiarity with low level effective descriptive set theory, as applying to Σ_{1}^{1}, Π_{1}^{1}, and Δ_{1}^{1} subsets of recursive Polish spaces; a development of recursive spaces adequate to our needs can be found in [20]; a presentation specific to the space ω^{ω} is given in [16], which should already be good enough since our recursive spaces can naturally be thought of as recursive closed subsets of ω^{ω}.

We will also use the theory of admissible sets. This is developed [1] and to a lesser extent [19].

While [1] completely covers the theory of admissible sets and while [20] thoroughly chronicles the effective theory for Σ_{1}^{1}, there seems to be no canonical reference for the connections between these two topics. Thus we sketch a few isolated proofs below.

Definition For x ∈ 2^{ω} we let ω_{1}^{ck(x)} be the supremum of the ranks of the well orders of ω recursive in x. ω_{1}^{ck} indicates the supremum of the ranks of the well orderings that are outright recursive.

Theorem 3.1 Any Σ_{1}^{1}(x) well founded relation on 2^{ω} has rank less than ω_{1}^{ck(x)}.

Proof We let R be our relation which is well founded in the sense of there being no sequence (y_{i})_{i∈ω} with

y_{i}Ry_{i+1}

at each i. We let

T ⊂ ⋃_{n∈ω} 2^{n} × ω^{n} × 2^{n}

be a recursive in x tree with

yRz

if and only if there is f ∈ ω^{ω} such that at all n

(y|_{n}, f|_{n}, z|_{n}) ∈ T.

With this set up, we can just go ahead and apply the usual proof of Kunen-Martin as found at 2G [20]. We let H be the set of all triples of the form

(s_{1}, u_{1}, s_{2}, u_{2}, ...u_{n}, s_{n+1})

where n ∈ ω and each s_{i} ∈ 2^{n}, each u_{i} ∈ ω^{n}, and each (s_{i}, u_{i}, s_{i+1}) ∈ T. This gives rise to a well founded relation by defining

(s_{1}, u_{1}, s_{2}, u_{2}, ...u_{n}, s_{n+1})S(s′_{1}, u′_{1}, s′_{2}, u′_{2}, ...u′_{n}, s′_{m+1})

if m ≥ n and for each j ≤ n we have u_{j} ⊂ u′_{j} and s_{j} ⊂ s′_{j}. We may embed the well founded relation R into S in the usual way: For any (y_{1}, y_{2}, ..., y_{n+1}) and (f_{1}, ..., f_{n}) with

(y_{i}, f_{i}, y_{i+1}) ∈ [T]

all i ≤ n, we can associate

(y_{1}|_{n}, f_{1}|_{n}, ..., f_{n}|_{n}, y_{n+1}|_{n}) ∈ S

and observe that it must have rank at least equal to y_{n+1}.

Thus the rank of S is at least that of R. The usual Kleene Brower ordering on S given at 4A of [20] gives a well ordering of the sequences in S with rank at least that of R. Since H is a recursive in x subset of the hereditarily finite sets, we obtain a well ordering of ω which is recursive in x and has rank at least that of R.

□

Recall that no ordinal between ω and ω_{1}^{ck(x)} can be admissible, since any ω-model of Kripke-Platek set theory can provide ordinals for all its orderings of ω which are actually well orderings in V.

Corollary 3.2 L_{ω_{1}^{ck(x)}}[x] is admissible.

Proof The main issue is to verify the characteristic Σ_{1} reflection axiom. So suppose that A ∈ L_{ω_{1}^{ck(x)}}[x] and

∀a ∈ A∃α < ω_{1}^{ck(x)}(L_{α}[x] ⊧ φ(x, a))

for some formula φ of set theory.

Unraveling the usual recursive definition of the well ordering of L[x] and using that A appears at a level coded by a recursive in x well ordering, we may assume that A = ω. We then define a well ordering on ω × ω by

(n, m) < (n′, m′)

if and only if either:

(i) n < n′; or

(ii) n = n′ and for <_{n} the first recursive in x well ordering of ω such that

L_{||<_{n}||}[x] ⊧ φ(x, n)

we have m <_{n} m′. It is easily checked that this is a Σ_{1}^{1}(x) well ordering of ω × ω, and thus it has rank less

than ω_{1}^{ck(x)}. If we let γ be its rank, then the definitions at once give

∀n ∈ ω∃α < γ(L_{α}[x] ⊧ φ(x, a)).
□

This granted we can take a further step with the notation.

Definition For a a set, ω_{1}^{ck(a)} is the least ordinal α > ω for which

L_{α}[a]

is admissible.

This is not our original definition, but equivalent to it in the case that a ⊂ ω. We can then go on and let ω_{2}^{ck(a)} be the next admissible ordinal for a and in general let ω_{δ}^{ck(a)} be the δth ordinal α > ω with

L_{α}[a]

admissible.

Notation One easily sees that for φ a formula of set theory there are corresponding P_{φ} ∈ Π_{1}^{1} and A_{φ} ∈ Σ_{1}^{1} such that for all x ∈ 2^{ω} and e ∈ ω with {e}^{x}, the eth recursive in x relation on ω, providing a well ordering of ω with rank γ < ω_{1}^{ck(x)} one has

L_{γ}[x] ⊧ φ(x)

if and only if

(x, e) ∈ P_{φ}

if and only if

(x, e) ∈ A_{φ}.

Theorem 3.3 (Spector-Gandy)

(1) A set P ⊂ ω^{ω} is Π_{1}^{1} if and only if there is a recursive closed set C ⊂ ω^{ω} × ω^{ω} such that

x ∈ P ⇔ ∃y ∈ Δ_{1}^{1}(x)((x, y) ∈ C).

(2) A set P ⊂ ω^{ω} is Π_{1}^{1} if and only if there is a formula φ of set theory such that

x ∈ P ⇔ ∃α < ω_{1}^{ck(x)}(L_{α}[x] ⊧ φ(x)).

Proof (1) is given at 4F.3 [20], so this leaves us facing down (2).

So suppose that φ is given. Then we may find P_{φ} ∈ Π_{1}^{1} as above so that for all x ∈ 2^{ω} and e ∈ ω with {e}^{x} presenting a recursive in x well ordering of ω of rank γ < ω_{1}^{ck(x)} one has

L_{||{e}^{x}||}[x] ⊧ φ(x)

if and only if

(x, e) ∈ P_{φ}.

Thus x ∈ P if and only if there is e ∈ ω with {e}^{x} a well ordering and (x, e) ∈ P_{φ}. The converse direction follows since given

P = {x ∈ 2^{ω} : ∀f ∈ ω^{ω}∃n((x|_{n}, f|_{n}) ∉ T)}

for T some recursive tree on x, we have x ∈ P if and only if the least admissible structure containing x can provide a ranking function for the recursive in x tree

T_{x} = {u : (x|_{lh(u)}, u) ∈ T }.

□

(2) implies that a subset of ω is Π_{1}^{1} if and only if it is Σ_{1} over L_{ω_{1}^{ck}}.

Theorem 3.4 (Boundedness for Σ_{1}^{1}.) Assume:

1. A ⊂ ω^{ω} is Σ_{1}^{1};

2. ψ(v_{0}, v_{1}) is a Σ_{1} formula of set theory;

3. for all x ∈ A there exists d ∈ L_{ω_{1}^{ck(x)}}[x] with

L_{ω_{1}^{ck(x)}}[x] ⊧ ψ(x, d).

Then there is some γ_{0} < ω_{1}^{ck} such that for all x ∈ A there exists d ∈ L_{γ_{0}}[x] with

L_{γ_{0}}[x] ⊧ ψ(x, d).

Proof We let B be the set of (x, e) ∈ 2^{ω} × ω such that {e}^{x} is a recursive linear ordering on ω and for all other e^{∗} ∈ ω we have either

(i) {e^{∗}}^{x} is not a well ordering of ω; or

(ii) (x, e^{∗}) ∈ A_{¬∃dψ(v_{0},d)}; or

(iii) there is an ordering preserving map of {e}^{x} into {e^{∗}}^{x}. By our assumptions this implies that (x, e) ∈ B if and only if {e}^{x} is a well ordering of ω

with rank no greater than α where α is least such that

L_{α}[x] ⊧ ∃dψ(x, d).

And then we can obtain a well founded Σ_{1}^{1} relation on B × B by setting

(x, e, n) > (x′, e′, m)

if and only if x = x′ and e = e′ and n occupies a higher position in the linear of ω provided by {e}^{x} than does m.

Now the result follows by 3.1.

□

Note that the property indicated for γ_{0} in the conclusion of 3.4 is uniformly Π_{1}^{1} in any recursive well ordering of length γ_{0}. Thus the property will be uniformly in any index for the Σ_{1}^{1} set Σ_{1} over L_{ω_{1}^{ck}}.

4 Equivalence relations

Definition For X and Y Polish spaces and E and F we write

E ≤_{B} F

if there is a Borel function

θ : X → Y

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

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

Here we say that E is Borel reducible to F and that θ is a reduction If we can find a reduction θ which is not only Borel but continuous, then we write E ≤_{c} F.

We write E ⊑_{B} F if we may find a Borel reduction which is one to one and E ⊑_{c} F if we can find a continuous reduction which is one to one.

Definition An equivalence relation E on a Polish space X is Borel if it appears in the σalgebra generated by the open sets in the product topology on X × X; in other words, it is Borel with respect to the canonical Polish topology on X × X.

An equivalence relation is countable if every equivalence class is countable.

Perhaps the simplest of the Borel equivalence relations are the identity relations on various Polish spaces.

Notation For X a Polish space we let id(X) be the identity relation on X, so that x_{1}id(X)x_{2} if and only if x_{1} = x_{2}.

These simplest of equivalence relations are the subject of Silver’s theorem from [22], restated below in modern notation. This theorem is also sometimes called the first dichotomy theorem for Borel equivalence relations.

Here it should be understood as implicit in its statement that we view ω as a discrete space, so that it is certainly Polish, and we view 2^{ω} as a Polish space in the product topology.

Theorem 4.1 (Silver) Let E be a Borel equivalence relation. Then exactly one of the following happens:

(I) E ≤_{B} id(ω);

(II) id(2^{ω}) ≤_{B} E.

In fact the statement of the theorem can be slightly embellished. In (II) we at once have that the reduction must be one to one, and so id(2^{ω}) ⊑_{B} E; then one can obtain a comeager subset of 2^{ω} on which the reduction is continuous, since every Borel function is continuous on a comeager set, and this comeager set must in turn contain a homeomorphic copy of the Cantor space, and thus in fact id(2^{ω}) ⊑_{c} E.

Just beyond the identity relations one has the Vitali equivalence relation.

Definition We let E_{v}, the Vitali equivalence relation, be the equivalence relation on ℝ arising from the cosets of ℚ; thus xE_{v}y if and only if x − y ∈ ℚ.

We let E_{0} be the equivalence relation of eventual agreement on 2^{ω}. Thus for f_{0}, f_{1} ∈ 2^{ω} we let f_{0}E_{0}f_{1} if there is some N ∈ ω such that for all k > N

f_{0}(k) = f_{1}(k).

Fact 4.2 (See [3]) E_{v} ≤_{B} E_{0} ≤ E_{v}.

Here one has the second dichotomy theorem:

Theorem 4.3 (Harrington-Kechris-Louveau; see [8]) Let E be a Borel equivalence relation. Then exactly one of the following happens:

(I) E ≤_{B} id(2^{ω});

(II) E_{0} ≤_{B} E.

In fact in (II) they obtain E_{0} ⊑_{c} E. In any case a short Baire category argument shows that for all equivalence relations F, if E_{0} ≤_{B} F then E_{0} ⊑_{c} F.

Among the Borel equivalence relations an important type are those induced by the continuous action of a Polish group on a Polish space. In the case that a Polish group G acts continuously on a Polish space X we use E_{G}^{X} to denote the orbit equivalence relation.

Here there is essentially only one known Borel equivalence relation not reducible to some such E_{G}^{X}.

Definition We view (2^{ω})^{ω} as a Polish space in the product topology. For x⃗ = ⟨x_{0}, x_{1}, x_{2}, ...⟩, y⃗ = ⟨y_{0}, y_{1}, ...⟩ ∈ (2^{ω})^{ω} we set

x⃗E_{1}y⃗

if there is some N ∈ ω such that

∀k > N(x_{k} = y_{k}).

Theorem 4.4 (Kechris-Louveau; see [18]) If G is a Polish group acting continuously on a Polish space X, then

E_{1} ≰_{B} E_{G}^{X}.

E_{1} is also the subject of the third dichotomy theorem of [18]:

Theorem 4.5 (Kechris-Louveau) If E ≤_{B} E_{1}, then exactly one of the following happens: (I) E ≤_{B} E_{0};

(II) E_{1} ≤_{B} E.

A parallel result was obtained in [14] for the countable product of E_{0}.

Definition For x⃗, y⃗ ∈ (2^{ω})^{ω} we set x⃗(E_{0})^{ω}y⃗

∀n ∈ ω(x_{n}E_{0}y_{n}).

Theorem 4.6 (Hjorth-Kechris) If E ≤_{B} (E_{0})^{ω}, then exactly one of the following happens: (I) E ≤_{B} E_{0};

(II) (E_{0})^{ω} ≤_{B} E.

Among the Borel equivalence relations an especially important class are those arising in the form

E_{H}^{X},

where H is a closed subgroup of the Polish group S_{∞}, consisting of all permutations of ω in the topology of pointwise convergence, acts continuously on the Polish space X. It is shown in [2] that these are up to Borel reducibility exactly the Borel isomorphism relations on classes of countable structures.

[14] further proved that whenever H a is sufficiently nice closed subgroup of S_{∞} – for instance, abelian – acting continuously on a Polish space X with a Borel orbit equivalence relation, we have either

E_{H}^{X} ≤ E

for some countable Borel equivalence relation E or

(E_{0})^{ω} ≤_{B} E_{H}^{X}.

Without any great conviction, and mainly out of a desire to be provocative, it was then conjectured that this result should hold for H an arbitrary closed subgroup of S_{∞}.

This paper proves that conjecture.

5 Model theoretic generalities

Definition For L a countable language, we let L_{ω_{1},ω} be the countably infinitary logic obtained from the atomic formulas of L by closing under countable conjunction

⋀

countable disjunction

⋁

as well as the first order operations of ∧, ∨, ¬, ∃x and ∀x, but allowing only formulas with finitely many variables.

L_{ω,ω} is the set of first order formulas generated by L.

We will use the term “fragment” in a specific sense; our meaning is more narrow than the usual model theoretic definition, in as much as we require that F be countable and that it include all atomic formulas, and hence determine the language from which it was cleaved.

Definition A set of formulas F ⊂ L_{ω_{1},ω} is a fragment if (i) F is countable; (ii) F is closed under the first order operations of ∧, ∨, ¬, ∃x and ∀x; (iii) F is closed under all substitution instances; (iv) F includes all atomic formulas;

(v) F is closed under subformulas.

Definition For L a countable language, we let Mod(L) be the space of all countable Lstructures whose underlying set is ω. We equip this with the topology generated by quantifier free formulas, so that the basic open sets have the form

{M ∈ Mod(L) : M ⊧ φ(a⃗)}

for some φ ∈ L_{ω,ω} in which no quantifiers appear and some a⃗ ∈ ω^{<ω}. We may naturally identify Mod(L) with

∏_{k}( ∏_{σ_{0}(k)} ω^{(ω^{k})} ∏_{σ_{1}(k)} 2^{(ω^{k})}),

where each σ_{0}(k) ∈ {0, 1, 2, ..., ℵ_{0}} is the number of function symbols of arity k and σ_{1}(k) ∈ {0, 1, 2, ..., ℵ_{0}} is the number of relation symbols of arity k.

Thus Mod(L) in the topology of quantifier free formulas is a recursive Polish space all of whose elements are subsets of the hereditarily finite sets. Thus as remarked at the end of section 2, there is no controversy in forming

L_{α}[M]

for α an ordinal and M ∈ Mod(L).

It is also well known, and can be found at [10] 2.3, that the resulting space Mod(L) equipped with the topology of all first order formulas is again Polish. Thus for any theory T the set

{M ∈ Mod(L) : M ⊧ T }

is a closed subset and hence a Polish space in its own right. Both these topologies, first order and quantifier free, give rise to the same Borel structure; thus from our point of view they are largely interchangeable.

Notation From now on let us take part in the usual model theoretic convention regarding sequences from a structure, thus using

a⃗ ∈ M

(rather than a⃗ ∈ M^{<ω}) to indicate that a⃗ is a sequence in M.

In the case that

ρ : M → N

is a mapping between two models and a⃗ = ⟨a_{0}, a_{1}, ..., a_{l}⟩ is a sequence from M of length l +1 let us simply write

ρ(a⃗)

for the sequence ⟨ρ(a_{0}), ρ(a_{1}), ..., ρ(a_{l})⟩ ∈ N.

Definition For F a fragment and M and N models, let us say that a map

ρ : M → N

is F -elementary if for all a⃗ ∈ M and and φ(x⃗) ∈ F we have

(M ⊧ φ(a⃗)) ⇔ (N ⊧ φ(ρ(a⃗))).

Notation For each language L let us fix a corresponding infinite sequence (c_{i})_{i∈ω} of fresh constants. For k ∈ ω we let L^{k} be the extension of L obtained by adding the constant symbols (c_{i})_{i<k}.

For M ∈ Mod(L) and a⃗ ∈ M we define

⟨M; a⃗⟩

to be the expansion of M to L^{lh(a⃗)} obtained by insisting that at each i < lh(a⃗)

⟨M; a⃗⟩ ⊧ c_{i} = a_{i}.

Naturally we may also write

⟨M; a⃗, b⃗, ...⟩

in place of ⟨M; a^{⌢}b⃗^{⌢}...⟩.

For F a fragment in L and L^{k} as in the previous definition, we may view F as giving rise to a canonical fragment for L^{k} by simply closing F under all substitution instances of the larger language. When there seems to be no threat of confusion it will be notationally convenient to identify F with this canonical extension

Definition For L a recursive language, F a fragment for L, M ∈ Mod(L), and a⃗ ∈ M we let

F −type_{M}(a⃗)

be the F type of a⃗ from the point of view of M. Explicitly:

{ψ(x⃗) : ψ ∈ F, M ⊧ ψ(a⃗)}.

Notation For M ∈ Mod(L) and L′ ⊂ L, we let

M|_{L′}

denote the reduction of M to the language L′.

Definition For σ ∈ L_{ω_{1},ω} we let

Mod(σ)

be the set of M ∈ Mod(L) with

M ⊧ σ.

Of course the space Mod(σ) may no longer be a Polish space, and we have an understandable bias in favor of not stepping too far away from this nice class of spaces. One solution would be to take the topology indicated by the smallest fragment containing σ; another is provided by the next definition and lemma.

Definition A formula ψ ∈ L_{ω_{1},ω} is Π_{1}^{0} if it has the form

⋀_{i∈ω} ψ_{j}

where each ψ_{j} is a quantifier free first order formula. A formula is Σ_{1}^{0} if it has the form

⋁_{i∈ω} ψ_{j}

where each ψ_{j} is quantifier free and first order. After this we just iterate through the ordinals in the usual fashion, with formulas of the form

⋁_{j∈ω} ∃x⃗ψ_{j}(y⃗, x⃗)

being Σ_{α}^{0} if each ψ_{j} is Π_{β}^{0} for some β < α and

⋀_{j∈ω} ∀y⃗ψ_{j}(y⃗, x⃗)

being Π_{α}^{0} if each ψ_{j} is Σ_{β}^{0} for some β < α.

The set of models satisfying a Π_{α}^{0} formula will be a Π ∼_{α}^{0} subset of Mod(L).

Lemma 5.1 Let L be a recursive language and let σ ∈ L_{ω_{1},ω}. Then there is a countable language L̂ ⊃ L and σ̂ ∈ L̂_{ω_{1},ω} such that

(i) σ̂ ∈ Π_{2}^{0};

(ii) the reduction map

Red : Mod(L̂) → Mod(L)

M ↦ M|_{L}

restricted to Mod(σ̂) witnesses

≅ |_{Mod(σ̂)} ≤_{B}≅ |_{Mod(σ)} ≤_{B}≅ |_{Mod(σ̂)}.

Proof Let F be the fragment generated by σ. For each ψ(x⃗) ∈ F we introduce a new relation R_{ψ(x⃗)} into our language L̂. Then for N ∈ Mod(L) we define

Exp(N) ∈ Mod(L̂)

to be the expansion of N given by

Exp(N) ⊧ R_{ψ(x⃗)}(a⃗)

if and only if

N ⊧ ψ(a⃗).

We also obtain that Red ∘ Exp : Mod(L) → Mod(L)

is the identity map.

The set

{Exp(N) : N ∈ Mod(L)}

is easily seen to be defined by a Π_{2}^{0} formula in Mod(L̂) and

{Exp(N) : N ⊧ σ}

equals

{Exp(N) : Exp(N) ⊧ ∀aR_{ψ(x)}(a)}

where ψ(x) is the formula

(x = x) ∧ σ.

□

Thus by the statement at 3C [17] that Π ∼_{2}^{0} subspaces of Polish spaces are Polish, we may identify any space Mod(σ) with a Polish subspace of some Mod(L̂)

Definition We let S_{∞} be the group of all permutations of ω equipped with the topology of pointwise convergence; we let it act in the natural manner on any space of the form Mod(L). (See [2] or [10] §2.1.)

Definition For σ ∈ L_{ω_{1},ω} we let ≅ |_{Mod(σ)} denote the isomorphism relation on models of σ in Mod(L).

Here of course the orbit equivalence relation arising from the action of S_{∞} on Mod(L) is just the relation ≅|_{Mod(σ)} of isomorphism.

Theorem 5.2 (Becker-Kechris; see [2]) Let H be a closed subgroup of S_{∞} and X a Polish space on which H acts continuously with orbit equivalence relation E_{H}^{X}. Then there is a countable language L and σ ∈ L_{ω_{1},ω} such that

E_{H}^{X} ≤_{B}≅|_{Mod(σ)} ≤_{B} E_{H}^{X}.

It will be helpful at some point to make the assumption that all our models have something close to a pairing function, which enables us to encode the type of any finite tuple by the type of a single point.

Lemma 5.3 Let L be a recursive language and σ ∈ L_{ω_{1},ω}. Then there is a richer recursive language L̂ ⊃ L and σ̂ ∈ L̂ such that:

(i) for each M ∈ Mod(σ̂) and a⃗ ∈ M there is some point ba⃗ ∈ M for any fragment F we have F -type_{M}(a⃗) first order definable from F -type_{M}(ba⃗); (ii) ≅ |_{Mod(σ̂)} ≤_{B}≅ |_{Mod(σ)} ≤_{B}≅ |_{Mod(σ̂)}.

Proof There are many ways to see this.

We can for instance pass from M to M^{eq} in the sense §4.3 [15]. The relevant processes of going back and forth are clearly Borel.

□

It will also be convenient at some stage to assume that each point in our model is repeatedly infinitely often.

Lemma 5.4 Let L be a recursive language and σ ∈ L_{ω_{1},ω}. Then there is a richer recursive language L̂ ⊃ L and σ̂ ∈ L̂ such that:

(i) for each M ∈ Mod(σ̂) and a⃗ ∈ M and b ∈ M there are infinitely many b′ ∈ M such that

⟨M; a^{⌢}b⟩ ≅ ⟨M; a^{⌢}b′⟩;

(ii) ≅ |_{Mod(σ̂)} ≤_{B}≅ |_{Mod(σ)} ≤_{B}≅ |_{Mod(σ̂)};

(iii) moreover if each M ∈ Mod(σ) satisfies 5.3(ii) then so too each M̂ ∈ Mod(σ̂) satisfies 5.3(ii).

Proof We introduce an equivalence relation E to the language L and let σ̂ express that each E-equivalence class is infinite and that E is a congruence with respect to the language L and that

M/E,

the result of quotienting out of the model M by the equivalence relation E, is a model of σ in the natural interpretation of L.

□

6 Aside: Something about Gandy-Harrington

We momentarily detrain for a kind of extended philosophical aside on Gandy-Harrington forcing viewed as a device to obtain “generic” members of a non-empty Σ_{1}^{1} set; the main arguments of section 11 and beyond are always working with the combinatorics of Σ_{1}^{1} sets and this naturally requires us to consider “typical” elements which are devoid of accidental properties. We present a sequence of little lemmas trying to suggest that the useful content of considering a generic member x of a Σ_{1}^{1} set A is exhausted by the specification ω_{1}^{ck(x)} = ω_{1}^{ck}.

Most of this section is never quoted again; only 6.10 and 6.11 reappear. These are in any case well known and have direct proofs.

We state everything for the point class of lightfaced Σ_{1}^{1}. It should be clear that they all hold in a relativized form for the relativized class Σ_{1}^{1}(z) whenever z is an element of a recursive Polish space.

Definition For X a recursive Polish space we let P_{X} denote the non-empty Σ_{1}^{1} subsets of X ordered by inclusion. We write A_{1} ≤ A_{2}, read as “A_{1} is stronger than A_{2}”, if

A_{1} ⊂ A_{2}.

In this way P_{X} becomes a partial order.

A subset G ⊂ P_{X} is a filter if (i) for any A_{1}, A_{2} ∈ G there is some B ∈ G with B ≤ A_{1}, B ≤ A_{2};

(ii) if A_{1} ≤ A_{2} and A_{1} ∈ G then A_{2} ∈ G.

A set D ⊂ P_{X} is dense if for all A_{1} ∈ P_{X} there is some A_{2} ≤ A_{1} with A_{2} ∈ D. For D a collection of dense sets, we say that a filter G is D-generic if for all D ∈ D we have

G ∩ D ≠ ∅.

For the accuracy and clarity of later computations it is helpful to isolate the precise degree of genericity required of our filters.

Definition A filter G ⊂ P_{X} is sufficiently generic if whenever

C ⊂ X × ω^{ω}

is a recursive closed set either (i) there is A ∈ G such that for all x ∈ A and f ∈ ω^{ω}

(x, f) ∉ C;

or (ii) there is A ∈ G and n ∈ ω such that for all x ∈ A there is some f ∈ ω^{ω} with

f(0) = n

and

(x, f) ∈ C.

Here are two easy facts about this definition, the second of which helps justify our choice of terminology. Neither of them should require a proof.

Fact 6.1 G is sufficiently generic if and only if for k ∈ ω and

C ⊂ X × ω^{ω}

either:

(i) there is A ∈ G such that for all x ∈ A and f ∈ ω^{ω}

(x, f) ∉ C;

or

(ii) there is A ∈ G and s ∈ ω^{k} such that for all x ∈ A there is some f ∈ ω^{ω} with

f|_{k} = s

and

(x, f) ∈ C.

Fact 6.2 There is a countable collection of dense sets, D = {D_{i} : i ∈ ω}, such that a filter G is sufficiently generic if and only if it is D-generic.

It turns out that a sufficiently generic filter gives rise to and can be encoded by a corresponding point in X. The next two lemmas are in some form standard and well known, and one can certainly find in [21], or in [8] working with a topological formulation, that there is a countable D which will enforce the conclusions of 6.3 and 6.4 for any D-generic G.

We give fragmentary proofs only to dispel doubts whether the notion of “sufficiently generic” really is sufficient.

Lemma 6.3 For G ⊂ P_{X} sufficiently generic there is a unique

x(G) ∈ X

such that for all O basic open we have

x(G) ∈ O

if and only

O ∈ G.

Proof First to see that there is at most one such x(G), note that for each rational number q > 0 we may let (U_{n})_{n∈ω} be an enumeration of open sets such that

(i) X = ⋃_{n∈ω} U_{n};

(ii) d_{X}(U_{n}) < q, where d_{X} is the complete metric for X and d_{X}(U_{n}) is the diameter of U_{n} with respect to that metric; (iii) C = \{(x, f) : x ∈ \overline{U_{f(0)}}\} is a recursive closed subset of X × ω^{ω}.

If G ⊂ P_{X} is sufficiently generic then there will be some k and A ∈ G such that for all x ∈ A one has that there is some f ∈ ω^{ω} with f(0) = k and (x, f) ∈ C. This amounts to saying that for all x ∈ A we have

x ∈ \overline{U_{k}}.

Thus

A ⊂ \overline{U_{k}}

and thus

\overline{U_{k}} ∈ G

since G is a filter. But then for all

x_{1}, x_{2} ∈ ⋂{O : O basic open ∈ G}

we have

d_{X}(x_{1}, x_{2}) < q.

Tending q → 0 we have x_{1} = x_{2}.

To see the converse we retrieve the argument from the first half of the proof to find an infinite sequence of basic open sets

(W_{n})_{n∈ω}

such that at each n \overline{W_{n+1}} ⊂ \overline{W_{n}}

d(W_{n}) < \frac{1}{n}

\overline{W_{n}} ∈ G

and for any basic open set O ∈ G we have some n with

\overline{W_{n}} ⊂ O.

Then we may find a point

x(G) ∈ ⋂_{n∈ω} \overline{W_{n}},

which must be as required.

□

Notation In the case that

X = X_{0} × X_{1} × ... × X_{n}

is the product of n + 1 many recursive Polish spaces, we define for each i ≤ n the projection map

p_{i} : P_{X} ↠ P_{X_{i}}

given by

A ↦ {x_{i} ∈ X_{i} : ∃x_{0}∃x_{1}...∃x_{i−1}∃x_{i+1}...((x_{0}, x_{1}, ..., x_{i−1}, x_{i}, x_{i+1}, ...) ∈ A)}.

This is parallel to the usual definition of the projection map

π_{i} : X ↠ X_{i}
(x_{0}, x_{1}, ..., x_{i}, x_{i+1}, ...) ↦ x_{i}.

The three lemmas are essentially due to Gandy, just rephrased in the context of our technical notion of sufficient genericity.

Lemma 6.4 If G ⊂ P_{X} is sufficiently generic then for all A ⊂ X in Σ_{1}^{1} we have

A ∈ G

if and only if

x(G) ∈ A.

Proof For the forward direction with A ∈ G we recall that any such Σ_{1}^{1} set has the form

A = {x : ∃f((x, f) ∈ C)}

for some C ⊂ X × ω^{ω} recursively closed.

Thus we can apply 6.1 as in [21] to successively obtain

s_{0} ⊂ s_{1} ⊂ ... ⊂ s_{i} ⊂ s_{i+1}...,

each s_{n} ∈ ω^{n}, and

A_{0} ⊃ A_{1} ⊃ .... ⊃ A_{i} ⊃ A_{i+1}...

with each A_{i} ∈ G and

∀x ∈ A_{i}∃f ⊃ s_{i}((x, f) ∈ A_{i}).

Then for

f = ⋃_{i∈ω} s_{i}

we have that for all basic open O ∈ G and i ∈ ω

A_{i} ∩ O ≠ ∅

and hence there is some y ∈ O with

(y, f) ∈ C.

Since the collection of basic open sets appearing in G forms a neighbourhood basis for x(G) we indeed have

(x(G), f) ∈ C.

Conversely if A ∉ G then there will be some B ∈ G with

B ∩ A = ∅.

Then since x(G) ∈ B by the only if direction above, we have

x(G) ∉ A,

as demanded.

□

Lemma 6.5 If G ⊂ P_{X} is sufficiently generic, then for all A ∈ Σ_{1}^{1} with A ⊂ X we have either:

(i) x(G) ∈ A; or

(ii) there is B ∈ G with A ∩ B = 0.

Proof If we let C ⊂ X × ω^{ω} be a recursive closed set such that

A = {x : ∃f((x, f) ∈ C)}

then the lemma follows from 6.4 and the definition of G being sufficiently generic.

□

Theorem 6.6 (Gandy)

If G ⊂ P_{X} is sufficiently generic, then

ω_{1}^{ck(x(G))} = ω_{1}^{ck}.

Proof This is exactly as in the usual proof, since if

{e}^{x(G)}

codes a recursive well ordering then by 6.5 there will be some B ∈ G such that for all y ∈ B one has that

{e}^{y}

codes a well ordering. Then by the boundedness theorem for Σ_{1}^{1} there must be some γ < ω_{1}^{ck} such that for all y ∈ B we have {e}^{y} as a well ordering of rank less than γ. Since x(G) ∈ B by 6.4 we are done.

□

Corollary 6.7 (Gandy) Any non-empty A ∈ Σ_{1}^{1} contains some x with

ω_{1}^{ck(x)} = ω_{1}^{ck}.

Proof Since we can clearly diagonalize in a filter below A to meet the countably many dense sets of 6.2.

□

The combination of 6.4 and 6.6 allows a converse, which we present below along with two other characterizations of being sufficiently generic which have a much more set theoretical flavor.

Lemma 6.8 The following are equivalent:

(0) G is sufficiently generic;

(i) there is some x(G) in the intersection of the basic open sets appearing in G and for this x(G) we have that

G = {A ∈ Σ_{1}^{1} : x(G) ∈ A}

and for all A ∈ Σ_{1}^{1} either (a) x(G) ∈ A, or

(b) there is some Σ_{1}^{1} set B with A ∩ B = 0 and x(G) ∈ B; (ii) there is some x(G) in the intersection of the basic open sets appearing in G and for this x(G) we have

G = {A ∈ Σ_{1}^{1} : x(G) ∈ A}

and

ω_{1}^{ck(x(G))} = ω_{1}^{ck};

(iii) there is some x(G) with

G = {A ∈ Σ_{1}^{1} : x(G) ∈ A}

and for this x(G) there is an ω-model M of ZFC minus the power set axiom and an M-generic filter

H ⊂ (P_{X})^{M}

such that

x(H) = x(G); (iv) there is some x(G) with

G = {A ∈ Σ_{1}^{1} : x(G) ∈ A}

and for this x(G) and any B ∈ G there is an ω-model M of ZFC minus the power set axiom and an M-generic filter

H ⊂ (P_{X})^{M}

such that (a) x(H) = x(G);

(b) M[H] ⊧ x(G) ∈ B.

Proof The equivalence of (0) and (i) is given by 6.4 and 6.5 and the definition of being sufficiently generic.

(ii)⇒(0): Let us fix C ⊂ X × ω^{ω} a recursive closed set as in the definition of being sufficiently generic.

If there exists f_{0} with (x(G), f_{0}) ∈ C then for k = f_{0}(0) we have that x(G) is an element of the Σ_{1}^{1} set

A = {x ∈ X : ∃f((x, f) ∈ C ∧ f(0) = k)}

and we are done.

Instead then suppose that x(G) is an element of the Π_{1}^{1} set

P = {x : ∀f((x, f) ∉ C)}.

Fix a recursive continuous function

ρ : X → LO

such that

ρ^{−1}[WO] = P.

Since ω_{1}^{ck(x(G))} = ω_{1}^{ck} we have some γ < ω_{1}^{ck} with

||ρ(x(G))|| = γ.

Then the Δ_{1}^{1} set

B = {x ∈ X : ||ρ(x)|| = γ}

will be in G by our assumptions and is exactly as required for the definition of sufficient genericity.

(i)⇒(iv): Given x(G) arising from a sufficiently generic G, and given a specific B ∈ G, we have that the conclusion of (iv) refers to x being in a certain Σ_{1}^{1} set. Thus it will fail the conclusion of (iv) if and only if there is some Σ_{1}^{1} set A_{0} ∈ G necessitating that failure. But this is plainly impossible, since given A_{0}, B ∈ G we may choose a countable elementary submodel of some rank initial segment V_{δ} of V and force below A_{0} ∩ B meeting all the dense sets existing in our countable submodel.

(iv)⇒(iii): Obviously.

(iii)⇒(ii): Fix M our ω-model and x = x(G) ∈ M. There are two possibilities. The first being that the ordinal (or an isomorphic copy of the ordinal) ω_{1}^{ck} is in M[H], whence M[H] correctly calculates the structure L_{ω_{1}^{ck}}[x], and thus by internalizing the proof of 6.6 to M[H] we have that L_{ω_{1}^{ck}}[x] is indeed admissible. Alternatively the ordinal does not appear in M[H], which since M[H] satisfies Kripke-Platek set theory gives that there is no well ordering of ω in M of length ω_{1}^{ck}, and in particular that there is no x-recursive well ordering of ω of length ω_{1}^{ck}.

□

Corollary 6.9 The set of x ∈ X for which there is some sufficiently generic G with x(G) = x is Σ_{1}^{1}.

Proof It is well known that

{x ∈ X : ω_{1}^{ck(x)} = ω_{1}^{ck}}

is Σ_{1}^{1}, and indeed it follows at once from the statement of (iii) from 6.8.

□

Corollary 6.10 For any non-empty A ∈ Σ_{1}^{1} the set

{x ∈ A : ω_{1}^{ck(x)} = ω_{1}^{ck}}

is a non-empty Σ_{1}^{1} set.

Corollary 6.11 If ω_{1}^{ck(x)} = ω_{1}^{ck} then for all A ∈ Σ_{1}^{1} we have either (i) x ∈ A; or (ii) there is B ∈ Σ_{1}^{1} with

x ∈ B

and

A ∩ B = 0.

Corollary 6.12 If X = X_{0} × X_{1} is a recursive Polish space and

G_{0} ⊂ P_{X_{0}}

is a sufficiently generic filter, with A ∈ Σ_{1}^{1} such that

{x_{0} : ∃x_{1} ∈ X_{1}((x_{0}, x_{1}) ∈ A)} ∈ G,

then there is a sufficiently generic filter G ⊂ P_{X} with

A ∈ G
p_{0}[G] = G_{0}.

Proof Since

ω_{1}^{ck(x(G_{0}))} = ω_{1}^{ck}

we can apply the relativized version of 6.7 to find some x_{1} with

(x(G_{0}), x_{1}) ∈ A

and

ω_{1}^{ck(x(G_{0}),x_{1})} = ω_{1}^{ck(x(G_{0}))} = ω_{1}^{ck}.

Then by 6.8 we have that

G = {B ∈ P_{X} : (x(G_{0}), x_{1}) ∈ B}

is as required.

□

7 The central definition

We do everything below for Σ_{1}^{1} sets, a recursive language L, and formulas and fragments in L_{ω_{1}^{ck}}. It should be clear that the entire sequence of statements relativizes to Σ_{1}^{1}(z) and recursive in z.

Notation For L a recursive language and A ⊂ Mod(L) a Σ_{1}^{1} set, M ∈ Mod(L), and

a⃗ = ⟨a_{0}, a_{1}, ..., a_{n}⟩ ∈ M,

let us write

M ⊧ A(a⃗)

if there is some π ∈ S_{∞} with

π(a_{l}) = l

all l ≤ n and

π · M ∈ A.

Notation For each recursive language L fix a Σ_{1}^{1} set

U^{L} ⊂ ω × Mod(L)

that is universal in the sense that any Σ_{1}^{1} set A ⊂ Mod(L) appears as

A = U_{n}^{L} = {M : (n, M) ∈ U^{L}}

for some suitable choice of n.

Fact 7.1 For L a recursive language we may find a function

R : ω × ω × ω_{1} → L_{ω_{1},ω}
(n, l, α) ↦ ψ_{n,α}^{L}

such that (i) R|_{ω×ω×δ} is uniformly Δ_{1}^{L_{δ}} for any countable admissible ordinal δ; (ii) for M ∈ Mod(L) and a⃗ ∈ M with lh(a⃗) = l we have

M ⊧ U_{n}^{L}(a⃗)

if and only if for all α < ω_{1}^{ck(M)}

M ⊧ ¬ψ_{n,l,α}^{L}(a⃗),

which in turn happens if and only if for all β < ℵ_{1}

M ⊧ ¬ψ_{n,l,β}^{L}(a⃗).

Proof Fix L, n, and l. Let A be the Σ_{1}^{1} set

{N : ∃π ∈ S_{∞} : ∀k < l(π(k) = k) ∧ π · N ∈ U_{n}^{L}}

obtained by suitably saturating U_{n}^{L}. Fix a recursive continuous

ρ : Mod(L) → LO

with

ρ^{−1}[WO] = Mod(L) \ A.

Following [23] or 16.C [17] we obtain ψ_{n,l,α}^{L} ∈ L_{ω_{1},ω} for each α with

M ⊧ ψ_{n,l,α}^{L}(a⃗)

if and only if for a relatively comeager set of π ∈ S_{∞} in the set of permutations sending each a_{j} to j we have

||ρ(n, π · M)|| ≤ α.

The various calculations of these ψ_{n,l,α}^{L} proceed in the effective category, and we have that

(n, l, α) ↦ ψ_{n,l,α}^{L}

is as required.

□

The notation of 7.1 is convoluted when given in explicit detail, so it seems wise to tolerate an abbreviation.

Notation For B a Σ_{1}^{1} set in Mod(L) with B = U_{n}^{L} let us write

ψ_{B,α}

for

ψ_{n,l,α}^{L},

where l is given by context and the formula ψ_{n,l,α}^{L} is given by 7.1.

Strictly speaking the formula ψ_{n,l,α}^{L} depends not just on B, l, and α, but also the choice of the index n with B = U_{n}^{L}. Although the notation is therefore not completely correct, this will never lead to problems and we will always understand the expression

M ⊧ ψ_{B,α}(a⃗)

to indicate that

M ⊧ ψ_{n,l,α}^{L}(a⃗)

where L is the language of M, n is some fixed choice of an index for B, and l is the length of the sequence a⃗.

Definition For L ∈ L_{ω_{1}^{ck}} and M, N ∈ Mod(L) let us say that an embedding

i : M → N

is ω_{1}^{ck(M,N)}-elementary if for all ψ ∈ L_{ω_{1}^{ck(M,N)}} ∩ L_{ω_{1},ω} and a⃗ ∈ M we have

M ⊧ ψ(a⃗)

if and only if

N ⊧ ψ(i(a⃗)).

Note here that the we only consider constructible ψ. The collection of formulas depends only on the size of the least (M, N)-admissible ordinal, and not on the exact composition of say the model L_{ω_{1}^{ck(M,N)}}[M, N].

However even with this restriction to this seemingly modest set of formulas we are already able to prove:

Fact 7.2 Let

i : M → N

be ω_{1}^{ck(M,N)}-elementary. Then for all a⃗ ∈ M and A ∈ Σ_{1}^{1} we have

M ⊧ A(a⃗)

if and only if

N ⊧ A(i(a⃗)).

Proof Tracing through the implications given by the definitions, and 7.1 we have

M ⊧ ¬A(a⃗)

if and only if

∃α < ω_{1}^{ck(M,N)}(M ⊧ ¬ψ_{A,α}(a⃗))

if and only if (by elementarity assumption on i)

∃α < ω_{1}^{ck(M,N)}(N ⊧ ¬ψ_{A,α}(i(a⃗)))

if and only if

N ⊧ ¬A(i(a⃗)).
□

Up until now this section has consisted in technicalities; the next definition is central to what will follow.

G. Hjorth 34

Definition Let F ∈ L_{ω_{1}^{ck}} be a fragment for some recursive language L. A Σ_{1}^{1} set A is F -barren for l if for all M_{0}, M_{1} ∈ Mod(L) and

i : M_{0} → M_{1}

ω_{1}^{ck(M_{0},M_{1})}-elementary and b⃗ ∈ M_{1} with lh(b⃗) = l we have if

M_{1} ⊧ A(b⃗)

then

F − type_{M_{1}}(b⃗) ∈ {F − type_{M_{0}}(a⃗) : a⃗ ∈ M_{0}}.

8 Consequences of the definition

We fix L a recursive language and prove various facts about the notion of being barren. They relativize smoothly to languages which are recursive in z.

First of all: The property of being F -barren is Π_{1}^{1} in the indices for Σ_{1}^{1} sets.

Lemma 8.1 Let U^{L} be a Σ_{1}^{1} subset of ω × Mod(L) which is universal in the sense of 7.1. Let F ∈ L_{ω_{1}^{ck}} be a fragment for L.

Then

{n ∈ ω : U_{n}^{L} is F −barren for l}

is a Π_{1}^{1} subset of ω.

Proof The set of (M, N , i) such that

i : M → N

is ω_{1}^{ck(M,N)}-elementary is Σ_{1}^{1} by Spector-Gandy. The set of all (M, N , i, a⃗) such that F - type_{N} (a⃗) is not realized in M is Δ_{1}^{1}.

That said, the lemma follows by the usual kinds of manipulation and counting of quantifiers.

□

Clearly the proof of 8.1 is uniform in F and L. If we let P be the set of

(n, m, k) ∈ ω × ω × ω

such that k gives the index for a recursive language, call it L_{k}, {m} is a recursive well order of ω, and α_{m} its rank, the α_{m}th object in L_{ω_{1}^{ck}} is a fragment F_{m} for L_{k}, and U_{n}^{L} is F_{m}-barren, then we obtain that P is Π_{1}^{1} set.

Corollary 8.2 Let F ∈ L_{ω_{1}^{ck}} be a fragment for L. Let A ∈ Σ_{1}^{1} be F -barren for l. Then there is a Δ_{1}^{1} set D ⊃ A which is again F -barren.

Proof There are a couple of ways to see this, the most brutal of which is to simply read it off from the statement of Π_{1}^{1} reflection from [9] after quoting 8.1.

Alternatively we may apply the boundedness theorem in the following way. Consider the Σ_{1}^{1} set B of (M, N , i, a⃗) with

i : M → N

L_{ω,ω}-elementary and the F -type_{N} (a⃗) not realized in M. We then let (ψ_{A,α})_{α∈ℵ_{1}} be as in 7.1 and the notational remark it precedes. We have then that for all (M, N , i, a⃗) ∈ B there is some α < ω_{1}^{ck(M,N)} such that

∃β < α(N ⊧ ψ_{A,β}(a⃗)).

But then by 3.4 we may find a single γ_{0} < ω_{1}^{ck} such that for all (M, N , i, a⃗) ∈ B

∃β < γ_{0}(N ⊧ ψ_{A,β}(a⃗)).

Thus we may take D to be

{N ∈ Mod(L) : N ⊧ ⋀_{β<γ_{0}} ¬ψ_{A,β}(0, 1, ..., l − 1)}.

□

Definition A formula ψ(x_{0}, x_{1}, ..., x_{l−1}) is F -barren for l if the corresponding set

D_{ψ(x⃗)} = {M : M ⊧ ψ(0, 1, ..., l − 1)}

is F -barren in the above sense.

Thus in the proof of 8.2 we actually obtained:

Corollary 8.3 If A is an F -barren for l Σ_{1}^{1} set then there is an F -barren for l formula ψ(x_{0}, x_{1}, ..., x_{l−1}) ∈ L_{ω_{1}^{ck}} with

D_{ψ(x⃗)} ⊃ A.

Corollary 8.4 For F ∈ L_{ω_{1}^{ck}} a fragment and l ∈ ω we have a set A_{F}^{l} ∈ Σ_{1}^{1} such that

M ⊧ A_{F}^{l} (a⃗)

if and only if for no A ∈ Σ_{1}^{1} that is F -barren for l do we have

M ⊧ A(a⃗).

Proof At once from 8.3 and Spector-Gandy.

□

Definition For each l ∈ ω and F ∈ L_{ω_{1}^{ck}} let A_{F}^{l} be the set of m such that there is no F -barren for l set A ∈ Σ_{1}^{1} with

M ⊧ A(0, 1, ..., l − 1).

It is not so elegant to continually be writing a superscript l, so we just use A_{F} where context indicates l. Similarly we use the abbreviated term F -barren when there seems no danger of confusion.

Lemma 8.5 Let ψ be F -barren. Then there is a fragment H ∈ L_{ω_{1}^{ck}} such that whenever

i : M → N

is H-elementary and b⃗ ∈ N,

N ⊧ ψ(b⃗)

implies that F -type_{N} (b⃗) appears in {F -type_{M}(a⃗) : a⃗ ∈ M}.

Proof The set of (M, N , i, b⃗) for which

M ⊧ ψ(b⃗)

and i is elementary with respect to first order formulas but F -type_{N} (b⃗) is not realized over M is Σ_{1}^{1}; the assumption on ψ then guarantees some α < ω_{1}^{ck(M,N)} and some φ ∈ L_{α} and some a⃗ ∈ M with

(M ⊧ φ(a⃗)) ⇔ (N ⊧ ¬φ(i(a⃗))).

Thus by the boundedness theorem for Σ_{1}^{1} we have some single γ_{0} < ω_{1}^{ck} such that whenever

i : M → N
F −type_{N} (b⃗) ∉ {F −type_{M}(a⃗) : a⃗ ∈ M}

then there exists α < γ_{0} and φ ∈ L_{α} with

(M ⊧ φ(a⃗)) ⇔ (N ⊧ ¬φ(a⃗)).

We finish with H = L_{ω_{1},ω} ∩ L_{γ_{0}}.

□

For future reference it may be helpful to note that the set of F -barren ψ(x⃗) is uniformly in F Π_{1}^{1} in the codes as is the set of H as in 8.5. Thus by Spector-Gandy we have that the set of

(F, ψ) ∈ L_{ω_{1}^{ck}}

such that F is a fragment for L and ψ is F -barren is a Σ_{1}^{L_{ω{ck \atop 1}}} set as is the set of triples

(F, H, ψ)

fulfilling the conclusion of 8.5.

In the course of section 11 we will need the following two lemmas.

Lemma 8.6 Suppose M ⊧ A_{F} (a) and ω_{1}^{ck(M)} = ω_{1}^{ck}. Then we may find N ∈ Mod(L) and ω_{1}^{ck(N ,M)}-elementary

j : N → M

with F -type_{M}(a) not realized in N.

G. Hjorth 38

Proof By 6.11 we obtain that the failure of the lemma would give some Σ_{1}^{1} set B with M ⊧ B(a) and for all M̂, â with

M̂ ⊧ B(â)

we have that there is no N̂ ∈ Mod(L) and ω_{1}^{ck(N̂ ,M̂)}-elementary

ĵ : N̂ → M̂

with F -typeM̂(â) not realized in N̂. However this would be a direct contradiction to our assumption that M ⊧ A_{F} (a).

□

Lemma 8.7 Suppose M ⊧ A_{F} (a) and ω_{1}^{ck(M)} = ω_{1}^{ck} and B ∈ Σ_{1}^{1} with

M ⊧ B(a).

Then we may find N ∈ Mod(L) and ω_{1}^{ck(M,N)}-elementary

j : M → N

and b ∈ N with

N ⊧ B(b)

and F -type_{N} (b) not realized in M. Proof Otherwise we may again apply 6.11 to find some single Σ_{1}^{1} set C such that

M ⊧ C(a)

and for all M̂, â with

M̂ ⊧ C(â)

we have that there is no N̂ ∈ Mod(L) and ω_{1}^{ck(M̂,N̂)}-elementary

ĵ : M̂ → N̂

with some b̂ ∈ N̂ having

N̂ ⊧ B(b̂)

but F -typeN̂ (b̂) not realized in M̂.

Claim: There are no M̂, N̂ ∈ Mod(L) and ω_{1}^{ck(M̂,N̂)}-elementary

ĵ : M̂ → N̂

with some b̂ ∈ N̂ having

N̂ ⊧ B(b̂) ∧ C(b̂)

but F -typeN̂ (b̂) not realized in M̂.

Proof of Claim: Otherwise fix M̂, N̂, ĵ, b̂ as indicated. Then the elementarity of ĵ along with 7.2 gives that there will exist some â ∈ M̂ with

M̂ ⊧ B(â) ∧ C(â).

Then we have a contradiction to assumption on C. (Claim□)

But then the claim implies that the set B ∩ C provides a direct contradiction to M ⊧ A_{F} (a).

□

9 Aside: Which sentences have uncountable models?

The definition just considered leads naturally to a characterization of when a sentence φ ∈ L_{ω_{1},ω} admits an uncountable model. We carry a parameter z ∈ 2^{ω} through the next couple of lemmas.

Nothing in this section will be used again; it may indeed be safely ignored.

Definition Let L be a recursive in z language and M, N ∈ Mod(L). An embedding

i : M → N

is Σ_{1}^{1}(z)-elementary if for all A ∈ Σ_{1}^{1}(z) and a⃗ ∈ M

M ⊧ A(a⃗)

implies

N ⊧ A(i(a⃗)).

Lemma 9.1 Let (M_{n})_{n∈ω} be a sequence in Mod(L) and suppose that at each n we have a Σ_{1}^{1}(z) elementary map

ρ_{n} : M_{n} → M_{n+1}.

Then for the direct limit model

Dir Lim_{n∈ω}(M_{n}) = M_{∞}

and for the various induced direct limit maps

ρ_{n,∞} : M_{n} → M_{∞}

we have that each ρ_{n,∞} is Σ_{1}^{1}(z)-elementary.

Proof It suffices to prove that for any Σ_{1}^{1}(z) set A we have that if

M_{0} ⊧ A

then

M_{∞} ⊧ A.

Fix at each n an enumeration (a_{i}^{n})_{i∈ω} of M_{n}. For each n ≤ m let

ρ_{n,m} : M_{n} → M_{m}

be the composition obtained from our given embeddings. These are all clearly Σ_{1}^{1}(z) elementary.

We may apply the definition of M ⊧ A and our space Mod(L) to find a recursive in z array

(φ_{n,l}(v_{0}, v_{1}, ...., v_{n−1}))_{(n,l)∈ω×ω}

of quantifier free formulas such that for all N ∈ Mod(L) we have

N ⊧ A

if and only if there is a permutation π ∈ S_{∞} and f : ω → ω such that at each k ∈ ω

N ⊧ φ_{k,f(k)}(π(0), π(1), ..., π(k − 1)).

Claim: We may find a sequence (m_{n})_{n∈ω} of natural numbers and a sequence of finite sets F_{n} ⊂ M_{n} and corresponding k_{n} equal to the size of F_{n}, with {b_{i}^{n} : i < k_{n}} enumerating F_{n} such that the following all hold:

(i) for each n and i < k_{n} we

ρ_{n}(b_{i}^{n}) = b_{i}^{n+1};

(ii) at each n there is a permutation π_{n} of ω and f : ω → ω such that (a) π_{n}(i) = b_{i}^{n} all i < k_{n}, and

(b) for all l ∈ ω

M_{n} ⊧ φ_{l,f(l)}(π_{n}(0), π_{n}(1), ..., π_{n}(l − 1));

(c) for all l ≤ n we have f(l) = m_{l}; (iii) for all i, l ≤ n there is some j(i, l) < k_{n} such that

b_{n}^{j(i,l)} = ρ_{l,n}(a_{l}^{i}).

Proof of Claim: We show the existence of these things by induction on n. Suppose we have done this up to F_{n} = {b_{i}^{n} : i < k_{n}} ⊂ M_{n} and we wish to continue one more step and find F_{n+1}.

Then obviously we start with b_{i}^{n+1} = ρ_{n}(b_{i}^{n}) for each i < k_{n}. Since ρ_{n} is a Σ_{1}^{1}(z)-elementary map we obtain that there is some permutation π_{n+1} of ω and function f : ω → ω such that

(a) π_{n+1}(i) = b_{i}^{n+1} all i < k_{n}, and

(b) for all l ∈ ω
M_{n+1} ⊧ φ_{l,f(l)}(π_{n+1}(0), π_{n+1}(1), ..., π_{n+1}(l − 1));
(c) for all l ≤ N we have f(l) = m_{l}.

But then we can go to some large enough k_{n+1} so that

{ρ_{l,n+1}(a_{l}^{i}) : i, l ≤ n + 1} ⊂ {π_{n+1}(j) : j < k_{n+1}}.

Taking b_{n+1}^{j} = π_{n+1}(j) and m_{n+1} = f(n + 1) we continue to the next round. (Claim□) Now we can define b_{i}^{∞} ∈ M_{∞} to be

ρ_{n,∞}(b_{i}^{n})

for any sufficiently large n; this is well defined by part (i) of the claim. The first order elementarity of the various ρ_{n} maps along with (ii) is sufficient to ensure that at every k ∈ ω

M_{∞} ⊧ φ_{k,m_{k}}(b_{0}^{∞}, b_{1}^{∞}, ..., b_{k−1}^{∞}).

Clause (iii) of the claim gives that {b_{i}^{∞} : i ∈ ω} enumerates M_{∞}.

G. Hjorth 42

□

Thus from 7.2 we have that ω_{1}^{ck(M,N ,z)}-elementary embeddings are Σ_{1}^{1}(z)-elementary. With a bit of shoving and squeezing we could probably go through the next few steps only using this original notion of ω_{1}^{ck(M,N ,z)}-elementarity, but the new definition is definitely more flexible. Definition A Σ_{1}^{1}(z) set A is said to be unyielding if whenever

i : M → N

is Σ_{1}^{1}(z)-elementary and

N ⊧ A

then

∀b ∈ N ∃a ∈ M(i(a) = b).

Lemma 9.2 If A is not unyielding then there is some pair M, N ∈ Mod(L) with

ω_{1}^{ck(M,N)} = ω_{1}^{ck},

N ⊧ A,

and

i : M → N

Σ_{1}^{1}(z)-elementary but not onto. Proof A simple consequence of A failing to be unyielding is that we may find (A, B, j) with

B ⊧ A,

while the map

j : A → B

is not onto and yet we still have for all ψ ∈ L_{ω_{1}^{ck(z)}}[z] ∩ L_{ω_{1},ω} and c⃗ ∈ A

A ⊧ ψ(c⃗)

if and only if

B ⊧ ψ(j(c⃗)).

Thus by 6.7 we can find (M, N , i) with

ω_{1}^{ck(M,N)} = ω_{1}^{ck},
N ⊧ A,
i : M → N

not onto, and for all ψ ∈ L_{ω_{1}^{ck(z)}}[z] ∩ L_{ω_{1},ω} and a⃗ ∈ M we have

M ⊧ ψ(a⃗)

if and only if

N ⊧ ψ(j(a⃗)).

But then it follows by 7.1 that j is Σ_{1}^{1}(z) elementary.

□

We then have a couple of lemmas in direct analogy with their counterparts in 8. Lemma 9.3 The property of being unyielding is Π_{1}^{1}(z) in the indices for Σ_{1}^{1}(z) sets. Proof Given 9.2, this has a proof like 8.1.

□

Corollary 9.4 If A ∈ Σ_{1}^{1}(z) is unyielding then there exists a Δ_{1}^{1}(z) set D ⊃ A which is again unyielding. Proof This follows 9.3 as 8.2 followed 8.1.

□

Definition A sentence ψ is unyielding if the corresponding set

D_{ψ} = {M : M ⊧ ψ}

is unyielding in the above sense.

Corollary 9.5 If A is an unyielding Σ_{1}^{1}(z) set then there is an unyielding sentence ψ ∈ L_{ω_{1}^{ck(z)}}[z] with

D_{ψ} ⊃ A.

Proof By the method of 8.3.

□

Corollary 9.6 We have a set A^{u,z} ∈ Σ_{1}^{1}(z) such that

M ⊧ A^{u,z}

if and only if for no A ∈ Σ_{1}^{1}(z) that is unyielding do we have M ⊧ A.

Proof By 9.6 and Spector-Gandy.

□

With the definition given by 9.6 we can state the theorem for this section. This is parallel to a similar result due to [7] in the special case that σ is the Scott sentence of a countable model.

Theorem 9.7 Let L be a recursive language and σ ∈ L_{ω_{1}^{ck(z)}}[z]. The following three things are equivalent:

(1) σ ∈ L_{ω_{1},ω} has an uncountable model.

(2) There are M, N ∈ Mod(σ) and Σ_{1}^{1}(z)-elementary

i : M → N

that is not onto.

(3) For some N ∈ Mod(σ)

N ⊧ A^{u,z}.

Proof First let us suppose in (1) that A is a model of σ of size ℵ_{1}. Let F be the fragment generated by σ Then a standard Skolem hull argument enables us to find a chain of F - elementary models

M′≺_{F} N′≺_{F} A

such that (i) M′ is properly included in N′; (ii) M′ and N′ are countable; (iii) for all A ∈ Σ_{1}^{1}(z) and a⃗ ∈ N_{0}

∃α < ℵ_{1}(N′ ⊧ ψ_{A,α}(a⃗))

if and only if

∃α < ℵ_{1}(M′ ⊧ ψ_{A,α}(a⃗)).

Thus if we choose M, N ∈ Mod(L) isomorphic to M′, N′ respectively then we can obtain a Σ_{1}^{1}(z)-elementary map between M, N that is not onto, and hence we have (2).

The implication from (2) to (3) should be obvious.

So this leaves us with the real work of showing that (3) implies (1).

Claim: We may build by induction on α < ℵ_{1} a sequence of pairs of models (A_{α}, B_{α}) and such that:

(i) A_{α} ∈ Mod(σ) and ω_{1}^{ck(A_{α},z)} = ω_{1}^{ck(z)};

(ii) B_{α} is isomorphic to A_{α};

(iii) for F the fragment generated by σ and α < β < ℵ_{1} we have

B_{α}≺_{F} B_{β}

and

B_{α} ≠ B_{β};

(iv) for α_{0} < α_{1} < ℵ_{1} there are Σ_{1}^{1}(z) elementary maps

τ_{α_{0},α_{1}} : A_{α_{0}} → A_{α_{1}},

and these commute, in the sense that for α_{0} < α_{1} < α_{2} we have

τ_{α_{0},α_{2}} = τ_{α_{1},α_{2}} ∘ τ_{α_{0},α_{1}}.

Proof of Claim; By induction on α.

Something does actually need to be said about the base case of this induction, so suppose that

N ⊧ A^{u,z}

and let us assume that ω_{1}^{ck(N ,z)} = ω_{1}^{ck(z)}. But then it follows by 6.11 and the formulation of being unyielding that we may find some M ∈ Mod(L) with

ω_{1}^{ck(M,N ,z)} = ω_{1}^{ck(z)}

and an ω_{1}^{ck(M,N ,z)}-elementary map

i : M → N

which is not onto. We then start the proof of the claim with A_{0} = M and A_{1} = N = B_{1} and B_{0} = i[M].

For the successor steps of the induction we imagine that we have some α and β < α

B_{β} ≠ B_{α}

and corresponding Σ_{1}^{1}(z) elementary τ_{β,α} : A_{β} → A_{α} which is not onto. Then since τ_{β,α} is Σ_{1}^{1}(z)-elementary we may transfer any relevant Σ_{1}^{1}(z) fact about A_{β} up to A_{α}. In particular we may find a model A with

ω_{1}^{ck(A_{α},A,z)} = ω_{1}^{ck(z)}

and an ω_{1}^{ck(z)}-elementary map

τ : A_{α} → A

which is not onto. Taking A_{α+1} = A and B_{α+1} an appropriate isomorphic copy of A_{α+1} we can continue to a further round.

For the limit stages of the construction we naturally wish to take

B_{λ} = ⋃_{α<λ} B_{α}

whenever λ is a limit, and then we are just left with trying to show that we can obtain an appropriate A_{λ}. And this is where 9.1 comes to our rescue.

We find a model A_{∞} from 9.1 to be the direct limit of the A_{α(n)}’s for some

α(n) → λ.

The direct limit construction gives

τ_{α(n),∞} : A_{α(n)} → A_{∞}

which commute and are Σ_{1}^{1}(z) elementary; by composing with suitable τ_{α,α(n)} we may find

τ_{α,∞} : A_{α} → A_{∞}

all α < λ.

The Σ_{1}^{1}(z)-elementarity of these maps ensures that we may find some

ρ : A_{λ} ≅ A_{∞}

with

ω_{1}^{ck(A_{λ},z)} = ω_{1}^{ck(z)}.

Choosing τ_{α,λ} = ρ ∘ τ_{α,∞} we finish. (Claim□)

But then the union

B_{ℵ_{1}} = ⋃_{α<ℵ_{1}} B_{α}

is as required

□

An immediate corollary of this theorem is a result previously proved by Keisler and Shelah using very different techniques. They showed the property of σ ∈ L_{ω_{1},ω} allowing an uncountable model to be absolute between models of set theory, and moreover if we restrict ourselves to

σ ∈ L_{ω_{1},ω} ∩ V_{α}

some α < ω_{1} then the set of such sentences is Σ ∼_{1}^{1}.

However I should add to this that it would be excessive to claw through the several reflection lemmas above if our only goal was to reproduce Keisler-Shelah. Hugh Woodin has in any case shown that their theorem allows a short proof using iterations of ultrapowers of the Frechet filter at ω_{1}.

10 The split in cases

We wish to prove a dichotomy theorem for the isomorphism relation on countable models of some countably infinitary sentence σ. After relativizing to a real we may assume the existence of some z ∈ 2^{ω} and countable language L such that:

(i) L is recursive in z;

(ii) the Scott ranks of models of σ are bounded below ω_{1}^{ck(z)};

(iii) σ ∈ L_{ω_{1}^{ck(z)}}[z].

The arguments depend not at all on y, and thus there is no harm in lightening our notation and assuming:

(i) L is a recursive language;

(ii) the Scott ranks of models of σ are bounded below ω_{1}^{ck};

(iii) σ ∈ L_{ω_{1}^{ck}};

and by 5.1 we may as well even assume

(iv) Mod(σ) is a Π_{2}^{0} subset of Mod(L);

following 5.3 and 5.4 we may further insist that

(v) each tuple in M ∈ Mod(σ) has its type first order definable from a single a ∈ M;

(vi) for all a⃗, b ∈ M, M ∈ Mod(σ), there are infinitely many c ∈ M with

⟨M; a⃗, b⟩ ≅ ⟨M; a⃗, c⟩.

And in the usual way we may assume that there are no function symbols to contend with:

(vii) L is relational.

CASE(I) There is a fragment F ∈ L_{ω_{1}^{ck}} and there is M ∈ Mod(σ) such that

∀b⃗ ∈ M∃a⃗ ∈ M(⟨M; b⃗⟩ ⊧ A_{F} (a⃗)).

In other words, for all b⃗ in M there is some other a⃗ in M such that whenever

⟨M; b⃗⟩ ⊧ A(a⃗)

we must have that A is not F -barren.

Definition Let X_{F} be the set of M as in case assumption.

Clearly X_{F} ∈ Σ_{1}^{1}.

CASE(II) Not case (I).

Here we need some observations and definitions before splitting into two further subcases. By 7.1 we may find a transfinite sequence ψ_{A_{F} ,α} such that

α ↦ ψ_{A_{F} ,α}

is uniformly Δ_{1} over admissible sets and the following three things are equivalent for all M ∈ Mod(L) and a⃗, b⃗ ∈ M:

(1) ⟨M; b⃗⟩ ⊧ A_{F} (a⃗);

(2) ∀α(⟨M; b⃗⟩ ⊧ ¬ψ_{A_{F} ,α}(a⃗));
(3) ∀α < ω_{1}^{ck(M)}(⟨M; b⃗⟩ ⊧ ¬ψ_{A_{F} ,α}(a⃗));

By case assumption and boundedness we can find a single γ_{0}^{F} < ω_{1}^{ck} such for all M ∈ Mod(σ) there is b⃗ ∈ M such that

⟨M; b⃗⟩ ⊧ ∀a⃗ ⋁_{α<γ_{0}^{F}} ψ_{A_{F} ,α}(a⃗).

Lemma 10.1 Under the assumptions of case(II) we may find for each fragment F ∈ L_{ω_{1}^{ck}} a corresponding fragment H ∈ L_{ω_{1}^{ck}} such that for all M, N ∈ Mod(σ) and

i : M → N

H-elementary map, we have every

F −type_{N} (a⃗)

is realized over M.

Proof Note that if H_{∀x⃗ ⋁_{α<γ^{F}_{0}} ψ_{A_{F} ,α}(x⃗)} is the fragment generated by the formula ∀x⃗ ⋁_{α<γ_{0}^{F}} ψ_{A_{F} ,α}(x⃗) then we must have that for any H_{∀x⃗ ⋁_{α<γ^{F}_{0}} ψ_{A_{F} ,α}(x⃗)}-elementary map

i : M → N

between countable models of σ there will be some b⃗ ∈ M such that

⟨N; i(b⃗)⟩ ⊧ ∀x⃗ ⋁_{α<γ_{0}^{F}} ψ_{A_{F} ,α}(x⃗);

and thus for every a⃗ ∈ N we would by 8.3 have some barren ψ such that

⟨N; i(b⃗)⟩ ⊧ ψ(a⃗).

Now as in the proof of 8.5 we may apply 3.4 to find a single fragment H ⊃ H_{∀x⃗ ⋁_{α<γ^{F}_{0}} ψ_{A_{F} ,α}(x⃗)} such that for all M, N ⊧ σ, all a⃗ ∈ N, and all

i : M → N

which is H-elementary and for all b⃗ ∈ M with

⟨N; i(b⃗)⟩ ⊧ A_{F} (a⃗)

we obtain the F -type_{⟨N;i(b⃗)⟩}(a⃗) appearing in ⟨M; b⃗⟩, and in particular F -type_{N} (a⃗) realized over M. This H suffices for the lemma.

□

Note that for any fragment F the set of H satisfying the conclusion of 10.1 is uniformly Π_{1}^{1} in the codes. Thus by Spector-Gandy:

Corollary 10.2 Under assumptions of case(II), we may find a Δ_{1}^{L_{ω{ck \atop 1}}} function

F ↦ H_{F}

such that for all M, N ∈ Mod(σ) and

i : M → N

H-elementary map, we have every

F −type_{N} (a⃗)

is realized over M.

Now we may assign to each M ∈ Mod(σ) and fragment F ∈ L_{ω_{1}^{ck}} a corresponding tree

T_{M}^{F} ⊂ M^{<ω}

such that:

(i) there is in L_{ω_{1}^{ck}} a sequence of formulas (φ_{i∈ω}^{F})_{i∈ω} in H_{F}, depending on F but not on M, such that for each n ∈ ω and a⃗ ∈ M^{n} we have

M ⊧ φ_{n}^{F} (a⃗)

if and only if

a⃗ ∈ T_{M}^{F};

(ii) a substructure N of M is an H_{F} -elementary substructure if and only if there is some infinite branch

f ∈ [T_{M}^{F}]

with

N = {f(n) : n ∈ ω}.

This is just a general fact; it does not depend at all on the specifics of our case assumption. We can tear apart all the sentences of interest and insist that the (φ_{i∈ω}^{F})_{i∈ω} be chosen so as to appropriately Skolemize the formulas appearing in H_{F}.

However in the setting of our case assumption we must moreover obtain:

(iii) for each a⃗ ∈ M and f ∈ [T_{M}^{F}] there will exist some c⃗ ∈ {f(n) : n ∈ ω} such that

F −type_{M}(a⃗) = F −type_{M}(c⃗);

this in particular implies the weaker but more useful conclusion that

(iv) for each a⃗ ∈ M and f ∈ [T_{M}^{F}] there will exist some c⃗ ∈ {f(n) : n ∈ ω} such that F −type_{M}(a⃗) is H-definable from c⃗. That is to say, there is some formula ψ ∈ H such that

(a) M ⊧ ψ(c⃗, a⃗);
(b) M ⊧ ∀b⃗^{0}, b⃗^{1}(⋀_{φ∈F} (ψ(c⃗, b⃗^{0}) ∧ ψ(c⃗, b⃗^{1}) ⇒ (φ(b⃗^{0}) ⇔ φ(b⃗^{1}))).

Thus we may define for any F ∈ L_{ω_{1}^{ck}}, H ⊃ H_{F}, M ∈ Mod(σ) a kind of ranking function

ρ_{F,M}^{H} : T_{M}^{F} × M^{<ω} → ℵ_{1}

defined by the specification that:

ρ_{F,M}^{H}(a⃗, b⃗) = 0 if F −type_{M}(b⃗) is H-definable from a⃗;

ρ_{F,M}^{H}(a⃗, b⃗) = sup{ρ_{F,M}^{H}(a^{⌢}c, b⃗) + 1 : a^{⌢}c ∈ T_{M}^{F}} whenever F −type_{M}(b⃗) is not Hdefinable from a⃗.

CASE(IIa): For all fragments F ∈ L_{ω_{1}^{ck}} there is some fragment H ⊃ H_{F} in L_{ω_{1}^{ck}} such that for all M ∈ Mod(σ) there is some a⃗ ∈ M with

sup{ρ_{F,M}^{H}(a⃗, b⃗) : b⃗ ∈ M} < ω.

CASE(IIb): There is some fragment F ∈ L_{ω_{1}^{ck}} such that for all H ⊃ H_{F} in L_{ω_{1}^{ck}} there is M ∈ Mod(σ) with

sup{ρ_{F,M}^{H}(a⃗, b⃗) : b⃗ ∈ M}

infinite for all a⃗ ∈ M.

11 Proof for case(I)

Fix the fragment F as in case hypothesis. It will be convenient to work with models of σ whose underlying set is something other than ω.

Notation Let Ω be the disjoint union of (2^{<ω})^{<ω} and (2^{<ω})^{<ω} × ω. Let Mod_{Ω}(L) be the space of L-structures on Ω equipped with the topology of quantifier free formulas. Let Mod_{Ω}(σ) be the subspace of models of σ. We again have that Sym(Ω), the collection of permutations of Ω, is a Polish group in the topology of pointwise convergence and gives rise to the isomorphism relation on Mod_{Ω}(L).

We can continue then by analogy with section 7.

Definition For A ⊂ Mod_{Ω}(L) a Σ_{1}^{1} set and f ⊂ Ω finite, M ∈ Mod_{Ω}(L), (a_{u})_{u∈f} a collection elements of M indexed by the elements of f, let us write

M ⊧ A((a_{u})_{u∈f})

if there is π ∈ Sym(Ω) with

π(a_{u}) = u

all u ∈ f and

π · M ∈ A.

For (a_{u})_{u∈f} in M we let ⟨M; (a_{u})_{u∈f}⟩ be the expansion of M by fresh constants (c_{u})_{u∈f} with

⟨M; (a_{u})_{u∈f}⟩ ⊧ c_{u} = a_{u}

all u ∈ f. Given f_{0}, f_{1}, ..., f_{n} finite disjoint subsets of Ω we may naturally write

⟨M; (a_{u})_{u∈f_{0}}, (a_{u})_{u∈f_{1}}, ...⟩

in place of

⟨M; (a_{u})_{u∈f_{0}∪f_{1}∪...}⟩

and

M ⊧ A((a_{u})_{u∈f_{0}}, (a_{u})_{u∈f_{1}}, ..)

in place of

M ⊧ A((a_{u})_{u∈f_{0}∪f_{1}∪...}).

In general it is convenient to extend the model theoretic conventions for sequences to our present situation. We may just write

(a_{u})_{u∈f} ∈ M

to indicate that (a_{u})_{u∈f} is an f-indexed collection of points in M.

Definition We write

⟨M; (a_{u})_{u∈f}⟩ ⊧ A_{F} (b)

if for all Σ_{1}^{1} sets A with

⟨M; (a_{u})_{u∈f}⟩ ⊧ A(b),

we can find

N_{0}, N_{1} ∈ Mod_{Ω}(σ),
(b_{u})_{u∈f} ∈ N_{0},
d ∈ N_{1},
τ : N_{0} → N_{1}

ω_{1}^{ck(N_{0},N_{1})}-elementary, with

⟨N_{1}; (τ(b_{u}))_{u∈f}⟩ ⊧ A(d),

but

F −type_{⟨N_{1};(τ(b_{u}))_{u∈f} ⟩}(d) ∉ {F −type_{⟨N_{0};(b_{u})_{u∈f} ⟩}(e) : e ∈ N_{0}}.

Strictly speaking we should introduce a different A_{F,f} for each finite subset f of Ω. We do not go to this trouble.

We should also distinguish these Σ_{1}^{1} sets from their counterparts in the space Mod(σ). Again we do not go to this trouble.

Definition We let X_{F} ⊂ Mod_{Ω}(σ) be the set of M such that for all b⃗ ∈ M there is a ∈ M with

⟨M; b⃗⟩ ⊧ A_{F} (a).

Our case assumptions appropriately translated across to the space Mod_{Ω}(σ) give that X_{F} is a non-empty set; here we have used that the conclusion of 5.3 is assumed to hold and so we can restrict ourselves to a a single point, instead of having to range over all sequences c⃗ ∈ M. 8.4 gives that X_{F} is Σ_{1}^{1}.

Lemma 11.1 Let N_{0}, N_{1} ∈ Mod_{Ω}(σ),

τ : N_{0} → N_{1}

ω_{1}^{ck(N_{0},N_{1})}-elementary, and let b ∈ N_{1} with

F −type_{N_{1}}(b) ∉ {F −type_{N_{0}}(c) : c ∈ N_{0}}.

Then for all finite f ⊂ Ω and (a_{u})_{u∈f} in N_{0} we have

⟨N_{1}; (τ(a_{u}))_{u∈f}⟩ ⊧ A_{F} (b).

Proof Fix (a_{u})_{u∈f} in N_{0}. Since F −type_{N_{1}}(b) ∉ {F −type_{N_{0}}(c) : e ∈ N_{0}} we have in particular that

F −type_{⟨N_{1};(τ(a_{u}))_{u∈f} ⟩}(b) ∉ {F −type_{⟨N_{0};(a_{u})_{u∈f} ⟩}(c) : c ∈ N_{0}}.

Thus we necessarily have that for all A ∈ Σ_{1}^{1} with

⟨N_{1}; (τ(a_{u}))_{u∈f}⟩ ⊧ A(b)

we can indeed find a pair of models and an elementary embedding (namely: ⟨N_{0}; (a_{u})_{u∈f}⟩, ⟨N_{1}; (τ(a_{u}))_{u∈f}⟩, τ!) as in the definition of A_{F} as above.

□

Definition We let ℚ_{0} the set of sequences ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩ such that:-

(i) n ∈ ω; each of the as⃗ and b_{v} are in Ω; (ii) there are l_{0}, l_{1}, ..., l_{n} ∈ ω with each f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{n}} and each g_{i} a finite subset of f_{i} × ω; (iii) A ∈ Σ_{1}^{1}; (iv) there is some M ∈ Mod_{Ω}(σ) with

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}});

for all M ∈ Mod_{Ω}(σ) with

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

M ⊧ X_{F};

(v) for each m ≤ n there is a linear ordering <^{m} on f_{m} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{m}} such that for all t⃗ ∈ f_{m} and M ∈ Mod_{Ω}(σ) with

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

⟨M; (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{m−1}}, (b_{v})_{v∈g_{m−1}}, (as⃗)_{s⃗<^{m}t⃗}⟩ ⊧ A_{F} (at⃗);

(vi) for each s⃗ ≠ t⃗ ∈ ⋃_{m≤n} f_{m} there is some ψ_{s⃗,t⃗} ∈ F such that whenever

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have must have

M ⊧ ψ_{s⃗,t⃗}(as⃗) ∧ ¬ψ_{s⃗,t⃗}(at⃗).

In fact the ordering <^{m} in (v) can be taken to be the lexicographic ordering under some appropriate isomorphism of 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{m}} with 2^{l_{0}+l_{1}+...+l_{m}}. There is no need for us to keep count of this specific detail and so we ignore it.

Note that it has been hard wired into our definitions that whenever s⃗ ≠ t⃗ and

⟨M; (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}⟩ ⊧ A

for any Σ_{1}^{1} set A then it must be the case that

as⃗ ≠ at⃗,
as⃗ ≠ bt⃗,
as⃗ ≠ bs⃗,
bs⃗ ≠ bt⃗.

Part (vi) of the definition of ℚ_{0} represents a minor redundancy. If we were to define ℚ_{0}^{∗} to be the set obtained by sequences only satisfying (i)-(v), then we would obtain that in some sense ℚ_{0} is dense in ℚ_{0}^{∗}.

Lemma 11.2 Suppose ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩ satisfies (i)-(v) from the definition of ℚ_{0} above. Then we may find a Σ_{1}^{1} set Â ⊂ A such that

⟨Â, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩ ∈ ℚ_{0}.

Proof For each m ≤ n let <^{m} be the indicated ordering on f_{m} as in (v) of the definition of ℚ_{0}. Let M ∈ Mod_{Ω}(σ) be such that

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}).

Then for each m ≤ n and t⃗ ∈ f_{m} we have

⟨M; (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗<^{m}t⃗}⟩ ⊧ A_{F} (at⃗),

and thus in particular it is an outright consequence of the definition of A_{F} that for any s⃗ <^{m} t⃗

M ⊧ ¬ ⋀_{ψ∈F}(ψ(as⃗) ⇔ ψ(at⃗)).

Thus we may choose some ψ_{s⃗,t⃗} ∈ F with

M ⊧ ψ_{s⃗,t⃗}(as⃗) ∧ ¬ψ_{s⃗,t⃗}(at⃗).

Then we can define Â ⊂ A by the specification that for all N ∈ Mod_{Ω}(σ)

N ⊧ Â((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

G. Hjorth 55

if and only if

N ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

and for all m ≤ n and t⃗ ∈ f_{m}

N ⊧ ⋀_{s⃗<^{m}t⃗}¬ψ_{s⃗,t⃗}(at⃗) ∧ ⋀_{s⃗>^{m}t⃗}ψ_{t⃗,s⃗}(at⃗).

□

Notation Suppose l_{0}, l_{1}, ..., l_{n} ∈ ω and f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{i}}. Then for each m ≤ n we let

f_{i}^{(m)} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{m−1}} × 2^{l_{m}+1} × 2^{l_{m+1}} × ... × 2^{l_{i}}.

(Naturally when m > i we simply have f_{i}^{(m)} = f_{i}.)

For s⃗ ∈ f_{i} we define s^{(m,0)} ∈ f_{i}^{(m)} by

(s^{(m,0)})_{j} = (s⃗)_{j}

for j ≤ i, j ≠ m, and

(s^{(m,0)})_{m} = (s⃗)_{j}^{⌢}0;

similarly

(s^{(m,1)})_{j} = (s⃗)_{j}

for j ≤ i, j ≠ m,

(s^{(m,1)})_{m} = (s⃗)_{j}^{⌢}1.

Thus in particular if s⃗ ∈ f_{i} and m > i then

s^{(m,0)} = s^{(m,1)} = s⃗.

We let

f_{i}^{(m,0)} = {s^{(m,0)} : s⃗ ∈ f_{i}},
f_{i}^{(m,1)} = {s^{(m,1)} : s⃗ ∈ f_{i}}.

In a similar fashion we extend this to g_{i} ⊂ f_{i} × ω. So for any v = (s⃗, k) ∈ g_{i} we let v^{(m,0)} = (s^{(m,0)}, k),

v^{(m,1)} = (s^{(m,1)}, k).

Then

g_{i}^{(m,0)} = {v^{(m,0)} : v ∈ g_{i}},
g_{i}^{(m,1)} = {v^{(m,1)} : v ∈ g_{i}},
g_{i}^{(m)} = g_{i}^{(m,0)} ∪ g_{i}^{(m,1)}.

The definitions are set up so that given any g_{i} ⊂ Ω finite and m ≤ i we have

g_{i}^{(m,0)} ∩ g = g_{i}^{(m,1)} ∩ g = 0.

This along with our assumption that Mod_{Ω}(σ) satisfies the conclusion of 5.4 is being used in the next lemma; together they keep a leash on the sets of the form (b_{v})_{v∈g_{i}}. Without these assumptions we can move forward only by painfully enumerating when b_{v} = b_{w}.

Lemma 11.3 Let

⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩

be in ℚ_{0}, where each f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{i}} and let m ≤ n.

Then there is some

⟨B, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ..., (b_{v})_{v∈g_{m−1}}, (as⃗)_{s⃗∈f_{m}^{(m)}}, (b_{v})_{v∈g_{m}^{(m)}}, ...(b_{v})_{v∈g_{n}^{(m)}}⟩

in ℚ_{0} such that for all

M ⊧ B((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ..., (b_{v})_{v∈g_{m−1}}, (as⃗)_{s⃗∈f_{m}^{(m)}}, (b_{v})_{v∈g_{m}^{(m)}}, (b_{v})_{v∈g_{n}^{(m)}})

we have

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ..., (b_{v})_{v∈g_{m−1}}, (a_{}_{s^{(m,0)}})_{s⃗∈f_{m}}, (b_{v^{(m,0)}})_{v∈g_{m}}, ...(b_{v^{(m,0)}})_{v∈g_{n}})

and

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ..., (b_{v})_{v∈g_{m−1}}, (a_{}_{s^{(m,1)}})_{s⃗∈f_{m}}, (b_{v^{(m,1)}})_{v∈g_{m}}, ...(b_{v^{(m,1)}})_{v∈g_{n}})

Proof For notational simplicity let us take the case that n = 1, l_{0} = 0, l_{1} = 1, m = 0, g_{0} = 2^{0} × {5, 6} = {0} × {5, 6}, g_{1} = 0. Thus f_{0} contains only the empty set and f_{1} is the set of size two whose only elements are ⟨0, ⟨0⟩⟩ and ⟨0, ⟨1⟩⟩; f_{0}^{(0,0)} contains ⟨0⟩ and f_{1}^{(0,0)} is the set whose elements are ⟨⟨0⟩, ⟨0⟩⟩ and ⟨⟨0⟩, ⟨1⟩⟩; f_{0}^{(0,1)} contains ⟨0⟩ and f_{1}^{(0,1)} contains ⟨⟨1⟩, ⟨0⟩⟩ and ⟨⟨1⟩, ⟨1⟩⟩.

Let us assume that

⟨0, ⟨0⟩⟩ <^{1} ⟨0, ⟨1⟩⟩

describes the linear ordering <^{1} on 2^{0} × 2^{1} = f_{1}.

Now from clause (v) of the definition of ℚ_{0} we may find N_{0}, N_{1} ∈ Mod_{Ω}(σ) and ω_{1}^{ck(N_{0},N_{1})}- elementary

τ_{0} : N_{0} → N_{1}

and

a_{⟨0⟩}^{0}, b_{⟨⟨0⟩,⟨5⟩⟩}^{0}, b_{⟨⟨0⟩,⟨6⟩⟩}^{0}, a_{⟨⟨0⟩,⟨0⟩⟩}^{0}, a_{⟨⟨0⟩,⟨1⟩⟩}^{0} ∈ N_{0},
a_{⟨1⟩}^{1}, b_{⟨⟨1⟩,⟨5⟩⟩}^{1}, b_{⟨⟨1⟩,⟨6⟩⟩}^{1}, a_{⟨⟨1⟩,⟨0⟩⟩}^{1}, a_{⟨⟨1⟩,⟨1⟩⟩}^{1} ∈ N_{1},
N_{0} ⊧ A((a_{s^{(0,0)}}^{0})_{s⃗∈f_{0}}, (b_{v^{(0,0)}}^{0})_{v∈g_{0}}, (a_{s^{(0,0)}}^{0})_{s⃗∈f_{1}}),

N_{1} ⊧ A((a_{s^{(0,1)}}^{1})_{s⃗∈f_{0}}, (b_{v^{(0,1)}}^{1})_{v∈g_{0}}, (a_{s^{(0,1)}}^{1})_{s⃗∈f_{1}}),
F −type_{N_{1}}(a_{⟨1⟩}^{1}) ∉ {F −type_{N_{0}}(c) : c ∈ N_{0}}

and therefore by 11.1

⟨N_{1}; τ_{0}(a_{⟨0⟩}^{0})⟩ ⊧ A_{F} (a_{⟨1⟩}^{1}).

We use the assumption that the conclusion of 5.4 holds to obtain b_{⟨⟨1⟩,⟨5⟩⟩}^{1}, b_{⟨⟨1⟩,⟨6⟩⟩}^{1} distinct to τ_{0}(b_{⟨⟨0⟩,⟨5⟩⟩}^{0}), τ_{0}(b_{⟨⟨0⟩,⟨6⟩⟩}^{0}).

N_{1} New a_{⟨0⟩}^{1} a_{⟨⟨0⟩,⟨0⟩⟩}^{1} a_{⟨⟨0⟩,⟨1⟩⟩}^{1} a_{⟨0⟩}^{0} a_{⟨⟨0⟩,⟨0⟩⟩}^{0} a_{⟨⟨0⟩,⟨1⟩⟩}^{0} b_{⟨⟨0⟩,⟨5⟩⟩}^{0} b_{⟨⟨0⟩,⟨6⟩⟩}^{0} N_{0}  a_{⟨1⟩}^{1} a_{⟨⟨1⟩,⟨0⟩⟩}^{1} a_{⟨⟨1⟩,⟨1⟩⟩}^{1}  a_{⟨0⟩}^{1} = τ_{0}(a_{⟨0⟩}^{0}) a_{⟨⟨0⟩,⟨0⟩⟩}^{1} = τ_{0}(a_{⟨⟨0⟩,⟨0⟩⟩}^{0}) a_{⟨⟨0⟩,⟨1⟩⟩}^{1} = τ_{0}(a_{⟨⟨0⟩,⟨1⟩⟩}^{0}) τ_{0}

So far the only properties mentioned for the pair (N_{0}, N_{1}) is that it falls inside finitely many Σ_{1}^{1} sets. Thus we may assume from 6.11

ω_{1}^{ck(N_{0},N_{1})} = ω_{1}^{ck}.

The elementarity of the map τ_{0} is sufficient by 7.2 to give

N_{1} ⊧ A((τ_{0}(a_{s^{(0,0)}}^{0}))_{s⃗∈f_{0}}, (τ_{0}(b_{v^{(0,0)}}^{0}))_{v∈g_{0}}, (τ_{0}(a_{s^{(0,0)}}^{0}))_{s⃗∈f_{1}}),

and hence

⟨N_{1}; (τ_{0}(a_{s^{(0,0)}}^{0}))_{s⃗∈f_{0}}, (τ_{0}(b_{v^{(0,0)}}^{0})_{v∈g_{0}})⟩ ⊧ A_{F} (τ_{0}(a_{⟨⟨0⟩,⟨0⟩⟩}^{0}))

G. Hjorth 58

by clause (v) of the definition of ℚ_{0}.

By 6.11 and 8.7 we may find N_{2} ∈ Mod_{Ω}(σ) with

ω_{1}^{ck(N_{0},N_{1},N_{2})} = ω_{1}^{ck(N_{0},N_{1})} = ω_{1}^{ck}

and ω_{1}^{ck}-elementary

τ_{1} : N_{1} → N_{2}

and

a_{⟨⟨0⟩,⟨0⟩⟩}^{2}, a_{⟨⟨0⟩,⟨1⟩⟩}^{2} ∈ N_{2},

with

N_{2} ⊧ A((τ_{1} ∘ τ_{0}(a_{s^{(0,0)}}^{0}))_{s⃗∈f_{0}}, (τ_{1} ∘ τ_{0}(b_{v^{(0,0)}}^{0}))_{v∈g_{0}}, (a_{s^{(0,0)}}^{2})_{s⃗∈f_{1}}),

and

F −type_{N_{2}}(a_{⟨⟨0⟩,⟨0⟩⟩}^{2}) ∉ {F −type_{N_{1}}(c) : c ∈ N_{1}},

and therefore in particular ⟨N_{2}; (τ_{1}∘τ_{0}(a_{⟨0⟩}^{0}))_{{⟨0⟩}}, (τ_{1}(a_{⟨1⟩}^{1}))_{{⟨1⟩}}, (τ_{1}∘τ_{0}(b_{v^{(0,0)}}^{0}))_{v^{(0,0)}∈g_{0}^{(0,0)}}, (τ_{1}(b_{v^{(0,1)}}^{1}))_{v^{(0,1)}∈g_{0}^{(0,1)}}⟩ ⊧ A_{F} (a_{⟨⟨0⟩,⟨0⟩⟩}^{2}).

a_{⟨0⟩}^{2} a_{⟨1⟩}^{2} a_{⟨⟨1⟩,⟨0⟩⟩}^{2} a_{⟨⟨1⟩,⟨1⟩⟩}^{2} a_{⟨⟨0⟩,⟨0⟩⟩}^{2} N_{2} N_{1} a_{⟨0⟩}^{1} a_{⟨⟨0⟩,⟨0⟩⟩}^{1} a_{⟨⟨0⟩,⟨1⟩⟩}^{1}  a_{⟨⟨0⟩,⟨1⟩⟩}^{2} New a_{⟨⟨1⟩,⟨1⟩⟩}^{1} a_{⟨⟨1⟩,⟨0⟩⟩}^{1} a_{⟨1⟩}^{1}  τ_{1}

We can repeat and find N_{3}, again with ω_{1}^{ck(N_{0},N_{1},N_{2},N_{3})} = ω_{1}^{ck},

G. Hjorth 59

and some a_{⟨⟨0⟩,⟨1⟩⟩}^{3} ∈ N_{3}, with N_{3} ⊧ A((τ_{2}∘τ_{1}∘τ_{0}(a_{s^{(0,0)}}^{0}))_{s⃗∈f_{0}}, (τ_{2}∘τ_{1}∘τ_{0}(b_{v^{(0,0)}}^{0}))_{v∈g_{0}}, (τ_{2}(a_{⟨⟨0⟩,⟨0⟩⟩}^{2}))_{{⟨⟨0⟩,⟨0⟩⟩}}, (a_{⟨⟨0⟩,⟨1⟩⟩}^{3})_{{⟨⟨0⟩,⟨1⟩⟩}}),

F −type_{N_{3}}(a_{⟨⟨0⟩,⟨1⟩⟩}^{3}) ∉ {F −type_{N_{2}}(c) : c ∈ N_{0}}

and thus

⟨N_{3}; (τ_{2} ∘ τ_{1} ∘ τ_{0}(a_{⟨0⟩}^{0}))_{{⟨0⟩}}, ⋯, (τ_{2}(a_{⟨⟨0⟩,⟨0⟩⟩}^{2}))_{{⟨⟨0⟩,⟨0⟩⟩}}⟩ ⊧ A_{F} (a_{⟨⟨0⟩,⟨1⟩⟩}^{3}).

a_{⟨⟨0⟩,⟨0⟩⟩}^{2} a_{⟨⟨0⟩,⟨1⟩⟩}^{2} a_{⟨0⟩}^{2}N_{2} a_{⟨1⟩}^{2} a_{⟨⟨1⟩,⟨0⟩⟩}^{2} a_{⟨⟨1⟩,⟨1⟩⟩}^{2}  a_{⟨0⟩}^{3} a_{⟨⟨0⟩,⟨0⟩⟩}^{3} a_{⟨⟨0⟩,⟨1⟩⟩}^{3} a_{⟨1⟩}^{3} a_{⟨⟨1⟩,⟨0⟩⟩}^{3} a_{⟨⟨1⟩,⟨1⟩⟩}^{3} N_{3}New

Now let us introduce the notations

τ_{0,3} = τ_{2} ∘ τ_{1} ∘ τ_{0} : N_{0} → N_{3},

τ_{1,3} = τ_{2} ∘ τ_{1} : N_{1} → N_{3},
τ_{2,3} = τ_{2} : N_{2} → N_{3}.

We can then go on and let

b_{v^{(0,0)}}^{3} = τ_{2} ∘ τ_{1} ∘ τ_{0}(b_{v^{(0,0)}}^{0})

for v^{(0,0)} ∈ g_{0}^{(0,0)},

b_{v^{(0,1)}}^{3} = τ_{2} ∘ τ_{1}(b_{v^{(0,1)}}^{1})

for v^{(0,1)} ∈ g_{0}^{(0,1)},

a_{⟨0⟩}^{3} = τ_{0,3}(a_{⟨0⟩}^{0}).
a_{⟨⟨0⟩,⟨0⟩⟩}^{3} = τ_{2,3}(a_{⟨⟨0⟩,⟨0⟩⟩}^{2}),
a_{⟨⟨1⟩,⟨0⟩⟩}^{3} = τ_{1,3}(a_{⟨⟨1⟩,⟨0⟩⟩}^{1}),
a_{⟨⟨1⟩,⟨1⟩⟩}^{3} = τ_{1,3}(a_{⟨⟨1⟩,⟨1⟩⟩}^{1}),
a_{⟨1⟩}^{3} = τ_{1,3}(a_{⟨1⟩}^{1}).

We have that each τ_{i,j} is ω_{1}^{ck(N_{i},N_{j})}-elementary, and hence respects Σ_{1}^{1} truths in the sense indicated by 7.2. Thus we have all the following in N_{3}:-

(a)

N_{3} ⊧ A((a_{s^{(0,0)}}^{3})_{s⃗∈f_{0}}, (b_{v^{(0,0)}}^{3})_{v∈g_{0}}, (a_{s^{(0,0)}}^{3})_{s⃗∈f_{1}});

(b)

⟨N_{3}; a_{⟨0⟩}^{3}⟩ ⊧ A_{F} (a_{⟨1⟩}^{3});

(c)

⟨N_{3}; (a_{⟨0⟩}^{3})_{{⟨0⟩}}, (a_{⟨1⟩}^{3})_{{⟨1⟩}}, (b_{v}^{3})_{v∈g_{0}^{(0)}}⟩ ⊧ A_{F} (a_{⟨⟨0⟩,⟨0⟩⟩}^{3});

(e) and by one last application of 11.1,

⟨N_{3}; (a_{⟨0⟩}^{3})_{{⟨0⟩}}, (a_{⟨1⟩}^{3})_{{⟨1⟩}}, (b_{v}^{3})_{v∈g_{0}^{(0)}}, (a_{⟨⟨0⟩,⟨0⟩⟩}^{3})_{{⟨⟨0⟩,⟨0⟩⟩}}⟩ ⊧ A_{F} (a_{⟨⟨0⟩,⟨1⟩⟩}^{3}).

Now holding onto a_{⟨0⟩}^{3}, a_{⟨1⟩}^{3}, (b_{v^{(0,0)}}^{3})_{v^{(0,0)}∈g_{0}^{(0,0)}}, (b_{v^{(0,1)}}^{3}))_{v^{(0,1)}∈g_{0}^{(0,1)}}, a_{⟨⟨0⟩}^{3}, a_{⟨⟨0⟩,⟨1⟩⟩}^{3}, we can work on a_{⟨1⟩}^{3} and obtain in perfect analogy to the construction of N_{1} given N_{0} above some ω_{1}^{ck}-elementary map

τ_{3} : N_{3} → N_{4}

and some a_{⟨⟨1⟩,⟨0⟩⟩}^{4}, a_{⟨⟨1⟩,⟨1⟩⟩}^{4} ∈ N_{4} with

N_{4} ⊧ A((τ_{3}(a_{s^{(0,1)}}^{4}))_{s⃗∈f_{0}}, (τ_{3}(b_{v^{(0,1)}}^{4}))_{v∈g_{0}}, (a_{s^{(0,1)}}^{4})_{s⃗∈f_{1}}),
F −type_{N_{4}}(a_{⟨⟨1⟩,⟨0⟩⟩}^{4}) ∉ {F −type_{N_{3}}(c) : c ∈ N_{3}}.

Then we go again to obtain N_{5},

τ_{4} : N_{4} → N_{5},

N_{2} ⊧ A((τ_{4} ∘ τ_{3}(a_{s^{(0,1)}}^{0}))_{s⃗∈f_{0}}, (τ_{4} ∘ τ_{3}(b_{v^{(0,1)}}^{3}))_{v∈g_{0}}, (τ_{4}(a_{⟨⟨1⟩,⟨0⟩⟩}^{4}))_{{⟨⟨1⟩,⟨0⟩⟩}}), (a_{⟨⟨1⟩,⟨1⟩⟩}^{5})_{{⟨⟨1⟩,⟨1⟩⟩}}),

F −type_{N_{5}}(a_{⟨⟨1⟩,⟨1⟩⟩}^{5}) ∉ {F −type_{N_{4}}(c) : c ∈ N_{4}}.

We may again obtain that τ_{4} and τ_{5} preserve the satisfaction with respect to Σ_{1}^{1} formulas.

Let

τ_{3,5} = τ_{4} ∘ τ_{3} : N_{3} → N_{5}.

Again

b_{v}^{5} = τ_{3,5}(b_{v}^{3}),

for v ∈ g_{0}^{(0)}. And again

a_{⟨⟨1⟩,⟨0⟩⟩}^{5} = τ_{4}(a_{⟨⟨1⟩,⟨0⟩⟩}^{5}),
a_{⟨0⟩}^{5} = τ_{3,5}(a_{0}^{3}),
a_{⟨⟨0⟩,⟨0⟩⟩}^{5} = τ_{3,5}(a_{⟨⟨0⟩,⟨0⟩⟩}^{3}),
a_{⟨⟨1⟩,⟨0⟩⟩}^{5} = τ_{3,5}(a_{⟨⟨1⟩,⟨0⟩⟩}^{3}),
a_{⟨⟨1⟩,⟨1⟩⟩}^{5} = τ_{3,5}(a_{⟨⟨1⟩,⟨1⟩⟩}^{3}),
a_{⟨1⟩}^{5} = τ_{3,5}(a_{⟨1⟩}^{3}).

By the preservation of the relevant Σ_{1}^{1} formulas we have

(a’)

N_{5} ⊧ A((a_{s^{(0,0)}}^{5})_{s⃗∈f_{0}}, (b_{v^{(0,0)}}^{5})_{v∈g_{0}}, (a_{s^{(0,0)}}^{5})_{s⃗∈f_{1}});

(b’)

⟨N_{5}; a_{⟨0⟩}^{5}⟩ ⊧ A_{F} (a_{⟨1⟩}^{5});

(c’)

⟨N_{5}; (a_{⟨0⟩}^{5})_{{⟨0⟩}}, (a_{⟨1⟩}^{5})_{{⟨1⟩}}, (b_{v}^{5})_{v∈g_{0}^{(0)}}⟩ ⊧ A_{F} (a_{⟨⟨0⟩,⟨0⟩⟩}^{5});

(d’)

⟨N_{5}; (a_{⟨0⟩}^{5})_{{⟨0⟩}}, (a_{⟨1⟩}^{5})_{{⟨1⟩}}, (b_{v}^{5})_{v∈g_{0}^{(0)}}, (a_{⟨⟨0⟩,⟨0⟩⟩}^{5})_{{⟨⟨0⟩,⟨0⟩⟩}}⟩ ⊧ A_{F} (a_{⟨⟨0⟩,⟨1⟩⟩}^{5});

(e’)

⟨N_{5}; (a_{⟨0⟩}^{5})_{{⟨0⟩}}, (a_{⟨1⟩}^{5})_{{⟨1⟩}}, (b_{v}^{5})_{v∈g_{0}^{(0)}}, ..., (a_{⟨⟨0⟩,⟨1⟩⟩}^{5})_{{⟨⟨0⟩,⟨1⟩⟩}}⟩ ⊧ A_{F} (a_{⟨⟨1⟩,⟨0⟩⟩}^{5});

(g’)

⟨N_{5}; (a_{⟨0⟩}^{5})_{{⟨0⟩}}, (a_{⟨1⟩}^{5})_{{⟨1⟩}}, ...(a_{⟨⟨1⟩,⟨0⟩⟩}^{5})_{{⟨⟨1⟩,⟨0⟩⟩}}⟩ ⊧ A_{F} (a_{⟨⟨1⟩,⟨1⟩⟩}^{5}).

Finally with N_{5} and the various points indicated above in place, we can return to the task of “splitting” the indicated sequence in ℚ_{0}. We can let

⟨0⟩ <^{0} ⟨1⟩

define the ordering on 2^{1} and

⟨⟨0⟩, ⟨0⟩⟩ <^{1} ⟨⟨0⟩, ⟨1⟩⟩ <^{1} ⟨⟨1⟩, ⟨0⟩⟩ <^{1} ⟨⟨1⟩, ⟨1⟩⟩

define the ordering on 2^{1} × 2^{1}. Taking B to be any Σ_{1}^{1} set describing enough about N_{5} and applying 11.2 we finish.

□

Definition For s⃗ ∈ f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{i}} and t⃗ ∈ 2^{k_{0}} × 2^{k_{1}} × ... × 2^{k_{j}} some j ≥ i, we define

s⃗ ∗ t⃗ ∈ 2^{l_{0}+k_{0}} × 2^{l_{1}+k_{1}} × ... × 2^{l_{i}+k_{i}}

by the specification that at each m ≤ i

(s⃗ ∗ t⃗)_{m} = (s⃗)_{m}^{⌢}(t⃗)_{m},

the concatenation of the sequences (s⃗)_{m} and (t⃗)_{m}. For

v = (s⃗, k) ∈ f_{i} × ω,

we let

v ∗ t⃗ = (s⃗ ∗ t⃗, k).

Definition For elements in ℚ_{0}

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩

and

p̄ = ⟨Ā, (ās⃗)_{s⃗∈f̄_{0}}, (b̄_{v})_{v∈ḡ_{0}}, (ās⃗)_{s⃗∈f̄_{1}}, ...(b̄_{v})_{v∈ḡn̄}⟩

we set p̄ ≤ p if the following all take place:- (i) n ≤ n̄; (ii) there are l_{0}, l_{1}, ..., l_{n}, k_{0}, ..., k_{n}, such that for each i ≤ n we have f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{i}} and f̄_{i} = 2^{l_{0}+k_{0}} × 2^{l_{1}+k_{1}} × ... × 2^{l_{i}+k_{i}}; (iii) for l_{0}, l_{1}, ..., l_{n}, k_{0}, ..., k_{n} as in (ii) we have that each

ḡ_{i} ⊃ {v ∗ t⃗: t⃗ ∈ 2^{k_{0}} × ... × 2^{k_{i}}, v ∈ g_{i}};

(iv) for any

M ⊧ Ā((ās⃗)_{s⃗∈f̄_{0}}, (b̄_{v})_{v∈ḡ_{0}}, (ās⃗)_{s⃗∈f̄_{1}}, ...(b̄_{v})_{v∈ḡn̄})

and t⃗ ∈ 2^{k_{0}} × ...2^{k_{n}} we have

M ⊧ A((a_{s⃗∗t⃗})_{s⃗∈f_{0}}, (b_{v∗t⃗})_{v∈g_{0}}, (a_{s⃗∗t⃗})_{s⃗∈f_{1}}, ...(b_{v∗t⃗})_{v∈g_{n}}).

Lemma 11.4 Fix

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}) ∈ ℚ_{0},

each f_{i} = 2^{l_{0}} × 2^{l_{1}} × ...2^{l_{i}}. Suppose k⃗ = ⟨k_{0}, k_{1}, ..., k_{n} and at each i ≤ n we have

f̄_{i} = {s⃗ ∗ t⃗: s⃗ ∈ f_{i}, t⃗ ∈ 2^{k_{0}} × 2^{k_{1}} × ..2^{k_{i}}},
ḡ_{i} = {v ∗ t⃗: v ∈ g_{i}, t⃗ ∈ 2^{k_{0}} × 2^{k_{1}} × ..2^{k_{i}}}.

Then we may find p̄ ≤ p in ℚ_{0} of the form

p̄ = ⟨Ā, (as⃗)_{s⃗∈f̄_{0}}, (b_{v})_{v∈ḡ_{0}}, ..., (as⃗)_{s⃗∈f̄_{n}}, (b_{v})_{v∈ḡ_{n}}⟩.

Proof By repeated applications of 11.3.

□

Lemma 11.5 If

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ ℚ_{0},

then there is some

p̄ = ⟨Ā, ((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}, (as⃗)_{s⃗∈f_{n+1}}, (b_{v})_{v∈g_{n+1}}⟩ ≤ p

again in ℚ_{0}.

Proof Let l_{0}, l_{1}, ..., l_{n} be such that each f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{i}}. We then take l_{n+1} = 0, f_{n+1} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{n}} × 2^{l_{n+1}} = f_{n} × {0}, and g_{n+1} = 0.

Fix some M ⊧ X_{F} in Mod_{Ω}(σ) with

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})).

By the definition of X_{F} we have that for all b⃗ ∈ M there is some a ∈ M with

⟨M; b⃗⟩ ⊧ A_{F} (a).

Applying this repeatedly we may find (as⃗)_{s⃗∈f_{n+1}} and a linear ordering <^{n+1} such that at each t⃗ ∈ f_{n+1} we have

⟨M; (as⃗)_{s⃗∈f_{0}}, ..., (b_{v})_{v∈g_{n}}, (as⃗)_{s⃗<^{n+1}t⃗}⟩ ⊧ A_{F} (at⃗).

Thus we may let A′ just be the Σ_{1}^{1} given by

N ⊧ A′((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}, (as⃗)_{s⃗∈f_{n+1}})

if and only if

N ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}))

and for each t⃗ ∈ f_{n+1} we have

⟨N; (as⃗)_{s⃗∈f_{0}}, ..., (b_{v})_{v∈g_{n}}, (as⃗)_{s⃗<^{n+1}t⃗}⟩ ⊧ A_{F} (at⃗).

Applying 11.2 we can find Ā ⊂ A′ as required.

□

Lemma 11.6 Let

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ ℚ_{0}

and

ψ(x_{0}, x_{1}, ..., x_{m_{0}}, z_{0}, z_{1}, ..., z_{m_{1}}, y) ∈ F.

Then there is

p̄ = ⟨Ā, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈ḡ_{n}}⟩ ∈ ℚ_{0}

such that:

(i) p̄ ≤ p; (ii) for each i ≤ n and c⃗ = ⟨c_{0}, c_{1}, ..., c_{m_{0}}⟩ in

⋃_{j≤i}{as⃗|s⃗ ∈ f_{j}},

d⃗ = ⟨d_{0}, d_{1}, ..., d_{m_{1}}⟩ in

⋃_{j≤i}{b_{v}|v ∈ g_{j}}

there is some v ∈ ḡ_{i} such that either (a) for all M ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈ḡ_{n}}) we have

M ⊧ ∀y¬ψ(c⃗, d⃗, y),

or

(b) for all M ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈ḡ_{n}}) we have

M ⊧ ψ(c⃗, d⃗, b_{v}).

Proof We go to M ∈ Mod_{Ω}(σ) with ω_{1}^{ck(M)} = ω_{1}^{ck} and M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}). By repeated applications of 8.6 and 6.10 we can find M_{0}, M_{1}, M_{2}, ..., M_{2^{l_{0}+...ln}} = M such that:

(a) each

ω_{1}^{ck(M_{i},M_{j})} = ω_{1}^{ck};

(b) there are ω_{1}^{ck}-elementary embeddings

τ_{i,j} : M_{i} → N_{j}

for i ≤ j which commute in the sense that if i ≤ j ≤ k then

τ_{i,k} = τ_{j,k} ∘ τ_{i,j};

(c) if t⃗ occupies the jth position in f_{i} under the ordering <^{i} then (c.i) τ_{2^{l_{0}+...l_{i}}+j,2^{l_{0}+...ln}}[M_{i}] includes (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{i}}, (b_{v})_{v∈g_{i}}, (as⃗)_{s⃗<^{i}t⃗}; (c.ii) but F -type_{M}(at⃗) is not realized in M_{j}.

Now we just fold into A all the information about which c⃗, d⃗ as above satisfy

M ⊧ ∃yψ(c⃗, d⃗, y).

If

c⃗ = ⟨c_{0}, c_{1}, ..., c_{m_{0}}⟩ ∈ ⋃_{j≤i}{as⃗|s⃗ ∈ f_{j}},

d⃗ = ⟨d_{0}, d_{1}, ..., d_{m_{1}}⟩ ∈ ⋃_{j≤i}{b_{v}|v ∈ g_{j}}

and M ⊧ ∃yψ(c⃗, d⃗, y) then we can apply the elementarity of the map τ_{2^{l_{0}+...l_{i}},2^{l_{0}+...ln}} to find some b_{v} ∈ τ_{2^{l_{0}+...l_{i}},2^{l_{0}+...+ln}}[M_{2^{l_{0}+...l_{i}}}] with

M ⊧ ψ(c⃗, d⃗, b_{v}).

Thus we can choose to add information about b_{v} to our description of M, at last obtaining a set Ā as indicated. 11.1 ensures that this process does not lead to a violation of (v) in the definition of ℚ_{0}.

□

We need to decide on a filter for ℚ_{0} meeting enough dense sets. For the sake of concreteness and using that ℚ_{0} ∈ L_{ω_{1}^{ck}+2·ω} I do so exactly in the next paragraph. It should be clear that any reasonably generic filter on ℚ_{0} will do.

Notation From now until the end of the section fix G_{0} ⊂ ℚ_{0} an L_{ω_{2}^{ck}}-generic filter. That is to say:

(i) [G_{0} is a filter] (a) if p ∈ G_{0} and p ≤ q, then q ∈ G_{0};

(b) if p_{1}, p_{2} ∈ G_{0} then there is some p ∈ G_{0} with p ≤ p_{1}, p_{2}; (ii) [L_{ω_{2}^{ck}}-generic] if D ⊂ ℚ_{0} is in L_{ω_{2}^{ck}} and is dense in the sense that

∀q ∈ ℚ_{0}∃p ∈ D(p ≤ q)

then we have

D ∩ G_{0} ≠ 0.

We may find such a filter for the usual reason: Letting (D_{n})_{n∈ω} enumerate the dense sets in L_{ω_{2}^{ck}} we find p_{0} ∈ D_{0} and then successively produce p_{n+1} ∈ D_{n+1} with p_{n+1} ≤ p_{n} and finally let G_{0} = {q : ∃n(p_{n} ≤ q)}. The rationale for doing so is slightly more subtle. Basically we wish to use G_{0} to associate to each x⃗ ∈ (2^{ω})^{ω} a corresponding model Mx⃗ of σ. In order for this to work out well we need that G_{0} has taken certain decisions correctly; all these correct choices will be seen by 11.3, 11.5, 11.4, and 11.6 above to correspond to G_{0} meeting various dense sets; all these dense sets are easily definable and obviously present already in L_{ω_{2}^{ck}}.

Of course we could build G_{0} sufficient to our needs by hand, laboriously meeting each specific requirement in some kind of explicit procedure. It is however less fuss notationally to simply summon G_{0} into existence as above.

Definition For x⃗ = (x_{n})_{n∈ω} ∈ (2^{ω})^{ω} we define a structure Mx⃗. We first just describe its underlying set and then wait until after lemma 11.7 to describe how it interprets the relations of L.

|Mx⃗|, the universe of Mx⃗, consists in

{a_{⟨y_{0},y_{1},..,y_{m}⟩}|m ∈ ω, ∀i ≤ m(y_{i}E_{0}x_{i})}
˙∪
{b_{w}|w = (⟨y_{0}, y_{1}, ..., y_{m}⟩, k) some k, m, y⃗ with ∀i ≤ m(y_{i}E_{0}x_{i})}.

For the purposes of this definition one should think of ay⃗ ≠ az⃗ any y⃗ ≠ z⃗, b_{v} ≠ b_{w} any w ≠ v, and ay⃗ ≠ b_{w} any y, w.

Definition For y⃗ = ⟨y_{0}, y_{1}, ..., y_{m}⟩, each y_{i} ∈ 2^{ω}, and for n ≥ m and l⃗ = (l_{0}, l_{1}, ..., l_{n}) ∈ ω^{n+1}, we let

πl⃗(y⃗) = ⟨y_{0}|_{l_{0}}, y_{1}|_{l_{1}}, ..., y_{m}|_{l_{m}}⟩.

Similarly if w = (y⃗, k) then

πl⃗(w) = (⟨y_{0}|_{l_{0}}, y_{1}|_{l_{1}}, ..., y_{m}|_{l_{m}}⟩, k).

Definition A subset F ⊂ G_{0} of our filter is cofinal if there is some q_{0} ∈ G_{0} such that

∀p ≤ q_{0}(p ∈ G_{0} ⇒ p ∈ F).

We can say then that “such and such” happens cofinally often in G_{0} if the set {p ∈ G_{0} : “such and such happens for” p} is a cofinal subset of our filter.

Lemma 11.7 For R ∈ L, x⃗ ∈ (2^{ω})^{ω}, and

a_{}_{y^{0}}, a_{}_{y^{1}}, ..., a_{}_{y^{k(0)}}, b_{w_{0}}, b_{w_{1}}, ..., b_{w_{k(1)}}

in |Mx⃗| we have one of the following two possibilities:

(i) for cofinally many

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

it is the case that or

(ii) for cofinally many

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})⟩ ∈ G_{0},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

M ⊧ ¬R(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

Proof First let us go to l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩ large enough to absorb all the relevant disagreements: That is to say:-

(a) for each y^{i} = ⟨y_{0}^{i}, y_{1}^{i}, ..., y_{m(i)}^{i}⟩ we have

x_{j}(l) = y_{j}^{i}(l)

all l ≥ l_{i} and j ≤ m(i);

(b) for each w_{i} = (⟨ŷ_{0}^{i}, ŷ_{1}^{i}, ..., ŷ_{m̂(i)}^{i}⟩, k̂_{i}) we have

x_{j}(l) = ŷ_{j}^{i}(l)

all l ≥ l_{i} and j ≤ m̂(i).

After possibly increasing l⃗ we may assume that there is a condition

q_{0} = ⟨B, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

with each f_{i} = 2^{l_{0}} ×...2^{l_{i}}, each g_{i} ⊃ f_{i} ×{k̂_{0}, k̂_{1}, ...}, deciding all the relevant questions about R: That is to say, for all

c⃗ ∈ {as⃗, b_{v} : s⃗ ∈ f_{0} ∪ f_{1} ∪ ... ∪ f_{n}, v ∈ g_{0} ∪ g_{1} ∪ ... ∪ g_{n}},
M_{0} ⊧ B((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}),
M_{1} ⊧ B((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}),

we have

M_{0} ⊧ R(c⃗)

if and only if

M_{1} ⊧ R(c⃗).

Now for any n̄ ≥ n and

k⃗ = ⟨k_{0}, k_{1}, ..., kn̄⟩

with k_{i} ≥ l_{i} all i ≤ n, and any

p = ⟨A, (as⃗)_{s⃗∈f̄_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f̄_{1}}, ...(b_{v})_{v∈ḡn̄}⟩

with p ≤ q_{0} and each f̄_{i} = 2^{k_{0}} × ...2^{k_{i}} we may discharge the assumptions (a) and (b) above to find some t⃗ ∈ 2^{k_{0}−l_{0}} × 2^{k_{1}−l_{1}} × ... × 2^{k_{n}−l_{n}} such that each

πl⃗(y^{i}) ∗ t⃗ = πk⃗(y^{i}),

πl⃗(w^{i}) ∗ t⃗ = πk⃗(w_{i}).

Then for any

M_{B} ⊧ B((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}),
M_{A} ⊧ A(as⃗)_{s⃗∈f̄_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f̄_{1}}, ...(b_{v})_{v∈ḡn̄}),

we have by p ≤ q_{0} that

M_{B} ⊧ R(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, a_{πl⃗(w_{0})}, ..., a_{πl⃗(w_{k(1)})})

if and only if

M_{A} ⊧ R(a_{πk⃗(y^{0})}, ..., a_{πk⃗(y^{k(0)})}, b_{πk⃗(w_{0})}, ..., b_{πk⃗(w_{k(1)})}).
□

Exactly the same proof extends to arbitrary formulas in L_{ω_{1}^{ck}}. Lemma 11.8 For ψ ∈ L_{ω_{1},ω} ∩ L_{ω_{1}^{ck}}, x⃗ ∈ (2^{ω})^{ω}, and

a_{}_{y^{0}}, a_{}_{y^{1}}, ..., a_{}_{y^{k(0)}}, b_{w_{0}}, b_{w_{1}}, ..., b_{w_{k(1)}}

in |Mx⃗| we have one of the following two possibilities:

(i) for cofinally many p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0}, with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that for all M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

it is the case that

M ⊧ ψ(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})});

or

(ii) for cofinally many p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0}, with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

M ⊧ ¬ψ(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

Definition With 11.7 in hand we can turn Mx⃗ into an L-structure as follows. For R a relation symbol in the language,

Mx⃗ ⊧ R(a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ...)

if and only if the following two things happen:

(a) a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ... are in |Mx⃗| (as given in the definition prior to 11.7);

(b) for all sufficiently large l⃗ and for cofinally many for cofinally many

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

it is the case that

M ⊧ R(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

We are assuming L to have no function symbols, so this does suffice to define an Lstructure.

Lemma 11.9 For ψ ∈ L_{ω_{1},ω} ∩ L_{ω_{1}^{ck}} and a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ... in |Mx⃗|, we have

Mx⃗ ⊧ ψ(a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ...)

if and only for all sufficiently large l⃗ and cofinally many

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that:

for all M ∈ Mod_{Ω}(σ), if

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}),

then

M ⊧ ψ(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

Proof This follows in the usual way by induction on the logical complexity of ψ and 11.8. In this induction on complexity, the passage from ψ to ∃zψ uses 11.6.

□

Lemma 11.10 If

x⃗(E_{0})^{ω}y⃗,

then

Mx⃗ = My⃗.

Proof Immediate from the definitions.

□

Lemma 11.11 If

Mx⃗ ≅ My⃗,

then

x⃗(E_{0})^{ω}y⃗.

Proof Suppose that x⃗ = ⟨x_{0}, x_{1}, ...⟩ and z⃗ = ⟨z_{0}, z_{1}, ...⟩ are not (E_{0})^{ω} equivalent. We will show that the resulting models are not isomorphic. In fact we will even show that the sets of F -types realized in the two models are distinct.

Fix k with x_{k} not E_{0} equivalent to z_{k}. Let y⃗ = ⟨x_{0}, x_{1}, ..., x_{k}⟩. I wish to claim that F -type_{Mx⃗}(ay⃗) does not appear in {F -type_{Mz⃗}(c) : c ∈ Mz⃗}. This splits into two cases.

Claim(1) For all ar⃗ ∈ |Mz⃗| we have F -type_{Mx⃗}(ay⃗) ≠ F -type_{Mz⃗}(ar⃗).

Proof of claim: We may choose l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, n ≥ k, f_{0} = 2^{l_{0}}, f_{1} = 2^{l_{0}} × 2^{l_{1}}, ..., f_{n} = 2^{l_{0}} × ...2^{l_{n}}, and

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

with

πl⃗(y⃗) ≠ πl⃗(r⃗).

Then for some ψ_{πl⃗(y⃗),πl⃗(r⃗)} it follows from the definition of the ordering on ℚ_{0} and 11.9 that

Mx⃗ ⊧ ψ_{πl⃗(y⃗),πl⃗(r⃗)}(ay⃗)

but

Mz⃗ ⊧ ¬ψ_{πl⃗(y⃗),πl⃗(r⃗)}(ar⃗).
(□Claim(1))

Claim(2) For all b_{w} ∈ |Mz⃗| we have F -type_{Mx⃗}(ay⃗) ≠ F -type_{Mz⃗}(b_{w}).

Proof of claim: First of all we may assume that there are cofinally

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

such that for some assignment

s⃗ ↦ φs⃗

of formulas in F to sequences in s⃗ ∈ ⋃_{i≤n} f_{i} such that for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

M ⊧ φs⃗(as⃗) ∧ ¬φs⃗(b_{πl⃗(w)});

the point is that if this failed then we can assume by genericity that we have

p = ⟨A, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0}

and some fixed t⃗ ∈ ⋃_{i≤n} f_{i} such that

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

M ⊧ ⋀_{φ∈F}(φ(at⃗) ⇔ φ(b_{πl⃗(w)})),

and this puts us back exactly into claim(1).

But now for t⃗ = πl⃗(y⃗) we are again able to apply 11.9 and the definition of the ordering on ℚ_{0} to get

Mx⃗ ⊧ φt⃗(ay⃗)

but

Mx⃗ ⊧ ¬φt⃗(b_{w}).
(□Claim(2))
□

Lemma 11.12 There is a Borel function

θ : (2^{ω})^{ω} → Mod(σ)

such that for any x⃗ ∈ (2^{ω})^{ω} we have

θ(x⃗) ≅ Mx⃗.

Proof This follows by the uniformization theorem for Borel sets with countable sections, as found in 18C of [17], since |Mx⃗| is a countable and uniformly Δ_{1}^{1}(x) set and all the relations on Mx⃗ are again uniformly Δ_{1}^{1}(x).

□

Corollary 11.13 Under the assumptions of case(I), we have

(E_{0})^{ω} ≤_{B}≅ |_{Mod(σ)}.

Proof By 11.10, 11.11, and 11.12.

□

12 Proof for case(IIb)

We leave case(IIa) to last, and instead fix F and H_{F} as in the assumptions of case(IIb). We let Y_{F} be the set of M ∈ Mod(σ) such that for all a⃗ ∈ T_{M}^{F} and fragments H ∈ L_{ω_{1}^{ck}} we have

sup_{b⃗∈M}ρ_{F,M}^{H}(a⃗, b⃗) ≥ ω.

Our case assumption is

Y_{F} ≠ 0.

Lemma 12.1 Given M ∈ Mod(σ), the set of (H, α, a⃗, b⃗) such that (i) α ∈ ω_{1}^{ck},

(ii) H is a fragment including H_{F} in L_{ω_{1}^{ck}},
(iii) a⃗ ∈ T_{M}^{F},
(iv) b⃗ ∈ M, and
(v) ρ_{F,M}^{H}(a⃗, b⃗) = α

is uniformly Δ_{1}(M) over L_{ω_{1}^{ck(M)}}[M].

Proof It is a routine exercise in transfinite recursion to see that (v) is Δ_{1} over any admissible set containing the relevant parameters; the other clauses are trivially Δ_{1}.

□

Corollary 12.2 Given M ∈ Mod(σ), the set of (H, α, a⃗, b⃗) such that (i) α ∈ ω_{1}^{ck},

(ii) H is a fragment including H_{F} in L_{ω_{1}^{ck}},
(iii) a⃗ ∈ T_{M}^{F},
(iv) b⃗ ∈ M, and
(v) for all fragments H′ ⊃ H in L_{ω_{1}^{ck}} we have ρ_{F,M}^{H′}(a⃗, b⃗) ≥ α

is uniformly Π_{1}(M) over L_{ω_{1}^{ck(M)}}[M].

Corollary 12.3 Given a fragment H ∈ L_{ω_{1}^{ck}} and α ∈ ω_{1}^{ck} we have that the set of (M, a⃗, b⃗) such that for all fragments H′ ⊃ H in L_{ω_{1}^{ck}} we have ρ_{F,M}^{H′}(a⃗, b⃗) ≥ α is Σ_{1}^{1}

Proof From 12.2 by Spector-Gandy.

□

Lemma 12.4 Given fragments H_{0}, H_{1} with H_{0} ⊃ H_{1} ⊃ H_{F}, and given M ∈ Mod(σ), we have for all a⃗ ∈ T_{M}^{F}, b⃗ ∈ M

ρ_{F,M}^{H_{0}}(a⃗, b⃗) ≤ ρ_{F,M}^{H_{1}}(a⃗, b⃗).

G. Hjorth 73

Proof Since H_{0} has more formulas, there are more c⃗ with

ρ_{F,M}^{H_{0}}(a^{⌢}c⃗, b⃗) = 0.

□

Corollary 12.5 For M ∈ Mod(σ), a⃗ ∈ T_{M}^{F}, b⃗ ∈ M there is H_{0} ⊃ H_{F} in L_{ω_{1}^{ck}} such that for all fragments H^{∗} ⊃ H_{0} in L_{ω_{1}^{ck}} we have

ρ_{F,M}^{H_{0}}(a⃗, b⃗) = ρ_{F,M}^{H^{∗}}(a⃗, b⃗).

Definition Thus given M ∈ Mod(σ), a⃗ ∈ T_{M}^{F}, and b⃗ ∈ Mod(σ) we may naturally define

ρ_{F,M}^{∞}(a⃗, b⃗)

to be the unique γ such that for all sufficiently large fragments H ∈ L_{ω_{1}^{ck}}

ρ_{F,M}^{H}(a⃗, b⃗) = γ.

The next lemma provides the whole reason why the ρ_{F,M}^{H}(·, ·) rank function is useful. It states that if b⃗ ∈ M, c ∈ M, and each b_{i} (from the finite sequence b⃗ = ⟨b_{0}, b_{1}, ...⟩) has lower rank than c, then the F -type of c is not definable from b⃗. Lemma 12.6 If

(i) M ∈ Mod(σ),

(ii) a⃗ ∈ T_{M}^{F},
(iii) c ∈ M,
(iv) b⃗ = ⟨b_{0}, b_{1}, ..., b_{n}⟩ ∈ M,
(iv) H ⊃ H_{F} is a fragment in L_{ω_{1}^{ck}}, and
(vi) ∀i ≤ n(ρ_{F,M}^{H}(a⃗, b_{i}) < ρ_{F,M}^{H}(a⃗, c)),

then there is no ψ ∈ H such that

M ⊧ ψ(a⃗, b⃗, c)

and

M ⊧ ∀c_{0}, c_{1}((ψ(a⃗, b⃗, c_{0}) ∧ ψ(a⃗, b⃗, c_{1})) ⇒ ⋀_{φ∈F}(φ(c_{0}) ⇔ φ(c_{1}))).

Proof We successively find d_{0}, d_{1}, ..., d_{k}, ... in M such that for all k ∈ ω

a^{⌢}d_{0}^{⌢}d_{1}^{⌢}...^{⌢}d_{k} ∈ T_{M}^{F}

and for all i ≤ n

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}d_{1}^{⌢}...^{⌢}d_{k}, b_{i}) < ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}, c).

Suppose we have succeeded so far in finding d_{0}, d_{1}, ..., d_{k} and we wish to produce d_{k+1}. First if we are at a successor ordinal, with

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}, c) = δ + 1

we can by the definition of this rank function choose d_{k+1} with

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}^{⌢}d_{k+1}, c) = δ.

Since at each i ≤ n we necessarily have

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}, b_{i}) > ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}^{⌢}d_{k+1}, b_{i}),

we do indeed obtain

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}d_{1}^{⌢}...^{⌢}d_{k}^{⌢}d_{k+1}, b_{i}) < ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}^{⌢}d_{k+1}, c).

The other possibility is that we are at some limit ordinal with

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}, c) = λ.

Then since b⃗ is finite we may apply the inductive assumption on ⟨d_{0}, d_{1}, ..., d_{k}⟩ and find some γ < λ with each

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}, b_{i}) ≤ γ.

Then we can choose d_{k+1} with

ρ_{F,M}^{H}(a^{⌢}d_{0}^{⌢}...^{⌢}d_{k}^{⌢}d_{k+1}, c) ≥ γ.

This process must eventually terminate, and it can only do so with some d⃗ such that at each i ≤ n

0 = ρ_{F,M}^{H}(a^{⌢}d⃗, b_{i}) < ρ_{F,M}^{H}(a^{⌢}d⃗, c).

But now whatever F -types we can define over H from a^{⌢}d⃗^{⌢}b⃗ we can already define from a^{⌢}d⃗.

□

Corollary 12.7 Fix M ∈ Mod(σ), c ∈ M, b⃗ = ⟨b_{0}, b_{1}, ..., b_{n}⟩ ∈ M, a⃗ ∈ M.

If

∀i ≤ n(ρ_{F,M}^{∞}(a⃗, b_{i}) < ρ_{F,M}^{∞}(a⃗, c))

then for all fragments H ∈ L_{ω_{1}^{ck}} we have that F -type_{M}(c) is not H-definable from a^{⌢}b⃗; that is to say, there is no ψ ∈ H such that

M ⊧ ψ(a⃗, b⃗, c)

and

M ⊧ ∀c_{0}, c_{1}((ψ(a⃗, b⃗, c_{0}) ∧ ψ(a⃗, b⃗, c_{1})) ⇒ ⋀_{φ∈F}(φ(c_{0}) ⇔ φ(c_{1}))).

Lemma 12.8 M, c, b⃗, a⃗ as in 12.7.

For any Σ_{1}^{1} set A with

M ⊧ A(a⃗, b⃗, c)

there exists N ∈ Mod(σ) and a^{∗}, b⃗^{∗}, c_{0}^{∗}, c_{1}^{∗} ∈ N such that

N ⊧ A(a^{∗}, b⃗^{∗}, c_{0}^{∗}),
N ⊧ A(a^{∗}, b⃗^{∗}, c_{1}^{∗}),

but F -type_{N} (c_{0}^{∗}) ≠ F -type_{N} (c_{1}^{∗}).

Proof Otherwise applying boundedness and 7.1, in a manner similar but easier than the proof of 8.2, we obtain some ψ ∈ L_{ω_{1},ω} ∩ L_{ω_{1}^{ck}} such that

(i) for all N ∈ Mod(σ) and a^{∗}, b⃗^{∗}, c^{∗} ∈ N,

N ⊧ A(a^{∗}, b⃗^{∗}, c^{∗}) ⇒ N ⊧ ψ(a^{∗}, b⃗^{∗}, c^{∗});
(ii) for all N ∈ Mod(σ) and a^{∗}, b⃗^{∗}, c_{0}^{∗}, c_{1}^{∗} ∈ N with
N ⊧ ψ (a^{∗}, b⃗^{∗}, c_{0}^{∗}),
N ⊧ ψ (a^{∗}, b⃗^{∗}, c_{1}^{∗}),
we have F -type_{N} (c_{0}^{∗}) = F -type_{N} (c_{1}^{∗}).

In particular then we have M ⊧ A(a⃗, b⃗, c) and for any d ∈ M

M ⊧ ψ(a⃗, b⃗, d) ⇒ ⋀_{φ∈F}(φ(c) ⇔ φ(d)).

Thus F -type_{M}(c) is H-definable from a^{⌢}b⃗ for any fragment H ⊃ H_{F} which contains ψ; which in turn is in violation of the assumptions on a⃗, b⃗, c, M, and the statement of 12.7.

□

Corollary 12.9 Suppose M ∈ Mod(σ), a⃗ ∈ M, b⃗ = ⟨b_{0}, b_{1}, ..., b_{n}⟩ ∈ M, c⃗ = ⟨c_{0}, c_{1}, ..., c_{k}⟩ ∈ M, and

∀i ≤ n∀j ≤ k(ρ_{F,M}^{∞}(a⃗, b_{i}) < ρ_{F,M}^{∞}(a⃗, c_{j})).

Then for any Σ_{1}^{1} set A with

M ⊧ A(a⃗, b⃗, c⃗)

we may find some N ∈ Mod(σ), a^{∗}, b⃗^{∗}, c^{0} = ⟨c_{0}^{0}, c_{1}^{0}, ..., c_{k}^{0}⟩, c^{1} = ⟨c_{0}^{1}, c_{1}^{1}, ..., c_{k}^{1}⟩ ∈ M such that

N ⊧ A(a^{∗}, b⃗^{∗}, c^{∗}),
N ⊧ A(a^{∗}, b⃗^{∗}, c^{∗∗}),

for all i, j ≤ k

F −type_{N} (c_{i}^{∗}) ≠ F −type_{N} (c_{j}^{∗∗}).

Proof First let us fix H, β⃗, γ⃗, such that for all i ≤ n, j ≤ k

ρ_{F,M}^{∞}(a⃗, b_{i}) = ρ_{F,M}^{H}(a⃗, b_{i}) = β_{i},
ρ_{F,M}^{∞}(a⃗, c_{j}) = ρ_{F,M}^{H}(a⃗, c_{j}) = γ_{i}.

By 12.3 we have that these various statements about the ranks are Σ_{1}^{1}. Thus appealing to 12.8 we can find N_{0} ∈ Mod(σ) and a^{∗0}, b⃗^{∗0}, c^{∗0} = ⟨c_{0}^{∗0}, c_{1}^{∗0}, ..., c_{k}^{∗0}⟩, c^{∗∗0} = ⟨c_{0}^{∗∗0}, c_{1}^{∗∗0}, ..., c_{k}^{∗∗0}⟩ ∈ N_{0} such that

N_{0} ⊧ A(a^{∗0}, b⃗^{∗0}, c^{∗0}),
N_{0} ⊧ A(a^{∗0}, b⃗^{∗0}, c^{∗∗0}),
ρ_{F,N_{0}}^{∞}(a^{∗0}, b_{i}^{∗0}) = ρ_{F,N_{0}}^{H}(a^{∗0}, b_{i}^{∗0}) = β_{i},
ρ_{F,N_{0}}^{∞}(a^{∗0}, c_{j}^{∗0}) = ρ_{F,N_{0}}^{H}(a^{∗0}, c_{j}^{∗0}) = γ_{i},
ρ_{F,N_{0}}^{∞}(a^{∗0}, c_{j}^{∗∗0}) = ρ_{F,N_{0}}^{H}(a^{∗0}, c_{j}^{∗∗0}) = γ_{i},

and for some φ_{∗0} ∈ F

N_{0} ⊧ φ_{∗0}(c_{0}^{∗0}) ∧ ¬φ_{∗0}(c_{0}^{∗∗0}).

But now we can apply the same reasoning to N_{0}, c^{0∗∗} and all the Σ_{1}^{1} sets implicit in the same description and find N_{1} ∈ Mod(σ), a^{∗1}, b⃗^{∗1}, c^{∗1} = ⟨c_{0}^{∗1}, c_{1}^{∗1}, ..., c_{k}^{∗1}⟩, d⃗^{0} = ⟨d_{0}^{0}, d_{1}^{0}, ..., d_{k}^{0}⟩, d⃗^{1} = ⟨d_{0}^{1}, d_{1}^{1}, ..., d_{k}^{1}⟩ ∈ N_{0} and φ ∈ F such that

N_{1} ⊧ A(a^{∗1}, b⃗^{∗1}, c^{∗1}),
N_{1} ⊧ A(a^{∗1}, b⃗^{∗1}, d⃗^{0}),
N_{1} ⊧ A(a^{∗1}, b⃗^{∗1}, d⃗^{1}),
N_{1} ⊧ φ_{∗0}(c_{0}^{∗0}) ∧ ¬φ_{∗0}(d_{0}^{0}) ∧ ¬φ_{∗0}(d_{0}^{1}),
N_{1} ⊧ φ(d_{1}^{0}) ∧ ¬φ(d_{1}^{1}),
ρ_{F,N_{1}}^{∞}(a^{∗1}, b_{i}^{∗1}) = ρ_{F,N_{1}}^{H}(a^{∗1}, b_{i}^{∗1}) = β_{i},
ρ_{F,N_{1}}^{∞}(a^{∗1}, c_{j}^{∗1}) = ρ_{F,N_{1}}^{H}(a^{∗1}, c_{j}^{∗1}) = γ_{i},
ρ_{F,N_{1}}^{∞}(a^{∗1}, d_{j}^{0}) = ρ_{F,N_{1}}^{H}(a^{∗1}, d_{j}^{0}) = γ_{i},
ρ_{F,N_{1}}^{∞}(a^{∗1}, d_{j}^{1}) = ρ_{F,N_{1}}^{∞}(a^{∗1}, d_{j}^{1}) = γ_{i}.

Then depending on whether φ(c_{1}^{∗1}) holds in N_{1} we either let c^{∗∗1} = d⃗^{1} and φ_{∗1} = ¬φ or c^{∗∗1} = d⃗^{0} and φ_{∗1} = φ.

Continuing in this fashion we at last arrive at N_{k}, φ_{∗0}, φ_{∗1}, ..., φ_{∗k} in F, a^{∗k}, b⃗^{∗k}, c^{∗k} = ⟨c_{0}^{∗k}, c_{1}^{∗k}, ..., c_{k}^{∗k}⟩, c^{∗∗k} = ⟨c_{0}^{∗∗k}, c_{1}^{∗∗k}, ..., c_{k}^{∗∗k}⟩ ∈ N_{0} and φ_{∗0}, φ_{∗1}, ..., φ_{∗k} ∈ F such that

N_{k} ⊧ A(a^{∗k}, b⃗^{∗k}, c^{∗k}),

N_{k} ⊧ A(a^{∗k}, b⃗^{∗k}, c^{∗∗k}),

and at each i ≤ k

N_{k} ⊧ φ_{∗i}(c_{i}^{∗k}) ∧ ¬φ_{∗i}(c_{i}^{∗∗k}).

N = N_{k}^{∗}, a^{∗} = a^{∗k}, b⃗^{∗} = b⃗^{∗k}, c^{0} = c^{∗k}, c^{1} = c^{∗∗k} is then as required.

□

Lemma 12.10 There is some γ < ω_{1}^{ck} such that for all M ∈ Mod(σ), a⃗ ∈ T_{M}^{F}, b⃗ ∈ M we have

ρ_{F,M}^{H_{F}}(a⃗, b⃗) < γ.

Proof Consider the Σ_{1}^{1} relation

(M, a⃗, b⃗)R(N , c⃗, d⃗)

if

M = N ,
c⃗ = d⃗,

c⃗ extends a⃗,

a⃗, c⃗ ∈ T_{M}^{F},

and F -type_{N} (d⃗) is not H_{F} definable from c⃗ over N. This relation is well founded by case assumption. Thus by 3.1 it has rank some γ < ω_{1}^{ck}, which, after unwinding the definitions, can be seen to be as required.

□

So far nothing mentioned is specific to case(IIb) as against case(IIa). We have simply used the existence of the ranking function and not that its supremum over the b⃗ is infinite; the next lemma however specifically uses our case assumptions.

Note there is a natural tendency for the supremums of the ranking functions to cluster around a limit ordinal. If sup_{b⃗∈M}ρ_{F,M}^{H}(a⃗, b⃗) = β + 1, then this implies directly from the definitions that whenever a^{⌢}c ∈ T_{M}^{F} then sup_{b⃗∈M}ρ_{F,M}^{H}(a^{⌢}c, b⃗) ≤ β. This dropping can happen finitely many times, since there is no infinite descending chain of ordinals; thus we can eventually produce a^{∗} ⊃ a⃗ in T_{M}^{F} such that for all (a^{∗})^{⌢}c we have

sup_{b⃗∈M}ρ_{F,M}^{H}(a^{∗}, b⃗) = sup_{b⃗∈M}ρ_{F,M}^{H}((a^{∗})^{⌢}c, b⃗);

but then this sup_{b⃗∈M}ρ_{F,M}^{H}(a^{∗}, b⃗) must be a limit.

Lemma 12.11 There is an infinite limit ordinal λ_{0} < ω_{1}^{ck}, M ∈ Y_{F}, a^{0} ∈ T_{M}^{F}, H_{0} ∈ L_{ω_{1}^{ck}} a fragment including H_{F}, such that

(i) sup_{b⃗∈M}ρ_{F,M}^{H_{0}}(a^{0}, b⃗) = λ_{0}

(ii) sup_{b⃗∈M}ρ_{F,M}^{∞}(a^{0}, b⃗) = λ_{0}.

Proof Suppose instead that for every such fragment H_{0} ∈ L_{ω_{1}^{ck}}, infinite limit λ_{0}, M ∈ Y_{F}, a^{0} ∈ T_{M}^{F},

sup_{b⃗∈M}ρ_{F,M}^{H_{0}}(a^{0}, b⃗) = λ_{0}

implies the existence of some γ_{0} < λ_{0} such that for all b⃗ ∈ M there is Hb⃗ ⊃ H_{0} in L_{ω_{1}^{ck}} with

ρ_{F,M}^{Hb⃗}(a^{0}, b⃗) ≤ γ_{0}.

Note that the indicated property of γ_{0} is Σ_{1} over L_{ω_{1}^{ck(M)}}[M] since the complexity class Σ_{1} is closed under bounded quantification inside any admissible set.

Then taking H_{0} as a parameter and considering the Σ_{1}^{1} set of such (M, a^{0}, b⃗) and applying 3.4 we can find a single δ_{0} < ω_{1}^{ck} such that we can always find the fragment Hb⃗ ∈ L_{δ_{0}}, and thus we have that H_{1} = L_{ω_{1},ω} ∩L_{δ_{0}+ω} suffices to obtain that for every M ∈ Y_{F}, a^{0}, b⃗ as above

sup_{b⃗∈M}ρ_{F,M}^{H_{1}}(a^{0}, b⃗) < λ_{0}.

But then for every such M, a^{0} we can find some limit ordinal λ_{1} < λ_{0} and some (a^{0})^{⌢}(a^{1}) ∈ T_{M}^{F} with

sup_{b⃗∈M}ρ_{F,M}^{H_{1}}((a^{0})^{⌢}(a^{1}), b⃗) = λ_{1}.

Then we can run up and find H_{2} (depending on only on H_{1} and λ_{1}) which again drops the supremums of the ranks below λ_{1}.

This process must eventually terminate for each M ∈ Y_{F} and a^{0} ∈ T_{M}^{F}. It can only come to rest by us having eventually obtained some (a^{0})^{⌢}(a^{1})^{⌢}...^{⌢}(a^{n}) ∈ T_{M}^{F} and H_{n} ∈ L_{ω_{1}^{ck}} with

sup_{b⃗∈M}ρ_{F,M}^{H_{n}}((a^{0})^{⌢}(a^{1})...^{⌢}(a^{n}), b⃗) = 0.

But then we have shown that for every M ∈ Y_{F} there is d⃗ ∈ T_{M}^{F} and H_{n} ∈ L_{ω_{1}^{ck}} with

sup_{b⃗∈M}ρ_{F,M}^{H_{n}}(d⃗, b⃗) = 0.

Thus by 3.4 we can in fact find a single α < ω_{1}^{ck} such that for all M ∈ Y_{F} there is d⃗ ∈ T_{M}^{F} and H_{n} ∈ L_{α} with

sup_{b⃗∈M}ρ_{F,M}^{H_{n}}(d⃗, b⃗) = 0.

Taking H = L_{α+ω} ∩ L_{ω_{1},ω} we finish with a contradiction to the case assumption.

□

Notation From now until the end of the proof for case(IIb) fix an infinite limit ordinal λ_{0} < ω_{1}^{ck} and fragment H_{0} ⊃ H_{F} such that H_{0} ∈ L_{ω_{1}^{ck}} and there exists M ∈ Y_{F}, a⃗ ∈ T_{M}^{F} such that

(i) sup_{b⃗∈M}ρ_{F,M}^{H_{0}}(a⃗, b⃗) = λ_{0};

(ii) sup_{b⃗∈M}ρ_{F,M}^{∞}(a⃗, b⃗) = λ_{0}. In what follows let us assume for notational simplicity that we can actually take a⃗ to be the empty sequence. Thus:

(i) sup_{b⃗∈M}ρ_{F,M}^{H_{0}}(0, b⃗) = λ_{0}; (ii) sup_{b⃗∈M}ρ_{F,M}^{∞}(0, b⃗) = λ_{0}.

Again it will be convenient to pass to the space Mod_{Ω}(σ), of models of σ with underlying set Ω = (2^{<ω})^{<ω}. We then let Z_{F} be the set of M ∈ Mod_{Ω}(σ) such that:

(i) there is an isomorphic copy, N ≅ M, with N ∈ Y_{F}; (ii) sup_{b⃗∈M}ρ_{F,M}^{H_{0}}(0, b⃗) = λ_{0}; (iii) sup_{b⃗∈M}ρ_{F,M}^{∞}(0, b⃗) = λ_{0}.

Note that Z_{F} is a Σ_{1}^{1} set.

Definition Let ℚ_{1} be the set of sequences of the form

⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩

such that (i) n ∈ ω; γ⃗ ∈ λ_{0}^{<ω}; γ_{0} = 0, γ_{1} > 1, each γ_{i+1} > γ_{i}; (ii) for some l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩ we have each f_{i} = 2^{l_{0}} × 2^{l_{1}} × ...2^{l_{i}} and each g_{i} a finite subset of f_{i} × ω; (iii) A is a non-empty Σ_{1}^{1} subset of Mod_{Ω}(σ); (iv) every M ∈ Mod_{Ω}(σ) with

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})

is in Z_{F};

(v) H is a fragment in L_{ω_{1}^{ck}} extending H_{0}; for any

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})

one has for each i ≤ n and s⃗ ∈ f_{i}, v ∈ g_{i} that

0 < ρ_{F,M}^{H}(0, as⃗) = ρ_{F,M}^{∞}(0, as⃗) ∈ [γ_{i}, γ_{i+1}),
0 ≤ ρ_{F,M}^{H}(0, b_{v}) = ρ_{F,M}^{∞}(0, b_{v}) ∈ [γ_{i}, γ_{i+1});

(vi) for each u⃗, t⃗ ∈ ⋃_{i≤n} f_{i} with u⃗ ≠ t⃗ there exists ψ_{u⃗,t⃗} ∈ F such that for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})

one has

M ⊧ ψ_{u⃗,t⃗}(au⃗) ∧ ¬ψ_{u⃗,t⃗}(at⃗).

We can think of elements in ℚ_{1} as partial descriptions of models of σ. This is very much parallel to the definition of ℚ_{0}, but with the difference that at (v) we do not ask that differing as⃗’s have the potential to come from the images of a nested array of elementary submodels, but rather that they occupy strata with respect to the rank functions; for i < j ≤ n and s⃗ ∈ f_{i}, u⃗ ∈ f_{j}, we are requiring that

γ_{i} ≤ ρ_{F,M}^{∞}(0, as⃗) < γ_{i+1} ≤ γ_{j} < ρ_{F,M}^{∞}(0, at⃗) < γ_{j+1}.

We then define an ordering on ℚ_{1} parallel to the ordering on ℚ_{0}.

Definition For

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩

and

p̄ = ⟨Ā, H̄, δ⃗, (as⃗)_{s⃗∈f̄_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f̄_{1}}, ...(b_{v})_{v∈ḡn̄}⟩

both in ℚ_{1} we set p̄ ≤ p if the following all take place:- (i) n ≤ n̄; δ⃗ extends the sequence γ⃗; H̄ ⊃ H; (ii) there are l_{0}, l_{1}, ..., l_{n}, k_{0}, ..., k_{n}, such that for each i ≤ n we have f_{i} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{i}} and f̄_{i} = 2^{l_{0}+k_{0}} × 2^{l_{1}+k_{1}} × ... × 2^{l_{i}+k_{i}}; (iii) for l_{0}, l_{1}, ..., l_{n}, k_{0}, ..., k_{n} as in (ii) we have that each

ḡ_{i} ⊃ {v ∗ t⃗: t⃗ ∈ 2^{k_{0}} × ... × 2^{k_{i}}, v ∈ g_{i}};

(iv) for any

M ⊧ Ā((as⃗)_{s⃗∈f̄_{0}}, (b_{v})_{v∈ḡ_{0}}, (ās⃗)_{s⃗∈f̄_{1}}, ...(b_{v})_{v∈ḡn̄})

and t⃗ ∈ 2^{k_{0}} × ...2^{k_{n}} we have

M ⊧ A((a_{s⃗∗t⃗})_{s⃗∈f_{0}}, (b_{v∗t⃗})_{v∈g_{0}}, (a_{s⃗∗t⃗})_{s⃗∈f_{1}}, ...(b_{v∗t⃗})_{v∈g_{n}}).

Lemma 12.12 For

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩

in ℚ_{1} and m ≤ n, there is

p̄ = ⟨Ā, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{m−1}}, (as⃗)_{s⃗∈f_{m}^{(m)}}, (b_{v})_{v∈g_{m}^{(m)}}, ..., (b_{v})_{v∈g_{n}^{(m)}}⟩ ∈ ℚ_{1}

with

p̄ ≤ p.

Proof The lemma asserts that we may fix (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{m−1}} as a parameter and essentially split the sequence (as⃗)_{s⃗∈f_{m}^{(m)}}, (b_{v})_{v∈g_{m}^{(m)}}, ..., (b_{v})_{v∈g_{n}^{(m)}} into two sequences with different F -types. This is exactly as stated at 12.9.

□

Lemma 12.13 For all

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩

in ℚ_{1} and λ < λ_{0} there is

p̄ = ⟨Ā, H̄, δ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}, (as⃗)_{s⃗∈f_{n+1}}, (b_{v})_{v∈g_{n+1}}⟩

in ℚ_{1} with (i) p̄ ≤ p;

(ii) δ⃗ = ⟨γ_{0}, γ_{1}, ..., γ_{n}, γ_{n+1}, γ_{n+2}⟩ for some γ_{n+2} > λ.

Proof Let γ⃗ = ⟨γ_{0}, γ_{1}, ...γ_{n+1}⟩. Fix some M ∈ Z_{F} with

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}).

Appealing to the definition of Z_{F} we may find some H̄ ⊃ H and γ > λ, γ_{n+1} and c ∈ M with

ρ_{F,M}^{∞}(0, c) = ρH̄ ; F,M(0, c) = γ.

Following 12.9 we may find some N with

N ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}})

inside which we can obtain |f_{n}| = |2^{l_{0}+l_{1}+...+l_{n}}| many such c, and so there will be (c_{j})_{j<|2^{l_{0}+l_{1}+...+ln}|} such that each

ρ_{F,N}^{∞} (0, c_{j}) = ρH̄ ; F,N (0, c_{j}) = γ

but

F −type_{N} (c_{j(0)}) ≠ F −type_{N} (c_{j(1)})

for j(0) ≠ j(1).

Then we may let l_{n+1} = 0 and f_{n+1} = f_{n} × {0}, g_{n+1} = 0, reindex the set (c_{j})_{j<|2^{l_{0}+l_{1}+...+ln}|} as (as⃗)_{s⃗∈f_{n+1}}, let δ⃗ = ⟨γ_{0}, γ_{1}, ..., γ_{n}, γ_{n+1}, γ + 1⟩ and choose Ā ∈ Σ_{1}^{1} to describing enough about

⟨N , (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}), (as⃗)_{s⃗∈f_{n+1}}, (b_{v})_{v∈g_{n+1}}⟩

to ensure that for

p̄ = ⟨Ā, H̄, δ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}, (as⃗)_{s⃗∈f_{n+1}}, (b_{v})_{v∈g_{n+1}}⟩ ∈ ℚ_{1}

and for any N^{∗} ∈ Mod_{Ω}(σ) with

N^{∗} ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ..., (as⃗)_{s⃗∈f_{n+1}}, (b_{v})_{v∈g_{n+1}})

we have

N^{∗} ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}).

□

Lemma 12.14 For all

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}⟩ ∈ ℚ_{1}

there is

p̄ = ⟨Ā, H̄, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(as⃗)_{s⃗∈fn̄}(b_{v})_{v∈ḡn̄}⟩ ∈ ℚ_{1}

such that for all

c⃗ ∈ {as⃗, b_{v} : s⃗ ∈ ⋃_{j≤n} f_{j}, v ∈ ⋃_{j≤n} g_{j}}

we have either:

(i) for all

M ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈ḡn̄})

we have

M ⊧ ∀y¬ψ(c⃗, y);

or

(ii) there is somei ≤ n̄ and v ∈ ḡ_{i} such that for all

M ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈ḡn̄})

we have

M ⊧ ψ(c⃗, b_{v}).

Proof It suffices to prove this for a single c⃗ ∈ {as⃗, b_{v} : s⃗ ∈ ⋃_{j≤n} f_{j}, v ∈ ⋃_{j≤n} g_{j}}. So let us fix c⃗ and

M_{0} ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈ḡ_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}}).

Case(1). M_{0} ⊧ ∀y¬ψ(c⃗, y).

Then we can simply tighten up A to Ā so that

M ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}})

if and only if

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}})

and

M ⊧ ∀y¬ψ(c⃗, y).

Case(2). There is some d ∈ M_{0} with M_{0} ⊧ ψ(c⃗, d).

Then after possibly applying 12.13 we may assume that

ρ_{F,M}^{∞}(0, d) < γ_{n+1}.

So we can choose a fragment H̄ ⊃ H with

ρH̄ ; F,M(0, d) = ρ_{F,M}^{∞}(0, d) < γ_{n+1}.

Now for i ≤ n with

γ_{i} ≤ ρH̄ ; F,M(0, d) < γ_{i+1}

we can simply extend g_{i} to ḡ_{i}, where {b_{v} : v ∈ ḡ_{i}} = {b_{v} : v ∈ g_{i}} ∪ {d} and let Ā be given by

M ⊧ Ā((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}})

if and only if

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, (as⃗)_{s⃗∈f_{1}}, ...(b_{v})_{v∈g_{n}})

and

M ⊧ ψ(c⃗, b_{v∗}),

where ḡ_{i} = g_{i} ∪ {v∗}.

□

Notation From now until the end of the section fix an L_{ω_{2}^{ck}}-generic filter G_{1} ⊂ ℚ_{1}.

Definition For x⃗ ∈ (2^{ω})^{ω} we define a countable structure Nx⃗; we define the underlying set now as in section 11, simply letting

|Nx⃗| = |Mx⃗|,

where Mx⃗ is as given just before lemma 11.7.

Lemma 12.15 For R ∈ L, x⃗ ∈ (2^{ω})^{ω}, and

a_{}_{y^{0}}, a_{}_{y^{1}}, ..., a_{}_{y^{k(0}}, b_{w_{0}}, b_{w_{1}}, ..., b_{w_{k(1)}}

in |Mx⃗| we have one of the following two possibilities:

(i) for cofinally many

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{1},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

it is the case that or

(ii) for cofinally many

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})⟩ ∈ G_{1},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

we have

M ⊧ ¬R(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

Proof Just as in 11.7.

□

Definition We provide Nx⃗ with an L-structure as follows. For R a relation symbol in the language,

Nx⃗ ⊧ R(a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ...)

if and only if the following two things happen:

(a) a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ... are in |Nx⃗|;

(b) for all sufficiently large l⃗ and for cofinally many

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}})⟩ ∈ G_{1},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that for all

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}})

it is the case that

M ⊧ R(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

Lemma 12.16 For ψ ∈ L_{ω_{1},ω} ∩ L_{ω_{1}^{ck}} and a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ... in |Nx⃗|, we have

Nx⃗ ⊧ ψ(a_{}_{y^{0}}, a_{}_{y^{1}}, ..., b_{w_{0}}, b_{w_{1}}, ...)

if and only for all sufficiently large l⃗ and cofinally many

p = ⟨A, H, γ⃗, (as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (as⃗)_{s⃗∈f_{n}}, (b_{v})_{v∈g_{n}}⟩ ∈ G_{0},

with each f_{j} = 2^{l_{0}} × 2^{l_{1}} × ... × 2^{l_{j}}, and l⃗ = ⟨l_{0}, l_{1}, ..., l_{n}⟩, we have that:

for all M ∈ Mod_{Ω}(σ), if

M ⊧ A((as⃗)_{s⃗∈f_{0}}, (b_{v})_{v∈g_{0}}, ..., (b_{v})_{v∈g_{n}}),

then

M ⊧ ¬ψ(a_{πl⃗(y^{0})}, ..., a_{πl⃗(y^{k(0)})}, b_{πl⃗(w_{0})}, ..., b_{πl⃗(w_{k(1)})}).

G. Hjorth 85

Proof This follows from 12.14 as 11.9 followed from 11.6.

□

Lemma 12.17 For all x⃗, y⃗ ∈ (2^{ω})^{ω},

x⃗(E_{0})^{ω}y⃗

implies

Nx⃗ = Ny⃗.

Proof As with 11.10 this follows immediately from the definitions.

□

Lemma 12.18 For all x⃗, y⃗ ∈ (2^{ω})^{ω},

Nx⃗ ≅ Ny⃗

implies

x⃗(E_{0})^{ω}y⃗.

Proof Almost word for word as in the proof of 11.11.

□

And again as at 11.12 and 11.13 we have: Lemma 12.19 There is a Borel function

θ : (2^{ω})^{ω} → Mod(σ)

such that for all x⃗ ∈ (2^{ω})^{ω}

Nx⃗ ≅ θ(x⃗).

Finally: Lemma 12.20 Under the assumptions of case(IIb) we have

(E_{0})^{ω} ≤_{B}≅|_{Mod(σ)}.

13 Proof for case(IIa)

From now on let us assume that for all fragments F there is some fragment H ⊃ H_{F} such that

∀M ∈ Mod(σ)∃c⃗ ∈ M(sup_{b⃗∈M}ρ_{F,M}^{H}(c⃗, b⃗) < ω).

Note that if sup_{b⃗∈M}ρ_{F,M}^{H}(c⃗, b⃗) = k some finite k, then for any c^{⌢}d⃗ ∈ T_{M}^{F} with lh(d⃗) = k we have

sup_{b⃗∈M}ρ_{F,M}^{H}(c^{⌢}d⃗, b⃗) = 0,

which states that every F -type is H-definable over M from a^{⌢}d⃗. Note moreover that there is a canonical formula in L_{ω_{1},ω} ∩ L_{ω_{1}^{ck}} which holds about c^{⌢}d⃗ exactly when every F -type realized in M is H-definable from c^{⌢}d⃗.

Thus for every F ∈ L_{ω_{1}^{ck}} we can find fragments

F^{++} ⊃ F^{+} ⊃ H_{F}

such that for all M ∈ Mod(σ):

(a) there exists a⃗ ∈ M such that for all b⃗ ∈ M there exists ψb⃗ ∈ F^{+} with

M ⊧ ψb⃗(a⃗, b⃗)

and for all φ ∈ F

M ⊧ ∀c^{0}, c^{1}((ψb⃗(a⃗, c^{0}) ∧ ψb⃗(a⃗, c^{1})) ⇒ (φ(c^{0}) ⇔ φ(c^{1})));

(b) we have Δ_{F} ∈ F^{++}, the canonical L_{ω_{1},ω} formula such that for all N , e⃗ ∈ N,

N ⊧ Δ_{F} (e⃗)

if and only if for all b⃗ ∈ N there is some ψ ∈ F^{+} with

N ⊧ ψ(e⃗, b⃗)

and for all φ ∈ F

M ⊧ ∀c^{0}, c^{1}((ψ(e⃗, c^{0}) ∧ ψ(e⃗, c^{1})) ⇒ (φ(c^{0}) ⇔ φ(c^{1}))).

The properties indicated for the tripe (F^{+}, F^{++}, Δ_{F}) are uniformly Π_{1}^{1} in any natural number encoding a well ordering of order type α where F is the αth object in L_{ω_{1}^{ck}}. Thus we may assume the functions

F ↦ F^{++}
F ↦ Δ_{F}

are uniformly Σ_{1} over L_{ω_{1}^{ck}}. Thus we may iterate, using that transfinite recursion applied to Σ_{1} over an admissible set leads to functions which are again Σ_{1} over that admissible; thus we obtain a Σ_{1} over L_{ω_{1}^{ck}} function

ω_{1}^{ck} → L_{ω_{1}^{ck}}
α ↦ H_{α},

where

H_{0} = L_{ω,ω},
H_{α+1} = (H_{α})^{++},

and at λ a limit,

H_{λ} = ⋃_{α∈λ} H_{α}.

Recall that at section 5 we define the notion of Σ_{α}^{0} and Π_{α}^{0} formula.

Lemma 13.1 Suppose φ ∈ L_{ω_{1},ω} ∩ (Σ_{α}^{0} ∪ Π_{α}^{0}), α < ω_{1}^{ck}, and M, N ∈ Mod(σ), with a⃗ ∈ M, c⃗ ∈ N such that

M ⊧ Δ_{H_{α}}(a⃗),
N ⊧ Δ_{H_{α}}(c⃗),
H_{α+1}−type_{M}(a⃗) = H_{α+1}−type_{N} (c⃗).

Then

M ⊧ φ(a⃗)

if and only if

N ⊧ φ(c⃗).

Proof We prove this by transfinite induction on α. The base case of α = 0 is trivial as is the passage through limit ordinals.

For successor step, suppose the lemma is true at α and {φ_{i}(x⃗, y⃗) : i ∈ ω} are all either Σ_{α}^{0} or Π_{α}^{0} and suppose

β = α + 1

with M, N ∈ Mod(σ), and a⃗ ∈ M, c⃗ ∈ N, and

M ⊧ Δ_{H_{β}}(a⃗),
N ⊧ Δ_{H_{β}}(c⃗),
H_{β+1}−type_{M}(a⃗) = H_{β+1}−type_{N} (c⃗).

We want to show

M ⊧ ⋁_{i∈ω} ∃y⃗φ_{i}(a⃗, y⃗)

if and only if

N ⊧ ⋁_{i∈ω} ∃y⃗φ_{i}(c⃗, y⃗).

We may as well assume that M ⊧ ∃y⃗φ_{i}(a⃗, y⃗), some i, the other case being symmetrical. Fix a^{0}, a^{1} ∈ M with

M ⊧ φ_{i}(a⃗, a^{0}),
M ⊧ Δ_{H_{α+1}}(a⃗, a^{0}, a^{1}).

By the definition of Δ_{H_{α+1}} we can find some ψ ∈ H_{β+1} such that

M ⊧ ψ(a⃗, a^{0}, a^{1})′

M ⊧ ∀z^{0}, z^{1}(ψ(a⃗, z^{0}, z^{1}) ⇒ ⋀_{θ∈H_{α+1}}(θ(a⃗, z^{0}, z^{1}) ⇔ θ(a⃗, a^{0}, a^{1}))).

Since H_{β+1}−type_{M}(a⃗) = H_{β+1}−type_{N} (c⃗) we can find c^{0}, c^{1} ∈ N with

N ⊧ ψ(c⃗, c^{0}, c^{1}).

Again by H_{β+1}−type_{M}(a⃗) = H_{β+1}−type_{N} (c⃗) we have that for all θ ∈ H_{α+1} with

M ⊧ θ(a⃗, a^{0}, a^{1})

one has

N ⊧ ∀z^{0}, z^{1}(ψ(c⃗, z^{0}, z^{1}) ⇒ θ(c⃗, z^{0}, z^{1})).

Thus we have H_{α+1}−type_{M}(a⃗, a^{0}, a^{1}) = H_{α+1}−type_{N} (c⃗, c^{0}, c^{1}), and we can appeal to the inductive assumption.

□

In the next corollary we use for the first and only time that ≅|_{Mod(σ)} is Borel.

Corollary 13.2 There is a single δ < ω_{1}^{ck} such that for all M, N ∈ Mod(σ)

M ≅ N

if and only if there exist a⃗ ∈ M, c⃗ ∈ N, and

M ⊧ Δ_{H_{δ}}(a⃗),
N ⊧ Δ_{H_{δ}}(c⃗),
H_{δ+1}−type_{M}(a⃗) = H_{δ+1}−type_{N} (c⃗).

Proof Choose δ < ω_{1}^{ck} such that each isomorphism type is Π ∼_{δ}^{0}. Then by [23] we have that for all M ∈ Mod(σ) there is some

φ_{M} ∈ L_{ω_{1},ω} ∩ Π_{δ}^{0}

with

{N ∈ Mod(σ) : N ⊧ φ_{M}} = {N ∈ Mod(σ) : N ≅ M}.

Now the corollary follows from the lemma.

□

Corollary 13.3 Under the case assumptions of case(IIa), ≅ |_{Mod}(σ) is Borel reducible to a countable Borel equivalence relation.

Proof Fix δ < ω_{1}^{ck} as in 13.2. H_{δ+1} is a countable fragment and for each M ∈ Mod(σ) there is by 13.2 a⃗ ∈ M with the H_{δ+1}-theory of ⟨M; a⃗ being ℵ_{0}-categorical. Thus we have by 4.3 of [13] that ≅|_{Mod}(σ) is reducible to a countable Borel equivalence relation

□

There is an alternative way to finish up 13.3. We can define a Borel function

f : Mod(σ) → 2^{H_{δ+1}}

so that for all M ∈ Mod(σ) there exists a⃗ ∈ M with

M ⊧ Δ_{H_{δ}}(a⃗),
H_{δ+1}−type_{M}(a⃗) = f(M).

Then we may alternatively quote from 5.1 of [11]

Lemma 13.4 (Kechris) Let F be a Borel equivalence relation on a Polish space X and

g : X → Y

a Borel function to any other Polish space Y. If (i) for all x ∈ X we have |{g(z) : zF x}| ≤ ℵ_{0}, and

(ii) for all x_{1}, x_{2} ∈ X
g(x_{1}) = g(x_{2}) ⇒ x_{1}F x_{2},

then F is Borel reducible to a countable Borel equivalence relation.

14 Variations and modifications

We have proved:

Theorem 14.1 Let σ ∈ L_{ω_{1},ω} be such that the isomorphism relation ≅|_{Mod(σ)} on its countable models is Borel. Then exactly one of the following occurs:

(I) ≅|_{Mod(σ)} ≤_{B} F for some countable Borel equivalence relation F; (II) (E_{0})^{ω} ≤_{B}≅|_{Mod(σ)}.

There are various refinements which can be obtained more or less immediately by inspection of the proof. The first of these is that we may replace (II) by the nominally stronger

(II*) (E_{0})^{ω} ≤_{c}≅|_{Mod(σ)}, since the process of constructing the model Mx⃗ in case(I) and Nx⃗ in case(IIb) is clearly continuous in x⃗. In fact one can even have

(II*) (E_{0})^{ω} ⊑_{c}≅|_{Mod(σ)}. Indeed an easy Baire category argument shows that:

Fact 14.2 If F is an equivalence relation with

(E_{0})^{ω} ≤_{B} F,

then

(E_{0})^{ω} ⊑_{c} F.

A rather different direction in which the main theorem can be sharpened is to work on Σ ∼_{1}^{1} subsets of the space of countable L-structures, as against only those which are defined by some σ ∈ L_{ω_{1},ω}. If B ∈ Σ_{1}^{1} and

B ∩ X_{F} ≠ 0

then the proof of case(I) at 11 goes as before to obtain (E_{0})^{ω} ≤_{B}≅ |_{B}. For the other cases we have that the application of boundedness at 12.11 works when restricted to a Σ_{1}^{1} set and case(IIa) is unaffected as long as we are working inside some set on which the isomorphism relation is Borel.

Using for instance

Lemma 14.3 (H. Friedman, [5]) If E is a Borel equivalence relation with E ≤_{B}≅ |_{Mod(L)} some countable language L then there is σ ∈ L_{ω_{1},ω} with

(i) ≅|_{Mod(σ)} Borel;

(ii) E ≤_{B}≅|_{Mod(σ)}

one obtains

Theorem 14.4 Let E be a Borel equivalence relation with E ≤_{B}≅ |_{Mod(L)} some countable language L. Then exactly one of the following occurs:

(I) E ≤_{B} F for some countable Borel equivalence relation F; (II) (E_{0})^{ω} ≤_{B} E.

It is possible to extend these results in some form to the case when ≅|_{Mod(σ)} is non-Borel. This is a little more than a routine paraphrasing of the arguments above. Essentially one asks if there is any fragment F appearing in some L_{ω_{1}^{ck(z)}}[z] for which we arrive at case(I) or case(IIb); if so, then we obtain (E_{0})^{ω} ≤_{B}≅ |_{Mod(σ)} by the arguments given there. The difficulty comes about if there is no such fragment.

It becomes necessary to use something along the lines of lemma 4.2 of [12]. One can in some sense perform the construction of section 13 “in the codes”. In this situation we obtain a weaker conclusion:

Theorem 14.5 Let σ ∈ L_{ω_{1},ω} for some countable language L. Then exactly one of the following holds:

(I) there is a Δ ∼_{2}^{1} in the codes function

f : Mod(σ) → 2^{<ℵ_{1}}

such that for (i) for all M ∈ Mod(σ) we have |{g(N) : N ≅ M}| ≤ ℵ_{0}, and

(ii) for all N_{1}, N_{2} ∈ Mod(σ)
g(N_{1}) = g(N_{2}) ⇒ N_{1} ≅ N_{2};

(II) (E_{0})^{ω} ≤_{B}≅|_{Mod(σ)}.

This has an obvious parallel with 13.4.

References

[1] J. Barwise, Admissible sets and structures: An approach to definability theory, Perspectives in Mathematical Logic, Springer-Verlag, New-York, 1975.

[2] H. Becker and A.S. Kechris, The descriptive set theory of Polish group actions, London Mathematical Society Lecture Notes Series, 232, Cambridge University Press, Cambridge, 1996.

[3] R. Dougherty, S. Jackson, A.S. Kechris, The structure of hyperfinite equivalence relations, Transactions of the American Mathematical Society, vol. 341(1994), pp. 193-225.

[4] I. Farah, Basis problem for turbulent actions, preprint, York University, Toronto, 1998.

[5] H. Friedman, Borel and Baire reducibility, to appear.

[6] H. Friedman, L. Stanley, A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic, vol. 54(1989), pp. 894–914.

[7] S. Gao, On automorphism groups of countable structures, Journal of Symbolic Logic, vol. 63(1998), pp. 891–896.

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

[9] L.A. Harrington, D. Marker, S. Shelah, Borel orderings, Transactions of the American Mathematical Society, vol. 310(1988), pp. 293–302.

[10] G. Hjorth, Classification and orbit equivalence relations, American Mathematical Society, Survey and Monographs Series 75, Rhode Island, 2000.

[11] G. Hjorth, Actions of the classical Banach spaces, to appear in the Journal of Symbolic Logic.

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

[13] G. Hjorth, A.S. Kechris, Borel equivalence relations and classifications by countable models, Annals of Pure and Applied Logic, vol. 82(1996), pp. 221-272.

[14] G. Hjorth, A.S. Kechris, New dichotomy theorems for Borel equivalence relations, Bulletin of Symbolic Logic, vol. 3(1997), pp. 329-346.

[15] W. Hodges, Model theory, Encyclopedia of Mathematics and its Applications, volume 42, Cambridge University Press, Cambridge, 1993.

[16] T. Jech, Set theory, Academic Press, New York, 1978.

[17] A.S. Kechris, Classical descriptive set theory, Springer-Verlag Graduate Texts in Mathematics, Berlin, 1995.

[18] A.S. Kechris, A. Louveau, The structure of hypersmooth equivalence relations, Journal of the American Mathematical Society, vol. 10(1997), pp. 215-242.

[19] H.J. Keisler, Model theory for infinitary logic, North-Holland, Amsterdam, 1971.

[20] Y.N. Moschovakis, Descriptive set theory, North-Holland, Amsterdam, 1980.

[21] G.E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990

[22] J. Silver, Counting the number of equivalence classes of Borel and co-analytic equivalence relation, Annals of Mathematical Logic, vol. 18(1980), pp. 1-28.

[23] R.J. Vaught, Invariant sets in topology and logic, Fundamenta Mathematica, vol. 82(1974/75) (collection of articles dedicated to Andrzej Mostowski on his sixtieth birthday), pp. 269-294.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555