

% LaTeX Article Template - customizing header and footer
\documentclass[12pt]{article}

\usepackage{amssymb}
\usepackage{latexsym}

% Set left margin - The default is 1 inch, so the following 
% command sets a 1.25-inch left margin.
\setlength{\oddsidemargin}{-0.25in}

% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
\setlength{\textwidth}{7in}

% Set top margin - The default is 1 inch, so the following 
% command sets a 0.75-inch top margin.
\setlength{\topmargin}{-0.25in}

% Set height of the header
\setlength{\headheight}{0.5in}

% Set vertical distance between the header and the text
\setlength{\headsep}{0.2in}

% Set height of the text
\setlength{\textheight}{8.5in}

% Set vertical distance between the text and the
% bottom of footer
\setlength{\footskip}{0.4in}

\pagestyle{myheadings}
%\markright{\empty}


% Set the beginning of a LaTeX document
\begin{document}

\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\Bbb R}}
\def\V{{\Bbb V}}
\def\N{{\Bbb N}}
\def\n{{\Bbb N}}
\def\Q{{\Bbb Q}}
\def\O{{\cal O}}
\def\e{\epsilon}
\def\h{{\hat{X}}}
\def\B{{\cal B}}
\def\n{\noindent}


\title{{Effective cardinality}}   
      % Enter your title between curly braces
\author{ Greg Hjorth \\Department of Mathematics\\
UCLA\\LA CA90095-1555}      
  % Enter your name between curly braces
\date{\today}          % Enter your date or \today between curly braces
\maketitle

%\leftskip 1in 


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 {\it Borel}. And 
Vladimir Kanovei in \cite{kanovei} 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 
\cite{hakelo} 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. 


\bigskip 

\n{\bf  $\S$1 Cardinality in ZFC} 

\medskip 

The usual notion of cardinality rests heavily on our ability to 
{\it 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. 

\medskip 


\n {\bf 1.1 Definition} A set $\alpha$ 
is said to be an {\it ordinal} if: 

\begin{enumerate} 

\item it is {\it transitive} -- that is to say, if $x\in\alpha$ and 
$y\in x$, then $y\in\alpha$; 

\item is linearly ordered by the membership relation -- that is to say, 
if $\gamma$, $\delta$ are in $\alpha$, then either 

\subitem $\gamma\in\delta$, or 

\subitem $\gamma=\delta$, or 

\subitem $\delta\in\gamma$. 

\end{enumerate} 

\medskip



It turns out that any two ordinals $\alpha$ and $\beta$ are {\it comparable}: 
that is to say, either $\alpha=\beta$, or 
\[\alpha\in\beta{\rm ,}\] 
or 
\[\beta\in\alpha.\] 
Moreover an initial segment of the ordinals are provided by the usual (finite) 
counting numbers. 


\medskip 

\n {\bf 1.2 Examples of ordinals} 
$\emptyset$, 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: 
\[\omega=\{0, 1, 2, ...\}.\] 
This again leads to a whole new ladder of ordinals: 
\[\omega+1=\{0, 1, 2, ..., \omega\}{\rm ,}\] 
\[\omega+2=\{0, 1, 2, ..., \omega, \omega+1\}{\rm ,}\] 
\[\omega+3=\{0, 1, 2, ..., \omega, \omega+1, \omega+2\}{\rm ,}\] 
and onwards: 
\[\omega+\omega=\{0, 1, 2, ..., \omega, \omega+1, \omega+2, ...\}{\rm ,}\] 
\[\omega+\omega+1=\{0, 1, 2, ..., \omega , \omega+1, \omega+2, ...,\omega+\omega\}{\rm ,}\] 
\[\omega\times\omega=\{0, 1, 2, ..., \omega , \omega+1,...\omega+\omega,...
\omega+\omega+\omega,...\}{\rm ,}\] 
ad infinitum. 

\medskip 


  

\n{\bf 1.3 Definition} A function $f:X\rightarrow Y$ is said to be a 
{\it bijection} if 

\begin{enumerate} 

\item $f$ is one-to-one: for all $x_1, x_2\in X$ with $x_1\neq x_2$ we 
have 
\[f(x_1)\neq f(x_2);\] 

\item $f$ is onto: for all $y_0\in Y$ there exists some $x_0\in X$ with 
\[f(x_0)=y_0.\] 

\end{enumerate} 

\medskip 


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. 

  
\medskip 

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

\bigskip 

All the finite ordinals of the $n=\{0, 1, 2, ..., n-1\}$ are cardinals. 
\[\omega=\{0, 1, 2, 3,...\}\] 
is the first infinite cardinal. 

On the other hand $\omega+1=\{0, 1, 2, ..., \omega\}$ is {\it not} a 
cardinal since we may place it in a bijection with $\omega$: 
\[f(\omega)= 0{\rm ,}\] 
\[f(0)=1{\rm ,}\]
\[f(1)=2{\rm ,}\]
and more generally 
\[f(n)=n+1{\rm .}\]

   

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

\medskip 

\n{\bf 1.5 Fact} Every set $X$ may be placed in a bijection with some ordinal. 

\medskip 

\n{\bf 1.6 Definition} We let the {\it 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|$. 

\medskip 


We say that a set has {\it 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 $\aleph_0$ if it may be placed 
in a bijection with $\omega$, that it has cardinality $\aleph_1$ if it may be placed in 
a bijection with the least cardinal after $\omega$, $\aleph_2$ if it may be placed in a 
bijection with the least cardinal after $\aleph_1$, and so on. 

  

Many examples of infinite sets have size $\aleph_0$: 


\medskip 

\n{\bf 1.7 Example} 
\begin{enumerate} 

\item The set of possible poems in english has size 
$\aleph_0$.\footnote{Assume here we raise no objection to poems going arbitrarily long.} 

\item The set of integers, positive and negative, has cardinality $\aleph_0$. For instance 
I can take as a bijection $f(0)=0$, 
\[f(-n)=2n+1{\rm ,}\] 
\[f(n)=2n+2.\] 

\item The set of all rationals ($\frac{n}{m}$ where $n, m$ are integers, suitably 
reduced) has cardinality $\aleph_0$. 

 
\end{enumerate} 

\medskip 

However not all important infinite 
sets have size $\aleph_0$. At the end of the last century 
George Cantor showed that 
\[|\R|\geq \aleph_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 $\omega$. 


  


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

Note here that the cardinality of $\R$ is the same as that ${\cal P}(\omega)$, 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 
$\R$ with ${\cal P}(\omega)$, the set of all subsets of the natural numbers, 
$\omega$. 
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.) 

\medskip 

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


\medskip 

\n{\bf 1.8 Theorem} (G\"{o}del, 1938) ZFC cannot prove $|\R|>\aleph_1$. 

\medskip 

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

\medskip 

\n{\bf 1.9 Theorem} (Cohen, 1963) ZFC cannot prove $|\R|=\aleph_1$. 

  
\medskip 

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 
$\R$, 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 $|\R|=\aleph_2$, and it may be that eventually 
some combination of plausibility arguments and heuristic considerations will lead 
to wide spread acceptance of this as {\it 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). 

\bigskip 
  

\n{\bf $\S$2 The notion of effective cardinality}

\bigskip 

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


 





Clearly it will take some effort to make precise what we 
mean by {\it reasonably definable} from ${\cal P}(\omega)$. 
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. 
  
\bigskip 
  

\n{\bf 2.1 Cardinality in $L(\R)$} 

\bigskip 

We let $L(\R)$ denote the smallest class of sets containing all the reals, all 
the ordinals, and closed under certain very basic set theoretical 
operations.\footnote{ 
Such as the pairing function: $(x, y)\mapsto \{x, \{x, y\}\}$. Product. 
Boolean operations. And such like.} 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(\R)$ models all the axioms of ZFC, except possibly choice. 
Under the additional and widely supported axiom of AD$^{L(\R)}$ the model 
$L(\R)$ has a canonical structure, and there are no known independence results 
along the lines of the continuum hypothesis. 

  
\medskip 

\n {\bf 2.1.1 Definition} 
For $A, B\in L(\R)$ we say that the $L(\R)$-cardinality of $A$ is no greater than that 
of $B$, written 
\[|A|_{L(\R)}\leq |B|_{L(\R)},\] 
if there is a one-to-one function $\rho\in L(\R)$ 
\[\rho: A\hookrightarrow B.\] 
Similarly  $|A|_{L(\R)}<|B|_{L(\R)}$ if 
\[|A|_{L(\R)}\leq |B|_{L(\R)}\] holds 
but $|B|_{L(\R)}\leq |A|_{L(\R)}$ fails. 


\medskip 


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 ${\Bbb R}$ by 
an appropriately chosen equivalence relation. Moreover it turns out 
that every set in $L({\Bbb R})$ can be placed in a bijection with a set 
of the form 
\[\bigcup_{\alpha\in \kappa} A_\alpha,\] 
where the $(A_\alpha)_{\alpha\in \kappa}$ is a sequence in 
$L({\Bbb R})$ for which there is (again in $L({\Bbb R})$) a 
corresponding sequence $(E_\alpha)_{\alpha\in \kappa}$ of equivalence 
relations on ${\Bbb R}$ and bijections 
\[\pi_{\alpha}: X_\alpha\cong {\Bbb R}/ E_\alpha.\] 
Since the ordinals are relatively well understood, we thus have that 
the study of cardinality in $L({\Bbb R})$ is largely the study of 
the quotients of ${\Bbb R}$ by equivalence relations.\footnote{For the 
proofs of this and other basic facts about cardinality in 
$L(\R)$ the reader could look in 
\cite{hjorth} and chapter nine of \cite{orbit}.} 

Here I am using ${\Bbb R}/E$ to indicate the collection of 
$E$-equivalence classes: $\{[x]_E: x\in \R\}$, where for each $x\in\R$ 
we write 
\[[x]_E=\{y\in \R: yEx\}\] 
for the equivalence class of $x$. 

\medskip  

\n{\bf 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={\Bbb R}$; at the very 
least we require $X$ to be a space which exists in $L({\Bbb R})$ and 
which $L({\Bbb R})$ can place in a bijection with the reals. 

\begin{enumerate} 

\item id$({\Bbb R})$, the identity relation on $\R$, setting each $x$ to be 
only equivalent to itself; 

\item $E_v$, the Vitali equivalence relation, given by 
\[xE_v y\] 
if $x-y$ is a rational number; 

\item $E_0$ on $2^\omega$, the space of infinite binary sequences, given by 
\[\langle x_0, x_1, x_2...\rangle =\vec x E_0 \vec y=\langle y_0, y_1,...\rangle\] 
if from some point on they agree: 
\[\exists N\in\omega\forall k>N(x_k=y_k);\] 

\item we may naturally identify ${\cal P}(\omega)$ with 
$2^\omega$ by associating with each $X\subset\omega$ its characteristic 
function: 
\[f_X: \omega \rightarrow \{0,1\},\] 
with $f_X(n)=1$ if $n\in X$, $=0$ otherwise. 
Then it is not hard to see that $E_0$ on $2^\omega$ corresponds to the 
equivalence relation Fin, where 
\[X \:{\rm Fin }\: Y\] 
if there are only finitely many natural numbers in exactly one of 
these sets; that is to say, their {\it symmetric difference} is 
finite. 

\end{enumerate} 



Here we have 
\[|\R|_{L(\R)}<|\R/E_v|_{L(\R)} .\] 
Moreover one has 
\[|\R/E_v|_{L(\R)}\leq |{\cal P}(\omega)/{\rm Fin}|_{L(\R)}\] 
and 
\[|{\cal P}(\omega)/{\rm Fin}|_{L(\R)}\leq |\R/E_v|_{L(\R)}.\] 
 

  
\medskip 

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 $\kappa$ and $\lambda$, either they 
are equal, or one is bigger than the other. 

 

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

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

\medskip 

\n {\bf 2.1.3. Definition} 
A subset of $\R^2$, two dimensional euclidean 
space, is said to be {\it 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 \}{\rm ,}\] 
by the 
operations of complementation, countable intersections (that is to say, 
if $(A_n)_{n\in\omega}$ are Borel, then so too is $\bigcap_{n\in\omega}A_n$), 
and countable unions. 
An equivalence relation $E$ on $\R$ is said to be a {\it Borel equivalence 
relation} if the set $\{(x_0, x_1): x_0 Ex_1\}$ is Borel as a subset of 
$\R^2$. 

All Borel sets appear in $L(\R)$. 

\medskip 

\n {\bf 2.1.4 Definition} For $E$ and $F$ equivalence relations on 
$\R$ we write 
\[E\leq_{L(\R)} F\] 
if there is a function $\pi: \R\rightarrow \R$ in 
$L(\R)$ such that for all $x_1, x_2\in L(\R)$ we have 
\[x_1 E x_2\Leftrightarrow \pi(x_1) F \pi(x_2).\] 

\medskip 

\n {\bf 2.1.5 Fact} (Folklore) For $E$ and $F$ Borel equivalence relations one has 
\[E\leq_{L(\R)} F\] if and only if 
\[|\R/E|_{L(\R)}\leq |\R/F|_{L(\R)}.\] 

\medskip 


Using a variation of the usual example of a set in $L(\R)$ that allows no 
uniformization -- namely, $\{(x, y): x\notin {\rm OD}(y)\}$ -- one can show that this 
is untrue for general $E, F\in L(\R)$. 
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. 




\bigskip 




  



\n{\bf 2.2 Borel cardinality} 


\bigskip 



  
\n {\bf 2.2.1 Definition} 
A function $f:\R\rightarrow \R$ is 
said to be {\it Borel} if its graph 
\[\{(x_0, x_1): f(x_0)=x_1\}\] 
is Borel as a subset of $\R^2$. 

\medskip 


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 
{\it Borel} plays in many branches of mathematics, it 
seems natural to restrict our attention from all the sets in 
$L(\R)$ to just those that are Borel.  We are then faced with  
the task of defining a notion of {\it Borel cardinality}. 
In view of various facts such as 2.1.5 most people in this field 
have come to accept the following explication. 


\medskip 

\n {\bf 2.2.2 Definition} 
For $E$ and $F$ Borel equivalence relations we say that $\R/E$ has {\it 
Borel cardinality} no greater than $\R/F$ if there is a Borel function 
$f:\R\rightarrow \R$  
such that for all $x_1, x_2\in \R$ 
\[x_1 E x_2 \Leftrightarrow f(x_1) F f(x_2).\] 
In other words, there is a one-to-one function 
\[\hat{f}: \R/E\hookrightarrow \R/F\] 
which lifts up to a Borel function. 

  

We write $E\leq_B F$ to indicate that there is such an $f$ with 
for all $x_1, x_2\in \R$ 
\[x_1 E x_2 
\Leftrightarrow f(x_1) F f(x_2){\rm .}\]  
Naturally we may write $E<_B F$ if $E\leq_B F$ holds but $E<_B F$ fails.  



Here one has 
\[{\rm id}(\R) <_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(\R)$. 

\bigskip 

\n{\bf  $\S$3. Why study this notion?} 

\bigskip 

\n{\bf 3.1 Distrust of the more abstract set theoretical objects} 

\medskip

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 $\R$, 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. 

  
\medskip

\n{\bf 3.2  dissatisfaction  with independence} 

\medskip

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 $\R$, it is also an attractive 
feature of the theory Borel cardinalities and of the theory of 
$L(\R)$ cardinality that these are largely immunized against independence. 

  
\medskip

\n{\bf 3.3 Recurrence of fundamental issues} 

\medskip

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 {\it recursion}\footnote{ or 
{\it computability}} theory. 

\medskip


\n{\bf 3.3.1 Infinite dimensional group representations} 

\medskip 

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 $\R$. His  
oblique proof was eventually replaced by a much simpler argument due 
to Effros, which in turn reduced to the following: 
  

  
\medskip



\n{\bf Theorem} (Effros) Let $E$ be a Borel  equivalence relation where we 
additionally assume: 

\leftskip 0.5in 

\n 1. $E$ is the orbit equivalence relation induced 
by the continuous action of a Polish group; and 

\n 2. $E$ is $F_\sigma$ (defined by the countable union of closed sets in the 
product space). 

\leftskip 0in 

Then either: 

(I) $E\leq_B$ id$(\R)$; or 

(II) $E_v\leq_B E$. 


\medskip

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 $\R$. 



In 1990, \cite{hakelo}, 
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. 

  
\bigskip

\n{\bf 3.3.2 The structure of the Turing degrees} 

\bigskip 

An important part of recursion theory is the study of subsets of 
$\omega$ considered up to {\it 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(\R)$ 
from the Turing degrees to the Turing degrees have relatively few 
possibilities. 



Letting $\cong_T$ denote the equivalence relation on Turing equivalence 
on subsets of $\omega$ (which for our purposes can be identified with 
elements of $\R$) Slaman and Steel proved a number of results, which in 
hindsight can be seen as impinging on the study of 
the Borel and $L(\R)$ cardinality of $\omega/ \!\cong_T$, as part of efforts to 
clarify Martin's conjecture. 

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 \cong_T.\] 
\[|\R/E_v|_{L(\R)}< |{\cal P}(\omega)/\!\cong_T\!|_{L(\R)}.\] 

\medskip 


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(\R)$ cardinality of 
\[{\cal P}(\omega)/\cong_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}=\{\varphi: F_2\rightarrow \{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 \cite{doughertykechris}. 



\bigskip 

\n{\bf 3.4 New ways of considering old knowledge} 

\bigskip 

We already obtain some sense of this with the results of 
3.3.2. One might want to view  
\[E_v<_B \cong_T\] 
as an indication that the Turing degrees are 
{\it 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. 

\medskip 

\n{\bf 3.4.1. Definition} One defines the Borel hierarchy 
of subsets of $\R$ like so: 
The $\Ubf{\Sigma}^0_1$ sets in $\R$ 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\in \R$. Then the $\Ubf{\Pi}^0_1$ sets are 
their complements. 

More generally, for $\alpha<\aleph_1$, we let 
$\Ubf{\Sigma}^0_\alpha$ be the countable unions of sets 
which are all $\Ubf{\Pi}^0_\beta$ some $\beta<\alpha$ and 
then define $\Ubf{\Pi}^0_\alpha$ to be those sets 
whose complements in $\R$ are 
$\Ubf{\Sigma}^0_\alpha$. 

\medskip 

Classically it was shown that for all $\alpha<\beta<\aleph_1$ 
we have 
\[\Ubf{\Sigma}^0_\alpha \neq \Ubf{\Sigma}^0_\beta.\] 
  
In \cite{absoluteness} this was strengthened to a result 
about effective cardinality: 

\medskip 

\n{\bf 3.4.2 Theorem} (Hjorth) For all 
$\alpha<\beta<\aleph_1$ 
we have 
\[|\Ubf{\Sigma}^0_\alpha|_{L(\R)} < |\Ubf{\Sigma}^0_\beta|_{L(\R)}.\] 


\bigskip 

\n{\bf 3.5 The intrinsic interest of structure of the effective cardinals} 


\bigskip  

At the low levels, the Borel equivalence relations and the cardinals of 
$L({\Bbb R})$ 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 ${\Bbb R}$ is the canonical obstruction to being well 
orderable, where we can respectively consider well orders in the Borel 
or $L({\Bbb R})$ 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({\Bbb R})$ echoes of the 
original theorems 3.5.1 and 3.5.2 for Borel. 

\medskip 



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

(I) $E\leq_B$ id$(\omega)$.

(II) id$(\R)\leq_B E$. 

\medskip 


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


\medskip 

\n{\bf 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\leq_B$ id$(\R)$. 


(II) $E_v\leq_B E$.  


\medskip 

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 $\R$. 


  

\medskip 

\n{\bf 3.5.3 Theorem} (Woodin) 
Let $A\in L(\R)$. Then exactly one of the following two things must happen: 

(I) $|A|_{L(\R)}\leq |\alpha|_{L(\R)}$, some ordinal $\alpha$. 

(II) $|\R|_{L(\R)}\leq |A|_{L(\R)}.$ 


\medskip 

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


\medskip  


\n{\bf 3.5.4 Theorem} (Hjorth) 
Let $A\in L(\R)$. Then exactly one of the following two things must happen: 

(I) $|A|_{L(\R)}\leq |{\cal P}(\alpha)|_{L(\R)}$.

(II)  $|{\cal P}(\omega)/{\rm Fin}|_{L(\R)}=
|\R/E_v|_{L(\R)}\leq |A|_{L(\R)}.$ 


\medskip 

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

  
\bigskip 

\n{\bf $\S$4 Further results} 

\bigskip 

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

\medskip 


\n{\bf 4.1 Theorem} (Louveau, Veli\v ckovi\'c) 
There is an assignment  
\[S\mapsto E_S\] 
of Borel equivalence relations to subsets of $\omega$ such that for all 
$S, T\subset \omega$ we have that $T\setminus S$ (the elements of $T$ not in 
$S$) is finite if and only if 
\[E_T\leq_B E_S.\] 

\medskip 

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 \cite{orbit}, and 
papers such at \cite{hjorthkechris3}, 
\cite{thomasvelickovic}, 
\cite{hjorthkechris4}, 
\cite{gaocamerlo}, and 
\cite{doughertykechris} 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 {\it isomorphism on countable structures,} 
or some {\it countable Borel equivalence relation,} that is to say a Borel 
equivalence relation all of whose classes are countable. 
  
\medskip 


\n{\bf 4.2 Question} (Hjorth, Kechris) Let Mod$(\sigma)$ be the space of countable 
models of a (possibly infinitary) sentence $\sigma$. Suppose the isomorphism relation 
$\cong_{{\rm Mod}(\sigma)}$ is Borel. 



Must exactly one of the following hold? 

(I) There is a countable Borel equivalence relation $E$ with 
\[\cong_{{\rm Mod}(\sigma)}
\leq_B E.\]  

(II) For $(E_v)^\omega$ the infinite product of the Vitali equivalence relation viewed 
as an equivalence relation on $\R^\omega$ we have 
\[(E_v)^\omega\leq_B \cong_{{\rm Mod}(\sigma)}.\] 

\medskip 

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)^\omega$. 



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


\bigskip 

\n {\bf Appendix} 
  
Here we give the counterexample from 
$\S 2.1$. The necessary terminology and background, along with 
a more comprehensive list of references, can be found in 
\cite{adamskechris}, \cite{hjorthkechris2}, 
\cite{orbit}, and 
\cite{hakelo}. 


\medskip 

\n {\bf Example}  
Following \cite{adamskechris} 
let $(E_x)_{x\in \R}$ be a  family of equivalence relations 
on $\R$ 
with associated Borel 
probability measures $(\mu_x)_{x\in \R}$ 
on $\R$ such that:  

\begin{enumerate} 

\item These sequences exist in $L(\R)$. 

\item Each $E_x$ has all its equivalence classes 
countable. 

\item The relation $\{(x, y, z): y E_x z\}$ is Borel. 

\item For $x_1, x_2$ distinct we have $E_{x_1}|_M$ is not Borel 
reducible to $E_{x_2}$ for any $\mu_{x_1}$-measure 
one set $M\subset  \R$. 

\item Each $E_x$ is $\mu_x$-ergodic, in the sense that if 
$B\subset  \R$ is $E_x$-invariant and $\mu_x$-measurable, then it 
is either null or conull. 

\item Each $E_x$ equivalence class is null. 

\end{enumerate}  

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 $ \R\times  \R$ 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 $ \R\times  \R\times  \R$ 
by 
$$(x_1, y_1, z_1) F (x_2, y_2, z_2)$$ if either 

\leftskip 0.5in 

\noindent (i) $z_1$ is ordinal definable from $(x_1, y_1)$ and 
$z_2$ is ordinal definable from $(x_2, y_2)$; or 

\noindent (ii) $z_1\notin $ OD$(x_1, y_1)$, $z_2\notin $ OD$(x_2, y_2)$, and 
$x_1=x_2$, and $y_1 E_{x_1} y_2.$ 

\leftskip 0in 

Clearly 
$$| \R\times  \R/E|_{L(\R)}\leq | \R\times  \R\times  \R/F|_{L(\R)}.$$ 
On the other hand if 
$$\theta: \R\times  \R\rightarrow  \R\times  \R\times  \R$$ 
performed a reduction of the equivalence relations in $L(\R)$, then it would 
be OD$(x)$, some $x\in  \R$. We then have by 2. and 3. above that 
$$\forall^{\mu_x} y\in  \R (\theta(x, y)=(x, \rho_0(y), \rho_1(y))),$$ 
some $\rho_0(y), \rho_1(y)\in  \R$. 
Let $N$ be this $\mu_x$-measure 1 set. 

\smallskip 

{\bf Claim:} For any $y_0\in N$, the set 
\[\{y: \rho_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: \rho_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(\R)$ under 
the assumption of AD, it follows that it is included in 
OD$(x, y_0)$. 

\hfill(Claim$\Box$) 

\medskip 

But now we can just choose 
$z_1, z_2$ in this conull set $N$ with 
$$z_1\neg E_x z_2,$$ 
and hence 
$$(x, \rho_0(z_1), \rho_1(z_1)))\neg F (x, \rho_0(z_2), \rho_1(z_2))),$$ 
and thus for some $i\in \{1, 2\}$ we have 
$$\rho_1(z_i)\notin {\rm \: OD}(x, \rho_0(z_i)),$$ 
with a contradiction to the claim. 

 



\begin{thebibliography}{99}


\bibitem{adamskechris} S. Adams, A.S. Kechris, 
{\it Linear algebraic groups and countable Borel equivalence relations,} 
preprint, 1999. 

\bibitem{gaocamerlo} R. Camerlo, S. Gao, {\it The classification of 
countable Boolean algebras,} to appear. 

\bibitem{cantor} G. Cantor, {\it \"{U}ber eine 
Eigenschaft des Ingebriffs aller reellen algebraischen Zahlen}, 
{\bf J. f. Math.}, vol. 77(1874), pp. 258--262. 


\bibitem{cohen} P. Cohen, 
{\it The independence of the continuum hypothesis}, 
{\bf Proceedings of the National Academy of Sciences of the United States of America}, 
vol. 50(1963), pp. 1143--1148.


\bibitem{doughertykechris} R. Dougherty, A.S. Kechris, 
{\it How many Turing degrees are there?}, 
to appear in {\bf Proceedings of the 
AMS Summer Research Conference on Computability Theory and
     Applications,} Boulder, Colorado, June 1999. 

\bibitem{effros} E. Effros, {\it Transformation groups and $C^*$-algebras,} 
{\bf Annals of Mathematics,} ser 2, vol. 81(1975), pp. 38-55. 




\bibitem{glimm} J. Glimm,  
{\it Type I $C\sp{*} $-algebras}, 
{\bf Annals of Mathematics}, vol. 73(1961), pp. 572--612. 

\bibitem{godel} K. G\"{o}del, {\it The consistency of the axiom of choice and the 
generalized continuum hypothesis,} 
{\bf Proceedings of the National Academy of Sciences of the United States of America}, 
vol. 24(1938), pp. 556-557. 

\bibitem{hakelo} L.A. Harrington, A.S. Kechris, A. Louveau, {\it A Glimm-Effros dichotomy for 
Borel equivalence relations,} {\bf Journal of the American Mathematical Society,} 
vol. 3(1990), pp. 903-928. 

\bibitem{hjorth} G. Hjorth, 
{\it A dichotomy for the definable universe},  
{\bf Journal of Symbolic Logic}, vol. 60(1995), pp. 1199--1207. 

\bibitem{absoluteness} G. Hjorth, 
{\it An absoluteness principle for Borel sets,} 
{\bf Journal of Symbolic Logic,} vol. 63(1998), pp. 663--693. 

\bibitem{orbit} G. Hjorth, 
{\bf Classification and orbit equivalence relations,} 
American Mathematical Society, Rhode Island, 2000. 

\bibitem{hjorthkechris2} G. Hjorth and A.S. Kechris, {\it Analytic equivalence relations 
and Ulm-type classifications,} {\bf Journal of Symbolic Logic,} vol. 60(1995), pp. 1273-1300. 

\bibitem{hjorthkechris3} {\sc G.\ Hjorth} and {\sc A.\ S.\ Kechris},
Borel equivalence relations and classifications
of countable models,  
{\em Annals of Pure and Applied Logic}
{\bf 82} (1996), 221--272.

\bibitem{hjorthkechris}  G. Hjorth, 
A.S. Kechris, {\it New dichotomies for 
Borel equivalence relations}, {\bf Bulletin of Symbolic Logic}, vol. 3(1997), 
pp. 329--346.

\bibitem{hjorthkechris4} G. Hjorth, 
A.S.Kechris, {\it The complexity of the classification of
Riemann surfaces and complex manifolds,} to appear in the 
{\bf Illinois Journal of Mathematics.} 



\bibitem{kanovei} V. Kanovei, 
{\it The cardinality of the set of equivalence 
classes,} {\bf Mathematik Zametki,} 
vol. 49(1991), pp. 55-62. 

\bibitem{love} 
A. Louveau, B. 
Veli\v ckovi\'c, {\it A note on Borel equivalence relations},  {\bf Proceedings of the 
American Mathematical Society}, vol. 120(1994), pp. 255--259.

\bibitem{silver} J.H. Silver, 
{\it Counting the number of equivalence classes of Borel 
and coanalytic equivalence relations}, 
{\bf Annals of Mathematical Logic}, vol. 18(1980), pp. 1--28.

\bibitem{slamansteel} T. Slaman, J. Steel, 
{\it Definable functions on degrees,} 
{\bf Cabal Seminar 81-85}, Springer Lecture Notes, 
vol. 1333, 1988, pp. 37-55. 

\bibitem{thomasvelickovic} {\sc S.\ Thomas} and {\sc B.\ Veli\v ckovi\'c},
On the complexity of the isomorphism relation for finitely generated groups, 
to appear in the {\bf Journal of Algebra.} 

\end{thebibliography}

%6363 MSB

%Mathematics

%UCLA

%CA90095-1555

greg@math.ucla.edu


\end{document}


