% 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