Effective cardinality

Greg Hjorth Department of Mathematics UCLA LA CA90095-1555

January 31, 2001

In this brief note I want to talk a little about a fairly recent development in modern set theory. When I say recent, I mean that it dates back to some time around the late 1980’s, at which point I understand it had Alexander Kechris and Alain Louveau as its main advocates. In an earlier form there are hints of these ideas in work of Harvey Friedman, who had tried to seriously consider what the world must look like to a mathematician who declares that the only things in their ontology are the objects which can be viewed as Borel. And Vladimir Kanovei in [17] has pointed to even earlier precursors of this idea in the works of the classical analysts. But even granting such instances I think it was not until [9] and the papers which followed that set theorists began a systematic study and that the central definitions were isolated.

Usually when one talks about a new idea in a mathematical discipline such as set theory, one has in mind a technique which enables old problems to be solved for the first time, or at the very least provides new proofs for previously known theorems. While there perhaps have been a few isolated cases of this taking place, the new idea I want to discuss represents instead a new way of looking at existing objects. It represents a different way of thinking about “how many” objects there are in a collection when that collection is infinite.

Before going any further we should at least consider the traditional notion of cardinality which operates among set theorists. The formulation of this notion at the end of the 19th century represents George Cantor’s great triumph, and it has been justifiably dominant ever since.

§1 Cardinality in ZFC

The usual notion of cardinality rests heavily on our ability to well order any given set. One can then compare the cardinality of sets by, in effect, comparing their shortest possible well ordering. Rather than become involve in defining the notion of a well order, I will instead take a different but equivalent course through the definitions.

1.1 Definition A set α is said to be an ordinal if:

1. it is transitive – that is to say, if x ∈ α and y ∈ x, then y ∈ α; 2. is linearly ordered by the membership relation – that is to say, if γ, δ are in α, then either

γ ∈ δ, or

γ = δ, or

δ ∈ γ.

It turns out that any two ordinals α and β are comparable: that is to say, either α = β, or

α ∈ β,

or

β ∈ α.

Moreover an initial segment of the ordinals are provided by the usual (finite) counting numbers.

1.2 Examples of ordinals ∅, the set having no members, which set theorists customarily identify with 0.

1 = {0}, the set whose only member is 0.

2 = {0, 1}, gives the usual set theoretical definition of 2. Then we keep going with 3 = {0, 1, 2}, 4 = {0, 1, 2, 3}, and so on.

We reach the first infinite ordinal with the set of natural numbers:

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

This again leads to a whole new ladder of ordinals:

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

and onwards:

ω + ω = {0, 1, 2, ..., ω, ω + 1, ω + 2, ...},
ω + ω + 1 = {0, 1, 2, ..., ω, ω + 1, ω + 2, ..., ω + ω},
ω × ω = {0, 1, 2, ..., ω, ω + 1, ...ω + ω, ...ω + ω + ω, ...},

ad infinitum.

1.3 Definition A function f : X → Y is said to be a bijection if

1. f is one-to-one: for all x_{1}, x_{2} ∈ X with x_{1} ≠ x_{2} we have

f(x_{1}) ≠ f(x_{2});

2. f is onto: for all y_{0} ∈ Y there exists some x_{0} ∈ X with

f(x_{0}) = y_{0}.

So for example, if we rummaged through my apartment and collected all the left shoes together in a set X and all the right shoes into a set Y, then hopefully we could provide a bijection by associating to each left shoe

x_{0}

the corresponding right shoe

f(x_{0})

which one needs to form a matching pair.

1.4 Definition An ordinal is said to be a cardinal if it can not be placed in a bijection with any earlier ordinal.

All the finite ordinals of the n = {0, 1, 2, ..., n − 1} are cardinals.

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

is the first infinite cardinal.

On the other hand ω + 1 = {0, 1, 2, ..., ω} is not a cardinal since we may place it in a bijection with ω:

f(ω) = 0,
f(0) = 1,
f(1) = 2,

and more generally

f(n) = n + 1.

Essentially as a consequence of the axiom of choice one has:

1.5 Fact Every set X may be placed in a bijection with some ordinal.

1.6 Definition We let the cardinality of a set X be the least ordinal with which it may be placed in a bijection. We denote that least ordinal by |X|.

We say that a set has cardinality n if it may be placed in a bijection with the finite set n = {0, 1, 2, ..., n − 1}. We say it has cardinality ℵ_{0} if it may be placed in a bijection with ω, that it has cardinality ℵ_{1} if it may be placed in a bijection with the least cardinal after ω, ℵ_{2} if it may be placed in a bijection with the least cardinal after ℵ_{1}, and so on.

Many examples of infinite sets have size ℵ_{0}:

1.7 Example

1. The set of possible poems in english has size ℵ_{0}.^{1} 2. The set of integers, positive and negative, has cardinality ℵ_{0}. For instance I can take as a

1Assume here we raise no objection to poems going arbitrarily long.

bijection f(0) = 0,

f(−n) = 2n + 1,
f(n) = 2n + 2.

3. The set of all rationals (\frac{n}{m} where n, m are integers, suitably reduced) has cardinality ℵ_{0}.

However not all important infinite sets have size ℵ_{0}. At the end of the last century George Cantor showed that

|ℝ| ≥ ℵ_{1}.

In other words, the least ordinal which may be placed in a bijection with the set of all real numbers is strictly bigger than ω.

Cantor went on to conjecture the continuum hypothesis, to the effect that the set of reals has size exactly ℵ_{1}. The issue of the truth of this conjecture became the first of the famous Hilbert problems.

Note here that the cardinality of ℝ is the same as that P(ω), the collection of sets of the natural numbers. (For the purposes of the rest of this article I want to largely identify the real number line ℝ with P(ω), the set of all subsets of the natural numbers, ω. These two objects are not literally the same, but one can find definable bijections between the two, and from the point of view of set theory they have essentially the same status.)

It turns out that ZFC, the usual axiomatization of mathematical reasoning is unable to provide an answer.

1.8 Theorem (Gödel, 1938) ZFC cannot prove |ℝ| > ℵ_{1}.

In other words, the continuum hypothesis is consistent with ZFC. A quarter of a century later it was shown to be independent.

1.9 Theorem (Cohen, 1963) ZFC cannot prove |ℝ| = ℵ_{1}.

Part of the difficulty with this problem is that although the axiom of choice promises us that there will exist some bijection between some ordinal and ℝ, it gives no information at all about the nature of this bijection or this ordinal. It is a pure existence axiom.

In the second half of the century various set theorists for various reasons have proposed |ℝ| = ℵ_{2}, and it may be that eventually some combination of plausibility arguments and heuristic considerations will lead to wide spread acceptance of this as true.

None the less it does seem that the status of the continuum hypothesis will not be settled in the way that mathematical questions are usually settled, by either a proof of counterexample being presented under ZFC (or perhaps ZFC extended by some large cardinal assumption).

§2 The notion of effective cardinality

A rather different notion is provided by restricting our attention to only those sets and functions which lay some claim on being reasonably definable from the most concrete of mathematical objects, such as the natural numbers or the subsets of the natural numbers. This is the new idea I want exposit.

Clearly it will take some effort to make precise what we mean by reasonably definable from P(ω). Here there are two quite different definitions in wide currency. The first of these is much more generous than the second, but the structural properties of both approaches are similar.

2.1 Cardinality in L(ℝ)

We let L(ℝ) denote the smallest class of sets containing all the reals, all the ordinals, and closed under certain very basic set theoretical operations.^{2} So in some loose sense this might be considered the universe of everything we can define in a ground up fashion from the reals.

It turns out that L(ℝ) models all the axioms of ZFC, except possibly choice. Under the additional and widely supported axiom of AD^{L(ℝ)} the model L(ℝ) has a canonical structure, and there are no known independence results along the lines of the continuum hypothesis.

2.1.1 Definition For A, B ∈ L(ℝ) we say that the L(ℝ)-cardinality of A is no greater than that of B, written

|A|_{L(ℝ)} ≤ |B|_{L(ℝ)},

if there is a one-to-one function ρ ∈ L(ℝ)

ρ : A ↪ B.

Similarly |A|_{L(ℝ)} < |B|_{L(ℝ)} if

|A|_{L(ℝ)} ≤ |B|_{L(ℝ)}

holds but |B|_{L(ℝ)} ≤ |A|_{L(ℝ)} fails.

One of the original impetuses for set theory was the study of the real number line, and indeed it turns out that many of the objects of greatest interest can be realized as quotients of ℝ by an appropriately chosen equivalence relation. Moreover it turns out that every set in L(ℝ) can be placed in a bijection with a set of the form

⋃_{α∈κ} A_{α},

where the (A_{α})_{α∈κ} is a sequence in L(ℝ) for which there is (again in L(ℝ)) a corresponding sequence (E_{α})_{α∈κ} of equivalence relations on ℝ and bijections

π_{α} : X_{α} ≅ ℝ/E_{α}.

Since the ordinals are relatively well understood, we thus have that the study of cardinality in L(ℝ) is largely the study of the quotients of ℝ by equivalence relations.^{3}

2Such as the pairing function: (x, y) ↦ {x, {x, y}}. Product. Boolean operations. And such like.

3For the proofs of this and other basic facts about cardinality in L(ℝ) the reader could look in [10] and chapter nine of [12].

Here I am using ℝ/E to indicate the collection of E-equivalence classes: {[x]_{E} : x ∈ ℝ}, where for each x ∈ ℝ we write

[x]_{E} = {y ∈ ℝ : yEx}

for the equivalence class of x.

2.1.2 Examples In all of the following, we have an equivalence relation on a reasonably nice space X. In most cases the X = ℝ; at the very least we require X to be a space which exists in L(ℝ) and which L(ℝ) can place in a bijection with the reals.

1. id(ℝ), the identity relation on ℝ, setting each x to be only equivalent to itself;

2. E_{v}, the Vitali equivalence relation, given by

xE_{v}y

if x − y is a rational number;

3. E_{0} on 2^{ω}, the space of infinite binary sequences, given by

⟨x_{0}, x_{1}, x_{2}...⟩ = x⃗E_{0}y⃗ = ⟨y_{0}, y_{1}, ...⟩

if from some point on they agree:

∃N ∈ ω∀k > N(x_{k} = y_{k});

4. we may naturally identify P(ω) with 2^{ω} by associating with each X ⊂ ω its characteristic

function:

f_{X} : ω → {0, 1},

with f_{X}(n) = 1 if n ∈ X, = 0 otherwise. Then it is not hard to see that E_{0} on 2^{ω} corresponds to the equivalence relation Fin, where

X Fin Y

if there are only finitely many natural numbers in exactly one of these sets; that is to say, their symmetric difference is finite.

Here we have

|ℝ|_{L(ℝ)} < |ℝ/E_{v}|_{L(ℝ)}.

Moreover one has

|ℝ/E_{v}|_{L(ℝ)} ≤ |P(ω)/Fin|_{L(ℝ)}

and

|P(ω)/Fin|_{L(ℝ)} ≤ |ℝ/E_{v}|_{L(ℝ)}.

In ZFC one obtains that the ordinals are arranged in a linear ordering, and thus the subclass of the ordinals corresponding to cardinals is again linearly ordered. For any two cardinals κ and λ, either they are equal, or one is bigger than the other.

The situation is completely different for L(ℝ). For instance one has that |ℝ|_{L(ℝ)} is incomparable with ℵ_{1} in L(ℝ). More generally, there is no ordinal with the same cardinality as ℝ inside L(ℝ).

It turns out that for reasonably simple equivalence relations, one has that the cardinality of ℝ/E is less than ℝ/F if and only if there is a kind of reduction of E to F.

2.1.3. Definition A subset of ℝ^{2}, two dimensional euclidean space, is said to be Borel if it is generated from the collection of open squares of the form

{(x_{0}, x_{1}) : r_{0} < x_{0} < s_{0}, r_{1} < x_{1} < s_{1}},

by the operations of complementation, countable intersections (that is to say, if (A_{n})_{n∈ω} are Borel, then so too is ⋂_{n∈ω} A_{n}), and countable unions. An equivalence relation E on ℝ is said to be a Borel equivalence relation if the set {(x_{0}, x_{1}) : x_{0}Ex_{1}} is Borel as a subset of ℝ^{2}.

All Borel sets appear in L(ℝ).

2.1.4 Definition For E and F equivalence relations on ℝ we write

E ≤_{L(ℝ)} F

if there is a function π : ℝ → ℝ in L(ℝ) such that for all x_{1}, x_{2} ∈ L(ℝ) we have

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

2.1.5 Fact (Folklore) For E and F Borel equivalence relations one has

E ≤_{L(ℝ)} F

if and only if

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

Using a variation of the usual example of a set in L(ℝ) that allows no uniformization – namely, {(x, y) : x ∉ OD(y)} – one can show that this is untrue for general E, F ∈ L(ℝ). While a set theorist would expect that some such counterexample should exist, it actually seems surprisingly difficult to construct. The somewhat technical argument I sketch in the appendix is the only one I know, and it rests heavily on a recent theorem due to Adams and Kechris.

2.2 Borel cardinality

2.2.1 Definition A function f : ℝ → ℝ is said to be Borel if its graph

{(x_{0}, x_{1}) : f(x_{0}) = x_{1}}

is Borel as a subset of ℝ^{2}.

Any continuous function is Borel, and more generally the functions which typically arise in calculus, most undergraduate mathematics, and many branches of analysis, are Borel.

Given the broad role the notion of Borel plays in many branches of mathematics, it seems natural to restrict our attention from all the sets in L(ℝ) to just those that are Borel. We are then faced with the task of defining a notion of Borel cardinality. In view of various facts such as 2.1.5 most people in this field have come to accept the following explication.

2.2.2 Definition For E and F Borel equivalence relations we say that ℝ/E has Borel cardinality no greater than ℝ/F if there is a Borel function f : ℝ → ℝ such that for all x_{1}, x_{2} ∈ ℝ

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

In other words, there is a one-to-one function

f̂: ℝ/E ↪ ℝ/F

which lifts up to a Borel function.

We write E ≤_{B} F to indicate that there is such an f with for all x_{1}, x_{2} ∈ ℝ

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

Naturally we may write E <_{B} F if E ≤_{B} F holds but E <_{B} F fails.

Here one has

id(ℝ) <_{B} E_{v}.

That is to say the quotient object arising from the Vitali equivalence relation has strictly bigger Borel cardinality than that of the reals. More generally all the results mentioned at 2.1.2, along with the overwhelming majority of specific cases that have been subject to serious study, hold for the Borel notion of cardinality exactly as they do for L(ℝ).

§3. Why study this notion?

3.1 Distrust of the more abstract set theoretical objects

One might for instance take the position that the mathematical objects for which we have the strongest evidence are firstly the natural numbers, then the subsets of the natural numbers, which for our purposes can be identified with ℝ, and finally those objects which are easily produced from the reals, such as the Borel sets and quotients by Borel equivalence relations.

This is not quite a rejection of abstract objects, since it is not clear that the number 5 is any less abstract than the first “supercompact cardinal”. Nevertheless there might be some interest in developing a parsimonious theory of cardinality, which refuses to borrow on any but the most concrete and well established of mathematical concepts.

3.2 dissatisfaction with independence

One reaction to the independence of the continuum hypothesis might be a kind of despair. If we are unable to ever know the answer to this kind of question, then perhaps we should dispose of it altogether.

While it would be unreasonable to conclude that a problem is meaningless or somehow bogus simply because we have no method to determine the answer, and while it is not even accepted among set theorists that future principles of reasoning will never determine the ZFC cardinality of ℝ, it is also an attractive feature of the theory Borel cardinalities and of the theory of L(ℝ) cardinality that these are largely immunized against independence.

3.3 Recurrence of fundamental issues

It turns out that some of the questions arising in the study of Borel cardinalities have reappeared in many different contexts. I will give two examples, one from a mainstream mathematical field and one from the branch of mathematical logic known as recursion^{4} theory.

3.3.1 Infinite dimensional group representations

In 1961 Glimm proved Mackey’s conjecture, an outstanding open problem in the theory of infinite dimensional group representations, by showing that in some sense the representations of a locally compact group have an appropriately nice structure if and only if the irreducible representations considered up to unitary equivalence have Borel cardinality below ℝ. His oblique proof was eventually replaced by a much simpler argument due to Effros, which in turn reduced to the following:

Theorem (Effros) Let E be a Borel equivalence relation where we additionally assume: 1. E is the orbit equivalence relation induced by the continuous action of a Polish group; and

2. E is F_{σ} (defined by the countable union of closed sets in the product space). Then either: (I) E ≤_{B} id(ℝ); or (II) E_{v} ≤_{B} E.

In other words, E is either no more complicated than the identity relation on the reals or at least as complicated as the Vitali equivalence relation given by rational translation on ℝ.

In 1990, [9], Harrington, Kechris, and Louveau proved this without the additional assumptions 1. and 2. above for general Borel equivalence relations. Thus one has the reduction of a landmark theorem to an entirely general fact regarding Borel cardinality.

3.3.2 The structure of the Turing degrees

An important part of recursion theory is the study of subsets of ω considered up to Turing equivalence, where one might loosely think of two subsets as having the same Turing degree if they have same information, from the point of view of some machine that is allowed only finitary operations. This has further led in particular to the still open Martin’s conjecture, which asserts that the functions in L(ℝ) from the Turing degrees to the Turing degrees have relatively few possibilities.

Letting ≅_{T} denote the equivalence relation on Turing equivalence on subsets of ω (which for our purposes can be identified with elements of ℝ) Slaman and Steel proved a number of results, which in hindsight can be seen as impinging on the study of the Borel and L(ℝ) cardinality of ω/≅_{T}, as part of efforts to clarify Martin’s conjecture.

4or computability

Appealing to Effros’ theorem, and certain easy facts about the low level Borel equivalence relations, one can obtain from their results that

E_{v} <_{B}≅_{T} .
|ℝ/E_{v}|_{L(ℝ)} < |P(ω)/≅_{T} |_{L(ℝ)}.

If either of these strict inequalities had failed to hold it would have at once lead to an immediate failure of Martin’s conjecture.

Determining the exact L(ℝ) cardinality of

P(ω)/ ≅_{T}

remains totally open and closely connected with the structure of the Turing degrees. Kechris has conjectured that it should be the same as the of 2^{F_{2}}/F_{2}, where F_{2} is the free group on two generators acting on the space

2^{F_{2}} = {φ : F_{2} → {0, 1}}

by shift, and this competing conjecture would in turn refute the Martin conjecture.

Further discussion of this line of research can be found in [5].

3.4 New ways of considering old knowledge

We already obtain some sense of this with the results of 3.3.2. One might want to view

E_{v} <_{B}≅_{T}

as an indication that the Turing degrees are complicated. For instance it is already sufficient to show that there is no Borel linear ordering on the Turing degrees, and thus that incomparable degrees exist.

Let me mention one other result along these lines.

3.4.1. Definition One defines the Borel hierarchy of subsets of ℝ like so: The Σ ∼_{1}^{0} sets in ℝ are the open sets – those that are the unions of intervals of the form

{x : r_{1} < x < r_{2}}

where r_{1}, r_{2} ∈ ℝ. Then the Π ∼_{1}^{0} sets are their complements.

More generally, for α < ℵ_{1}, we let Σ ∼_{α}^{0} be the countable unions of sets which are all Π ∼_{β}^{0} some β < α and then define Π ∼_{α}^{0} to be those sets whose complements in ℝ are Σ ∼_{α}^{0}.

Classically it was shown that for all α < β < ℵ_{1} we have

Σ ∼_{α}^{0} ≠ Σ ∼_{β}^{0}.

In [11] this was strengthened to a result about effective cardinality:

3.4.2 Theorem (Hjorth) For all α < β < ℵ_{1} we have

|Σ ∼_{α}^{0}|_{L(ℝ)} < |Σ ∼_{β}^{0}|_{L(ℝ)}.

3.5 The intrinsic interest of structure of the effective cardinals

At the low levels, the Borel equivalence relations and the cardinals of L(ℝ) display a dramatic and interesting structure, encapsulated in the following “dichotomy theorems”. In the first and third of these one has that the cardinality of ℝ is the canonical obstruction to being well orderable, where we can respectively consider well orders in the Borel or L(ℝ) context. The second and fourth are more subtle; the second at least can be viewed as providing an analysis of when we may think of a Borel cardinality as corresponding to a subset of the reals.

It is also interesting here to observe the parallels between our different contexts. 3.5.3 and 3.5.4 can be thought of as L(ℝ) echoes of the original theorems 3.5.1 and 3.5.2 for Borel.

3.5.1 Theorem (Silver) Let E be a Borel equivalence relation. Then exactly one of the following two things must happen:

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

(II) id(ℝ) ≤_{B} E.

In other words, there are either only countably many equivalence classes or there are as many equivalence classes as real numbers.

3.5.2 Theorem (Harrington, Kechris, Louveau) Let E be a Borel equivalence relation. Then exactly one of the following two things must happen:

(I) E ≤_{B} id(ℝ).

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

In other words, E is either as complicated as the Vitali equivalence relation or the collection of E-equivalence classes may be identified with a subset of ℝ.

3.5.3 Theorem (Woodin) Let A ∈ L(ℝ). Then exactly one of the following two things must happen:

(I) |A|_{L(ℝ)} ≤ |α|_{L(ℝ)}, some ordinal α.

(II) |ℝ|_{L(ℝ)} ≤ |A|_{L(ℝ)}.

So in other words, every set in L(ℝ) is either well orderable or has a subset which admits a bijection with ℝ.

3.5.4 Theorem (Hjorth) Let A ∈ L(ℝ). Then exactly one of the following two things must happen: (I) |A|_{L(ℝ)} ≤ |P(α)|_{L(ℝ)}. (II) |P(ω)/Fin|_{L(ℝ)} = |ℝ/E_{v}|_{L(ℝ)} ≤ |A|_{L(ℝ)}.

In other words, any set in L(ℝ) is either injectable into the subsets of some ordinal or it is as complicated as the subsets of ω considered up to finite difference.

§4 Further results

Globally the Borel equivalence relations are a hopeless mess. For instance

4.1 Theorem (Louveau, Veličković) There is an assignment

S ↦ E_{S}

of Borel equivalence relations to subsets of ω such that for all S, T ⊂ ω we have that T \ S (the elements of T not in S) is finite if and only if

E_{T} ≤_{B} E_{S}.

The overall structure seems to be incomprehensible.

One response would be to leave all structural questions to the side. Accept the effective cardinals on their face value, and instead try to categorize various classes of mathematical objects in terms of the more prominent cardinalities.

This has been discussed extensively in [12], and papers such at [14], [21], [16], [2], and [5] can indeed be thought of as trying to calculate the effective cardinality of certain standard mathematical objects.

An alternative approach is to continue the structural investigation but with a much more limited focus; we do not try to enumerate every possible effective cardinal, but instead we can try to understand certain crucial parts and dividing lines. For instance we can try to understand which cardinals exist below some specific effective cardinal or what kinds of obstructions prevent us, for instance, reducing a a cardinal to isomorphism on countable structures, or some countable Borel equivalence relation, that is to say a Borel equivalence relation all of whose classes are countable.

4.2 Question (Hjorth, Kechris) Let Mod(σ) be the space of countable models of a (possibly infinitary) sentence σ. Suppose the isomorphism relation ≅_{Mod(σ)} is Borel.

Must exactly one of the following hold?

(I) There is a countable Borel equivalence relation E with

≅_{Mod(σ)}≤_{B} E.

(II) For (E_{v})^{ω} the infinite product of the Vitali equivalence relation viewed as an equivalence relation on ℝ^{ω} we have

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

Many special cases of this have been verified. At most one of 1. and 2. can hold and there is no Borel cardinality strictly between E_{v} and (E_{v})^{ω}.

Presumably if this is true then there should be an L(ℝ) version for the hereditarily well orderable sets, but this has not been seriously examined.

Appendix

Here we give the counterexample from §2.1. The necessary terminology and background, along with a more comprehensive list of references, can be found in [1], [13], [12], and [9].

Example Following [1] let (E_{x})_{x∈ℝ} be a family of equivalence relations on ℝ with associated Borel probability measures (μ_{x})_{x∈ℝ} on ℝ such that:

1. These sequences exist in L(ℝ).

2. Each E_{x} has all its equivalence classes countable.

3. The relation {(x, y, z) : yE_{x}z} is Borel.

4. For x_{1}, x_{2} distinct we have E_{x_{1}}|_{M} is not Borel reducible to E_{x_{2}} for any μ_{x_{1}}-measure one set M ⊂ ℝ.

5. Each E_{x} is μ_{x}-ergodic, in the sense that if B ⊂ ℝ is E_{x}-invariant and μ_{x}-measurable, then it is either null or conull.

6. Each E_{x} equivalence class is null.

We then can define two different ways to thread this family into a single equivalence relation. First we may define E as an equivalence relation on ℝ × ℝ by

(x_{1}, y_{1})E(x_{2}, y_{2})

if x_{1} = x_{2} and y_{1}E_{x_{1}}y_{2}. Then we can define F on ℝ × ℝ × ℝ by

(x_{1}, y_{1}, z_{1})F (x_{2}, y_{2}, z_{2})

if either (i) z_{1} is ordinal definable from (x_{1}, y_{1}) and z_{2} is ordinal definable from (x_{2}, y_{2}); or (ii) z_{1} ∉ OD(x_{1}, y_{1}), z_{2} ∉ OD(x_{2}, y_{2}), and x_{1} = x_{2}, and y_{1}E_{x_{1}}y_{2}.

Clearly

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

On the other hand if

θ : ℝ × ℝ → ℝ × ℝ × ℝ

performed a reduction of the equivalence relations in L(ℝ), then it would be OD(x), some x ∈ ℝ. We then have by 2. and 3. above that

∀^{μ_{x}}y ∈ ℝ(θ(x, y) = (x, ρ_{0}(y), ρ_{1}(y))),

some ρ_{0}(y), ρ_{1}(y) ∈ ℝ. Let N be this μ_{x}-measure 1 set.

Claim: For any y_{0} ∈ N, the set

{y : ρ_{0}(y) = y_{0}}

is included in OD(x, y_{0}).

Proof of claim: Since E_{x} is an equivalence relation with all its equivalence classes countable, it follows that {y : ρ_{0}(y) = y_{0}} is a countable set. Since this set is countable, ordinal definable from (x, y_{0}), and we are working in L(ℝ) under the assumption of AD, it follows that it is included in OD(x, y_{0}).

(Claim□)

But now we can just choose z_{1}, z_{2} in this conull set N with

z_{1}¬E_{x}z_{2},

and hence

(x, ρ_{0}(z_{1}), ρ_{1}(z_{1})))¬F (x, ρ_{0}(z_{2}), ρ_{1}(z_{2}))),

and thus for some i ∈ {1, 2} we have

ρ_{1}(z_{i}) ∉ OD(x, ρ_{0}(z_{i})),

with a contradiction to the claim.

References

[1] S. Adams, A.S. Kechris, Linear algebraic groups and countable Borel equivalence relations, preprint, 1999.

[2] R. Camerlo, S. Gao, The classification of countable Boolean algebras, to appear.

[3] G. Cantor, Über eine Eigenschaft des Ingebriffs aller reellen algebraischen Zahlen, J. f. Math., vol. 77(1874), pp. 258–262.

[4] P. Cohen, The independence of the continuum hypothesis, Proceedings of the National Academy of Sciences of the United States of America, vol. 50(1963), pp. 1143–1148.

[5] R. Dougherty, A.S. Kechris, How many Turing degrees are there?, to appear in Proceedings of the AMS Summer Research Conference on Computability Theory and Applications, Boulder, Colorado, June 1999.

[6] E. Effros, Transformation groups and C^{∗}-algebras, Annals of Mathematics, ser 2, vol. 81(1975), pp. 38-55.

[7] J. Glimm, Type I C^{∗}-algebras, Annals of Mathematics, vol. 73(1961), pp. 572–612.

[8] K. Gödel, The consistency of the axiom of choice and the generalized continuum hypothesis, Proceedings of the National Academy of Sciences of the United States of America, vol. 24(1938), pp. 556-557.

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

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

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

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

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

[14] G. Hjorth and A. S. Kechris, Borel equivalence relations and classifications of countable models, Annals of Pure and Applied Logic 82 (1996), 221–272.

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

[16] G. Hjorth, A.S.Kechris, The complexity of the classification of Riemann surfaces and complex manifolds, to appear in the Illinois Journal of Mathematics.

[17] V. Kanovei, The cardinality of the set of equivalence classes, Mathematik Zametki, vol. 49(1991), pp. 55-62.

[18] A. Louveau, B. Veličković, A note on Borel equivalence relations, Proceedings of the American Mathematical Society, vol. 120(1994), pp. 255–259.

[19] J.H. Silver, Counting the number of equivalence classes of Borel and coanalytic equivalence relations, Annals of Mathematical Logic, vol. 18(1980), pp. 1–28.

[20] T. Slaman, J. Steel, Definable functions on degrees, Cabal Seminar 81-85, Springer Lecture Notes, vol. 1333, 1988, pp. 37-55.

[21] S. Thomas and B. Veličković, On the complexity of the isomorphism relation for finitely generated groups, to appear in the Journal of Algebra.

greg@math.ucla.edu