%This is an AMS-LaTex Document

\documentstyle{amsart}

\input amssym.def
\input amssym

\title{The Measure Problem and the Continuum Hypothesis}

\author{Christopher C. Leary}

\address{Department of Mathematics\\
State University of New York\\
College at Geneseo\\
Geneseo, NY  14454}

\email{leary@@geneseo.bitnet}

\date{}

\def\diag#1#2#3{\underset{#1 \in #2}{\bigtriangledown}#3_#1}
\def\NS{N\!S_\kappa}

\newcommand{\arrow}{\rightarrow}
\newcommand{\cross}{\times}
\newcommand{\Intersect}{\bigcap}
\newcommand{\intersect}{\cap}
\newcommand{\rationals}{{\Bbb Q}}
\newcommand{\reals}{{\Bbb R}}
\newcommand{\Union}{\bigcup}
\newcommand{\union}{\cup}


\newtheorem{theo}{Theorem}
\newtheorem{lem}[theo]{Lemma}
\newtheorem{defi}[theo]{Definition}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{cor}[theo]{Corollary}
\newtheorem{prob}{Problem}


\begin{document}

\thanks {The author would like to thank Akihiro Kanamori, Ed
Wallace, Andreas Blass, and Norm Levenberg for their
helpful comments on early drafts of this paper.}
\maketitle

The purpose of this article
is to remind the reader of one simple example of the interplay
between set theory and analysis.  None of the mathematics contained
herein is new, but I believe it all to be important, beautiful,
and accessible to undergraduate mathematics majors.  It is my hope
that this note will provide an opportunity for students in a first
real analysis course to see an example of a wonderful set theoretic
proof, and that it will emphasize consequences of certain set theoretic
assumptions.

In particular, we show 

\begin{theo} If there is a $\sigma$-additive  
measure on $\reals$, then the
Continuum Hypothesis fails.
\end{theo}

Thus here is a case where the existence of a measure-theoretic object
tells us something basic and  non-intuitive about the structure
of the set-theoretic universe.

\section{Set Theoretic Prerequisites}

In an effort to make this paper reasonably self-contained, I will remind
the reader of certain set-theoretic facts that he or she may have forgotten.
A countable set is a collection that can be placed in one-to-one
correspondence with the set of natural numbers.  Cantor proved that
the collection of real numbers is not countable, and he hypothesized
that the cardinality of the reals was exactly $\aleph_1$, the first
uncountable cardinal number.  This statement is the Continuum Hypothesis,
which we will show fails if there is a  
$\sigma$-additive measure on $\reals$.

The collection of 
 ordinal numbers can be defined by induction:  the empty set is
an ordinal (called 0); if $\alpha$ is an ordinal, then so is
$\alpha \union \{\alpha\}$ (called $\alpha + 1$); and if
$\{\alpha, \beta, \gamma,  \dotsc \}$ is any set of ordinals, 
then $\alpha \union \beta \union \gamma \union \dotsb $ is also an ordinal.  
This formal
 definition will be of less use to us than a picture of the first 
few ordinals.  (For a more complete development of ordinal and 
cardinal numbers, see any  book on axiomatic set theory,
for example  \cite{H}, \cite{Jech} or \cite{R}).  

Since 0 is an ordinal, so is $0\union\{0\}=
\emptyset\union\{\emptyset\}=\{\emptyset\}=\{0\}$; we call that 
ordinal 1.  Then, since 1 is an ordinal, so is
 $2=1\union\{1\}=\{0,1\}$ and, after a few iterations,
$42=\{0,1,2,\ldots,41\}$ is also an ordinal.  After a while we
notice that we have the collection of ordinals $\{0,1,2,\ldots\}$.  By our
second rule of construction, $0 \union 1 \union 2 \union \dotsb$ is
an ordinal, and the reader can easily check that 
$0 \union 1 \union 2 \union \dotsb = \{0,1,2,\dotsc\}$, the ordinal that
we will christen $\omega$.  
Then $\omega + 1 = \{0,1,2,\ldots , \omega\}$ is an 
ordinal, as is $\omega +2$, and so on.  By taking unions again we
can construct the ordinal
 $\{0,1,2,\ldots ,\omega, \omega+1, \omega+2, \ldots\}$, which we call
(naturally enough) $\omega + \omega$, or $\omega \cdot 2$.  And so on.
Thus the very rough picture of the ordinals that we have developed
 is a long string of numbers, stretched  out like this:
\[0,1,2,\ldots,\omega, \omega +1, \omega +2, \ldots, \omega \cdot 2, 
\omega \cdot 2 + 1, \ldots, \omega \cdot 3, \ldots, \omega \cdot \omega, 
\ldots \]

One fact about ordinals that should be noted is that each ordinal
is the set of all its ordinal predicessors.  In other words, if
$\alpha$ and $\beta$ are ordinals, then $\alpha < \beta $ if and
only if $\alpha \in \beta$.

Notice that each ordinal that we have constructed  is countable.
For example, the function $f:\omega \arrow \omega \cdot 2$ defined by
\[f(n) = \begin{cases} n/2& \text{if $n$ is even},\\
                       \omega + (n-1)/2 & \text{if $n$ is odd}
            \end{cases} \]
is a bijection between $\omega$ and $\omega \cdot 2$.  Fortunately, we
will only need countable ordinals for this paper, with one
exception.  If we look at the collection
of all countable ordinals,
$\{\,\alpha \mid \alpha $ is a countable ordinal$\,\}$, this set, called
 $\omega_1$, is an ordinal but is not countable.  If it were, then we would
have $\omega_1 \in \omega_1$, contradicting one of the basic
axioms of set theory.  In fact $\omega_1$ is the first uncountable
ordinal, since if $\beta < \omega_1$, then $\beta \in \omega_1$, and thus
$\beta$ is countable.  The Continuum
Hypothesis claims that the cardinality of $\reals$ is $\aleph_1$, in 
other words, that the set of real numbers can be placed in one-to-one
correspondence with the set of countable ordinals.

The Axiom of Choice is one of the more interesting (and more controversial)
axioms of set theory.  It states that if $I$ is a nonempty set and, for each
$i \in I$, $X_i$ is a nonempty set, then there is a function $f$ with domain
$I$ such that for each $i \in I$, $f(i) \in X_i$.  The function $f$ is
called a choice function, since it chooses one element from each $X_i$.  
We will assume the Axiom of Choice throughout our discussion.
One of the consequences of the Axiom of Choice is 
that if $\{A_\alpha\}_{\alpha
< \omega}$ is a
countable collection of sets, and if each $A_\alpha$ is countable, then
$\underset{\alpha
< \omega}{\union} A_\alpha $ is also countable.  In particular, this says that
if you take an uncountable set and partition it into countably many parts, one
of the parts must be uncountable.  The technical phrase is that $\aleph_1$ is
a ``regular'' cardinal.

\section{Measures}

We are quite familiar with the length of an interval of the real line,
and the idea of a measure on a set was developed to generalize that concept 
so as to give an idea of the ``length'' of more general sets.  


\begin{defi} A measure on a set $X$ is a function 
$\mu:{\cal P}(X) \arrow [0,1]$
such that

\begin{enumerate}

\item $\mu(\emptyset) = 0$; $\mu(X)=1$

\item $\mu(\{x\}) = 0$ for all $x \in X$

\item If $\{X_i\}$ is a countable collection of pairwise disjoint
subsets of $X$, then $\mu(\union X_i) = \sum \mu (X_i)$
\end{enumerate}
\end{defi}

Condition 3 in the above list is called $\sigma$-additivity, and  
is supposed to make explicit the idea that if you take disjoint intervals
of length 1/2, 1/4, 1/8, and so on, then the length of the union of your
collection ought to be 1.  Notice that
$\sigma$-additivity implies that if $A$ and $B$ are subsets of $X$ and
$A \subseteq B$, then $\mu(A) \leq \mu(B)$.  Also notice that, thanks
to Conditions 2 and 3, the measure of any countable set must
be 0.  

What has been presented is a rather set-theoretic definition of a measure.
Analysts will usually allow their measures to take values in the interval
$[0,\infty]$, and they will often allow point masses, and so conditions
(2) and the second part of (1) are ommitted.  

Analysts, when looking for
measures on $\reals$, also often demand that the measure be 
{\em translation invariant}:  
Suppose that we know the measure of a set $Y \subseteq \reals$, and
suppose that $Z$ is a translate of $Y$.  So the set $Z$ looks just like the
set $Y$ except that it has been shifted over by some amount.  Our measure
is translation invariant if
 the measure of $Z$ is the same as the measure of $Y$.
One of the many surprising consequences of
 the Axiom of Choice is that we cannot hope to
have a translation invariant measure on $\reals$.
  For a fine proof of this subtle but important fact, see 
\cite[pages 63--64]{Roy}.

The analyst's answer to this problem has been to construct a measure
$\mu$, called Lebesgue measure, 
that {\em is} translation invariant---but Lebesgue measure is
 not defined on {\em all} of the subsets
of $\reals$.  The analyst would say that there are non-measurable sets. 
A different approach to the problem would be to define a  
measure whose domain includes every  subset of $\reals$, but 
not to ask the measure to be translation invariant.  That is the tack that
we will take.  So let us assume for a moment that we have
such a measure  and let us also assume the Continuum Hypothesis.
  Since the Continuum Hypothesis implies that 
there is a bijection between $\reals$ and $\omega_1$, any measure on 
$\reals$ would (by composition of functions) give rise to a measure
on $\omega_1$.

\section{The Theorem}

Suppose we review where we stand now.  We are assuming that there is 
a  measure on $\reals$.  
If the Continuum Hypothesis were true, this would give rise to a
 measure on $\omega_1$.  Since the theorem says that the Continuum
Hypothesis is not true if there is a  measure on $\reals$, you will not be
surprised to see the following:

\begin{lem} There is no  measure on $\omega_1$.
\end{lem}

\begin{pf}  We assume that there is such a  measure and find a
contradiction.  Notice, for every countably infinite ordinal $\xi$, there
is a bijection mapping $ \omega$ to $\xi$.  Use the Axiom of Choice
to pick such a bijection, $f_\xi$, for each countable $\xi$.  Define,
for each ordinal $\alpha < \omega_1$ and each $n < \omega$, the set
$$A_{\alpha,n}=\{\,\xi \mid f_\xi(n)=\alpha\,\}.$$  Thus $A_{\alpha,n}$ is 
the collection of (indices of) functions that send $n$ to $\alpha$.  It
is convenient to think of the collection of $A_{\alpha,n}$'s in a matrix,
called an Ulam matrix, as follows:

\[
\begin{matrix}
A_{0,0}&A_{0,1}&A_{0,2}&\cdots&A_{0,n}&\cdots\\
A_{1,0}&A_{1,1}&A_{1,2}&\cdots&A_{1,n}&\cdots\\
&\vdots&&\cdots&\vdots\\
A_{\alpha,0}&A_{\alpha,1}&A_{\alpha,2}&\cdots&A_{\alpha,n}&\cdots\\
&\vdots&&\cdots&\vdots\\
\end{matrix}
\]

Notice that each row of the Ulam matrix is countable, while
each column of the matrix is uncountable.  There are two things which
need to be pointed out about the entries in the matrix.  The first is
that if $\alpha \neq \beta$, then $A_{\alpha,n} \intersect A_{\beta,n}=
\emptyset$.  This is true since  $A_{\alpha,n}$ codes up the collection of
functions that map $n$ to $\alpha$, while  $A_{\beta,n}$ codes the set of 
functions that map $n$ to $\beta$.  Since no function can map $n$ to
both $\alpha$ and $\beta$, the columns of the matrix are
collections of pairwise disjoint sets.

The second useful fact about the Ulam matrix  is 
that for each $\alpha < \omega_1$, if we let $B_\alpha =
\overset{\infty}{\underset{n=0}{\union}}A_{\alpha,n}$,
then $\omega_1 - B_\alpha$ is a
countable set.  To see that this is true, fix such an 
$\alpha$ and consider any
countable ordinal $\xi > \alpha$.  Since $f_\xi$ is a bijection between
$\omega$ and $\xi$, there must be some natural number $n$ such that
$f_\xi(n)=\alpha$.  In other words, for some $n$, $\xi \in A_{\alpha,n}$.
Thus $\omega_1 - B_\alpha
\subseteq \alpha \union \{\alpha\}$, and so 
$\omega_1 - B_\alpha$ is 
countable.

Now, our assumption has been that there is a  measure $\mu$ on $\omega_1$.
This means that $\mu(\omega_1) = 1$.  Since a countable set has
measure 0 and  $\omega-B_\alpha$
is countable for each $\alpha$, $\mu(B_\alpha) = 1$.
If the measure of each $A_{\alpha,n}$ was 0, then we would have
$\mu(B_\alpha)=0$, and so, for each $\alpha$, there is some $n$ such that
the measure of $A_{\alpha,n}$ is positive.  This means that there
are uncountably many  $A_{\alpha,n}$'s with positive measure while
there are only countably many columns in the Ulam matrix.  Using the
Axiom of Choice we see that 
 there is some number $\hat n$, such that for uncountably many $\alpha$,
$A_{\alpha,\hat n}$ has positive measure.  Take the collection of those
$A_{\alpha,\hat n}$'s with positive measure and 
partition it into countably many pieces, as follows:  those $A_{\alpha,\hat n}$
that have measure greater than 1/2, those that have measure between
1/2 and 1/3, those that have measure between 1/3 and 1/4, and so on.
Since we have partitioned this uncountable collection into countably many
parts, it is easy to see that  
at least one of the parts must be infinite.    But this leads to a 
contradiction:  Suppose infinitely many $A_{\alpha,\hat n}$'s have measure
greater than 1/17.  Since the $A_{\alpha,\hat n}$'s are pairwise disjoint,
the measure of the union of countably many of these large $A_{\alpha,\hat n}$'s
ought to be the sum of their measures.  But if we even take 18 of the
big $A_{\alpha,\hat n}$'s, the sum of their measures is at least 1.05, which
is greater than the
measure of $\omega_1$.  In general, if infinitely many $A_{\alpha,\hat n}$'s
have measure greater than $1/k$, then any $k+1$ of them would together
have measure greater than 1.  Thus we are led to conclude that there can be no
 measure on $\omega_1$.
\end{pf}


\section{What does it all mean?}

All of this is fine and good, but it continues to beg the question of
whether or not there is a  measure on $\reals$.  Unfortunately, the 
situation cannot be cleared up in a decisive way.  What is known is the 
following:  If the Axiom of Choice holds, we know that there is no
translation invariant $\sigma$-additive measure on $\reals$.  If we
are willing to jettison the Axiom of Choice we have a little more
freedom.  Recall that ZF is the Zermelo-Fraenkel set of axioms for
set theory, and ZFC is the axiom system ZF together with the
Axiom of Choice.  Robert Solovay has proven
(using the strong set-theoretic tool of forcing) that it is possible
to have a $\sigma$-additive translation-invariant 
measure on $\reals$, given certain large
cardinal hypotheses.  To be more precise, he proved that
if ``ZFC and there is an inaccessible cardinal'' is a consistent set of
axioms, then so is ``ZF and Dependent Choice and every set of reals
is Lebesgue measurable.''  (Dependent Choice is a weak version of the
Axiom of Choice).  

In 1984, Saharon Shelah published a proof that if ``ZF and Dependent Choice
and every set of reals is Lebesgue measurable'' is consistent, then so
is ``ZFC and there is an inaccessible cardinal.''  Since it is an easy
consequence of G\"{o}del's Theorem that ZFC cannot prove the consistency
of the existence of an inaccessible cardinal, this shows that to assume
that every set of reals is Lebesgue measurable is to make  an assumption
with strong set-theoretic consequences.  



\begin{thebibliography}{99}



\bibitem{H} K. Hrb\'{a}\v{c}ek and T. Jech, 
{\bf Introduction to Set Theory} (New York,
Marcel Dekker, 1984).

\bibitem{Jech} T. Jech, {\bf Set Theory} (New York, Academic Press, 1978).

\bibitem{K} A. Kanamori, {\bf The Higher Infinite},
preprint

\bibitem{Rai} J. Raisonnier, {\em A mathematical proof of S. Shelah's theorem
on the measure problem and related results}, Israel J. Math. {\bf 48} (1984),
48--56.

\bibitem{R} J. Roitman, {\bf Introduction to Modern Set Theory} (New York, 
John Wiley, 1990).

\bibitem{Roy} H. Royden, {\bf Real Analysis} (New York, Macmillan, 1968).

\bibitem{Shelah} S. Shelah, {\em Can you take Solovay's inaccessible away?},
Israel J. Math. {\bf 48} (1984), 1--47.

\bibitem{Solovay} R. Solovay, {\em A model of set theory in which every
set of reals is Lebesgue measurable}, Ann. of Math. (2) {\bf 92} (1970),
1--56.

\bibitem{Ulam} S. Ulam, {\em Zur Masstheorie in der allgemeinen Mengenlehre},
Fund. Math. {\bf 16} (1930), 140--150.

\bibitem{Ulam2} S. Ulam, {\em What is measure?}, Amer. Math. Monthly {\bf
50} (1943), 597--602.

\end{thebibliography}

\end{document}