Knight’s model, its automorphism group, and characterizing the uncountable cardinals

Greg Hjorth April 2, 2001

Contents

1 Introduction 1 2 Technicalities 3 3 Characterizing ℵ_{1} 4 4 Characterizing ℵ_{2} 10 5 The general construction 15 6 Atomic models 22 7 Equivalence relations 23 8 An amusing footnote to a theorem of Becker’s 24

1 Introduction

This paper comes about as a response to both the recent work relating to the topological Vaught conjecture in [2], [5], and the much older work by Julia Knight on characterizing cardinals. Definition A countable structure M is said to characterize a cardinal κ if

1. there is a model of cardinality κ satisfying exactly the same L_{ω_{1},ω} sentences as M;

2. but there is no model with cardinality greater than κ satisfying the same L_{ω_{1},ω} sentences as M.

It is well known that for a countable model M the corresponding Scott sentence, as defined in §8 below, φ_{M} ∈ L_{ω_{1},ω} (see [13]) has the property that for any N we have

N ⊧ φ_{M}

if and only if N satisfies the same L_{ω_{1},ω} sentences as M. Thus we may equivalently rephrase the above definition in terms of the models N satisfying the Scott sentence of M.

Here it is easy to see that there is a countable model characterizing ℵ_{0}. For instance, in the language with infinitely many unary functions (U_{n})_{n∈ω}, any model satisfying

∃a∀b ⋁_{n∈ω}(U_{n}(a) = b)

does so.

On the other hand, [15] shows that there are much more subtle examples of models characterizing ℵ_{0}, and thus the following theorem covers an interesting range of automorphism groups.

Theorem 1.1 (Becker, Gao; see [2], [5].) If M characterizes ℵ_{0}, then the automorphism group of M satisfies Vaught’s conjecture.

Indeed here it was shown under sharps in [2] (and in just ZFC in [9]) that such an automorphism group will satisfy Vaught’s conjecture even on analytic sets. This very strong conclusion, defined precisely in §7 below, to the effect that a continuous action of the group always give rise to either countably many or perfectly many orbits on Σ ∼_{1}^{1} sets, is known to fail for the infinite symmetric group.

At the level of the next cardinal it was demonstrated in the 1970’s that:

Theorem 1.2 (Knight; see [14]) There is a countable model characterizing ℵ_{1}.

And recently:

Theorem 1.3 (See [9]) The automorphism group of Knight’s model satisfies the Vaught conjecture even on analytic sets.

In view of these results one might hope that there would be a heirarchy of properties corresponding to whether a model characterizes a certain cardinal.

Here however we halt the direction of the above results, and thereby answer negatively a question from [9]:

Theorem 1.4 There is a model characterizing ℵ_{1} whose automorphism group has a closed subgroup mapping continuously and homomorphically onto S_{∞} and thereby violates the topological Vaught conjecture on analytic sets.

The model constructed here is, as one would expect, very different in flavor from Knight’s model. In particular it makes possible generalizations which appear more resistant to her method:

Theorem 1.5 For each α < ω_{1} there is a countable model characterizing ℵ_{α}.

The question of characterizing the ℵ_{n}’s in this way is mentioned as an open problem in [14].^{1} However for κ ≥ ℵ_{ω_{1}} we cannot hope for the same kind of theorem in ZFC. For one thing, the Hanf number of sentances in L_{ω_{1},ω} is ℶ_{ω_{1}}, and under GCH this equals ℵ_{ω_{1}}. But even with GCH failing badly, Shelah in [16], and independently Hrushovski and Velickovic in unpublished work, have shown it is relatively consistent with 2^{ℵ_{0}} > ℵ_{ω_{1}} that every sentence in L_{ω_{1},ω} with a model of size ℵ_{ω_{1}} has a model of size 2^{ℵ_{0}}.

In the final section of the paper we consider a question of Howard Becker’s and obtain a near counterexample by showing that for G_{K} the automorphism group of Knight’s countable model one has:

Theorem 1.6 Whenever G_{K} acts continuously on a Polish space X with resulting equivalence relation E_{G_{K}}^{X}:-

(I) we may assign in a {Δ_{2}^{1} \atop ∼} manner real numbers as a complete invariant for E_{G_{K}}^{X}; or (II) we may continuously embed the equivalence relation of eventual agreement on infinite

binary sequences into E_{G_{K}}^{X}.

In alternative (I) of this theorem one would expect to be able to prove that the assignment can be carried out in a Borel manner; thus the result is unlikely to be optimal. On the other hand, the proof – with its curious use of large cardinal ideas, and its strange forcing over the Frechet filter on ℵ_{1} – would seem to have some independent interest.

Acknowledgements: I wish to thank Chris Laskowski for a sequence of helpful emails.

2 Technicalities

Let us indulge in the usual notational shortcuts.

Models will be identified with their underlying sets. Thus M ⊂ N indicates that the underlying set of the structure M is included in N and that M is a substructure of M. Instead of writing b⃗ = (b_{0}, b_{1}, ...b_{k−1}) is a finite sequence from the underlying set, we may instead simply write

b⃗ ∈ M.

For Q a predicate in the language of M, we may find it convenient to use Q^{M} for the set of all a in the underlying set of M for which

M ⊧ Q(a).

Similarly if R(·, ·) is a relation in the language of M and a ∈ M, then R(a, ·)^{M} indicates the set

{b : M ⊧ R(a, b)}.

1Though here, as we point out in the section on atomic models, this had essentially been solved for n = 2 by Lakowski and Shelah.

Much of the paper deals with infinitary logic, but unless otherwise indicated elementary substructure means elementary with respect to finitary logic, L_{ω,ω}, and will be denoted by ≺. I will loosely use L_{ω_{1},ω} to indicate the countably infinitary logic generated by whatever language is currently of interest; strictly speaking we should distinguish, with say (L_{0})_{ω_{1},ω} the countably infinitary logic generated by the language L_{0} and (L_{1})_{ω_{1},ω} the countably infinitary logic generated by the language L_{1}.

The usual kind of logical folklore is presupposed. For instance, the theory of dense linear orderings without end points is ℵ_{0}-categorical, and any countable model of this theory can be realized as the Fraisse limit of finite structures. A discussion of this Fraisse construction can be found in [4].

Lemma 2.1 (Folklore) Let φ ∈ L_{ω_{1},ω} be such that any two countable models of φ are isomorphic. Then any two models of φ of any size at all satisfy the same sentences in L_{∞,ω}.

Proof Let ψ ∈ L_{∞,ω}. By induction on logical complexity one sees that whether a given structure satisfies ψ is absolute between transitive models of ZFC.

Let A, B be two possibly uncountable models of φ. Let V [G] be a generic extension in which A and B are countable. They both still satisfy φ. By Shoenfield absoluteness (see [12]) it follows that even in V [G] any two countable models of φ are isomorphic, and thus

V [G] ⊧ A ≅ B
∴ (A ⊧ ψ ⇔ B ⊧ ψ).

□

The necessary infinitary logic appears in [13] and [1]. We will eventually present a precise definition of Scott sentance in §8; for the first few sections below a much more primitive working definition is provided if we simply accept that for each countable model M there is a corresponding φ_{m} ∈ L_{ω_{1},ω} such that for all other countable N we have

M ≅ N

if and only if

N ⊧ φ_{M}.

3 Characterizing ℵ_{1}

Definition We let L_{0} be the language generated by {S_{n} : n ∈ ω} and {R_{k} : k ∈ ω} where each S_{n} is binary and each R_{k} is k + 2-ary.

Definition We introduce the following axioms, stated in infinitary logic:

(*1): the conjunction of: (*1a) ∀a, b ⋁_{n∈ω} S_{n}(a, b);

(*1b) ∀a, b ⋀_{n≠m}(S_{n}(a, b) ⇒ ¬S_{m}(a, b)).

(*2): the conjunction of: (*2a) for each k and i < j < k

∀a_{0}, a_{1}, b_{0}, ..., b_{k−1}(R_{k}(a_{0}, a_{1}, b_{0}, ..., b_{k−1}) ⇒ (b_{i} ≠ b_{j} ∧ a_{0} ≠ a_{1}));

(*2b) for each k and permutation π of k

∀a_{0}, a_{1}, b_{0}, ..., b_{k−1}(R_{k}(a_{0}, a_{1}, b_{0}, ..., b_{k−1}) ⇔ R_{k}(a_{1}, a_{0}, b_{π(0)}, ..., b_{π(k−1)}));

(*2c) ∀a_{0}, a_{1}, b_{0}, ... ⋀_{n∈ω} ∧_{i<k}(R_{k}(a_{0}, a_{1}, b_{0}....) ⇒ (S_{n}(a_{0}, b_{i}) ⇔ S_{n}(a_{1}, b_{i})); (*2d) ∀a_{0}, a_{1}, b_{0}, ...∀c ⋀_{n∈ω}[(R_{k}(a_{0}, a_{1}, b_{0}....) ∧_{i<k} c ≠ b_{i}) ⇒

(S_{n}(a_{0}, c) ⇒ ¬S_{n}(a_{1}, c))].

In other words, (*1) asserts that for each a and b there is a (unique) natural number f(a, b) with S_{f(a,b)}(a, b). (*2) asserts that given R_{k}(a_{0}, a_{1}, b_{0}, ..., b_{k−1}) we have that {b_{0}, b_{1}, ..., b_{k−1}} exactly comprises the set on which f(a_{0}, ·) and f(a_{1}, ·) agree.

Definition An L_{0} structure F is L_{0}-neat if

1. F is finite;

2. F ⊧ (∗1), (∗2);

3. ∀a_{0}, a_{1} ∈ F (a_{0} ≠ a_{1} ⇒ ∃k∃b⃗ ∈ F (R_{k}(a_{0}, a_{1}, b⃗))).

Lemma 3.1 Let F be an L_{0}-neat structure. Let F_{0}, F_{1} be L_{0}-neat structures extending F. Then there are L_{0}-neat H_{0} ⊃ F_{0}, H_{1} ⊃ F_{1} and an isomorphism

i : H_{0} ≅ H_{1}

with i|_{F} the identity map.

Proof We may assume F_{0} ∩ F_{1} = F. We then take H = F_{0} ∪ F_{1} and are faced with the task of making it into a neat structure extending F_{0} and F_{1}.

For any a_{0} ∈ F_{0} and a_{1} ∈ F_{1} we stipulate

H ⊧ R_{k}(a_{0}, a_{1}, b_{0}, b_{1}, ...b_{k−1}),

where b_{0}, b_{1}, ...b_{k−1} enumerates the elements b of F for which there is some m with

F_{0} ⊧ S_{m}(a_{0}, b_{i})

and

F_{1} ⊧ S_{m}(a_{1}, b_{i}).

We can then easily find one to one

f : (F_{0} \ F) × (F_{1} \ F) ∪ (F_{1} \ F) × (F_{0} \ F) ↪ ω

such that for all a_{0}, a_{1} ∈ F_{0} and b_{0}, b_{1} ∈ F_{1}, if S_{n}(a_{0}, a_{1}) or S_{n}(b_{0}, b_{1}) then n is not in the range of f. We then complete the task of making H into a neat structure with

H ⊧ S_{f(c_{0},c_{1})}

for each (c_{0}, c_{1}) ∈ (F_{0} \ F) × (F_{1} \ F) ∪ (F_{1} \ F) × (F_{0} \ F).

Then H_{0} = H = H_{1} and i = identity suffice.

□

Note that the proof works even for F = ∅.

Definition An L_{0}-structure M is L_{0}-full if

1. for all finite A ⊂ M there is L_{0}-neat F ⊃ A, F ⊂ M;

2. for all L_{0}-neat F ⊂ M and L_{0}-neat H_{0} ⊃ F there is neat H_{1} ⊂ M with F ⊂ H_{1} there is i : H_{0} ≅ H_{1} with i|_{F} the identity.

The lemma 3.1 entails the existence of L_{0}-full structures in the usual way.

Lemma 3.2 Any two L_{0}-full structures M, N of cardinality ℵ_{0} are isomorphic.

In fact for any L_{0} neat F ⊂ M and L_{0} neat H ⊂ N and isomorphism i : H ≅ F there is an isomorphism

i_{∞} : M ≅ N

extending i.

Proof Fix i : H ≅ F. We may repeatedly apply the fullness assumption in a back and forth argument to find sequences

F_{0} = F ⊂ F_{1} ⊂ F_{2}... ⊂ M,
H_{0} = H ⊂ H_{1} ⊂ H_{2}... ⊂ N ,
i_{0} = i ⊂ i_{1} ⊂ i_{2} ⊂ ...,

with each i_{n} : F_{n} ≅ H_{n} and

⋃_{n∈ω} F_{n} = M,

⋃_{n∈ω} H_{n} = N ,

and so

i_{∞} = ⋃_{n∈ω} i_{n}

is as required. □

Thus we may find φ_{0} ∈ L_{ω_{1},ω} such that φ_{0} is the Scott sentence of any L_{0}-full model. The models of φ_{0} can be viewed as arising from a version of the Fraisse construction.

Literally they fall short of actually arising as a Fraisse limit of finite structures, since we only obtain the distinctive amalgamation property for the cofinal collection of neat structures, and while it is true that the method could be shoe horned into the usual Fraisse format by enlarging the language, it seems less natural and more complicated to do so.

Lemma 3.3 φ_{0} has no model of size ℵ_{2}.

Proof Suppose instead that N ⊧ φ_{0} is of size ℵ_{2} and choose

N_{0} ≺ N ,
|N_{0}| = ℵ_{1},

noting in particular that for all a_{0}, a_{1} ∈ N_{0} there is some neat F ⊂ N_{0} containing a_{0}, a_{1}, and thus for all b ∈ N \ N_{0} we have

⋀_{n∈ω} S_{n}(a_{0}, b) ⇒ ¬S_{n}(a_{1}, b).

Choosing some fixed b ∉ N_{0} we would in particular obtain that

a ↦ μn(S_{n}(a, b))

provides an injection from N_{0} into ω, a contradiction. □

Definition Let L_{1} be the language obtained from L_{0} by adding unary predicates (P_{n})_{n∈ω}.

Definition We introduce the following infinitary axiom:

(*3): the conjunction of: (*3a): ∀a ⋁_{n∈ω} P_{n}(a);

(*3b): ∀a ⋀_{n≠m} ¬(P_{n}(a) ∧ P_{m}(a)).

In other words, (*3) states that for each a there is a unique g(a) ∈ ω with P_{g(a)}(a).

Definition An L_{1} structure F is L_{1}-neat if

1. F is finite;

2. F ⊧ (*1), (*2), (*3);

3. ∀a_{0}, a_{1} ∈ F (a_{0} ≠ a_{1} ⇒ ∃k∃b⃗ ∈ F (R_{k}(a_{0}, a_{1}, b⃗))).

So we have simply bumped up the definition of neatness from L_{0} to L_{1}, accounting for the new axiom.

Lemma 3.4 Let F be an L_{1}-neat structure. Let F_{0}, F_{1} be L_{1}-neat structures extending F. Then there are L_{1}-neat H_{0} ⊃ F_{0}, H_{1} ⊃ F_{1} and an isomorphism

i : H_{0} ≅ H_{1}

with i|_{F} the identity map.

Proof As in 3.1; the only minor difference is that now when we take H = F_{0} ∪ F_{1} we (obviously) are required to define for each a ∈ H

(H ⊧ P_{n}(a)) ⇔ [(a ∈ F_{0} ∧ F_{0} ⊧ P_{n}(a)) ∨ (a ∈ F_{1} ∧ F_{1} ⊧ P_{n}(a))].

□

Definition An L_{1}-structure M is L_{1}-full if

1. for all finite A ⊂ M there is L_{1}-neat F ⊃ A, F ⊂ M;

2. for all L_{1}-neat F ⊂ M and L_{1}-neat H_{0} ⊃ F there is neat H_{1} ⊂ M with F ⊂ H_{1} there is i : H_{0} ≅ H_{1} with i|_{F} the identity.

Lemma 3.5 Any two L_{1}-full structures M, N of cardinality ℵ_{0} are isomorphic.

Proof Exactly as in the proof of 3.2. □

Lemma 3.6 Let M be a countable L_{1}-full structure and let M|_{L_{0}} denote the reduct of M to the language L_{0}. Then for any π ∈ S_{∞} there are corresponding σ in the automorphism group of M|_{L_{0}} such that for all a ∈ M

M ⊧ P_{n}(a) ⇔ P_{π(n)}(σ(a)).

Proof We define N by requiring

N |_{L_{0}} = M|_{L_{0}},

but at each n ∈ ω and a ∈ M

N ⊧ P_{n}(a) ⇔ M ⊧ P_{π(n)}(a).

Now it simply follows from the structure of the definitions that N must also be L_{1}-full, and so we can apply 3.5 to find σ. □

Corollary 3.7 For M_{0} a countable model of φ_{0} we have that S_{∞} divides Aut(M_{0}), in the sense that there is a closed subgroup G < Aut(M_{0}) and continuous onto homomorphism

p : G ↠ S_{∞}.

Proof Let M_{1} be an expansion of M_{0} to an L_{1}-full model. Let G be the group of all automorphisms σ of M_{0} such that for all a, b ∈ M_{0}, for all n, m ∈ ω, if

M_{1} ⊧ P_{n}(a), P_{n}(b), P_{m}(σ(a))

then

M_{1} ⊧ P_{m}(σ(b)).

To each such σ we may continuously and homomorphically associate π_{σ} with

M_{1} ⊧ P_{n}(a) ⇔ M_{1} ⊧ P_{π_{σ}(n)}(σ(a)).

By 3.6 the map

σ ↦ π_{σ}

is onto. □

Of course the proof of this corollary is general. Given any countable language and related notion of finite “neat” structure which allows amalgamation we may form a corresponding notion of “full” and observe S_{∞} to divide the automorphism group of any countable full model.

Theorem 3.8 (Gao) (i) If G and H are Polish groups, G allowing a compatible complete left invariant metric, and

π : G ↠ H

is continuous, onto homomorphism, then H allows a complete left invariant metric.

(ii) A countable model M characterizes ℵ_{0} if and only if Aut(M) allows a complete left invariant metric.

Corollary 3.9 (i) For M a countable model of φ_{0}, Aut(M) does not have a complete left invariant metric.

(ii) φ_{0} has a model of size ℵ_{1}.

Proof It is well known that S_{∞} does not have a complete left invariant metric, and so by 3.8(i) and 3.7 neither can Aut(M). Then we obtain (ii) by 3.8(ii) and the non-existence of a complete left invariant metric. □

Thus:

Theorem 3.10 There is a countable model M such that:

G. Hjorth 10

1. the Scott sentence of M characterizes ℵ_{1};

2. S_{∞} divides Aut(M);

3. and hence Aut(M) violates Vaught’s conjecture on analytic sets. Proof 1. and 2. above are covered by earlier lemmas; 3. is a consequence of 2. and [3] together with results from [8]. □

4 Characterizing ℵ_{2}

Before becoming seriously involved in this construction, we step back a moment and note some variations on 3.5 and the notion of L_{1}-full. Definition Let L̂_{ω_{1}} be the expansion of L_{0} by unary predicates (P_{α})_{α∈ω_{1}}. For each α < ω_{1} let L̂_{α} be the expansion of L_{0} just by (P_{β})_{β<α}. Definition We introduce a new infinitary axion for each α ≤ ω_{1}:

(*N_{α}): the conjunction of: (*N_{α}a): ∀a ⋁_{β∈α} P_{β}(a);

(*N_{α}b): ∀a ⋀_{β_{1}≠β_{2}} ¬(P_{β_{1}}(a) ∧ P_{β_{2}}(a)).

In other words, (*N_{α}) states that for each a there is a unique g(a) ∈ α with P_{g(a)}(a). Definition An L̂_{α} structure F is L̂_{α}-neat if

1. F is finite;

2. F ⊧ (*1), (*2), (*N_{α});

3. ∀a_{0}, a_{1} ∈ F (a_{0} ≠ a_{1} ⇒ ∃k∃b⃗ ∈ F (R_{k}(a_{0}, a_{1}, b⃗))).

By the same proof one obtains: Lemma 4.1 Let F be an L̂_{α}-neat structure. Let F_{0}, F_{1} be L̂_{α}-neat structures extending F.

Then there are L̂_{α}-neat H_{0} ⊃ F_{0}, H_{1} ⊃ F_{1} and an isomorphism

i : H_{0} ≅ H_{1}

with i|_{F} the identity map and i[F_{0}] ∩ F_{1} = F. Definition An L̂_{α}-structure M is L̂_{α}-full if

1. for all finite A ⊂ M there is L̂_{α}-neat F ⊃ A, F ⊂ M; 2. for all L̂_{α}-neat F ⊂ M and L̂_{α}-neat H_{0} ⊃ F there is neat H_{1} ⊂ M with

F ⊂ H_{1}

there is i : H_{0} ≅ H_{1} with i|_{F} the identity.

At least for countably infinite α we have the same situation as before.

Lemma 4.2 For ω ≤ α < ω_{1}, any two L̂_{α}-full structures M, N of cardinality ℵ_{0} are isomorphic.

Here is the point which we will need for later:

Lemma 4.3 There exist L̂_{ω_{1}}-full structures of cardinality ℵ_{1}.

Proof It suffices to find a chain of countable structures

M_{ω} ⊂ M_{ω+1} ⊂ ...M_{α} ⊂ ...

where each M_{α} is L̂_{α}-full and of size ℵ_{0}, since then we can simply take M_{ω_{1}} to be the union of {M_{α} : α < ω_{1}}.

We build M_{α} by induction on α. At limit stages we can take unions, and thus all the work happens at successor steps.

So suppose we have M_{α}. We represent

M_{α} = ⋃_{n∈ω} F_{n},

where each F_{n} is L̂_{α}-neat. At once from the definitions each F_{n} must be L̂_{α+1}-neat, and thus by 4.1, for any L̂_{α+1}-neat

H ⊃ F_{n},

with H ∩ M_{α} = F_{n}, we can find L̂_{α+1}-neat

H′ ⊃ H ∪ F_{n+1}.

Therefore repeated applications of 4.1 enables us to find a sequence of L̂_{α+1}-neat structures

H_{0} ⊂ H_{1} ⊂ ...H_{n} ⊂ H_{n+1} ⊂ ...

where each F_{n} ⊂ H_{n}, each H_{n} ∩ M_{α} = F_{n}, and for any L̂_{α+1}-neat

H ⊃ F_{n}

there will exist a sufficiently large m at which we have some H′ ⊂ H_{m} and

i : H ≅ H′,

with i|_{F_{n}} = identity.

Thus we move on with M_{α+1} = ⋃ H_{n}. □

Definition We let L_{2} be generated by L_{0}, the new unary predicate Q, and binary relations E_{0}, E_{1}, and <.

Definition We introduce a whole collection of new axioms.

(*4) < linearly orders the objects satisfying Q and is completely inert outside Q:

(*4a) ∀a, b, c(Q(a) ∧ Q(b) ∧ Q(c) ⇒

(a < b ∨ b < a ∨ a = b) ∧ (¬(a < a)) ∧ ((a < b ∧ b < c) ⇒ a < c)));

(*4b) ∀a, b(a < b ⇒ (Q(a) ∧ Q(b)). (*5) As a ranges over Q the sets {c : E_{0}(a, c)} partition ¬Q and this is all that E_{0} does:

(*5a) ∀c(Q(c) ∨ ∃!a(Q(a) ∧ E_{0}(a, c))); (*5b) ∀a, c(E_{0}(a, c) ⇒ (Q(a) ∧ ¬Q(c))).

(*6) In a similar way, for each a the sets {c : E_{1}(b, c)} as b ranges over b < a partition {c : E_{0}(a, c)}:

(*6a) ∀c, a((Q(a) ∧ E_{0}(a, c) → ∃!b(E_{1}(b, c))); (*6b) ∀a, b, c((E_{0}(a, c) ∧ E_{1}(b, c)) ⇒ b < a); (*6c) ∀b, c(E_{1}(b, c) ⇒ (Q(b) ∧ ¬Q(c))).

(*7) For each a in Q we have that the set {c : E_{0}(a, c)} viewed as an L_{0} structure satisfies (*1) and (*2) and moreover the L_{0} relations are inert except inside the sets of the form {c : E_{0}(a, c)}:

(*7a) ∀d, b[(∃a(E_{0}(a, b) ∧ E_{0}(a, d))) ⇒ ⋁_{n∈ω} S_{n}(d, b)]; (*7b) ∀d, b ⋀_{n≠m}(S_{n}(d, b) ⇒ ¬S_{m}(d, b)). (*7c) for each k and i < j < k

∀c_{0}, c_{1}, b_{0}, ..., b_{k−1}(R_{k}(c_{0}, c_{1}, b_{0}, ..., b_{k−1}) ⇒ (b_{i} ≠ b_{j} ∧ c_{0} ≠ c_{1}));

(*7d) for each k and permutation π of k

∀c_{0}, c_{1}, b_{0}, ..., b_{k−1}(R_{k}(c_{0}, c_{1}, b_{0}, ..., b_{k−1}) ⇔ R_{k}(c_{1}, c_{0}, b_{π(0)}, ..., b_{π(k−1)});

(*7e) ∀c_{0}, c_{1}, b_{0}, ... ⋀_{n∈ω} ∧_{i<k}(R_{k}(c_{0}, c_{1}, b_{0}....) ⇒ (S_{n}(c_{0}, b_{i}) ⇔ S_{n}(c_{1}, b_{i})); (*7f) ∀c_{0}, c_{1}, b_{0}, ...∀d ⋀_{n∈ω}[(R_{k}(c_{0}, c_{1}, b_{0}....) ∧_{i<k} d ≠ b_{i}) ⇒

(S_{n}(a_{0}, d) ⇒ ¬S_{n}(a_{1}, d))];

(*7g) ⋀_{n} ∀c_{0}, c_{1}(S_{n}(c_{0}, c_{1}) ⇒ ∃a(E_{0}(a, c_{0}) ∧ E_{0}(a, c_{1}))); (*7h) ⋀_{n} ∀c_{0}, c_{1}∀b_{0}, b_{1}, ...b_{k−1}(R_{k}(c_{0}, c_{1}, b⃗) ⇒

∃a(E_{0}(a, c_{0}) ∧ E_{0}(a, c_{1}) ∧ ⋀_{i<k} E_{0}(a, b_{i}))).

Definition An L_{2} structure F is L_{2}-neat if

1. F is finite;

2. F ⊧ (*4)-(*7); 3. ∀c_{0}, c_{1} ∈ F ∀a((E_{0}(a, c_{0}) ∧ E_{0}(a, c_{1}) ∧ c_{0} ≠ c_{1}) ⇒ ∃k∃b⃗ ∈ F (R_{k}(c_{0}, c_{1}, b⃗))).

In other words, an L_{2}-neat structure is a finite structure in which the various fibres {c : E_{0}(a, c)} are L_{2}-neat as ranges over Q, and for each c ∈ ¬Q there are unique b < a in Q with E_{1}(b, c) and E_{0}(a, c).

We will prove something stronger than the next lemma shortly, but it seems helpful to at least present this simpler argument on its own before we become enmeshed in proving results at full generality.

Lemma 4.4 Let F be an L_{2}-neat structure. Let F_{0}, F_{1} be L_{2}-neat structures extending F. Then there are L_{2}-neat H_{0} ⊃ F_{0}, H_{1} ⊃ F_{1} and an isomorphism

i : H_{0} ≅ H_{1}

with i|_{F} the identity map.

Proof We may assume first of all that the substructures of F_{0} and F_{1} formed by

{a : F_{0} ⊧ Q(a)},
{a : F_{1} ⊧ Q(a)},

are in fact equal for the simple reason that finite linear orderings have the strong amalgamation property, in the sense that given any two finite linear orderings L_{1} and L_{2} which agree on their intersection we may find a linear ordering L ⊃ L_{1} ∪ L_{2}.

Then we can assume that for each a with F_{0} ⊧ Q(a) (or equivalently given our simplifying assumption F_{1} ⊧ Q(a)) we have that

E_{0}(a, ·)^{F_{0}} ∩ E_{0}(a, ·)^{F_{1}} ⊂ F.

But now we can simply go through each a with Q(a) and amalgamate the sets E_{0}(a, ·)^{F_{0}} and E_{0}(a, ·)^{F_{1}} just as in the proof of 3.4, treating the sets

{{c : E_{1}(b, c)} : b < a}

as we treated the fresh predicates {P_{n} : n ∈ ω}. □

By now the next definition comes as no surprise.

Definition An L_{2}-structure M is L_{2}-full if

1. for all A ⊂ M finite there is L_{2}-neat F ⊃ A, F ⊂ M;

2. for all L_{1}-neat F ⊂ M and L_{2}-neat H_{0} ⊃ F there is neat H_{1} ⊂ M with F ⊂ H_{1} there is i : H_{0} ≅ H_{1} with i|_{F} the identity.

Again we obtain that any two countable L_{2}-full models are isomorphic and thus there is φ_{2} ∈ L_{ω_{1},ω} which is the Scott sentence of any L_{2}-full model.

Lemma 4.5 φ_{2} has no model of size ℵ_{3}.

Proof Otherwise let N be such a model and note that for each a with N ⊧ Q(a) we have that E_{0}(a, ·)^{N} has size at most ℵ_{1} by 3.3 and the fact that this set viewed as an L_{0} structure is L_{0}-full. Since for each a ∈ Q^{N} the axiom (*6) provides a surjection

p_{a} : {c : N ⊧ E_{0}(a, c)} ↠ {b ∈ N : N ⊧ b < a}

we conclude that each set of the form

{b ∈ N : N ⊧ b < a}

has cardinality at most ℵ_{1}.

This means that (Q^{N}; <^{N}) is a linear ordering of size ℵ_{3} all of whose initial segments are no bigger than ℵ_{1}, which is impossible. □

Lemma 4.6 φ_{2} does have a model of size ℵ_{2}.

Proof First let us choose a linear ordering A = (A; <) such that

1. A has size ℵ_{2};

2. for each a ∈ A the set {b ∈ A : A ⊧ b < a} has size ℵ_{1};

3. (A; <) is a dense linear order without endpoints.

Then for each a ∈ A we can let

π_{a} : {b ∈ A : A ⊧ b < a} → ω_{1}

be a bijection. For each a ∈ A we can apply 4.3 to choose a L̂_{ω_{1}}-full structure N_{a} of size ℵ_{1}. We can assume that for a ≠ a′ we have N_{a} and N_{a′} disjoint.

Now we define M. The set Q^{M} will be A, with the linear ordering <^{A} above being <^{M}. The set ¬Q^{M} will be the disjoint union of the underlying sets of the structures {N_{a} : a ∈ A}. In the natural way we demand that ¬Q^{M} viewed as an L_{0} structure is just the disjoint union of the L_{0} structures {N_{a}|_{L_{0}} : a ∈ A}. For each a ∈ Q^{M} we let {c : M ⊧ E_{0}(a, c)} just be the underlying set of N_{a}.

We are only left with defining the relation E_{1}.

But now we appeal to the extra information obtained from the various N_{a}’s actually being L̂_{ω_{1}}-full structures. We demand that for each a ∈ Q^{M} and b with

M ⊧ b < a

and for each c ∈ N_{a}

(M ⊧ E_{1}(b, c)) ⇔ N_{a} ⊧ P_{π_{a}(b)}(c).

It follows more or less immediately from the definitions that this structure is L_{2}-full, the main point being that the various sets

{c : M ⊧ E_{0}(a, c)}

are isolated from one another with respect to the language of M. □

5 The general construction

The next few lemmas would seem to be a slight diversion from the task at hand, but isolate the combinatorics used in the general construction.

Definition For κ an uncountable cardinal and γ ≤ κ, let L^{κ,γ} be the language generated by binary relations {S_{β} : β < κ}, unary predicates {P_{β} : β < γ}, and for each k ∈ ω a corresponding (k + 2)-ary relation R_{k}.

Definition Some new axioms for L^{κ,γ}, fashioned after the old:

(*1^{κ,γ}): the conjunction of: (*1a^{κ,γ}) ∀a, b ⋁_{β∈κ} S_{β}(a, b);

(*1b^{κ,γ}) ∀a, b ⋀_{β≠α}(S_{β}(a, b) ⇒ ¬S_{α}(a, b)).

(*2^{κ,γ}): the conjunction of: (*2a^{κ,γ}) for each k and i < j < k

∀a_{0}, a_{1}, b_{0}, ..., b_{k−1}(R_{k}(a_{0}, a_{1}, b_{0}, ..., b_{k−1}) ⇒ (b_{i} ≠ b_{j} ∧ a_{0} ≠ a_{1}));

(*2b^{κ,γ}) for each k and permutation π of k

∀a_{0}, a_{1}, b_{0}, ..., b_{k−1}(R_{k}(a_{0}, a_{1}, b_{0}, ..., b_{k−1}) ⇔ R_{k}(a_{1}, a_{0}, b_{π(0)}, ..., b_{π(k−1)}));

(*2c^{κ,γ}) ∀a_{0}, a_{1}, b_{0}, ... ⋀_{β∈κ} ∧_{i<k}(R_{k}(a_{0}, a_{1}, b_{0}....) ⇒

(S_{β}(a_{0}, b_{i}) ⇔ S_{β}(a_{1}, b_{i}));

(*2d^{κ,γ}) ∀a_{0}, a_{1}, b_{0}, ...∀c ⋀_{β∈κ}[(R_{k}(a_{0}, a_{1}, b_{0}....) ∧_{i<k} c ≠ b_{i}) ⇒

(S_{β}(a_{0}, c) ⇒ ¬S_{β}(a_{1}, c))].

(*3^{κ,γ}): the conjunction of: (*3a^{κ,γ}): ∀a ⋁_{β∈γ} P_{β}(a);

(*3b^{κ,γ}): ∀a ⋀_{β≠α} ¬(P_{β}(a) ∧ P_{α}(a)).

Definition An L^{κ,γ} structure F is L^{κ,γ}-neat if

1. F is finite; 2. F ⊧ (*1^{κ,γ}), (*2^{κ,γ}), (*3^{κ,γ});

3. ∀a_{0}, a_{1} ∈ F (a_{0} ≠ a_{1} ⇒ ∃k∃b⃗ ∈ F (R_{k}(a_{0}, a_{1}, b⃗))).

Definition An L^{κ,γ} structure M is L^{κ,γ}-happy if for any finite A ⊂ M there is L^{κ,γ}-neat F ⊃ A with F ⊂ M.

Definition An L^{κ,γ} structure M is L^{κ,γ}-full if

1. it is L^{κ,γ}-happy;

2. for all L^{κ,γ}-neat F ⊂ M and L^{κ,γ}-neat H_{0} ⊃ F there is L^{κ,γ}-neat H_{1} ⊂ M with F ⊂ H_{1} there is i : H_{0} ≅ H_{1} with i|_{F} the identity.

Lemma 5.1 Let M be an L^{κ,γ}-happy structure of size δ, where δ is an infinite cardinal less than κ. Let

F ⊂ M

and

H ⊃ F

both be L^{κ,γ}-neat. Then there exists L^{κ,γ}-happy N ⊃ M of size δ and H′ ⊂ N and

i : H ≅ H′

with i|_{F} = identity.

Proof Fix H and assume for notational simplicity that H ∩ M = F.

Let T ⊂ κ be the set of β < κ such that there exist c_{0}, c_{1} ∈ M or c_{0}, c_{1} ∈ H with

S_{β}(c_{0}, c_{1}).

T has size less than κ, so we may find a one-to-one function

f : (M \ H) × H ∪ H × (M \ H) ↪ κ \ T.

We can then make M ∪ H into an L^{κ,γ} structure by setting

S_{f(c_{0},c_{1})}

(and ¬S_{β}(c_{0}, c_{1}) for β ≠ f(c_{0}, c_{1})) for all c_{0}, c_{1} ∈ (M\H)×H ∪H ×(M\H) and stipulating that

R_{k}(c_{0}, c_{1}, b_{1}, ..., b_{k})

where b_{1}, b_{2}, ..., b_{k} enumerate the elements b of F where there is some

β ∈ κ

S_{β}(c_{0}, b_{i}) ∧ S_{β}(c_{1}, b_{i}).

It is more or less immediate that the structure thereby produced satisfies (*1^{κ,γ}) and (*3^{κ,γ}). ¿From the assumption on f, it follows that for any c_{0}, c_{1} ∈ (M\H)×H∪H×(M\H) the set

{b ∈ M ∪ H : ∃β(S_{β}(c_{0}, b) ∧ S_{β}(c_{1}, b))}

is included in F, and thus we have (*2^{κ,γ}).

¿From the way that the R_{k} relations have been defined over F ∪ M, it follows that F′ is L^{κ,γ}-neat and

F ⊂ F′ ⊂ M

then F′ ∪ H is L^{κ,γ}-neat. □

Corollary 5.2 There is an L^{κ,γ}-full structure of cardinality κ.

Proof Note that for any finite F there are up to isomorphism only κ many L^{κ,γ}-neat H ⊃ F. Thus by 5.1 and a direct diagonalization argument we may produce an increasing chain of structures

M_{0} ⊂ M_{1} ⊂ ...M_{α} ⊂ M_{α+1} ⊂ ...

such that for all α < κ

1. M_{α} is L^{κ,γ}-happy;

2. M_{α} has cardinality at most α + ω;

3. M_{α+1} \ M_{α} is finite;

4. for each L^{κ,γ}-neat F ⊂ M_{α} and L^{κ,γ}-neat H ⊃ F there is some β > α and L^{κ,γ}-neat

H′ ⊃ F, H′ ⊂ M_{β}, and

i : H ≅ H′

with i|_{F} = identity.

Then

M = ⋃_{α<κ} M_{α}

is as required. □

Lemma 5.3 There is no L^{κ,γ}-full structure of cardinality greater than κ^{+}.

Proof This is as in 3.3. We assume N is a L^{κ,γ}-full structure of cardinality greater than κ^{+} and choose a substructure N_{0} ≺ N of size κ^{+} that is elementary with respect to first order formulas, so that for all a_{0}, a_{1} ∈ N_{0} there is some b⃗ ∈ N_{0} with R_{k}(a_{0}, a_{1}, b⃗). Thus for any b ∈ N \ N_{0} we have an injection

π : N_{0} ↪ κ

a ↦ μβ(S_{β}(a, b)).

□

Of course L^{κ,γ} is an uncountable language, and the afore mentioned axioms and notions of fullness go far beyond what we can say in L_{ω_{1},ω}. The purpose of the last few lemmas is to give us some grip on the situation where we try to bootstrap up, using a Scott sentence φ_{α} which characterizes ℵ_{α} to find one for ℵ_{α+1}. Instead of literally using κ and δ above, we instead will use some model of φ_{α} whose size is at most κ to give us a kind of surrogate cardinal.

Definition Let M and N be structures with languages L_{M} and L_{N}, which we will assume for notational convenience to have no non-logical symbols in common and to be entirely relational. Let S be a ternary relation not appearing in L_{M} ∪ L_{N} and let P be a binary relation not appearing in L_{M} ∪ L_{N}. For each k let T_{k} be a fresh (k + 2)-ary relation. Let L(L_{M}, L_{N}) be the language generated by L_{M}, L_{N}, S, P, and {T_{k} : k ∈ ω}.

Definition An L(L_{M}, L_{N}) structure A including M and N is (M, N)-neat if

1. A \ (M ∪ N) is finite;

2. for any relation symbol R in L_{M} and a⃗ ∈ A, if

A ⊧ R(a⃗)

then a⃗ ∈ M;

3. similarly for any relation symbol R in L_{N} and a⃗ ∈ A, if

A ⊧ R(a⃗)

then a⃗ ∈ N;

4. if A ⊧ T_{k}(a_{0}, a_{1}, b⃗) then a_{0}, a_{1}, b⃗ ∈ A \ (M ∪ N);

5. if A ⊧ P (a, c) then a ∈ N and c ∉ (M ∪ N);

6. if A ⊧ S(a, c_{0}, c_{1}) then a ∈ M and c_{0}, c_{1} ∉ (M ∪ N);

(*1^{M,N}): A satisfies the conjunction of: (*1a^{M,N}) ∀c_{0}, c_{1} ⋁_{a∈M} S(a, c_{0}, c_{1}); (*1b^{M,N}) ∀c_{0}, c_{1} ⋀_{a_{0}≠a_{1}}(S(a_{0}, c_{0}, c_{1}) ⇒ ¬S(a_{1}, c_{0}, c_{1}));

(*2^{M,N}): and A satisfies the conjunction of: (*2a^{M,N}) for each k and i < j < k

∀c_{0}, c_{1}, b_{0}, ..., b_{k−1}(T_{k}(c_{0}, c_{1}, b_{0}, ..., b_{k−1}) ⇒ (b_{i} ≠ b_{j} ∧ c_{0} ≠ c_{1}));

(*2b^{M,N}) for each k and permutation π of k

∀c_{0}, c_{1}, b_{0}, ..., b_{k−1}(T_{k}(c_{0}, c_{1}, b_{0}, ..., b_{k−1}) ⇔ T_{k}(c_{1}, c_{0}, b_{π(0)}, ..., b_{π(k−1)}));

(*2c^{M,N}) ∀c_{0}, c_{1}, b_{0}, ... ⋀_{a∈M} ∧_{i<k}(T_{k}(c_{0}, c_{1}, b_{0}....) ⇒

(S(a, c_{0}, b_{i}) ⇔ S(a, c_{1}, b_{i}));

(*2d^{M,N}) ∀c_{0}, c_{1}, b_{0}, ...∀d ⋀_{a∈M}[(T_{k}(c_{0}, c_{1}, b_{0}....) ∧_{i<k} d ≠ b_{i}) ⇒

(S(a, c_{0}, d) ⇒ ¬S(a, c_{1}, d))];

(*3^{M,N}): and A satisfies the conjunction of: (*3a^{M,N}): ∀c ⋁_{a∈N} P (a, c);

(*3b^{M,N}): ∀c ⋀_{a_{0}≠a_{1}} ¬(P (a_{0}, c) ∧ P (a_{1}, c));

7. for all c_{0}, c_{1} ∈ A \ (M ∪ N) there is k ∈ ω and b⃗ ∈ A with

A ⊧ T_{k}(c_{0}, c_{1}, b⃗).

In other words, it is as if we are equipping the finite set A\(M∪N) with binary relations (S_{a})_{a∈M} and unary predicates (P_{b})_{b∈N} and demanding that the resulting structure satisfy the analog of L^{κ,γ} neatness for κ = |M|, γ = |N |.

Definition An L(L_{M}, L_{N}) structure A including M and N is (M, N)-happy if for all finite A ⊂ A there is some (M, N)-neat substructure B of A with B ⊃ A.

Lemma 5.4 Let γ ≤ κ be cardinals, κ infinite. Let M be a structure of size κ and N a structure of size γ. Let A ⊃ (M ∪ N) be (M, N)-happy. Let

F ⊂ A

and

H ⊃ F

both be (M, N)-neat. Then there is (M, N)-happy B ⊃ A and H′ ⊂ N and

i : H ≅ H′

with i|_{F} = identity.

Proof With the obvious changes, this follows exactly as in 5.1. The obvious changes are that {S_{β}(·, ·) : β < κ} is replaced by {S(a, ·, ·) : a ∈ M}, {P_{β}(·) : β < γ} by {P (a, ·) : a ∈ N }, and each R_{k} by T_{k}. □

Corollary 5.5 Under the same assumptions on M and N, there is an (M, N)-full structure of cardinality κ.

Proof Again this has a proof “isomorphic” to 5.2. □

Lemma 5.6 Under the same assumptions on M and N, there is no (M, N)-full structure of size greater than κ^{+}.

Proof As in the proof of 5.3. □

Lemma 5.7 Let |M| = ℵ_{0}, |N | ≤ ℵ_{0}, and let A, B be (M, N)-full structures of size ℵ_{0}. Then

A ≅ B,

and in fact there is an isomorphism i : A ≅ B with i|_{M} and i|_{N} both equal to the identity.

Proof As in the isomorphism proof in 3.2 for L_{0}-full structures. □

Thus given countable M, N with Scott sentences φ_{M}, φ_{N} we may find a countable model A with Scott sentence φ_{A} such that for any other B in the same language

B ⊧ φ_{A}

if and only if {(Q_{i})^{B} : i < 3} partition B, there are M̂ ⊧ φ_{M}, N̂ ⊧ φ_{N} with underlying sets (Q_{0})^{B} and (Q_{2})^{B}, and B|_{L(L_{M},L_{N})} is an (M̂, N̂)-full structure.

Theorem 5.8 For each countable ordinal α there is a countable model M_{α} whose Scott sentence characterizes ℵ_{α}.

Proof By induction on α, with the passage through limit stages being trivial.

Thus let us suppose that φ_{α} is the Scott sentence for a countable model M_{α} which characterizes ℵ_{α}.

Let N_{0} be the trivial one point model whose only relation is =. Then following 5.5 we may find a countable model M̂_{α} of size ℵ_{0} which is (M_{α}, N_{0})-full. Let φ̂_{α} be its Scott sentence. Any model of φ̂_{α} will be (M̂, N_{0})-full for some M̂ ⊧ φ_{α}, and thus will have size at most ℵ_{α}^{+} by 5.3 and the assumption on φ_{α}. If there is indeed a model of size ℵ_{α+1} then we are done, otherwise we need to go one more round.

Let us then introduce fresh unary predicates Q_{0}, Q_{1}, Q_{2} and fresh binary relations E_{0} and <, and let φ_{α+1} be the Scott sentence of a countable model M_{α+1} where:

1. the language of M_{α+1} is generated by L(L_{M_{α}}, {<}) and {Q_{0}, Q_{1}, Q_{2}, E_{0}};

2. Q_{0}^{M_{α+1}}|_{L_{Mα}} is a model of φ_{α}; 3. ⟨Q_{2}^{M_{α+1}}, <^{M_{α+1}}⟩ is a dense linear ordering without end points; moreover, < is elswhere

vacuous, in that

M_{α+1} ⊧ ∀a, b(a < b ⇒ (Q_{2}(a) ∧ Q_{2}(b)));

4. for each a ∈ Q_{2}^{M_{α+1}} the set

Q_{0}^{M_{α+1}} ∪ E_{0}(a, ·)^{M_{α+1}} ∪ {b : M_{α+1} ⊧ b < a}

restricted to the appropriate language is a ((Q_{0})^{M_{α+1}}|_{L_{Mα}}, ⟨{b : M_{α+1} ⊧ b < a}, =⟩)- full structure;

5. the sets {E_{0}(a, ·)^{M_{α+1}} : a ∈ Q_{2}^{M_{α+1}}} partition Q_{1}^{M_{α+1}};

6. M_{α+1} ⊧ ∀a, c(E_{0}(a, c) ⇒ (Q_{2}(a) ∧ Q_{1}(c)));

7. the various relations {P, S, T_{0}, T_{1}, ....} are trivial in all cases not covered by above: for all a, b, c, we have M_{α+1} ⊧ (E_{0}(a, c) ∧ P (b, c)) ⇒ b < a; for all c_{0}, c_{1}, d we have M_{α+1} ⊧ S(d, c_{0}, c_{1}) ⇒ ∃a(E_{0}(a, c_{0}) ∧ E_{0}(a, c_{1})); for all c_{0}, c_{1}, b_{0}, b_{1}, ..., b_{k−1}, all k ∈ ω, we have

M_{α+1} ⊧ T_{k}(c_{0}, c_{1}, b⃗) ⇒ ∃a(E_{0}(a, c_{0}) ∧ E_{0}(a, c_{1}) ∧_{i<k} E_{0}(a, b_{i})).

In other words, the model M_{α+1} can be viewed as a disjoint union of a dense linear ordering, a model of φ_{α}, and a disjoint sequence of fibres, one associated with each strict initial segment of the linear ordering, each of which is appropriately full.

Let φ_{α+1} be the Scott sentence of M_{α+1}.

Claim(1): If M is a model of φ_{α+1} and a ∈ Q_{2}^{M} we have that E_{0}(a, ·)^{M} is of size at most ℵ_{α}.

Proof of claim: Since we may naturally view E_{0}(a, ·)^{M} as a

((Q_{0})^{M}|_{M_{α}}, N_{0})-full

structure, and hence a model of φ̂_{α}, the claim follows by assumption on φ̂_{α}. (Claim(1)□)

Claim(2): If M is a model of φ_{α+1} and a ∈ Q_{2}^{M} we have that {b : M ⊧ b < a} has size at most ℵ_{α}.

Proof of claim: This follows from the previous claim, since the assumption of

((Q_{0})^{M}|_{M_{α}}, ⟨{b : M ⊧ b < a}, =⟩)-fullness

yields a map from E_{0}(a, ·)^{M} onto {b : M ⊧ b < a}. (Claim(2)□)

Claim(3): No model of φ_{α+1} has size bigger than ℵ_{α+1}.

Proof of claim: For M such a model, we have that ⟨Q_{2}^{M}, <^{M}⟩ is by claim(2) a linear ordering all of whose initial segements have size at most ℵ_{α}, and thus Q_{2}^{M} can have size at most ℵ_{α+1}. Then claim(1) gives that Q_{1}^{M} has size at most ℵ_{α+1}, and the inductive assumption on φ_{α} restricts Q_{0}^{M} to size at most ℵ_{α}. (Claim(3)□)

Claim(4): φ_{α+1} does have a model of size ℵ_{α+1}.

Proof of claim: Let D = ⟨D, <⟩ be a dense linear ordering without end points of size ℵ_{α+1} all of whose initial segments have size ℵ_{α}. Let A_{α} be a model of φ_{α} of size ℵ_{α}.

For each a ∈ D we can choose a

(A_{α}, ⟨{b : D ⊧ b < a}, =⟩)-full

model N_{a} of size ℵ_{α} and we may assume that for a_{0} < a_{1} we have

N_{a_{0}} ∩ N_{a_{1}} = {b : D ⊧ d < a_{0}} ∪ A_{α}.

Then we can obtain a model A_{α+1} of size ℵ_{α+1} as the union of the {N_{a} : a ∈ D}.

The absence of relations between the various fibres E_{0}(a_{0}, ·)^{A_{α+1}} and E_{0}(a_{1}, ·)^{A_{α+1}} for a_{0} ≠ a_{1} ensures that A_{α+1} ⊧ φ_{α+1}. (Claim(4)□) □

6 Atomic models

It should be commented that there is a close connection between characterizing a cardinal in the sense of Knight and finding a theory T ⊂ L_{ω,ω} which posses an atomic model at that cardinal but no higher. Since there is an infinitary sentance ψ ∈ L_{ω_{1},ω} which holds in M if and only if M is atomic (with respect to formulas in L_{ω,ω}), one easily sees that:

Lemma 6.1 If T ⊂ L_{ω,ω} is a countable complete theory with atomic models of size κ but no larger, then the Scott sentance of the countable atomic model of T is realized by models of size κ but no models of larger cardinality.

The converse is also true:

Lemma 6.2 If the Scott sentance of M, φ_{M} ∈ L_{ω_{1},ω}, has a model of size κ but no larger, then there a corresponding countable first order theory T_{M} which has atomic models of size κ but no larger.

Proof Let F be the countable fragment of L_{ω_{1},ω} generate by φ_{M}. Let L^{∗} be the extension of L otbained by adding an n-ary relation R_{ψ(x_{1},...,x_{n})}(·, ..., ·) for each formula ψ(x_{1}, ..., x_{n}) ∈ F with n free variables. Let E(F, M) be the expansion of M obtained by

E(F, M) ⊧ R_{ψ(x_{1},...,x_{n})}(a_{1}, ..., a_{n})

if and only if

M ⊧ ψ(a_{1}, ..., a_{n}).

Let T_{M} ⊂ L_{ω,ω}^{∗} be the complete (finitary) theory of the resulting model E(F, M).

It is not hard to show that any atomic model of T_{M} will satisfy the Scott sentance of M. We leave the details to the reader. □

In this way, we have the equivalence of Knight’s problem with that of finding theories whose atomic models reach a given ℵ_{n}.

Here Chris Lakowski has informed me that he and Saharon Shelah many years previously constructed a countable complete theory T with atomic models of size ℵ_{2} but no higher. Thus the solution of Knight’s problem for characterizing ℵ_{2} should be credited to them.

7 Equivalence relations

Definition For E and F equivalence relations on Polish spaces X and Y, we say that E is Borel reducible to F, written

E ≤_{B} F,

if there is a Borel function f : X → Y such that for all x_{1}, x_{2} ∈ X we have

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

We use E ≤_{c} F to indicate that there is a continuous reduction, E ⊑_{B} F and E ⊑_{c} F to indicate that the reduction may respectively chosen Borel and one to one or continuous and one to one, and E <_{B} F if E ≤_{B} F holds and F ≤_{B} E fails.

Of course one can consider reductions that use functions which are not Borel but still have some claim on being “reasonably nice”. A discussion of these more general classes – such as absolutely Δ ∼_{2}^{1} – can be found in [7] and [10].

Definition If G is a Polish group acting continuously on a Polish space X we use E_{G}^{X} for the orbit equivalence relation given by

x_{1}E_{G}^{X} ⇔ ∃g ∈ G(g · x_{1} = x_{2}).

Among the Borel equivalence relations are: id(X), the identity relation on a Polish space X; E_{0}, the equivalence relation of eventual agreement on infinite binary sequences: thus for x, y ∈ 2^{ℕ} we have

xE_{0}y

if there exists some N ∈ ℕ such that

∀n > N(x(n) = y(n)).

It is known from [6] that id(ℝ) and E_{0} occupy a privileged position among the Borel equivalence relations:

Theorem 7.1 (Harrington, Kechris, Louveau) If E is a Borel equivalence relation, then either:

(I) E ≤_{B} id(ℝ); or
(II) E_{0} ⊑_{c} E.

An important class of equivalence relations arise as those of the form E_{G}^{X}, for G a Polish group acting continuously on a Polish space; in general these equivalence relations are not Borel. Thus one is not able to directly apply the Harrington-Kechris-Louveau theorem, and it is known (see [7]) that in general counterexamples do exist.

Nonetheless for many interesting classes of Polish groups one can prove the conclusion that whenever G acts continuously on a Polish space X we have either:

(I) E_{G}^{X} ≤_{B} id(ℝ); or

(II) E_{0} ⊑_{c} E_{G}^{X}.

Here a sequence of papers, most of which are discussed in [10], have culminated in a result of Howard Becker’s, who showed that this dichotomy theorem holds for all Polish groups allowing a complete left invariant metric.

The language of equivalence relations has also led to the following reformulation of the topological Vaught conjecture. While not equivalent to the original Vaught conjecture – which stated that for every Polish group G acting continuously on a Polish space X, there are either ≥ 2^{ℵ_{0}} many orbits or ≤ ℵ_{0} many orbits – it is known to be equiprovable over ZFC. We can prove one in ZFC if and only if we can prove the other.

Conjecture The topological Vaught conjecture (strong form). Let G be a Polish group acting continuously on a Polish space X. Then either

(I) E_{G}^{X} ≤_{B} id(ℕ) (where we view ℕ as a Polish space by giving it the discrete metric); or (II) id(ℝ) ⊑_{c} E_{G}^{X}.

The conclusion of the Harrington-Kechris-Louveau theorem, when it can be proved for an orbit equivalence relation, implies even this strong form of the topological Vaught conjecture. One has that if E_{0} ⊑_{c} E_{G}^{X} then id(ℝ) ⊑_{c} E_{G}^{X}, since id(ℝ) ⊑_{c} E_{0}; alternatively if E_{G}^{X} ≤_{B} id(ℝ) then the perfect set theorem for Σ ∼_{1}^{1} sets entails that either there are just countably many orbits, all of which are Borel, or there is a perfect set of orbit inequivalent points.

A discussion of these and related facts can be found in [3] and [2]; [11] also surveys recent work on the topological Vaught conjecture.

8 An amusing footnote to a theorem of Becker’s

This section is an extended footnote to the afore mentioned theorem from [2] and consequent question:

Theorem 8.1 (Becker) Let G be a Polish group admitting a complete left invariant metric. Then for any Polish G-space X, either

(I) E_{0} ⊑_{c} E_{G}^{X} or

(II) E_{G}^{X} ≤_{B} id(ℝ).

Question (Becker) Suppose G is a Polish group satisfying the conclusion of the above theorem. Must it have a compatible complete left invariant metric?

As a partial answer we prove here:

Theorem 8.2 There is a Polish group G without a complete left invariant metric such that whenever X is a Polish G-space: either

(I) E_{0} ⊑_{c} E_{G}^{X} or

(II) E_{G}^{X} is reducible to id(ℝ) by an absolutely Δ ∼_{2}^{1} function.

What is amusing and curious about the proof of this main theorem is its left handed use of large cardinal ideas. The key step is to force with the Frechet filter on ω_{1} of some inner model and consider the combinatorial consequences of the generic ultrapower. Of course this ideal of countable subsets of ω_{1} is never precipitous – the ultrapower is never well founded – and yet this generic embedding is precisely matched for the needs of the proof.

The reader might expect that this is somehow parallel to the proof of Silver’s theorem in cardinal arithmetic, where the proof is smoother in the event of there being access to a precipitous ideal on ω_{1}, but can be made to work in ZFC alone using less. Here the opposite is true. The argument could not fare at all with a precipitous ideal, or even one which gives rise to ω_{1} + 1 being included in the well founded part of the ultrapower. There is a strong homogeneity property for P(ω_{1})/Countable which lies diametrically opposite to any trace of well foundedness and is essential to the method.

Of course, this is not to say that the result above is optimal. In (II) one would prefer ≤_{B} id(ℝ), and so this is a curious footnote, rather than a finished answer.

We need the following detailed restatement of Knight’s result:

Theorem 8.3 (Knight) There is a countable structure M such that (i) there is a model M̂ of size ℵ_{1} which is L_{ω_{1},ω} equivalent to M; (ii) M = (M; <, (g_{n})_{n∈ℕ}) such that

(a) < totally orders M;

(b) for all a, b ∈ M

a < b ⇒ ∃n(g_{n}(b) = a).

Without further addressing the details of this construction – details which we will never need – let G_{K} denote the automorphism group of Knight’s model M, Aut(M). This group does not admit a complete left invariant metric in light of 3.8

Theorem 8.4 (Becker-Kechris, see [3]) Let G =Aut(N) be a closed subgroup of S_{∞}; let L be the language of N. Let X be a Polish G-space. Then there is a language L′ ⊃ L extending the language of N and σ ∈ L′_{ω_{1}ω} such that σ ⊧ φ_{N} (the Scott sentence of N) and |X/G| is Borel equivalent to Mod(σ), in the sense that there are θ : X →Mod(σ) and ρ : Mod(σ) → X such that:

(i) θ witnesses E_{G}^{X} ≤_{B}≅ |Mod(σ);

(ii) ρ witnesses ≅ | Mod(σ) ≤_{B} E_{G}^{X}; and

(iii) these are orbit inverses to one another in the sense that for all x ∈ X, xE_{G}^{X}(ρ∘θ(x)).

Theorem 8.5 (Becker; Hjorth-Kechris, [7], [10]) Let G be a Polish group and X a Polish G-space; then either

(I) E_{0} ⊑_{c} E_{G}^{X} or

(II) E_{G}^{X} is reducible to id(2^{<ω_{1}}) by a function that is absolutely Δ ∼_{2}^{1} in the codes.

We also need to fix some notation and terminology for talking about the Scott sentence of a structure.

Definition For A a model and a⃗ a finite sequence from A we define

φ_{α}^{a⃗,A}

by induction on the ordinal α.

φ_{0}^{a⃗,A} = ⋀{ψ(x⃗) : ψ(x⃗) quantifier free, a⃗ ⊧ ψ(a⃗)}
φ_{α+1}^{a⃗,A} = ⋀{∃y⃗φ_{α+1}^{a⃗b⃗,A}(x⃗, y⃗) : b⃗ ∈ A^{<ℕ}} ∧ ∀y⃗ ⋁{φ_{α+1}^{a⃗b⃗,A}(x⃗, y⃗) : b⃗ ∈ A^{<ℕ}}.

For λ a limit we set

φ_{λ}^{a⃗,A} = ⋀_{α<λ} φ_{α}^{a⃗,A}.

As shown in [13], we will come to an ordinal δ such that for all a⃗, b⃗ ∈ A

∃γ(φ_{γ}^{a⃗,A} ≠ φ_{γ}^{b⃗,A}) ⇔ φ_{δ}^{a⃗,A} ≠ φ_{δ}^{b⃗,A}.

The least such δ is the Scott height of A and is denoted by α(A).

This ordinal will have the same cardinality as A. φ_{α(A)+2}^{∅,A} =_{df} φ^{A} is the (canonical) Scott sentence of A; φ_{α(A)+2}^{a⃗,A} =_{df} φ^{a⃗,A} (or just φa⃗ when context indicates A) is the Scott sentence of a⃗ (in A); each φ_{α}^{a⃗,A} is the αth approximation of the Scott sentence for a⃗. In the text below we will also call it the canonical α-type of a⃗.

Proof of Theorem 8.2

Letting X be a Polish G_{K} space, we can apply the result above due to Becker and Kechris, and let σ ∈ L′_{ω_{1}ω} be the infinitary sentence whose countable models correspond naturally to the orbits of G_{K} in X. Assuming for the moment that E_{0} ⊑_{c} E_{G}^{X} fails, we apply the result of Becker, Hjorth, and Kechris to find

θ : Mod(σ) → 2^{<ω_{1}},

absolutely Δ ∼_{2}^{1} in the codes such that for all N_{1}, N_{2} ∈ Mod(σ) we have

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

Let z code θ and σ. We wish to show that we can somehow massage θ into an absolutely Δ ∼_{2}^{1} injection from Mod(σ)/ ≅ into 2^{ℕ}.

Claim(1) It suffices to show that there is always (for any N appearing in any generic extension of 𝕍) N_{0} ∈ L[θ(N), z] ∩ Mod(σ) (so in particular it has ℕ as its underlying set) with

N_{0} ≅ N .

Proof of claim: If so, choose N_{0} least such in the canonically definable in θ(N), z well order of L[θ(N), z]. (This we may do since θ(N) is a subset of the ordinals.) Then we choose x_{N} to be the first (in L[θ(N), z]) element of, say, 2^{ℕ} coding N_{0}. Since θ(N) depends only on [θ(N)]≅ (the isomorphism type of N)

N ↦ x_{N}

is an invariant; since x_{N} codes a model isomorphic to N it is a complete invariant, and we do indeed have reduction to id(2^{ℕ}), and hence id(ℝ). The reduction is clearly Δ ∼_{2}^{1}; by appealing to the absoluteness of θ in the Becker/Hjorth-

Kechris theorem, we have that it is absolutely Δ ∼_{2}^{1}. (Claim □)

Claim(2) In any generic extension L[θ(N), z][G] of L[θ(N), z] in which θ(N) is countable we have

L[θ(N), z][G] ⊧ ∃N_{0} ∈ Mod(σ)(θ(N_{0}) = θ(N)).

Proof of Claim: Since for w some real coding θ(N) in L[θ(N), z][G] the existence of some such N_{0} as indicated is Σ_{2}^{1}(z, w), and so we may apply Shoenfield absoluteness. (Claim □)

Claim(3) For any partial order ℙ in L[θ(N), z] and ℙ-term τ with

L[θ(N), z] ⊧ (ℙ ⊩ τ(Ġ) ∈ Mod(σ) ∧ θ(τ(Ġ)) = θ(N)))

we have

L[θ(N), z] ⊧ ℙ × ℙ ⊩ τ(Ġ_{l}) ≅ τ(Ġ_{r}).

Proof of Claim. Otherwise choose (p_{1}, p_{2}) ∈ ℙ × ℙ forcing otherwise, and then G_{l} × G_{r} ⊂ ℙ × ℙ below this condition which is 𝕍-generic. By Shoenfield, τ(G_{l}) ≅ τ(G_{r}) is absolute to L[θ(N), z][G_{l} × G_{r}], as is the calculation of θ(τ(G_{l})) and θ(τ(G_{r})), and so for either N_{0} = τ(G_{l}) or N_{0} = τ(G_{r}) we have a generic extension of 𝕍 containing some N_{0} ∈ Mod(σ) with

θ(N_{0}) = θ(N),
N_{0} ≅ N̸ .

Once more by Shoenfield, existence of such an N_{0} is absolute to 𝕍, and this contradicts the assumption on θ. (Claim □)

Claim(4) There is φ ∈ (L′_{∞,ω})^{L[θ(N),z]} such that L[θ(N), z] believes that for ℙ = Coll(ω, |θ(N)|) we have

ℙ ⊩ φ is the Scott sentence of some N_{0} with θ(N_{0}) = θ(N).

Proof of Claim. Let τ be a ℙ-term for some model in the generic extension L[θ(N), z]^{ℙ} with θ(τ(Ġ)) = θ(N); this term exists by Claim(1). Then the Scott sentence φ does not depend on the choice on G by the last claim. Hence, by standard facts about forcing (namely: whenever ℙ_{1} × ℙ_{2} ⊩ τ_{1}(Ġ_{l}) = τ_{2}(Ġ_{r}) one may prove by induction on the rank of the terms τ_{1} and τ_{2} that there is some a in the ground model with ℙ_{1} × ℙ_{2} ⊩ τ_{1}(Ġ_{l}) = τ_{2}(Ġ_{r}) = a) we can find φ ∈ L[θ(N), z] as required. (Claim □)

Now let α be the Scott height of any model of φ and let A = (ψ_{β})_{β∈κ} enumerate the canonical α-types realized in any model of φ. (This can be calculated in L[θ(N), z].) We need to introduce a prelinear ordering ≤^{∗} on these canonical α-types. For ψ, ψ′ appearing in the sequence A, let us define

ψ ≤^{∗} ψ′

to hold if in any model N_{0} of φ there exist x, y ∈ N_{0} with

N_{0} ⊧ ψ(x),
N_{0} ⊧ ψ′(y),

and

N_{0} ⊧ x ≤ y;

equivalently: ∃x, y ∈ N_{0}, n ∈ ℕ(N_{0} ⊧ ψ(x), N_{0} ⊧ ψ′(y), g_{n}(y) = x);

equivalently since ψ′ determines every L′_{ω_{1},ω} fact about a tuple satisfying it: ∃n ∈ ℕ such that for all y ∈ N_{0}(N_{0} ⊧ ψ′(y) ⇒ ψ(g_{n}(y))).

Thus ≤^{∗} is a prelinear order on A with every initial segment of the form {a ∈ A : a ≤^{∗} b} countable. If A were itself countable, then we would necessarily have that φ is countable, and we would happily sign off with Claim(1). So suppose instead that A is uncountable in L[θ(N), z], and we prepare to force to make A larger.

Here it should be pointed out that many of the elements of A diverge even before ω_{1}^{L[θ(N),z]} – and so that in this sense only a countable ordinal is needed to verify that they are distinct:

Claim(5) There is in L[θ(N), z] some L[θ(N), z]-uncountable Z ⊂ κ and γ ≤ ω_{1}^{L[θ(N),z]} such that

(i) for all β_{1} ≠ β_{2} in Z we have

ψ|_{β_{1}} ≠ ψ|_{β_{2}};

(ii) each ψ_{β}|_{γ} is either in HC^{L[θ(N),z]} or of the form

⋀_{ξ∈ω_{1}^{L[θ(N),z]}} ψ_{β,ξ},

with each ψ_{β,ξ} ∈HC^{L[θ(N),z]}.

Proof of Claim: Since if the Scott height of a model N_{0} is greater than or equal to some ordinal γ then for β < γ there are a⃗, b⃗ ∈ N_{0}^{<ℕ} such that

φ_{β}^{a⃗,N_{0}} = φ_{β}^{b⃗,N_{0}}

(the canonical β-types are the same) but

φ_{β+1}^{a⃗,N_{0}} ≠ φ_{β+1}^{b⃗,N_{0}}

(at the next stage of the Scott analysis they diverge). (Claim □)

¿From now until the finish let ℙ denote the forcing

(P(ω_{1})/Countable)^{L[θ(N),z]}

consisting of L[θ(N), z]’s uncountable subsets of ω_{1}^{L[θ(N),z]} considered up to (its version) of the countable symmetric difference. For G ⊂ ℙ a L[θ(N), z]-generic object, let U_{G} indicate the generic ultrafilter (of all those Y ⊂ ω_{1}^{L[θ(N),z]} with [Y] ∈ G). We then define the generic embedding

j_{G} : L[θ(N), z] → Ult(U_{G}, L[θ(N), z])

of L[θ(N), z] into the generic ultrapower.

Let ℚ denote the forcing ℙ ∗ Coll(ω, |jĠ(θ(N))|^{Ult(UĠ,L[θ(N),z])}) – where we force intitially with ℙ, and then in the illfounded model Ult(UĠ, L[θ(N), z]) we collapse its |jĠ(θ(N)). Using elementarity and claim(2) we can let τ̇ be a ℚ-term for a model that satisfies in Ult(UĠ, L[θ(N), z]) the (from its point of view) infinitary sentence jĠ(φ).

The key point in all these steps is the next one:

Claim(6) ℚ × ℚ ⊩ τ(Ġ_{l}) ≅ τ̸(Ġ_{r}).

Proof of Claim: Otherwise (after perhaps refining to some (q_{1}, q_{2}) ∈ ℚ × ℚ) we can apply the argument of Claim(4) and obtain some q ∈ ℚ and φ′ ∈ L[θ(N), z] such that

q ⊩_{ℚ} τ has φ′ as its Scott sentence.

Let α′ be the Scott height of any model of φ′ and let A′ = (ψ′_{β})_{β∈κ′} enumerate the canonical α′-types of any model of φ′. By analogy with the preceding definition, for ψ, ψ′ appearing in A′

ψ ≤^{∗} ψ′

if in any model N_{0} of φ′ there exist x, y ∈ N_{0} with

N_{0} ⊧ ψ(x),
N_{0} ⊧ ψ′(y),

and

N_{0} ⊧ x ≤ y.

Let G ⊂ ℙ be L[θ(N), z]-generic, and let B = (φ_{β})_{β∈ζ} be j_{G}(A) in Ult(UĠ, L[θ(N), z]). (Note that ζ will only be an ordinal from the point of view of Ult(UĠ, L[θ(N), z]), and not genuinely wellfounded in 𝕍; similarly I have no real right to use notation indicating that B is only a sequence from the perspective of this highly non-transitive – not even wellfounded – model Ult(UĠ, L[θ(N), z]).) Now let ζ′ be an ordinal of Ult(UĠ, L[θ(N), z]) not in the image of j_{G}; in other words, let us choose

ζ′ ∈ Ordinals^{Ult(UĠ,L[θ(N),z])} \ j_{G}[Ordinals].

Remembering the prelinear ordering ≤^{∗} of A we have

∀α < κ(Ult(UĠ, L[θ(N), z]) ⊧ j_{G}(ψ_{α}) ≤^{∗} φ_{ζ′})

since j_{G} fixes ℕ and each element of A appears in a countable ≤^{∗} initial segment. Thus for G_{1} ⊂ Coll(ω, |jĠ(θ(N))|^{Ult(UĠ,L[θ(N),z])}) an L[θ(N), z][G]-generic we have some N_{0} ∈ Mod(σ) ∩ Ult(UĠ, L[θ(N), z])[G_{1}] with

Ult(UĠ, L[θ(N), z])[G_{1}] ⊧ (N_{0} ⊧ j_{G}(φ)).

Thus we may fix a which Ult(UĠ, L[θ(N), z])[G_{1}] considers to be in N_{0} with

Ult(UĠ, L[θ(N), z])[G_{1}] ⊧ (N_{0} ⊧ φ_{ζ′}(a)).

Hence for all β < κ there exists b_{β} ∈^{Ult(UĠ,L[θ(N),z])[G_{1}]} N_{0} and n_{β} ∈ ℕ with

Ult(UĠ, L[θ(N), z])[G_{1}] ⊧ (N_{0} ⊧ j_{G}(ψ_{β})(b_{β}) ∧ g_{n_{β}}(a) = b_{β}).

Now let φ^{∗} be the true^{2} canonical α′-type of a and for β ∈ κ let φ_{β}^{∗} be the true canonical α′-type of b_{β}. By the characteristic properties of the Scott sentence

φ′ ⊧ ∀x(φ^{∗}(x) ⇒ φ_{β}^{∗}(g_{n_{β}}(x)).

Thus in particular, φ^{∗} ≥^{∗} φ_{β}^{∗}. Note that φ′, φ^{∗} and so on are all in L[θ(N), z].

Now there is a split into two cases. For ψ = φ_{α}^{a⃗,N_{0}} some canonical α-type in the model N_{0}, and for γ < α, let ψ|_{γ} denote φ_{γ}^{a⃗,N_{0}} – the γ level approximation to ψ = φ_{α}^{a⃗,N_{0}}. This is welldefined; it does not depend on the choice of N_{0} and a⃗.

Now recall from claim(5) that we have some sequence (ψ_{β})_{β∈Z} of canonical α-types, appearing in the Scott analysis of N, and we have some γ ≤ ω_{1}^{L[θ(N),z]} such that each ψ_{β}|_{γ} is either in HC^{L[θ(N),z]} or of the form

⋀_{ξ∈ω_{1}^{L[θ(N),z]}} ψ_{β,ξ},

with each ψ_{β,ξ} ∈HC^{L[θ(N),z]}.

2As calculated by any wellfounded inner model – for instance L[θ(N), z][G][G_{1}]

Case A. γ < ω_{1}^{L[θ(N),z]}.

Note then that each such ψ_{β}|γ is in HC^{L[θ(N),z]} and then left fixed by j_{G}. Thus in particular b_{β} ⊧ ψ_{β}|γ, and so φ_{β}^{∗} ⇒ ψ_{β}|γ. Then we may choose in L[θ(N), z] and a maximal (and necessarily uncountable by case assumption) Z_{0} ⊂ κ such that for all distinct β_{1}, β_{2} ∈ Z_{0} we have

ψ_{β_{1}}|γ ≠ ψ_{β_{2}}|γ,
∴ ψ_{β_{1}}|γ ⇒ ¬ψ_{β_{2}}|γ.

For each β ∈ Z_{0} let A_{β} = {β′ ∈ κ′ : ψ′_{β′} ⇒ ψ_{β}|γ}. We have then immediately from the above that the A_{β}’s are non-empty, disjoint as β ranges over Z_{0}, and for each β ∈ κ there is some ψ′ ∈ A_{β} with

ψ′ ≤^{∗} φ^{∗},

and hence (since φ′ is the Scott sentence of an expansion of Knight’s model) there is some n with

φ′ ⊧ ∀x(φ^{∗}(x) ⇒ ψ′(g_{n}(x))).

This contradicts the uncountability of Z_{0}.

Case B. Not case A.

But we still have ψ_{β}|_{γ′} is in HC^{L[θ(N),z]} for each γ′ < ω_{1}^{L[θ(N),z]} and hence invariant under j_{G}. Analogously to case A we have that b_{β} ⊧ ψ_{(ω_{1})^{L[θ(N),z]}}, and hence φ_{β}^{∗} ⇒ ψ_{β}|ω_{1}^{L[θ(N),z]}. Letting C_{β} = {β′ ∈ κ′ : ψ′_{β′} ⇒ ψ_{β}|ω_{1}^{L[θ(N),z]}} we arrive at the same contradiction as in case A. (Claim □)

For G ⊂ ℙ an L[θ(N), z]-generic let φ_{G} denote the Scott sentence in L[θ(N), z][G] of any model in Ult(UĠ, L[θ(N), z])^{Coll(ω,ω_{1}^{L[θ(N),z][G]})} satisfying j_{G}(φ). (So we can identify the isomorphism type of τ̇ without proceeding on to the second step of the forcing; this uses the upwards absoluteness of Σ ∼_{1}^{1} between ω-models, and that Ult(UĠ, L[θ(N), z]) itself does not believe that the isomorphism type depends on the second part of the forcing ℚ.)

Claim(7) For any p_{1}, p_{2} ∈ ℙ there is an automorphism

π : ℙ ≅ ℙ

L[θ(N), z] with p_{1} and π(p_{2}) compatible, and such that if G ⊂ ℙ is L[θ(N), z]-generic, then there is some

π̂ : Ult(U_{G}, L[θ(N), z]) ≅ Ult(U_{π(G)}, L[θ(N), z])

such that

π̂ ∘ j_{G} = j_{π(G)}.

Proof of Claim. Let A_{1}, A_{2} ⊂ ω_{1}^{L[θ(N),z]} be representatives of p_{1}, p_{2} respectively. Without loss of generality, they are both cocountable. So L[θ(N), z] may find a bijection π_{0} of its ω_{1} with

π_{0}[A_{2}] = A_{1}.

Then π_{0} naturally induces π, which in turn naturally lifts to an isomorphism of the ultrapowers since π_{0} ∈ L[θ(N), z]. (Claim □)

Now we can complete the Glimm-Effros/Harrington-Kechris-Louveau type of argument of [6] or [3]. One finds in [3] a theorem to the effect that if we have a Polish group action where every orbit is dense and meager, then E_{0} continuously reduces to the orbit equivalence relation. Claim(6) was the analogue of every orbit meager; Claim(7) was in spirit that every orbit is dense.

Let (D_{i})_{i∈ℕ} enumerate the open dense subsets of ℙ × ℙ existing in L[θ(N), z]. We build conditions p_{s} ∈ ℙ for s ∈ 2^{<ℕ} and automorphisms π_{n} ∈ L[θ(N), z] as in Claim(7) such that:

(i) for s ⊃ t we have p_{s} ≤ p_{t};

(ii) for n ∈ ℕ and s, t ∈ 2^{n} we have
(p_{s0}, p_{t1}), (p_{t1}, p_{s0}) ∈ D_{n} ∩ D_{n−1} ∩ ... ∩ D_{0};
(iii) for 0^{n} ∈ 2^{n} consisting of n zeroes, and u ∈ 2^{<ℕ} we have
π_{n}(p_{0^{n}0u}) = p_{0^{n}1u}.

We can clearly do all this; (i) and (ii) just follow by the usual abstract nonsense, while (iii) is a direct consequence of claim(7).

Then for w ∈ 2^{ℕ} let G_{w} be the filter generated by {p_{w|n} : n ∈ ℕ}.

Claim(8) For w_{0}, w_{1} ∈ 2^{ℕ}, if they are E_{0}-inequivalent, then (G_{w_{0}}, G_{w_{1}}) is ℙ × ℙ-generic. Proof of Claim: By (ii). (Claim□)

Thus φ_{G_{w_{0}}} = φ_{G_{w_{1}}} implies w_{0}E_{0}w_{1} by Claim(6).

Claim(9) For w_{0}, w_{1} ∈ 2^{ℕ}, w_{0}E_{0}w_{1} implies φ_{G_{w_{0}}} = φ_{G_{w_{1}}}.

Proof of Claim. Since by applying (ii) finitely many times we may find some π ∈ L[θ(N), z] with

π : ℙ ≅ ℙ

lifting to some π̂ : Ult(U_{G_{w_{0}}}, L[θ(N), z]) ≅ (U_{G_{w_{1}}}, L[θ(N), z]) as in Claim(7). Then since these models are isomorphic under an isomorphism sending j_{G_{w_{0}}}(φ) to j_{G_{w_{1}}}(φ) it follows from the definition of these Scott sentences that φ_{G_{w_{0}}} = φ_{G_{w_{1}}}. (Claim□)

By passing to a generic extension in which a large enough initial segment of L[θ(N), z] is countable we may then easily obtain that in some generic extension 𝕍[G_{2}] we have

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

But then it is a general fact that whenever E_{0} is Borel reducible to an equivalence relation it is continuously and injectively reducible as well, therefore

𝕍[G_{2}] ⊧ E_{0} ⊑_{c}≅ |_{Mod(σ)}.

This last fact is easily seen to be absolute between transitive class models, and hence

𝕍 ⊧ E_{0} ⊑_{c}≅ |_{Mod(σ)},

and we are finished. □

References

[1] J. Barwise, Admissible sets and structures. An approach to definability theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1975.

[2] H. Becker, Polish group actions: dichotomies and generalized elementary embeddings, Journal of the American Mathematical Society, vol. 11(1998), pp. 397–449.

[3] 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.

[4] P.J. Cameron, Oligomorphic permutation groups, London Mathematical Society Lecture Note Series, 152. Cambridge University Press, Cambridge, 1990.

[5] S. Gao, On automorphism groups of countable structures, Journal of Symbolic Logic, vol. 63(1998), pp. 891–896.

[6] 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.

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

[8] G. Hjorth, Vaught’s conjecture on analytic sets, Journal of the American Mathematical Society, vol. 14(2001), pp. 125-143.

[9] G. Hjorth, Orbit cardinals, Israel Journal of Mathematics, vol. 111(1999), pp. 221-261.

[10] G. Hjorth, Classification and orbit equivalence relations, American Mathematical Society, Rhode Island, 2000.

[11] G. Hjorth, Group actions and countable models, to appear in Logic Colloquium 1999, proceedings of the ASL European meeting held Utrecht.

[12] T. Jech, Set theory, Academic Press, New York, 1978.

[13] H.J. Keisler, Model theory for infinitary logic, North-Holland, Amsterdam, 1971.

[14] J.F. Knight, A complete L_{ω_{1}ω}-sentence characterizing ℵ_{1}, Journal of Symbolic Logic, vol. 42(1977), pp. 59–62.

[15] M. Makkai, An example concerning Scott heights, Journal of Symbolic Logic, vol. 46(1981), pp. 301-318.

[16] S. Shelah, Borel sets with large squares, Fundamenta Mathematicae, vol. 159(1999), pp. 1–50.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555