Overview

Main Goal: Survey some of the recent work on Borel and Σ ∼_{1}^{1} equivalence relations We will specifically consider the Σ ∼_{1}^{1} equivalence relation which arises as the isomorphism relation on a class of countable structures.

Definition A topological space is Polish if it is separable^{1} and it allows a complete metric.

Examples 1. ℝ, ℂ in their usual topologies.

2. Any countable ordinal in the order topology, where the basic open sets are {β : γ_{1} < β < γ_{2}}. (This requires some proof of course. One way to do this is to show by transfinite induction on α < ω_{1} that for any a < b ∈ ℝ ∪ {+∞} we can find a closed homeomorphic copy of α in [a, b) if α is a limit ordinal or in [a, b] if α is a successor.)

3. ℕ^{ℕ} = {f : ℕ → ℕ}. Here we can take as our complete metric

d(f, g) = 2^{−Δ(f,g)}

where Δ(f, g) is the least n at which f(n) ≠ g(n).

Actually for us some of the most important examples of Polish spaces will arise from model theory.

4. Let L be some countable language and let Mod(L) be the space of Lstructures on ℕ with the topology whose basic open sets are all those of the form

{M|M ⊧ φ(n_{1}, n_{2}, .., n_{k})}

for k, n_{1}, ..., n_{k} ∈ ℕ and φ a quantifier-free formula.

So as a simple case of this let us say that L = {U, R} where U is a unary function and R is a binary relation. Then we can associate to any M ∈ Mod(L) the pair

(U^{M}, χ_{(R^{M})}) ∈ ℕ^{ℕ} × {0, 1}^{ℕ},

where U^{M} is M’s interpretation of the unary function symbol and χ_{(R^{M})} is the characteristic function of the binary relation from the point of view of M.

We obtain as in example 3 that ℕ^{ℕ} × {0, 1}^{ℕ} is Polish^{2}. And our association

M ↦ (U^{M}, χ_{(R^{M})})

is a homeomorphism.

5. Actually, as we will see later, the topology in which we take as basic open sets those of the form

{M|M ⊧ φ(n_{1}, n_{2}, .., n_{k})}

φ a first order formula gives rise to a Polish topology. Richer than the first, but obviously closely connected.

6. More generally, if F ⊂ L_{ω_{1},ω} is any countable “fragment”^{3} then the topology generated by sets of the form

1I.e. there is a countable dense subset

2For instance, d((f_{1}, f_{2}), (g_{1}, g_{2})) = 2^{−Δ(f_{1},g_{1})} + 2^{−Δ(f_{2},g_{2})}.

3Again, the definition of L_{ω_{1},ω} and “fragment” will be given in a couple of weeks.

{M|M ⊧ φ(n_{1}, n_{2}, .., n_{k})}

for φ ∈ F is Polish.

Definition A subset of a Polish space is Borel if it can be generated from the open sets by the operations of complementation, countable union, and countable intersection. A function

f : X → Y

is Borel if f^{−1}[B] is Borel for any Borel B ⊂ Y. (Equivalently we simply have required that the pullbacks of open sets along f are all Borel; the point is that the operations of complementation, intersection, and union behave nicely with respect to pullback.)

An equivalence relation E on a Polish space X is Borel if it is Borel as a subset of X × X in the product topology.

With respect to this last definition, it is not hard to see that the product of two Polish spaces is Polish; in particular X × X is Polish.

Here a theorem dating back to the early 1900’s describes the possible structure of an arbitrary Borel set.

Theorem (Classical) If B is a Borel set then either (I) |B| ≤ ℵ_{0} (B is countable), or (II) |B| = 2^{ℵ_{0}} (B has cardinality continuum).

\underline{Moreover} any two Borel sets of the same cardinality are Borel isomorphic.

By this last part of the theorem I mean the following. If X_{1}, X_{2} are Polish and B_{i} ⊂ X_{i} (i = 1, 2) are Borel with |B_{1}| = |B_{2}| then there is a function

f : B_{1} → B_{2}

with (a) f a bijection;

(b) f^{−1}[C] Borel all C ⊂ B_{2} Borel; and

(c) f[C] Borel all C ⊂ B_{1} Borel. (Just in passing I should add that (c) above follows from the conjunction of

(a) and (b) – but we probably won’t need that particular fact.)

The situation for Borel equivalence relations initially appears the same.

Theorem (Silver) Let E be a Borel equivalence relation on a Polish space X. Then either

(I) |X/E| ≤ ℵ_{0} (E has only countably many equivalence classes), or (II) |X/E| = 2^{ℵ_{0}} (E has continuum many classes).

But there is no “moreover”. The problem is with part (II), where there is an enormous range of possible types of equivalence relations with continuum many equivalence classes.

Definition Let E and F be Borel equivalence relations on Polish X and Y. We write

E ≤_{B} F,

and say that E is Borel reducible to F, if there is a Borel function

f : X → Y

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

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

E ∼_{B} F indicates that we have both

E ≤_{B} F

and

F ≤_{B} E.

Examples 1. For any Polish space X we have id(X) as the identity relation on X: {(x_{1}, x_{2}) ∈ X × X : x_{1} = x_{2}}.

2. E_{0}, eventual agreement on

2^{ℕ} = {0, 1}^{ℕ},

the space of infinite binary sequences. So that f_{1}E_{0}f_{2} if there is some N ∈ ℕ such that

∀m > N(f_{1}(m) = f_{2}(m)).

3. E_{v}, the Vitali equivalence relation consisting of cosets of ℚ in ℝ. So r_{1}E_{v}r_{2} if

r_{1} − r_{2} ∈ ℚ.

Actually it turns out that E_{0} ∼_{B} E_{v} and for any two uncountable Polish spaces X_{1}, X_{2} one has id(X_{1}) ∼_{B} id(X_{2}).

Possibility (II) from Silver’s theorem represents the start of a very long story. The first major result was obtained at the end of the 1980’s:

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

(I) E ≤_{B} id(2^{ℕ}); (II) E_{0} ≤_{B} E.

It takes a non-trivial amount of descriptive set theory to prove this theorem. Instead I will probably try to work through the analogue for isomorphism relation on countable structures.

Just as a warning, for L a countable language we do not have that the isomorphism relation on countable L-structures is Borel in any of the previously mentioned Polish topologies, except when L is composed solely of unary predicates. Thus Harrington-Kechris-Louveau will not generally apply.

However it turns out that an analogue can be proved.

Here for σ ∈ L_{ω_{1},ω} I will let Mod(σ) be the subset of Mod(L) consisting of models of σ. This is a Borel subset of Mod(L) under any of our topologies, and a Polish space in its right in the topology generated by any countable fragment F ⊂ L_{ω_{1},ω} which includes σ.

Theorem (Becker; Hjorth-Kechris) For L a countable language and σ ∈ L_{ω_{1},ω} we have either

(I) there is a Δ ∼_{1}^{HC} function^{4} assigning elements of 2^{<ω_{1}} as complete invariants, or (II) E_{0} ≤_{B}≅ |_{Mod(σ)}.

Beyond E_{0} the picture becomes extremely complicated, and it is poorly understood. If time allows, we might be able to work in some discussion of this still largely uncharted territory. Another side topic will be the theory of continuous actions of Polish groups and some special cases of the topological Vaught conjecture ; this should fit naturally into the proof of “Becker; Hjorth-Kechris” above, since it too requires some discussion of the general actions of Polish groups.

4That is to say, some function which is Δ_{1}(x) over the hereditarily countable sets for some hereditarily countable x. The details of this definition are not so important; it is just that we can not use the old standby of Borel reduction for various technical reasons.

One might choose to think of the complexity class Δ ∼_{1}^{HC} as being the analogue to HC of recursive to HF (the hereditarily finite sets).

Borel sets

Definition A topological space is Polish if it is separable and there exists a complete metric which generates its topology.

Note then that a Polish space always has a countable basis for its topology. Just to give some context, let me mention a classical characterization of

Polish spaces. We will never use this result, so I mention it without proof.

Theorem (Hausdorff) A topological space is Polish if and only if it is homeomorphic to some subset of the Hilbert cube, [0, 1]^{ℕ}, and it is the image of ℕ^{ℕ} under some continuous, open function.

Definition The σ-algebra generated by the open sets forms the Borel subsets of a Polish space.

Example Let L be a countable language and Mod(L) the space of L-structures on ℕ; if we equip this space with the topology generated by quantifier free formulas then it is naturally homeomorphic to

∏_{no of unary predicates}{0, 1}^{ℕ} × ∏_{no of binary relations}{0, 1}^{ℕ×ℕ}×

∏_{no of ternary relations}{0, 1}^{ℕ×ℕ×ℕ} × ⋯

∏_{no of unary functions} ℕ^{ℕ} × ∏_{no of binary functions} ℕ^{ℕ×ℕ} · · · .

We will shortly prove that countable products of Polish spaces are Polish, and so this is as well.

Then one has for any first order formula φ and n⃗ ∈ ℕ^{<ℕ} that the set of

{M|M ⊧ φ(n⃗)}

is a Borel set. This is easily proved by induction on the logical complexity of φ, starting with the quantifier free formulas as the base case, and working up through the addition of existential and universal quantifiers^{5} by observing that

{M : M ⊧ ∃xφ(n⃗, x)} = ⋃_{m∈ℕ}{M : M ⊧ φ(n⃗, m)}

and

{M : M ⊧ ∀xφ(n⃗, x)} = ⋂_{m∈ℕ}{M : M ⊧ φ(n⃗, m)}.

5Since every formula is provably equivalent to one with all the quantifiers on the outside and all the Boolean connectives on the inside, this is all we need to worry about.

Thus the topology of quantifier free formulas and the topology of first order logic give rise to the same Borel sets.

Definition A set X with a σ-algebra of sets B is said to be a standard Borel space if there is some Polish topology which gives rise to B as its Borel sets.

Now we can at least state the our temporary goals, just for this section.

1. Mod(L) in the topology of first order formulas is Polish.

2. A Borel subset of a standard Borel space is again standard Borel.

3. Any uncountable Borel set has size 2^{ℵ_{0}}.

Actually in the proof of this last point we will follow the path chosen in Kechris’ Classical descriptive set theory, reducing it to 2. and the perfect set theorem for Polish spaces.

The arguments here are all fairly elementary. One does little calculations with respect to metrics, and the typical step is to show that we can fiddle some coordinates to produce a complete metric with various desirable properties.

Ultimately we will use these little results as part of the proof the above mentioned dichotomy theorem for the isomorphism relation on classes of countable structures. The proof requires us to repeatedly modify a given space of structures, through transfinitely many steps, and at each stage it will be necessary to maintain the Polishness of the space.

The study of Polish space has emerged as a central theme in descriptive set theory. It is generally accepted that these are the spaces we can work with, applicable to a wide context but sufficiently specific to avoid certain pathologies.

Recently a few people – notably Becker and Kechris - have made some use of the more general “strong Choquet” spaces. But it is not clear that this is likely to ever unseat the current prejudice in favor of Polish.

Lemma Let X be a Polish space. Then it has as a compatible complete metric bounded by 1. Proof Let d′ be some complete metric. Let

d(x_{1}, x_{2}) = \frac{d′(x_{1}, x_{2})}{1 + d′(x_{1}, x_{2})}.

The transformation

r ↦ \frac{r}{1 + r}

provides an order preserving transformation of [0, ∞) onto [0, 1). Thus, jumping ahead to the end of the argument, once we establish that d is a metric then we have the same Cauchy sequences for the two metrics, and from this completeness follows for free. Similarly the two metrics have the same open balls, and hence give rise to the same topologies.

We are therefore only left with proving it to be a metric. And here the main issue is showing that the triangle inequality holds.

Let x_{1}, x_{2}, x_{3} ∈ X. We want to show

d(x_{1}, x_{3}) ≤ d(x_{1}, x_{2}) + d(x_{2}, x_{3}).

We may assume that

d′(x_{1}, x_{3}) ≥ d′(x_{1}, x_{2}), d′(x_{2}, x_{3});

since if for instance d′(x_{1}, x_{3}) ≤ d′(x_{1}, x_{2}) then

d(x_{1}, x_{3}) ≤ d(x_{1}, x_{2}),

since our change in coordinates is order preserving, and we are done. But now we have

d(x_{1}, x_{2}) + d(x_{2}, x_{3}) = \frac{d′(x_{1}, x_{2})}{1 + d′(x_{1}, x_{2})} + \frac{d′(x_{2}, x_{3})}{1 + d′(x_{2}, x_{3})}

≥ \frac{d′(x_{1}, x_{2}) + d′(x_{2}, x_{3})}{1 + d′(x_{1}, x_{3})},

by our assumption above, which in turn, by the triangle inequality for d′, is at least as large as \frac{d′(x_{1},x_{3})}{1+d′(x_{1},x_{3})}. □

Corollary Let (X_{i})_{i} be a sequence of Polish spaces. Then

∏_{i∈ℕ} X_{i}

is Polish. Proof Let d_{i} be a complete metric on X_{i}, i ∈ ℕ. By the lemma we may assume the metric bounded by one. Then for

x⃗ = (x_{0}, x_{1}, x_{2}, ...), y⃗ = (y_{0}, y_{1}, y_{2}, ...) ∈ ∏_{i∈ℕ} X_{i}

we can let

d(x⃗, y⃗) = ∑_{i∈ℕ} 2^{−i}d_{i}(x_{i}, y_{i}).

□

Lemma An open subset of a Polish space is Polish in the subspace topology. Proof Let X be a Polish space, d a complete metric, O ⊂ X open.

Let us fix a continuous

π : O → ℝ

which has the property

π(x) → +∞

as x → X \ O. For instance we can take

π(x) = \frac{1}{inf\{d(x, y)|y ∉ O\}}.

Then let

d_{O}(x_{1}, x_{2}) = d(x_{1}, x_{2}) + |π(x_{1}) + π(x_{2})|.

Since π is continuous we do not add to the topology of O by taking this metric. For instance, if V ⊂ O is open, x ∈ V, then we can find some ϵ such that for all y with d(x, y) < ϵ we have y ∈ V; but then from the definition of d_{O} we have every y with d_{O}(x, y) < ϵ in V, which is just what we need to show V is open with respect to d_{O}. Conversely if V ⊂ O is d_{O}-open, x ∈ V, then we can choose some ϵ with the open ball of radius ϵ with respect to d_{O} included in V; and then the continuity of π enables us to find some δ < \frac{ϵ}{2} such that for all y ∈ O with d(x, y) < δ we have

|π(x) − π(y)| < \frac{ϵ}{2},

and thus the ball of radius δ with respect to d is included in V.

And the various facts required for d_{O} to be a metric are trivial to verify. The main issue is completeness.

But if (x_{i})_{i} is a Cauchy sequence in (O, d_{O}) then it will necessarily be d-Cauchy, and so it will have a limit x_{∞} ∈ X. We need to check x_{∞} ∈ O.

But otherwise we obtain

π(x_{i}) → +∞

and hence for all x_{N} on our sequence

|π(x_{N}) − π(x_{i})| → +∞

as i → ∞, contradicting our assumption on the sequence (x_{i})_{i}. □

Definition A subset of a Polish space is G_{δ} if it is given by a countable intersection of open sets.

Some people use Π ∼_{2}^{0} instead of G_{δ}. And in fact this is a better notation, since it forms part of a general scheme to refer to the entire Borel hierarchy, while the

G_{δ}, F_{σ}, G_{δσ}, F_{σδ}, ...

method only extends to the finite levels.

Note that every closed set is G_{δ}. If C ⊂ X is closed, then it equals

⋂_{n∈ℕ}\{x : ∃y ∈ C(d(x, y) ≤ \frac{1}{n})\}.

Corollary Any G_{δ} subset of a Polish space is Polish in the subspace topology. Proof Let X be Polish,

B = ⋂_{i∈ℕ} O_{i}

a G_{δ} subset, where each O_{i} is open, and let d_{i} be a complete metric on O_{i} for i ∈ ℕ.

We may assume each d_{i} is bounded by 1, and then let

d_{B}(x, y) = ∑_{i∈ℕ} 2^{−i}d_{i}(x, y).

□

Lemma For L a countable language, the space Mod(L) equipped with the topology of first order formulas is a Polish space. Proof Let {c_{n}|n ∈ ℕ} be fresh constants and let L̂ = L ∪ {c_{n}|n ∈ ℕ} be the language obtained by adding them to L. Let S be the collection of sentences in L̂. Then

{0, 1}^{S}

in the product topology is naturally homeomorphic to {0, 1}^{ℕ}, and thus Polish.

Let B be the set of f ∈ {0, 1}^{S} such that (a) {φ|f(φ) = 1} is consistent, and

(b) for all φ we have

f(φ) = 0 ⇔ f(¬φ) = 1,

and

(c) for all φ we have

f(∃xφ(x)) ⇔ ∃n ∈ ℕ(f(φ(c_{n})) = 1).

Claim: B is a G_{δ} subset of {0, 1}^{S}.

Proof of Claim: Since countable intersections of G_{δ} sets are G_{δ}, it suffices to show that the conditions (a), (b), and (c) all correspond to G_{δ} sets. This is almost trivially true for (a), since a first order theory is inconsistent if and only if it includes a finite set of set of sentences which are inconsistent; thus if I ⊂ [S]^{<ℕ} is the set of finite inconsistent subset of S then (a) corresponds to the G_{δ} set

⋂_{F ∈I} ⋃_{ψ∈F}{f|f(ψ) = 0}.

Similarly (b) is G_{δ} (and as with (a), it is actually closed).

Finally, (c) corresponds to the conjunction of the sets

⋂_{φ∈S} ⋂_{n∈ℕ}{f|f(φ(c_{n})) = 1 ⇒ f(∃xφ(x)) = 1}

and

⋂_{φ∈S}({f|f(∃xφ(x)) = 0} ∪ ⋃_{n∈ℕ}{f|f(φ(c_{n})) = 1}),

and is thus G_{δ}. (Claim□)

To each M ∈ Mod(L) let T_{M} ∈ {0, 1}^{S} be given by

T_{M}(φ(c_{n_{1}}, c_{n_{2}}, ...)) = 1 ⇔ M ⊧ φ(n_{1}, n_{2}, ...).

It is more or less immediate from the definitions that each such T_{M} is in B.

Claim: The map

Mod(L) → B
M ↦ T_{M}

is a bijection of Mod(L) onto B.

Proof of Claim: The map is obviously one-to-one, since for any M_{1} ≠ M_{2} there will be some atomic ψ(x⃗) and n_{1}, n_{2}, ... on which they disagree, whence T_{M_{1}} and T_{M_{2}} disagree on ψ(c_{n_{1}}, c_{n_{2}}, ...).

As for showing it onto, fix T ∈ B. We define M by the requirements that for any relation R ∈ L

M ⊧ R(n_{1}, n_{2}, ...)

if and only if T (R(c_{n_{1}}, c_{n_{2}}, ...)) = 1, and for any function symbol F ∈ L

F^{M}(n_{1}, n_{2}, ...) = ℓ

if and only if T (F (c_{n_{1}}, c_{n_{2}}, ...) = c_{ℓ}) = 1. (This is well defined. By (a) and (b) we have T (∃x(F (c_{n_{1}}, c_{n_{2}}, ...) = x)) = 1, and then by (c) we have some witness c_{ℓ}.) Then an easy induction on logical complexity shows that for any first order ψ

M ⊧ ψ(n_{1}, n_{2}, ...) ⇔ T (ψ(c_{n_{1}}, c_{n_{2}}, ...)) = 1.
(Claim□)

But this basically finishes the lemma. It follows from the definitions of the topologies that

M ↦ T_{M}

is a homeomorphism. Thus Mod(L) in the topology generated by first order formulas is homeomorphic to B; and we know B must be Polish since it is a G_{δ} subset of a Polish space. □

Up to now I have done the usually sloppy, convenient, but not quite correct thing, and simply identified a topological space with its underlying set. Over the next couple of lemmas we need to be more precise. Thus let us agree to write (X, τ) for a Polish space with underlying set X and topology τ.

Lemma Let (X, τ) be a Polish space and O ⊂ X open. Then there is a new topology τ̂ such that:

(a) τ̂ ⊃ τ;

(b) every τ̂-open set is τ-Borel (and hence the two topologies give rise to the same standard Borel structure);

(c) O is τ̂-clopen. Proof: Let d_{X} be a compatible complete metric on (X, τ). Since O is open we can find a complete metric d_{O} on O which is compatible with its subspace topology from τ. By earlier lemmas we can assume both to be bounded by 1.

Now we can define d on X by cases.

(i) If x, y ∈ O then d(x, y) = d_{O}(x, y). (ii) If x, y ∉ O then d(x, y) = d_{X}(x, y). (iii) If x ∈ O, y ∉ O then d(x, y) = 2. (iii) If x ∉ O, y ∈ O then d(x, y) = 2.

It is as if we have split the space up into two halves, O and X \ O, each a distance of 2 away from the other. Any d-Cauchy sequence must eventually decide to stay in one of these two halves, and hence will be either d_{X} or d_{O} Cauchy. □

Really this proof is using the fact that the disjoint union of two Polish spaces is again Polish.

The next lemma appears to be a folklore result. I am going to give a proof I saw presented by Ramez Sami.

Lemma Let (X, τ) be a Polish space and B ⊂ X Borel. Then there is a richer topology τ̂ ⊃ τ such that:

(a) τ̂ ⊃ τ;

(b) every τ̂-open set is τ-Borel;

(c) B is τ̂-open. Proof: Let C be the collection of all B ⊂ X for which we can find τ̂ satisfying the lemma. We have previously seen that this include all open sets. Then by the structure of the definition we have that it must be closed under complementation – that is to say, if B ∈ C then (X \ B) ∈ C.

Therefore to show it forms a σ-algebra we need only show it is closed under countable intersections. For this the following observation suffices.

Claim: Suppose for each i we have a Polish topology τ_{i} ⊃ τ. Then the union of these topologies generates a Polish topology.

Proof of Claim: Consider the space

∏_{i∈ℕ}(X, τ_{i}).

This is a product of Polish spaces, and hence Polish. As is the closed subset

{x⃗|∀i, j ∈ ℕ(x_{i} = x_{j})}

consisting of all constant sequences.

If we associate to each x ∈ X the sequence with constant value x then we obtain a homeomorphism of X under the topology generated by ⋃_{i∈ℕ} τ_{i} and {x⃗|∀i, j ∈ ℕ(x_{i} = x_{j})} with the subspace topology. (Claim□)

□

Definition A subset P of a Polish space X is perfect if it is (a) non-empty,

(b) closed, and

(c) it has no isolated points – that is to say, if U ⊂ X is open with |U ∩ P | ≥ 1 then we actually have |U ∩ P | ≥ 2.

Lemma If X is an uncountable Polish space, then it contains a perfect set. Proof Let B = {U_{n}|n ∈ ℕ} be a countable basis for X. Then define B_{0} ⊂ B to be the set of {U_{n}|U_{n} ∩ P is countable } and define P to be the elements of X not contained in any element of B_{0}:

P = X \ (⋃ B_{0}).

Since ⋃ B_{0} is a union of open sets, we certainly have that P is closed.

If P is empty, then X is a countable union of countable sets and we have a contradiction.

So instead assume P ≠ ∅, x ∈ P, and we try to show x not isolated.

For this purpose fix open U containing x. After possibly shrinking U we can assume U ∈ B. But then if |U ∩ P | = 1 we would have

|U \ (⋃ B_{0})| = 1

and hence

|U| ≤ | ⋃ B_{0}| + 1 ≤ ℵ_{0} + 1 = ℵ_{0},

which would place U into B_{0}, contradicting x ∈ P. □

It is implicit in this proof that any Polish space without isolated points must contain a perfect subset.

Lemma If P is a perfect subset of a Polish space, then P = |2^{ℵ_{0}}|, and in fact contains a homeomorphic copy of

{0, 1}^{ℕ}

as a closed subset. Proof We first need an observation about the structure of open sets in our perfect set.

Claim: If U is open with U ∩ P ≠ ∅ and ϵ > 0 then there are open V_{0}, V_{1} with:

1. V_{0} ∩ P, V_{1} ∩ P ≠ ∅; 2. \overline{V_{0}}, \overline{V_{1}} ⊂ U;^{6}

3. V_{0} ∩ V_{1} = ∅;

4. d(V_{0}), d(V_{1}) < ϵ.^{7}

Proof of Claim: Since P has no isolated points we may choose x_{0}, x_{1} ∈ U ∩P with x_{0} ≠ x_{1}. Then we may choose sufficiently small open neighborhoods B_{2δ}(x_{0}), B_{2δ}(x_{1}) with:^{8}

1. B_{2δ}(x_{0}), B_{2δ}(x_{1}) ⊂ V;

2. B_{2δ}(x_{0}) ∩ B_{2δ}(x_{1}) = ∅;

3. δ < ϵ.

Then the sets B_{δ}(x_{0}) = V_{0} and B_{δ}(x_{1}) = V_{1} are as in the claim. (Claim □) Claim: There is a collection of open sets indexed by finite binary sequences,

(U_{s})_{s∈{0,1}^{<ℕ}}, such that:

1. U_{s} ∩ P ≠ ∅ all s ∈ {0, 1}^{<ℕ};

2. \overline{U_{s^{⌢}0}}, \overline{U_{s^{⌢}1}} ⊂ U_{s} all s ∈ \{0, 1\}^{<ℕ};^{9}

3. d(U_{s}) < \frac{1}{n} all s ∈ \{0, 1\}^{n};

4. U_{s^{⌢}0} ∩ U_{s^{⌢}1} = ∅ all s ∈ {0, 1}^{<ℕ}.

Proof of Claim: We build (U_{s})_{s∈{0,1}^{≤n}} by induction on n. We can just begin with U_{∅} any sufficiently small open set meeting P.

Given the collection (U_{s})_{s∈{0,1}^{n}} we can choose for each s

U_{s^{⌢}0}, U_{s^{⌢}1} ⊂ U_{s}

as in the last claim for ϵ = \frac{1}{n+1}. (Claim □)

In this way we have obtained a nested collection of open sets whose structure resembles the canonical basis of open sets in the space {0, 1}^{ℕ} of infinite binary sequences. For each f : ℕ → {0, 1} and n ∈ ℕ we let f|_{n} be the binary sequence of length n obtained by restricting f to its first n many values.

Claim: For each f : ℕ → {0, 1} there is x_{f} ∈ P with

x_{f} ∈ ⋂_{n∈ℕ} U_{f|_{n}}.

6\overline{A} indicates the closure of a set A.

7Here and elsewhere I use d(V) to denote the diameter of V, sup{d(x, y) : x, y ∈ V }, where d is some complete metric on our Polish space.

8In general B_{r}(x) denotes the open ball of radius r around x: {y : d(x, y) < r}.

9For s : {0, 1, ..., n − 1} → {0, 1} we use s^{⌢}i to indicate the sequence of length n + 1 obtained by concatenating s with the sequence ⟨i⟩; that is to say, s^{⌢}i extends s, has length equal to length(s) + 1, and assumes i as its final value.

Proof of Claim: We may choose z_{n} ∈ U_{f|_{n}} ∩ P for each n by assumption on our nested collection of open sets. Then we obtain that d(z_{n}, z_{m}) < \frac{1}{n} all m ≥ n since both points are in U_{f|_{n}} and this open set has diameter less than \frac{1}{n}. Thus (z_{n}) must be a Cauchy sequence, which will necessarily converge to some point

z_{∞} ∈ P ∩ ⋂_{n∈ℕ} \overline{U_{f|_{n}}}.

Since \overline{U_{f|_{n+1}}} ⊂ U_{f|_{n}} we obtain x_{f} = z_{∞} is as required. (Claim □) For each such f there will be exactly one x_{f} as in the claim, for any other

x′_{f} ∈ ⋂_{n∈ℕ} U_{f|_{n}}

would have to have d(x_{f}, x′_{f}) < 1/n all n.

Thus f ↦ x_{f} provides some kind of map from the space of infinite binary sequences to P. It is obviously one to one, since if f ≠ f′ then we may let s = f ∩ f′ be the longest initial segment contained in both, and obtain that one of x_{f}, x_{f′} is in U_{s^{⌢}0} and the other is in U_{s^{⌢}1}. The main issue is continuity.

Claim: f ↦ x_{f} is continuous.

Proof of Claim: Let V be an open neighborhood of x_{f}. (We need an open W containing f with {x_{h} : h ∈ W } ⊂ V.) Choose n with B_{1/n}(x_{f}) ⊂ V. Then since any two points y_{0}, y_{1} of U_{f|_{n}} have d(y_{0}, y_{1}) < 1/n we obtain U_{f|_{n}} ⊂ V, and thus for W the open set {h : ℕ → {0, 1}|h ⊃ f|_{n}} we have x_{h} ∈ V all h ∈ W. (Claim □)

Thus

{0, 1}^{ℕ} → P
f ↦ x_{f}

is a continuous function. Since {0, 1}^{ℕ} is compact the map sends closed sets to closed sets. Since it is injective we then have that it sends open sets to sets which are relatively open in its image, and thus it is a homeomorphism onto a closed subset of P.

P is at least as big as the number of subset of ℕ; thus |P | ≥ 2^{ℵ_{0}}. But conversely, P is a Polish space in its own right, and so it has a countable dense subset, D say; and then P is no bigger than the number of Cauchy sequences from D, which gives us the bound

|P | ≤ |D|^{ℕ} ≤ |P(D × ℕ)| = |2^{D×ℕ}| = 2^{ℵ_{0}}.
□

Corollary Any uncountable Borel set has size 2^{ℵ_{0}}. Proof Since we have previously seen that any Borel set allows a Polish topology and any uncountable Polish space contains a perfect subset and hence has cardinality continuum. □

Corollary Any Polish space without isolated points has size 2^{ℵ_{0}}. Proof As remarked above, a Polish space without isolated points must contain a perfect set. □

Thus in particular ℚ in the subspace topology it inherits from ℝ is not a Polish space.

We are yet to see that any two Borel sets of the same cardinality are Borel isomorphic. In light of our lemmas on changing topologies we need only see that any two Polish spaces of the same cardinality are isomorphic as standard Borel spaces. The proof of this is sketched in the exercises below.

Exercises

1. Show that ℕ^{ℕ} is homeomorphic to a G_{δ} subset of {0, 1}^{ℕ}. (Namely, the set of binary sequences with infinitely many 1’s).

2.(a) Show that if X is Polish then we may find a nested collection of sets (V_{s})_{s∈ℕ^{<ℕ}} such that

1. each V_{s} is non-empty and open,

2. \overline{V_{s}} ⊂ V_{t} whenever s strictly extends t,

3. V_{∅} = X,

4. d(V_{s}) < \frac{1}{n} whenever s : \{0, 1, ..., n − 1\} → ℕ, n > 0,

5. each V_{s} equals ⋃_{k∈ℕ} V_{s^{⌢}k}.

(b) Conclude that any Polish space is the continuous, open image of ℕ^{ℕ}.

(c) Show that if X is Polish then there is a Borel B ⊂ ℕ^{ℕ} which is Borel isomorphic to X.

3. Let X_{1}, X_{2} be Polish spaces, B_{1} ⊂ X_{1}, B_{2} ⊂ X_{2} Borel sets, π_{1} : X_{1} → B_{2}, π_{2} : X_{2} → B_{1} Borel isomorphisms.

Show that X_{1} and X_{2} are Borel isomorphic. (Hint: This is close to the proof of Schroeder-Bernstein which does not use choice. You can find that proof in Tom Jech’s Set Theory.)

4. Conclude from 1-3 above and the earlier results about perfect sets that any two uncountable Borel sets are Borel isomorphic.

5. Show that if X is a countable Polish space then any subset is Borel. Thus any function between countable Polish spaces is Borel.

Borel equivalence relation

Definition An equivalence relation E on a Polish space X is Borel if it is Borel as a subset of X × X in the product topological structure. A function

θ : X → Y

between Polish spaces is Borel if θ^{−1}[U] is Borel for any open set U ⊂ Y. (Actually this is equivalent to the graph of θ being Borel as a subset of X × Y, but we are unlikely to need that particular result.)

For E, F equivalence relations on X, Y we write

E ≤_{B} F,

E Borel reducible to F, if there is a Borel θ : X → Y such that for all x_{1}, x_{2} ∈ X

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

We can then go ahead and set E <_{B} F if there is a Borel reduction of E to F but not the other way around, and E ∼_{B} F if there is a Borel reduction in both directions.

Of course there are other notions of comparison we might use for Borel equivalence relations. We might ask that the reduction be one-to-one. Or that it provide a bijection with some invariant Borel subset of the target space. And so on.

Although certainly not the only notion worth investigating, ≤_{B} is the main one studied by descriptive set theorists. It, and its variant, which allow classes of functions more general than Borel, also provides the most generous notion of reduction, and thus the non-reducibility below have the most force if we phrase them for ≤_{B}.

Notation For X a Polish space we let id(X) be the identity relation on X. (Some people use Δ(X) for this relation, which is suggested by it being the diagonal in X × X.)

E_{0} is the equivalence relation of agreement mod finite on {0, 1}^{ℕ}: f_{1}E_{0}f_{2} if

∃N∀m > N(f_{1}(m) = f_{2}(m)).

¿From now on let me just write 2^{ℕ} for the space {0, 1}^{ℕ}. It is a little less cumbersome and formal.

Lemma id(2^{ℕ}) ≤_{B} E_{0}. Proof Let (s_{n})_{n∈ℕ} enumerate the set {0, 1}^{<ℕ} of all finite binary sequences. For each f ∈ 2^{ℕ} we define θ(f) by

(θ(f))(n) = 1 ⇔ s_{n} ⊂ f.

That is to say, (θ(f))(n) = 1 if s_{n} is a substring of f.

This is continuous, since if s_{n} : {0, 1, ..., k − 1} → {0, 1} and (θ(f_{0}))(n) = i (i ∈ {0, 1}), then for any other f in the open set {h : ∀j < k(h(j) = f_{0}(j))} we have (θ(f))(n) = i.

And obviously if f_{1} id(2^{ℕ})f_{2} then by definition f_{1} = f_{2} and so θ(f_{1}) = θ(f_{2}) and they are certainly E_{0} equivalent.

Conversely if f_{1}(k) ≠ f_{2}(k) then for all s_{n} with s_{n} ⊂ f_{1} of length greater than k we have (θ(f_{1}))(n) = 1 while (θ(f_{2}))(n) = 0. □

To show failure of reducibility in the other direction I will use Baire category techniques. The idea here is to approximate Borel functions on some suitably “large” set by continuous functions.

Definition A subset of a space X is nowhere dense if its intersection with any non-empty open subset of X is not dense. A subset is meager if it is included in the countable union of sets which are each closed and nowhere dense. The complement of a meager set is said to be comeager.

Fact The countable unions of meager sets are meager; countable intersections of comeager sets are comeager. The meager sets form a σ-ideal; the comeager sets form a σ-filter.

Some books only state the Baire category theorem for a few specific spaces like the unit interval. The usual proof extends to Polish spaces.

Baire category theorem Any comeager subset of a Polish space is non-empty.

Corollary If X is a Polish space without isolated points then any comeager set is uncountable.

Definition A set A has the Baire property if for some open O the symmetric difference

AΔO = (A \ O) ∪ (O \ A)

is meager.

Lemma Every Borel set has the Baire property. Proof Clearly the open sets have Baire property.

If C is closed then for

C^{o} = ⋃{U : U ⊂ C, U open}

we have that C^{o} is the largest open set included in C and CΔC^{o} = C \ C^{o} is nowhere dense. Thus in general the complement of a set with Baire property has Baire property, since if BΔO is included in a meager set M, and C is the complement of the open set O, then

(X \ B)ΔC^{o} ⊂ M ∪ (C \ C^{o}).

Finally if (B_{i})_{i} is a sequence of Borel sets, (O_{i})_{i} a sequence of open sets with B_{i}ΔO_{i} always meager, then

(⋃_{i∈ℕ} B_{i})Δ(⋃_{i∈ℕ} O_{i})

is included in the countable union of meager sets, and is hence meager in its own right. □

Corollary Any Borel function between Polish spaces is continuous on a comeager set.

That is to say, if θ : X → Y is Borel, then there is a comeager C ⊂ X having θ|_{C} continuous. Proof Let {U_{n}|n ∈ ℕ} be a countable basis of Y. For each n choose open O_{n} ⊂ X with

(θ^{−1}[U_{n}])ΔO_{n} ⊂ M_{n}

for some meager set M_{n}. Let

C = X \ ( ⋃_{n∈ℕ} M_{n}).

Then we have that θ|_{C} pulls basic open sets back to relatively open subsets of C, and thus is continuous. □

Lemma E_{0} is not Borel reducible to id(2^{ℕ}). Proof Instead let θ : 2^{ℕ} → 2^{ℕ} be a Borel reduction. Let C be a comeager set on which θ is continuous.

For each finite binary sequence s ∈ {0, 1}^{<ℕ} define

ψ_{s} : 2^{ℕ} → 2^{ℕ}

by

(ψ_{s}(f))(n) = s(n) + f(n) mod 2

if n is less than the length of s, and equal to f(n) otherwise.^{10} Each ψ_{s} is a homeomorphism, and thus ψ_{s}(C) is again comeager.

Thus we can let

Ĉ = ⋃_{s∈2^{<ℕ}} ψ_{s}[C]

and obtain a comeager set which is invariant under E_{0}, in the sense that it includes any equivalence class it meets, and on which θ is continuous. Now choose f ∈ Ĉ. The E_{0}-equivalence class

[f]_{E_{0}}

10A way to think of this. Identify {0, 1}^{ℕ} with the product group ℤ_{2}^{ℕ} and consider the subgroup G consisting of elements which have finite support. To each finite binary sequence s we can associate a corresponding g_{s} ∈ G and let ψ_{s} be translation by g_{s}.

of f is dense in 2^{ℕ} and included in Ĉ; hence it is dense in Ĉ. θ is constant on [f]_{E_{0}} by the assumption it perform a reduction.

θ|Ĉ is continuous and constant on a dense subset, and therefore it is constant on Ĉ. But this really does give us a contradiction, since Ĉ must be uncountable, and we can choose some

h ∈ Ĉ \ [f]_{E_{0}}

with θ(h) = θ(f). □

Exercises

1. Show that for any two uncountable Polish spaces X and Y we have id(X) ≤_{B} id(Y).

2. Let L be a language consisting of just countably many unary predicates and let F_{2} be the isomorphism relation on Mod(L). Show that E_{0} ≤_{B} F_{2}.

Hence that id(ℝ) <_{B} F_{2}.

The non-reducibility of F_{2} to the identity relation on a Polish space even works for notions of reducibility which allow broader classes of functions. Consistently with ZFC F_{2} is non-reducible to id(ℝ) using “set recursive” or even “ℝ-ordinal definable” functions.^{11} So although this isomorphism relation for countably many unary predicates might seem to be almost trivial from the point of view of model theory, there is already a substantial restriction on the kinds of objects one can hope to assign as complete invariants.

If you want a considerably harder exercise you might try showing that E_{0} <_{B} F_{2}. And at the end of the course perhaps we will have time to discuss the general result that F_{2} is not Borel reducible to any equivalence relation all of whose equivalence classes are countable.

11I only say “consistently with ZFC” since we need to avoid, for instance, certain things which can happen in Gödel’s L as a result of the simply definable well order of ℝ. Certainly with a little bit of forcing one can guarantee all Δ ∼_{2}^{1} sets have Baire property and with quite a lot of forcing one obtains the same for the ℝ-ordinal definable sets.

Infinitary logic

Definition Let L be a language. L_{ω_{1},ω} is obtained by closing the atomic formulas of L under the usual first order operations

(a) ψ ↦ ∃xψ, ψ ↦ ∀xψ,

(b) (ψ, ϕ) ↦ ψ ∨ ϕ, (ψ, ϕ) ↦ ψ ∧ ϕ,
(c) ψ ↦ ¬ψ,

as well as infinitary conjunction and disjunction, (d) whenever {ψ_{i}|i ∈ ℕ} is a countable set of formulas in L_{ω_{1},ω} we have

⋁_{i∈ℕ} ψ_{i} ∈ L_{ω_{1},ω},

⋀_{i∈ℕ} ψ_{i} ∈ L_{ω_{1},ω}.

Definition If M is an L-structure, and φ(x_{1}, x_{2}, ..., x_{k}) is a formula of L_{ω_{1},ω} with just finitely many free variables, then we can define

M ⊧ φ(a_{1}, ..., a_{k})

by induction on the complexity of φ in the usual way. The only clauses which differ from first order logic and the ones corresponding to infinite conjunction and disjunction, and here we stipulate that

M ⊧ ⋀_{i∈ℕ} ψ_{i}

⇔ (∀i ∈ ℕ(M ⊧ ψ_{i})),

and

M ⊧ ⋁_{i∈ℕ} ψ_{i}

⇔ (∃i ∈ ℕ(M ⊧ ψ_{i})).

Technical remarks

(i) The infinite conjunction ⋁_{i∈ℕ} ψ_{i} ∈ L_{ω_{1},ω} and infinite disjunction ⋀_{i∈ℕ} ψ_{i} ∈ L_{ω_{1},ω} depend solely on the set {ψ_{i}|i ∈ ℕ}, and not the particular enumeration (ψ_{i})_{i∈ℕ}.

(ii) I have allowed formulas with infinitely many free variables, but not given any role to them in the satisfaction relation. There seems to be some variation in the literature on this point.

(iii) Later we will need to perform a range of computations with languages and formulas, and for these purposes it will be helpful to adopt some conventions. Firstly that we assume L consists solely of symbols which are themselves hereditarily countable^{12} sets; all our languages will be countable, so this is not overly restrictive. After that we can assume that L_{ω_{1},ω} is a subset of the hereditarily countable sets; for instance we can have as our convention that ⋁ is some fixed hereditarily countable set, such as the number 17, and that

⋁_{i∈ℕ} ψ_{i} = {{ψ_{i}, ⋁} : i ∈ ℕ}.

(iv) I will only use countably many variable symbols. Keisler handles this point somewhat differently.

Definition F ⊂ L_{ω_{1},ω} is a fragment if:

(a) it contains the atomic formulas;

(b) it is closed under the first order operations

ψ ↦ ∃xψ,
ψ ↦ ∀xψ,
(ψ, ϕ) ↦ ψ ∨ ϕ,
(ψ, ϕ) ↦ ψ ∧ ϕ,
ψ ↦ ¬ψ;

(c) it is closed under subformulas, in the sense that

∃xψ ∈ F ⇒ ψ ∈ F,
∀xψ ∈ F ⇒ ψ ∈ F,
ψ ∧ ϕ ∈ F ⇒ ψ, ϕ ∈ F,
ψ ∨ ϕ ∈ F ⇒ ψ, ϕ ∈ F,
¬ψ ∈ F ⇒ ψ ∈ F,

⋀_{i∈ℕ} ψ ∈ F ⇒ {ψ_{i} : i ∈ ℕ} ⊂ F,

⋁_{i∈ℕ} ψ ∈ F ⇒ {ψ_{i} : i ∈ ℕ} ⊂ F;

(d) if φ(x_{1}, x_{2}, x_{3}...) ∈ F and t is a term, then

φ(t, x_{2}, x_{3}, ...) ∈ F.

In this definition of fragment (d) is important for what it does not do. It does not license substitutions which replace infinitely many variables with terms. Otherwise all our fragments would be uncountable.

12A set A is hereditarily countable if it is countable, all its elements are countable, all their elements are countable, and so on. More precisely, HC, the collection of hereditarily countable sets, is the smallest set containing all its countable subsets.

In Ramez Sami’s Polish group actions and the topological Vaught conjecture he uses a somewhat weaker notion of fragment. As it turns out this weaker notion is still sufficient to prove that countable fragments generate Polish topologies, but not quite sufficient for us to obtain a nice characterization of atomic model relative to a given fragment.

Definition For F ⊂ L_{ω_{1},ω} a fragment we let τ_{F} be the topology on Mod(L) whose basis consists of open sets of the form

{M ∈ Mod(L) : M ⊧ φ(n_{1}, n_{2}, ..., n_{k})},

where n_{1}, n_{2}, ..., n_{k} ∈ ℕ and φ(x⃗) ∈ F.

Lemma If F is a countable fragment then (Mod(L), τ_{F}) is a Polish space. Proof This follows our proof for the topology generated by first order logic. We let L̂ be the language obtained by adding fresh constants (c_{n})_{n∈ℕ} to L; and then we obtain F̂ as the fragment generated by F in L̂_{ω_{1},ω}. And parallel to the proof from before we let Ŝ be the set of sentences in F̂.

2Ŝ =_{df} {0, 1}Ŝ

gives us a Polish space, and we can let AŜ be the set of f ∈ 2Ŝ satisfying: (a) any finite subset of {ψ : f(ψ) = 1} is consistent, in the sense that it has some model;

(b) f(ψ) = 1 if and only if f(¬ψ) = 0;

(c) f(∃xψ(x)) = 1 if and only if there is some n with f(ψ(c_{n})) = 1;

(d) f(⋁_{i∈ℕ} ψ_{i}) = 1 if and only if there is some i ∈ ℕ with f(ψ_{i}) = 1. We had to modify (a) a bit, so that it still corresponds to a closed condition.

We also had to add a condition (d), which is G_{δ} by the same calculation we previously used for (c). With these modifications one can show that if we assign to each M ∈ Mod(L) the characteristic function of F -theory of its canonical expansion to a model of L̂, T_{M} where

T_{M}(ψ(c_{n_{1}}, c_{n_{2}}, .., c_{n_{k}})) = 1 ⇔ M ⊧ ψ(n_{1}, n_{2}, ..., n_{k}),

then

(Mod(L), τ_{F}) → AF̂
M ↦ T_{M}

provides a homeomorphism. □

Definition If σ ∈ L_{ω_{1},ω} is a sentence then we let Mod(σ) be the collection of M ∈ Mod(L) satisfying σ; we let F (σ) be the fragment generated by σ, and obtain from the last lemma that Mod(σ) is a Polish space in the subspace topology bequeathed by τ_{F (σ)}.

If F is a countable fragment and T ⊂ F a theory, then we let Mod(T) be the models of T. This is a closed subset of (Mod(L), τ_{F}), and hence a Polish space in the subspace topology.

Definition Given a countable fragment F we can define an n-type over F to be some subset of the F -formulas in free variables x_{1}, x_{2}, ..., x_{n}, and more generally we can define an F -type to be an n-type over F for some for n. A type is F - complete if any ψ(x⃗) ∈ F in the appropriate variables is either in the type or has its negation in F. We then say that a complete type is principal over a complete theory T ⊂ F if it contains some φ(x⃗) such that for all other and for all ψ(x⃗) ∈ F we have either

∀x⃗(φ(x⃗) → ψ(x⃗))

or

∀x⃗(φ(x⃗) → ¬ψ(x⃗)).

Given a model M and a⃗ ∈ M we let the F -type over M be the set of ψ(x⃗) : M ⊧ ψ(a⃗). M omits an F -type if there is no a⃗ which has that type as its F -type over M. For F a fragment Th_{F} (M) is the set of sentences in F satisfied by M. We say that a model M is F -atomic if it realizes no nonprincipal types over Th_{F} (M).

These definitions out of the way, all the usual facts for first order logic generalize easily.

Lemma Let F be a countable fragment, T ⊂ F a complete theory. Any two countable F -atomic models of T are isomorphic.

Lemma Let F be a countable fragment. Let Σ(x_{1}, x_{2}, ..., x_{n}) be a complete non-principal type over F and let k_{1}, k_{2}, ..., k_{n} ∈ ℕ. Let T ⊂ F be a complete theory. Then the set of M ∈ Mod(T) with

M ⊧ Σ(k_{1}, k_{2}, ..., k_{n})

is closed nowhere dense (with respect to τ_{F}).

Corollary (Omitting types theorem) F, T, Σ(x⃗) as above. The set of M in (Mod(T), F) omitting Σ(x⃗) is comeager (in (Mod(T), F)).

Lemma Let F be a countable fragment, T ⊂ F a complete theory, M_{0} ∈ Mod(T). The set of N ∈ (Mod(T), F) isomorphic to M_{0} is comeager if and only if M_{0} is atomic. Proof First suppose that M_{0} is atomic. Then:

Claim: For each n⃗ ∈ ℕ^{<ℕ} the set of N ∈ (Mod(T), F) with n⃗ realizing a principal type is open dense.

Proof of Claim: The set is immediately open by the definition of the topology. To see density, let us consider some non-empty basic open set of the form

V = {N : N ⊧ ψ(n⃗, m⃗)}

where m⃗ ∈ ℕ^{<ℕ} has been chosen to be disjoint from n⃗ and ψ(x⃗, y⃗) ∈ F. Then we can consider the formula

∃y⃗ψ(x⃗, y⃗) ∧ ⋀_{i<lh(x⃗)} ⋀_{j<lh(y⃗)} x_{i} ≠ y_{j}.

Since this is realized by some tuple in some model in our space, and since M_{0} satisfies the complete theory T, we may find some a⃗ ∈ M_{0} with

M_{0} ⊧ ∃y⃗ψ(a⃗, y⃗) ∧ ⋀_{i<lh(x⃗)} ⋀_{j<lh(y⃗)} a_{i} ≠ y_{j}.

We then find some φ(x⃗) with

M_{0} ⊧ φ(a⃗)

witnessing that a⃗ realizes some principal type. But then the set

U = {N : N ⊧ ψ(n⃗, m⃗) ∧ φ(n⃗) ∧ ⋀_{i<lh(x⃗)} ⋀_{j<lh(y⃗)} n_{i} ≠ m_{j}}

is an open subset of V all of whose elements have n⃗ realizing a principal type; to see that this set is non-empty we choose some b⃗ ∈ M_{0} disjoint from a⃗ with M_{0} ⊧ φ(a⃗, b⃗) and some isomorphic copy of M_{0} where n⃗ goes to a⃗ and m⃗ goes to b⃗. (Claim□)

Thus we have that the set of atomic models is comeager, and since any two comeager models are isomorphic we are done.

Conversely, if M_{0} is not atomic, then we can consider some principal complete type Σ(x⃗) realized by M_{0}. By the omitting types theorem the collection of models omitting Σ(x⃗) is comeager. By the Baire category theorem we have that this set intersects any comeager set. □

Lemma Let F be a countable fragment, T ⊂ F a complete theory, M_{0} ∈ Mod(T). If there is no F -atomic model of T then the isomorphism relation is meager as a subset of

(Mod(T), τ_{F}) × (Mod(T), τ_{F}).

Proof It is easily seen that the non-existence of an atomic model is equivalent to the principal types not being dense in the space of n-types for some n. So let us choose some ψ(x⃗) which extends to no principal type. Then we have that for any n⃗, m⃗ the collection U_{m⃗n⃗} of (M, N) with

M ⊧ ψ(m⃗),
N ⊧ ψ(n⃗),

is relatively clopen in the product space; but the subset C_{m⃗,n⃗} consisting of (M, N) over which m⃗ and n⃗ respectively realize the same type is a closed nowhere dense subset of U_{m⃗,n⃗}.

But then we have for any (M, N) in the comeager set

⋂_{m⃗,n⃗}(X \ C_{m⃗,n⃗})

there must, by completeness of T, be some k⃗, ℓ⃗ with

M ⊧ ψ(k⃗),
N ⊧ ψ(ℓ⃗).
□

The above lemma is the main fact we will need about infinitary logic. There is one other result worth mentioning just for comparison. This further result requires another definition.

Definition S_{∞} is the group of all permutations of the natural numbers with topology of pointwise convergence. Thus a basic open set consists of all bijections π : ℕ → ℕ with

∀i < k(π(i) = n_{i}),

for some k, n_{1}, n_{2}, ..., n_{k} ∈ ℕ.

S_{∞} is a topological group, since the group operations are all continuous; it is also G_{δ} as a subset of ℕ^{ℕ}, and hence Polish as a space.

Note that S_{∞} acts continuously and in a canonical fashion on any (Mod(L), L); and moreover its orbit equivalence relation is the isomorphism relation.

Theorem (Becker-Kechris) Let X be a standard Borel space on which S_{∞} acts in a Borel manner^{13}. Then there is some countable L and sentence σ ∈ L_{ω_{1},ω} and Borel isomorphism

θ : X → Mod(σ)

intertwining the actions – that is to say, for all π ∈ S_{∞} and x ∈ X

π · θ(x) = θ(π · x).

Exercises

1. Show that if T is a complete theory for the countable fragment F then every isomorphism type in Mod(T) is dense. That is to say, if M ∈ Mod(T), then the set of N ∈ Mod(T) with

M ≅ N

13I.e. the map

(π, x) ↦ π · x, S_{∞} × X → X is Borel

is dense relative to τ_{F}.

2. T, F as above. Show that if the isomorphism type of M is G_{δ}, then it is comeager; and moreover if M is atomic then its isomorphism type is G_{δ}.

3. T, F as above. Show that canonical action of S_{∞} on (Mod(T), τ_{F}) is continuous.

4. T, F as above. For M ∈ (Mod(T), τ_{F}) we have that the induced map

S_{∞} → {N ∈ Mod(T) : N ≅ M}
π ↦ π · M

is open if and only if M is F -atomic.

5. Conclude that for T, F as above the following are equivalent for M ∈ (Mod(T), τ_{F}):

(a) M is atomic;

(b) the isomorphism type of M is comeager;

(c) the isomorphism type of M is G_{δ};

(d) the map π ↦ π · M is open as a map to the isomorphism type of M.

For an arbitrary continuous action of a Polish group G on a Polish space Ed Effros has shown that an orbit [x] is G_{δ} if and only if it is comeager in its closure, if and only if the natural map g ↦ g · x is open.

Scott’s analysis

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

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

by induction on the ordinal α.

φ_{0}^{a⃗,M} = ⋀{ψ(x⃗) : ψ(x⃗) quantifier free, M ⊧ ψ(a⃗)}

φ_{α+1}^{a⃗,M} = φ_{α}^{a⃗,M} ⋀{∃y⃗φ_{α}^{a⃗b⃗,M}(x⃗, y⃗) : b⃗ ∈ M^{<ℕ}}∧

⋀_{n∈ℕ} ∀y_{0}, y_{1}, ..., y_{n} ⋁{φ_{α}^{a⃗b⃗,M}(x⃗, y⃗) : b⃗ ∈ M^{n+1}}.

For λ a limit we set

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

Note then that if M is a countable model of a countable language L then we have for each α < ω_{1} and a⃗ ∈ M

φ_{α}^{a⃗,M} ∈ L_{ω_{1},ω}.

For α < β

M ⊧ φ_{β}^{a⃗,M} = φ_{β}^{b⃗,M} ⇒ φ_{α}^{a⃗,M} = φ_{α}^{b⃗,M}.

Thus:

Lemma: For M, L countable there will be an ordinal δ < ω_{1} such that for all a⃗, b⃗ ∈ M

∃γ < ω_{1}(φ_{γ}^{a⃗,M} ≠ φ_{γ}^{b⃗,M}) ⇔ φ_{δ}^{a⃗,M} ≠ φ_{δ}^{b⃗,M}.

In general such an ordinal δ with the property that

∀a⃗, b⃗ ∈ M(∃γ(φ_{γ}^{a⃗,M} ≠ φ_{γ}^{b⃗,M}) ⇔ (φ_{δ}^{a⃗,M} ≠ φ_{δ}^{b⃗,M}))

will be guaranteed to exist by replacement, as we may take the supremum over a⃗, b⃗ ∈ M of the least α (when it exists) with

φ_{α}^{a⃗,M} ≠ φ_{α}^{b⃗,M}.

However it may be uncountable. For instance taking the usual ordering on ordinals, the Scott height of the structure

(ω_{1}, <) is itself ω_{1}.

Definition For M a countable model the least δ as in the last lemma is the Scott height of M, and will be denoted by α(M).

φ_{α(M)+2}^{∅,M} =_{df} φ^{M}

is the (canonical) Scott sentence of M;

φ_{α(M)+2}^{a⃗,M} =_{df} φ^{a⃗,M}

(or just φa⃗ when context indicates M) is the Scott sentence of a⃗ (in M); each φ_{α}^{a⃗,M} is the αth approximation of the Scott sentence for a⃗ or the canonical α-type of a⃗.

Note that if a⃗, b⃗ ∈ M with

φ_{α(M)}^{a⃗,M} = φ_{α(M)}^{b⃗,M}

then it follows from the definition of α(M) that in particular we must have

φ_{α(M)+1}^{a⃗,M} = φ_{α(M)+1}^{b⃗,M}.

Lemma If φ_{β}^{a⃗,M} ≠ φ_{β}^{b⃗,M} then in any other model N

N ⊧ ∀x⃗(φ_{β}^{a⃗,M}(x⃗) ⇒ ¬φ_{β}^{b⃗,M}(x⃗)).

Proof We prove this by induction on β. It is obvious for β = 0 and the passage through limits follows trivially from the structure of the definition.

For the inductive step, assume the lemma is true at β and without loss that

N ⊧ φ_{β+1}^{a⃗,M}(c⃗)

and that there is some d⃗ ∈ M with

∀e⃗ ∈ M(φ_{β}^{a⃗d⃗,M} ≠ φ_{β}^{b⃗e⃗,M}).

Then we may find some f⃗ ∈ N with

N ⊧ φ_{β}^{a⃗d⃗}(c⃗, f⃗),

and hence for all e⃗ ∈ M we have

N ⊧ ¬φ_{β}^{b⃗e⃗,M}(c⃗, f⃗).
□

Theorem (Scott) Any two countable models satisfying the same Scott sentence are isomorphic. Proof Let M, N be countable models with

N ⊧ φ^{M}.

Fix some ordinal α = α(M) as the Scott height of M.

Claim: For all a⃗ ∈ N, b⃗ ∈ M

N ⊧ φ_{α}^{b⃗,M}(a⃗)

implies that

N ⊧ φ_{α+1}^{b⃗,M}(a⃗).

Proof of Claim: Otherwise from the assumption that N satisfies the Scott sentence of M we have

N ⊧ ∀x⃗ ⋁_{c⃗∈M} φ_{α+1}^{c⃗,M}(x⃗)

we may find some c⃗ ∈ M with

N ⊧ φ_{α+1}^{c⃗,M}(a⃗)
∴ N ⊧ φ_{α}^{c⃗,M}(a⃗)

and so by the last lemma we must have

φ_{α}^{c⃗,m} = φ_{α}^{b⃗,M}
∴ M ⊧ φ_{α}^{c⃗,M}(b⃗)

but by the assumption the claim fails

M ⊧ ¬φ_{α+1}^{c⃗,M}(b⃗),

with a contradiction to α being the Scott height of M. (Claim□)

But now we can just go ahead the usual back and forth kind of argument. We can define a sequence

a_{0}, a_{1}, a_{2}, ... ∈ M,
b_{0}, b_{1}, b_{2}, ... ∈ N ,

with at each k

N ⊧ φ_{α}^{⟨a_{0},a_{1},...,a_{k}⟩,M}(b_{0}, b_{1}, ..., b_{k})

and under some fixed enumerations of the two models we have that the i^{th} element of M appears among {a_{0}, a_{1}, ..., a_{2i}} and the i^{th} element of N appears among the {b_{0}, b_{1}, ..., b_{2i+1}}. We are able to propagate this construction since the claim above in particular implies that if M ⊧ φ_{α}^{b⃗,N} (a⃗) and d ∈ N then

M ⊧ ∃yφ_{α}^{b⃗^{⌢}d,N} (a⃗, y),

which is the same as saying there is some d′ ∈ M with

M ⊧ φ_{α}^{b⃗^{⌢}d,N} (a⃗, d′).
□

This was all proved because Dana Scott wanted to show:

Corollary The isomorphism type of any countable model is Borel in Mod(L).

It has previously been shown that the isomomorphism type of any countable ordinal is Borel in Mod({<}); indeed it is a nice exercise to prove this by induction on the ordinal, without any appeal to the Scott analysis. With this result in mind Kuratowski had asked whether the isomorphism type of any countable structure was Borel, which in turn was explicitly answered as above.

Exercises

1. F a countable fragment and T an F -complete theory. The isomorphism type of any M ∈ (Mod(T), τ_{F}) has Baire property and is non-meager if and only if it is comeager.

2. Let L be a countable language and (F_{α})_{α∈ω_{1}} be an increasing sequence of countable fragments in L_{ω_{1},ω}. Suppose M ∈ Mod(L) is fortunate enough that for each α and a⃗ ∈ M there is some ψ(x⃗) ∈ F_{α+1} such that

M ⊧ ψ(a⃗)

M ⊧ ∀x⃗∀y⃗ ⋀_{φ∈F_{α}}(ψ(x⃗) ∧ ψ(y⃗) ⇒ (φ(x⃗) ⇔ φ(y⃗)));

in other words, for each a⃗ there is some formula in F_{α+1} satisfied by a⃗ which “isolates its type over F_{α}”.

Then show that there is some countable γ < ω_{1} with M atomic relative to the fragment F_{γ} and the theory Th_{F_{γ}} (M).

3. Show that if δ is the Scott height of a countable model then we have for all ordinals γ

φ_{γ}^{a⃗,M} ≠ φ_{γ}^{b⃗,M} ⇒ φ_{δ}^{a⃗,M} ≠ φ_{δ}^{b⃗,M}.

4. (a) Show that if T ⊂ F is a complete theory then

{φ_{0}^{a⃗,M} : M ⊧ T, a⃗ ∈ M}

is a Borel set in some standard Borel structure; and hence has size continuum or ≤ ℵ_{0}.

(b) Show that if σ is sentence appearing in some fragment F then the collection of countable complete “consistent”^{14} T ⊂ F containing σ is a Borel set.

(c) Conclude that for any σ ∈ L_{ω_{1},ω}

{φ_{0}^{a⃗,M} : M ⊧ σ, a⃗ ∈ M}

is either countable or has cardinality 2^{ℵ_{0}}.

(d) Iterating the argument of (a)-(c) show that for any σ ∈ L_{ω_{1},ω} and α < ω_{1}

{φ_{α}^{a⃗,M} : M ⊧ σ, a⃗ ∈ M}

is either countable or has cardinality 2^{ℵ_{0}}.

(e) (“Morley’s lemma”) Show that if σ has less than continuum many nonisomorphic countable models then it has ≤ ℵ_{1} many non-isomorphic countable models.

Actually the proof of the main theorem we are heading towards parallels the above argument due to Morley. There again is a kind of transfinite induction, where the failure at each level for their being “lots of models” gives us the ability to perform one further step of the analysis.

In Morley’s lemma “lots of models” corresponds to 2^{ℵ_{0}} many countable models; and the technical tool used at each step is the perfect set theorem for Borel sets. In our setting the “lots of models” case will correspond to an embedding of E_{0} and the central technical device is a version of Glimm-Effros due to Becker and Kechris.

14Of course I have been trying to avoid use of this word in the context of infinitary model theory. Here I mean that the theory has some model.

Glimm-Effros

Theorem (Becker-Kechris) Let E be an equivalence relation on a Polish space X and let G be a group acting by homeomorphisms on X. Then assuming

(a) E is meager as a subset of X × X, and

(b) for all g ∈ G, x ∈ X we have

g · xEx

(that is to say, the orbit equivalence relation induced by G is included in E), and

(c) there is some x_{0} ∈ X with [x_{0}]_{G} =_{df} {g · x_{0}|g ∈ G} dense, then

E_{0} ≤_{B} E.

Proof Fix a complete metric d on X and a point x_{0} ∈ X whose orbit under the action of G is dense. Let (F_{n})_{n∈ℕ} be a countable sequence of closed nowhere dense subsets of X × X with

E ⊂ ⋃_{n∈ℕ} F_{n}.

The theorem is proved by a construction. We build a sequence of non-empty open sets (V_{s})_{s∈2^{<ℕ}} in X and an array of group elements {(g_{s,t})_{s,t∈{0,1}^{n}} : n ∈ ℕ} such that:

(i) for s : {0, 1..., n − 1} → {0, 1} we have

d(V_{s}) < \frac{1}{n};

(ii)

V_{s} ⊂ V_{t}

for s ⊃ t and moreover

\overline{V_{s}} ⊂ V_{t}

if t ⊊ s; (iiia) for s, t ∈ 2^{n} and u ∈ 2^{<ℕ} we have

g_{s,t} · V_{s^{⌢}u} = V_{t^{⌢}u};

(iiib) and in fact if 0 is the sequence of all zeroes of length n and s, t ∈ 2^{n} then we have g_{s,t} = g_{0,t} ∘ g_{0,s}^{−1}; (iiic) for s, t ∈ 2^{n} and u ∈ 2^{<ℕ} we have

g_{s,t} = g_{s^{⌢}u,t^{⌢}u};

(iv) for s, t ∈ 2^{n} with s ≠ t we have

V_{s} × V_{t} ∩ ( ⋃_{m≤n} F_{m}) = ∅.

If we succeed in doing all this, then the theorem follows quickly. We define for each f ∈ 2^{ℕ} a corresponding

x_{f} ∈ ⋃_{n∈ℕ} V_{f|_{n}}.

There will be a unique such point x_{f} in the infinite intersection by (i) and (ii); and then by the nature of the construction we have

f ↦ x_{f}

as a Borel, in fact continuous, map. ¿From (iiia) we have that if N ∈ ℕ is the largest integer with f_{1}(N − 1) ≠ f_{2}(N − 1) then

g_{f_{1}|_{N} ,f_{2}|_{N}} · x_{f_{1}} = x_{f_{2}}

and thus

x_{f_{1}}E_{0}x_{f_{2}}.

(iv) moreover yields that if there are infinitely many n with f_{1}(n) ≠ f_{2}(n) then there are infinitely many n with

(x_{f_{1}}, x_{f_{2}}) ∉ ⋃_{m≤n} F_{n},

and so

(x_{f_{1}}, x_{f_{2}}) ∉ E ⊂ ⋃_{n∈ℕ} F_{n}.

So let us now concentrate on showing that some such sequence of open sets and array of group elements has been produced. We do it by induction on lh(s), and for this purpose assume that (V_{s})_{s∈2^{≤n}} and {(g_{s,t})_{s,t∈{0,1}^{m}} : m ≤ n} have the properties indicated above. We will begin by refining the open set V0, where 0 is the sequence of length n which takes zero as its value on each coordinate.

Remember that the group G is acting by homeomorphisms, and so

{(x, y) : (g · x, h · y) ∈ F }

is closed nowhere dense for any g, h ∈ G and closed nowhere dense F ⊂ X × X. Moreover the finite union of closed nowhere dense sets is again closed nowhere dense.

Thus we may chose some open non-empty W, W′ ⊂ V0 such that for all g, h ∈ {(g_{s,t})_{s,t∈{0,1}^{m}} : m ≤ n}

g · W × h · W′ ∩ ( ⋃_{m≤n+1} F_{m}) = ∅.

After further refinement we may assume that

d(g · W), d(g · W′) < \frac{1}{n + 1}

and

\overline{g_{0,s} · W} , \overline{g_{0,s} · W′} ⊂ V_{s}

all s ∈ 2^{n}.

Then since [x_{0}]_{G} is dense we may choose

x ∈ W ∩ [x_{0}]_{G},
x′ ∈ W′ ∩ [x_{0}]_{G}.

In particular there will be some h_{0} ∈ G with

h_{0} · x = x′.

Since G acts by homeomorphisms we may find V_{0^{⌢}0} ⊂ W, V_{0^{⌢}1} ⊂ W′ with

h_{0} · V_{0^{⌢}0} = V_{0^{⌢}1}.

At this stage we can finish up with

V_{s^{⌢}0} = g_{0,s} · V_{0^{⌢}0},
V_{s^{⌢}1} = g_{0,s}h_{0} · V_{0^{⌢}0} = g_{0,s} · V_{0^{⌢}1},
g_{0^{⌢}0,s^{⌢}1} = g_{0,s} ∘ h_{0},

for s ∈ 2^{n}. The decisions

g_{0^{⌢}0,s^{⌢}0} = g_{0,s}
g_{s^{⌢}i,t^{⌢}i} = g_{s,t}

all s, t ∈ 2^{n}, i ∈ {0, 1} are forced on us by (iiib) and (iiic). Taking

g_{s^{⌢}0,t^{⌢}1} = g_{0,t} ∘ h_{0} ∘ g_{0,s}^{−1}

and

g_{s^{⌢}1,t^{⌢}0} = g_{t^{⌢}0,s^{⌢}1}^{−1}

provides us with the full armory of group elements to go up to n + 1. □

Corollary Let F ⊂ L_{ω_{1},ω} be a countable fragment, T ⊂ F a complete theory. Then either

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

or there is an F -atomic model. Proof Completeness of the theory gives that every isomorphism type is dense in (Mod(T), τ_{F}). The orbit equivalence relation is induced by a continuous action of the infinite symmetric group, S_{∞}, and so we can use the previous lemma to conclude that either

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

or the orbit equivalence relation is not meager; and in this later case we saw two sections ago that we must have an atomic model. □

Definition A topological group^{15} is a Polish group if it is Polish as a topological space.

Exercises

1. Let G be a Polish group acting continuously on a Polish space X. Show that there is a Borel function

θ : X → ℝ

such that θ(x_{1}) = θ(x_{2}) if and only if the orbits of x_{1} and x_{2} have the same closure.

2. Let G be a locally compact Polish group acting continuously on a Polish space X with orbit equivalence relation E_{G}.

(a) Show that E_{G} is F_{σ} as a subset of X × X.

(b) Show that if there is dense orbit then it must contain an open set.

(c) Show that in general, even without a dense orbit, we have either

E_{G} ≤ id(ℝ)

or

E_{0} ≤_{B} E_{G}.

15That is to say, a group equipped with a topology under which the group operations of multiplication and inversion are continuous.

Final theorem

Definition HC denotes the collection of hereditarily countable sets. A formula ψ(x⃗) in the language of set theory is Σ_{0} if the only quantifiers appearing are the bounded quantifiers

∀x ∈ y
∃x ∈ y.

A subset A ⊂ HC is said to be Σ ∼_{1}^{HC} if there is some Σ_{0} formula ψ and parameter a ∈ HC such that A equals the set of b ∈ HC for which

(HC, ∈) ⊧ ∃xψ(a, b, x).

D ⊂ HC is Δ ∼_{1}^{HC} if both it and its complement are Σ ∼_{1}^{HC}. I will say that a function is Δ ∼_{1}^{HC} if its graph and domain are both Δ ∼_{1}^{HC}.

It will be convenient to phrase the next result in terms of Δ ∼_{1}^{HC} reductions; but I will skip over any detailed verifications about certain functions and sets appearing in the definition being Δ ∼_{1}^{HC}. Instead here are some facts without proof. For many of these facts there are similar facts with similar proofs holding for the recursive functions.

Facts 1. Ordinal addition, multiplication, and exponentiation are Δ ∼_{1}^{HC}.

2. If

G : ω_{1} × HC → HC
H : HC → HC

Δ ∼_{1}^{HC}, then so is the function defined recursively by

F (α + 1) = H(G(α, F (α)))

and

F (λ) = ⋃{F (α) : α < λ}

when λ a limit.

3. For a ∈ HC

α ↦ L_{α}(a)

is Δ ∼_{1}^{HC}, where we here use L_{α}(a) to denote the α^{th} level of the constructible hierarchy built over a.

4. The Δ ∼_{1}^{HC} recursive functions are closed under μ-recursion with respect to the ordinals. Thus if for each z ∈ HC there exists α < ω_{1} with

L_{α}(z, a) ⊧ ψ(a, z),

then the function assigning to each z the least such α is Δ ∼_{1}^{HC}.

5. Given L a countable language, there is a Δ ∼_{1}^{HC} function assigning to each M ∈ Mod(T) and countable fragment F ⊂ L_{ω_{1},ω} the theory of M in that fragment.

6. Every set recursive function (in the sense of Garvin Melles) is Δ ∼_{1}^{HC}; and in fact the theorem below could equally be phrased in terms of set recursive functions instead of Δ ∼_{1}^{HC}.

Theorem Let L be a countable language and σ ∈ L_{ω_{1},ω}. Then either (I) E_{0} ≤_{B}≅|_{Mod(σ)}; or (II) there is a Δ ∼_{1}^{HC} function

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

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

M ≅ N ⇔ θ(M) = θ(N).

In other words, ≅ |_{Mod(σ)} is either as complicated as E_{0} or allows a Δ ∼_{1}^{HC} assignment of bounded subset of ℵ_{1} as complete invariants. Proof Assume E_{0} is not Borel reducible to ≅|_{Mod(σ)}; by the corollary to Becker-Kechris this will ensure that we have many atomic models, no matter which fragment we choose to consider.

First fix a fragment F_{0} containing σ. For each α < ω_{1} and positive integer n let P_{α,n} be a new n-ary relation; we can do this so that

(α, n) ↦ P_{α,n}

is a Δ ∼_{1}^{HC} function. We let L^{α} be the language generated by L and {P_{β,n} : n > 0, β < α} and we let F_{α} ⊂ L_{ω_{1},ω}^{α} be the fragment generated by F_{0} and all formulas of the form

⋁_{{β:γ≤β<γ′}} P_{β,n}(x⃗)

for γ < γ′ ≤ α. We may simultaneously fix a Δ ∼_{1}^{HC} increasing sequence of ordinals,

(γ_{α})_{α∈ω_{1}}

and bijections

π_{α} : γ_{α} → F_{α}

which are uniformly Δ ∼_{1}^{HC}, in the sense that

(α, β) ↦ π_{α}(β)

is a Δ ∼_{1}^{HC} function.

Fix M ∈ Mod(σ). We describe a a sequence of expansions

M_{0} = M, M_{1}, ⋯, M_{α} ⋯

out through the ordinals, the isomorphism type of each M_{α} depending only on the isomorphism type of M and each M_{α} an L^{α}-structure; at each α we let T_{α}^{M} be the theory of M_{α} with respect to the fragment F_{α}.

Thus in particular we begin with

T_{0}^{M} = Th_{F} (M),

the theory of M with respect to F.

Claim: T_{0}^{M} has an atomic model.

Proof of Claim: Or else Becker-Kechris gives

E_{0} ≤_{B}≅|_{Mod(T_{0}^{M})},
∴ E_{0} ≤_{B}≅|_{Mod(σ)}.
(□Claim)

We then define M_{1} to be the expansion of M to L^{1} as follows. For each a_{1}, a_{2}, ..., a_{n} ∈ M we let

M_{1} ⊧ P_{0,n}(a⃗)

if and only if a⃗ realizes a principal type relative to the theory T_{M}^{0}. Then we let T_{1}^{M} be the theory of M_{1} relative to the fragment F_{1}.

And we can keep going in the obvious way. We let

T_{α}^{M} = Th_{F_{α}}(M_{α});

M_{α+1} is the expansion to L^{α+1} obtained by letting

M_{α+1} ⊧ P_{α,n}(a⃗)

if lh(a⃗) = n and a⃗ realizes a principal type over the theory T_{α}^{M}. At limit stages we can let M_{λ} be the unique model in the language

L^{λ} = ⋃_{α<λ} L^{α}

which expands the all the preceding

{M_{α} : α < λ}.

One possibility is that regardless of our particular choice of M we always arrive at some F_{κ} with M_{κ} the T_{κ}^{M}-atomic model for F_{κ}. Then we are done. We can just let κ(M) be the first such κ for M and let

θ(M) = {β < γ_{κ(M)} : M_{κ(M)} ⊧ π_{κ(M)}(β)} ∪ {γ_{κ(M)}}

to obtain an invariant which indicates to us γ_{κ(M)}, and hence κ(M), and hence the fragment F_{κ(M)}, as well as the theory T_{κ(M)}^{M} and the fact that M_{κ(M)} is atomic with respect to this theory; since each complete countable theory has at most one atomic model up to isomorphism, the invariant indicates the isomorphism type of M_{κ(M)}; since M_{κ(M)} is up to isomorphism an invariant of M, we obtain that θ(M) is a complete invariant for the isomorphism type of M. And finally in this case it would be routine to establish that the association

M ↦ θ(M)

is Δ ∼_{1}^{HC}.

So instead let us try to show that some such ordinal κ(M) always exists. And for this let us assume that M is a counterexample and try to derive a contradiction.

Claim: For each n > 0 and δ < ω_{1} there is a larger countable ordinal δ′ > δ such that for each a_{1}, a_{2}, ..., a_{n} ∈ M

M_{δ′} ⊧ ⋁_{α∈[δ,δ′)} P_{α,n}(a⃗).

Proof of Claim: Instead we obtain that each δ′

M_{δ′} ⊧ ∃x⃗ ⋀_{α∈[δ,δ′)} ¬P_{α,n}(x⃗).

Since T_{δ}^{M} has an atomic model, by Becker-Kechris, we obtain some principal type refining the type

⋀_{α∈[δ,δ′)} ¬P_{α,n}(x⃗),

and thus by the nature of our construction some a^{δ′} with

M_{δ′+1} ⊧ P_{δ′}(a^{δ′}) ⋀_{α∈[δ,δ′)} ¬P_{α,n}(a^{δ′});

but then

δ′ ↦ a^{δ′}

gives us ℵ_{1} distinct n-tuples in M, with an obvious contradiction to its countability. (Claim□)

Thus by repeated application of this claim we can find an increasing sequence of ordinals,

(δ_{α})_{α<ω_{1}},

such that for each α ∈ ω_{1}, n > 0, a⃗ ∈ M^{n} there is some

β > ⋃_{α′<α} δ_{α′}

with β ≤ δ_{α} and

M_{δ_{α}} ⊧ P_{β,n}(a⃗).

We may also fix for each β < ω_{1} and n > 0 a sequence of formulas (ψ_{β,n}^{m})_{m} such that

M_{β+1} ⊧ ∀x_{1}, x_{2}, ..., x_{n}(P_{β,n}(x⃗) ⇔ ⋁_{m∈ℕ} ψ_{β,n}^{m}(x⃗))

and each ψ_{β,n}^{m}(x⃗) ∈ F_{β} defines a principal type over T_{β}^{M}. Unfortunately the disjunction ⋁_{m∈ℕ} ψ_{β,n}^{m}(x⃗) has not been placed in any of our fragments, so we need to observe that the equivalence

N ⊧ ∀x_{1}, x_{2}, ..., x_{n}(P_{β,n}(x⃗) ⇔ ⋁_{m∈ℕ} ψ_{β,n}^{m}(x⃗))

holds for any sufficiently “generic” N in the space of T_{β}^{M} models, for any α > β.

Claim: For each n > 0, a⃗ ∈ ℕ^{n} and β < α, the set of

N ∈ (Mod(T_{α}^{M}), τ_{F_{α}^{M}})

with

N ⊧ P_{β,n}(a⃗) ⇔ ⋁_{m∈ℕ} ψ_{β,n}^{m}(a⃗)

is open dense.

Proof of Claim: It is a straight calculation to determine that the set of such N is open. For density we use that the isomorphism type of M_{α} is dense in (Mod(T_{α}^{M}, τ_{F_{α}^{M}}) and

M_{β} ⊧ ∀x_{1}, x_{2}, ..., x_{n}(P_{β,n}(x⃗) ⇔ ⋁_{m∈ℕ} ψ_{β,n}^{m}(x⃗)).

(Claim□)

Thus for each α there is a comeager set

C_{α} ⊂ (Mod(T_{α}^{M}), τ_{F_{α}^{M}})

such that for all β < α, n > 0, N ∈ C_{α}

N ⊧ ∀x_{1}, x_{2}, ..., x_{n}(P_{β,n}(x⃗) ⇔ ⋁_{m∈ℕ} ψ_{β,n}^{m}(x⃗)).

In the next claim I will use N|_{L} to indicate the reduction of some L^{α} model to our base language L. As usual,

φ_{κ}^{ℓ⃗,N|_{L}}

will indicate the κ^{th} approximation to the Scott sentence of ℓ⃗ over N|_{L}.

Claim: For each N ∈ C_{α}, δ_{κ} ≤ β < α < ω_{1}, n > 0, m ∈ ℕ, ℓ⃗, k⃗ ∈ ℕ^{n} we have that if

M_{α} ⊧ ψ_{β,n}^{m}(k⃗)

and

N ⊧ ψ_{β,n}^{m}(ℓ⃗)

then

φ_{κ}^{ℓ⃗,N|_{L}} = φ_{κ}^{k⃗,M}.

Proof of Claim: We prove this by induction on κ. It should be clear for κ = 0, since ψ_{β,n}^{m} ∈ F_{0} defines a principal type over F_{0}, and thus is sufficient to decide the quantifier free type, even if N does not belong to our comeager set C_{α}. The limit steps follow almost vacuously from the structure of the Scott analysis and its requirement that we take conjunctions at limit stages.

For successor steps, let us suppose δ_{κ+1} ≤ β < α < ω_{1},

M_{α} ⊧ ψ_{β,n}^{m}(k⃗),

and

N ⊧ ψ_{β,n}^{m}(ℓ⃗).

Choose some a⃗ ∈ N; we need to show that there is some other b⃗ ∈ M with

φ_{κ}^{ℓ⃗a⃗,N|_{L}} = φ_{κ}^{k⃗b⃗,M}.

But since N and M_{β} realize the same the theory it must be the case that there

N ⊧ ∀x_{1}, ..., x_{n} ⋁_{{β′:γ_{κ}≤β′<γ_{κ+1}}} P_{β′,n}(x⃗),

and thus in particular for some β′ ∈ [γ_{κ}, γ_{κ+1}) and n′ = lh(ℓ⃗) + lh(a⃗) we have

N ⊧ P_{β′,n′}(ℓ⃗, a⃗);

then by assumption on N ∈ C_{α} we have some m′ with

N ⊧ ψ_{β′,n′}^{m′}(ℓ⃗, a⃗);

then since ψ_{β,n}^{m} decides the type of k⃗ over the fragment F_{β′} we have

M_{α} ⊧ ∃y⃗ψ_{β′,n′}^{m′}(k⃗, y⃗);

and so for some b⃗

M_{α} ⊧ ∃y⃗ψ_{β′,n′}^{m′}(k⃗, k⃗)

and so by the inductive assumption

φ_{κ}^{ℓ⃗a⃗,N|_{L}} = φ_{κ}^{k⃗b⃗,M}.

The converse direction is that for all b⃗ ∈ M there is a⃗ ∈ N with φ_{κ}^{ℓ⃗a⃗,N|_{L}} = φ_{κ}^{k⃗b⃗,M}. This is similar, but only easier. (Claim□)

Thus we obtain in particular that for any α > α(M) + 2 and N ∈ C_{α}

φ_{α(M)+2}^{∅,N|_{L}} = φ_{α(M)+2}^{∅,M},

and thus by Scott’s theorem

N|_{L} ≅ M;

but then it follows from the definition of the various M_{β}’s that the isomorphism from N|_{L} to M lifts to one from N to M_{β} for each β < α.

Thus the isomorphism type of M_{α} will be comeager in some

(Mod(T_{α}^{M}), τ_{F_{α}^{M}});

and thus M_{α} will be atomic, and so the process must have terminated at some stage after all. □.

In general this theorem can be improved by slightly sharpening the reduction to one that is provably or absolutely Δ ∼_{1}^{HC}; these complexity classes are a little technical to define^{16}, but have the advantage of being just inside the region for which ZFC alone can prove regularity properties, such as any absolutely Δ ∼_{1}^{HC} function between Polish spaces is continuous on a comeager set. In this sharper form the theorem would then become a dichotomy theorem: (I) and a suitably amended version of (II) would be incompatible.

A respect in which the theorem cannot be sharpened is with regards to the kinds of invariants we obtain in (II). For instance we cannot ask that we have say elements of 2^{ℕ} being assigned as complete invariants. The isomorphism relation on abelian p-groups provides a counterexample under suitable set theoretical assumptions for general Δ ∼_{1}^{HC} functions and outright in ZFC for the absolutely Δ ∼_{1}^{HC}.

However this class is not first order definable, so I don’t know whether one might hope to prove that for any first order theory T we have either have

(I) E_{0} ≤_{B}≅|_{Mod(T)}, or
(II’) ≅|_{Mod(T)} ≤_{B} id(2^{ℕ}).

Even showing this with (II’) replaced by

(II”) there is a Δ ∼_{1}^{HC} assignment of elements of 2^{ℕ} as complete invariants.

would be extremely interesting, and sufficient to prove Vaught’s conjecture under large cardinal assumptions, or even prove Vaught’s conjecture outright in ZFC if, as most likely, one could obtain

(II^{∗}) there is an absolutely Δ ∼_{1}^{HC} assignment of elements of 2^{ℕ} as complete invariants.

16See e.g. Classification and orbit equivalence relations, G. Hjorth, AMS, Rhode Island, 2000 for the precise definitions

More reading

There is always more to read, but in this case especially there are a number of issues we only touched on which could have been discussed at length.

The canonical references for the descriptive set theory of group actions connections with the isomorphism relation on countable models are

H. Becker, A.S. Kechris, The descriptive set theory of Polish group actions, London Mathematical Society Lecture Notes Series, 232, Cambridge University Press, Cambridge, 1996

and

R. Sami, The topological Vaught conjecture, Transactions of the American Mathematical Society, vol. 341(1994), pp. 335-353.

The serious mathematical discussion of dichotomy theorems for Borel equivalence relations was initiated in

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.

A more recent survey is given by

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

A continued discussion of some of the material above, in much the same elementary style, is given by

G. Hjorth, Classification and orbit equivalence relations, Mathematical Surveys and Monographs, 75, American Mathematical Society, Providence, RI, 2000.

This includes some easy proofs of some things we didn’t quite get to, such as F_{2} not being Borel reducible to any of the countable Borel equivalence relations, such as E_{0}.

The main theorem, which we finished with, was first presented in

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

and is also independently due to Howard Becker. The proof given there is rather different, in that it is derived as a corollary of Harrington-Kechris-Louveau; and indeed in this paper the main battle was to extend the result to general Σ ∼_{1}^{1} equivalence relations, while above we have been primarily concerned with developing an argument that uses no non-trivial descriptive set theory.

If there had been more time we might have discusses special versions of this dichotomy theorem which can be proved for specific classes of Polish groups. Then one often can hope to replace (II) by

(II’) ≅|_{Mod(T)} ≤_{B} id(2^{ℕ}).

In

G. Hjorth, S. Solecki, Vaught’s conjecture and the Glimm-Effros property for Polish transformation groups, Transactions of the American Mathematical Society, vol. 351(1999), pp. 2623-2641

this was done for the orbit equivalence relations induced by continuous actions of nilpotent and invariantly metrizable Polish groups, while

H. Becker, The topological Vaught’s conjecture and minimal counterexamples, Journal of Symbolic Logic, vol. 59(1994), pp. 757-784

obtained more general results for solvable or under the assumption of a complete left invariant metric.

A rather different approach to some of these questions can be found in

G. Melles, One cannot show from ZFC that there is an Ulm-type classification of the torsion-free abelian groups, pp. 293-309, MSRI Publication 26, Springer-Verlag, 11992, New-York.