% 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