%&latex209
\documentstyle[amssymb,amsfonts]{amsart}

% \usepackage{amsmath}
% \usepackage{amsthm}
% \usepackage{amsfonts}
% \usepackage{amssymb}


% \newcommand*{\Rd}{\ensuremath{\mathbb{R}}}                  % reals
\newcommand{\norm}[1]{ \left|  #1 \right| }
\newcommand{\Ecal}{{\cal E}}
\newcommand{\Tcal}{{\cal T}}
\newcommand{\ifof}{\Leftrightarrow}
\newcommand{\Norm}[1]{ \left\| #1 \right\| }
\renewcommand{\Re}{{\mbox{Re}}}
\def\be#1{\begin{equation} \label{#1}}
\def\bs{\begin{split}}
\def\bi{\begin{itemize}}
\def\es{\end{split}}
\def\ba{\begin{align}}
\def\bas{\begin{align*}}
\def\ea{\end{align}}
\def\eas{\end{align*}}
\def\grad{\nabla}
\def\R{{\mbox{\bf R}}}
\def\T{{\mbox{\bf T}}}
\def\m{m}
\def\dist{{\mbox{\rm dist}}}
\def\diam{{\mbox{\rm diam}}}
\def\supp{{\mbox{\rm supp}}}
\def\range{{\mbox{\rm range}}}
\def\ker{{\mbox{\rm ker}}}
\def\spn{{\mbox{\rm span}}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\Qcal{{\cal Q}}
\def\K{{\mbox{\bf K}}}
\def\D{{\mbox{\bf D}}}
\def\Z{{\mbox{\bf Z}}}
\def\eps{\varepsilon}
\def\pp{{p^\prime}}
\def\ppt{{\tilde p^\prime}}
\def\np{{n^\prime}}
\def\qp{{q^\prime}}
\def\lp{{l^\prime}}
\def\Qp{{Q^\prime}}
\def\PT{{\prod_{t=1}^2}}
\def\qpt{{\tilde q^\prime}}
\def\kp{{k^\prime}}
\def\mP{{m^\prime}}
\def\x{{\underline{x}}}
\newcommand{\qtil}{{\tildeq}}
\newcommand{\ktil}{{\tilde{k}}}
\newcommand{\ptil}{{\tilde{p}}}
\newcommand{\uxi}{{\overline{\xi}}}
% \def\lesssim{<_\sim}
\def\emph#1{{\it #1}}
\def\textbf#1{{\bf #1}}
\newenvironment{proof}{\noindent {\bf Proof} }{\endprf\par}
\def \endprf{\hfill  {\vrule height6pt width6pt depth0pt}\medskip}

% \swapnumbers
% \pagestyle{headings}

\theoremstyle{plain}
  \newtheorem{theorem}[subsection]{Theorem}
  \newtheorem{proposition}[subsection]{Proposition}
  \newtheorem{lemma}[subsection]{Lemma}
  \newtheorem{corollary}[subsection]{Corollary}
  \newtheorem{conjecture}[subsection]{Conjecture}
  \newtheorem{problem}[subsection]{Problem}

\theoremstyle{remark}
  \newtheorem{remark}[subsection]{Remark}
  \newtheorem{remarks}[subsection]{Remarks}

\theoremstyle{definition}
  \newtheorem{definition}[subsection]{Definition}

\include{psfig}

\begin{document}

\title{The Banach-Tarski paradox}

\author{Terence Tao}
\address{Department of Mathematics, UCLA, Los Angeles, CA 90024}
\email{tao@@math.ucla.edu}

\subjclass{42B15, 35L05}
\begin{abstract}
An exposition of the Banach-Tarski paradox.
\end{abstract}

\maketitle

\section{Introduction}

Let $SO(3)$ denote the group of rotation operators on $\R^3$.  The first version of the Banach-Tarski paradox, which we give below, shows that
we can find a group of rotations with the curious property that $G$ can be disassembled into four pieces, which after rotation can be reassembled to form two complete copies of $G$.

\begin{theorem}[Banach-Tarski paradox, first version]\label{bta}  There exists a countable subgroup $G$ of $SO(3)$, and a partition
$$ G = G_1 \uplus G_2 \uplus G_3 \uplus G_4 $$
into disjoint sets $G_1, G_2, G_3, G_4$, such that one can write
$$ G = G_1 \uplus A G_2 = G_3 \uplus B G_4$$
for some rotations $A, B \in SO(3)$.
\end{theorem}

\begin{proof}
We first need to find two rotation operators $A, B$ such that no non-trivial word from the alphabet $A, B, A^{-1}, B^{-1}$ gives the identity, where
``nontrivial'' means that the word is non-empty, that $A$ and $A^{-1}$ are never adjacent, and $B$ and $B^{-1}$ are never adjacent.  This is easily done but requires some algebra and we defer it to the Appendix.  Assuming we have these operators, we let $G$ be the subgroup of $SO(3)$ generated by $A, B, A^{-1}, B^{-1}$; this is thus the group of all non-trivial words using the alphabet $A, B, A^{-1}, B^{-1}$,
together with the empty word $I$, which is the identity.  In particular we have the partition
$$ G = \{I\} \cup G(A) \cup G(A^{-1}) \cup G(B) \cup G(B^{-1})$$
where $G(A)$ is the set of all non-trivial words in $G$ which start with $A$, etc.  Observe that
$$ G = G(A) \uplus A G(A^{-1}),$$
because every word in $G$ either starts with $A$, or is equal to $A$ times a non-trivial word beginning with $A^{-1}$, but never both.  Similarly we have
$$ G = G(B) \uplus B G(B^{-1}).$$
We are almost done, except that we have to deal with the empty word $I$.  But this is easily accomplished by defining
\begin{align*}
G_1 &:= G(A) \cup \{ I, A^{-1}, A^{-2}, A^{-3}, \ldots \} \\
G_2 &:= G(A^{-1}) \backslash \{ A^{-1}, A^{-2}, A^{-3}, \ldots \} \\
G_3 &:= G(B) \\
G_4 &:= G(B^{-1})
\end{align*}
and one easily verifies that all the claims of the theorem hold.
\end{proof}

Note that the above theorem did not require the axiom of choice.  However, the following corollary, which passes from the countable rotation group 
$G$ to most of the sphere $S^2$, does rely very much on the axiom of choice.

\begin{corollary}[Hausdorff paradox, first version]  There exists a countable subset $C$ of the sphere $S^2$, and a decomposition
$$ (S^2 \backslash C) = \Omega_1 \uplus \Omega_2 \uplus \Omega_3 \uplus \Omega_4$$
such that
$$ (S^2 \backslash C) = \Omega_1 \uplus A \Omega_2 = \Omega_3 \uplus B \Omega_4$$
for some rotation matrices $A, B \in SO(3)$.
\end{corollary}

\begin{proof} Let $A, B, G, G_1, G_2, G_3, G_4$ be as in Theorem \ref{bta}.  Each rotation in $G$ fixes two points on the sphere $S^2$ (the intersection of $S^2$ with the axis of the rotation); let $C$ be the union of all those fixed points.  Then the rotation group $G$ acts freely on
the complement $S^2 \backslash C$.  Thus, using the axiom of choice, one can foliate $S^2 \backslash C = \biguplus_{x \in X} Gx$ for some set $X$
(picking one representative from each $G$-orbit in $S^2 \backslash C$).  If one then sets $\Omega_i := \biguplus_{x \in X} G_i x$ then the claim
now follows from Theorem \ref{bta}.
\end{proof}

Next, we eliminate this countable set $C$, using the following simple lemma.

\begin{lemma}\label{countable-lemma}  Let $C$ be a countable subset of the sphere $S^2$.  Then there exists a decomposition
$$ S^2 = \Sigma_1 \uplus \Sigma_2$$
such that
$$ S^2 \backslash C = \Sigma_1 \uplus R \Sigma_2$$
for some rotation matrix $R \in SO(3)$.
\end{lemma}

\begin{proof}  Pick $R$ at random.  Since $C$ is countable, then with probability 1 we can ensure that any two elements of $C$ lie in distinct
$R$-orbits, i.e. $R^i C \cap R^j C = \emptyset$ whenever $i \neq j$.  We then set
$$ \Sigma_2 := C \cup RC \cup R^2 C \cup \ldots; \quad \Sigma_1 := S^2 \backslash \Sigma_2$$
and the claim follows.
\end{proof}

Combining this Lemma with the preceding corollary, we obtain

\begin{corollary} There exists a partition
$$ S^2 = \Gamma_1 \uplus \ldots \uplus \Gamma_8$$
and rotation matrices $R_1,\ldots,R_8 \in SO(3)$ such that
$$ S^2 = \biguplus_{i=1}^4 R_i \Gamma_i = \biguplus_{i=5}^8 R_i \Gamma_i.$$
\end{corollary}

Since the punctured ball $B^3 \backslash 0$ can be viewed in polar co-ordinates as the product of the sphere $S^2$ and
the interval $(0,1]$, we conclude

\begin{corollary}[Banach-Tarski paradox] There exists a partition
$$ B^3 \backslash \{0\} = E_1 \uplus \ldots \uplus E_8$$
and rotation matrices $R_1,\ldots,R_8 \in SO(3)$ such that
$$ B^3 \backslash \{0\}= \biguplus_{i=1}^4 R_i E_i = \biguplus_{i=5}^8 R_i E_i.$$
\end{corollary}

Of course, at least one of the $E_i$ has to be non-Lebesgue measurable.  One can eliminate the puncture at the origin if one allows translations
as well as rotations, by using a trick similar to that used to prove Lemma \ref{countable-lemma}; we leave this as an exercise to the reader.

\section{Appendix: the algebraic bit}\label{appendix} 

We now give the rotation operators $A, B \in SO(3)$ needed to prove Theorem \ref{bta}.  
It turns out that we can give very explicit matrices, namely
$$ A(x,y,z) := (\frac{3}{5}x + \frac{4}{5} y, -\frac{4}{5} x + \frac{3}{5} y, z ); \quad
B(x,y,z) := (x, \frac{3}{5}y + \frac{4}{5} z, -\frac{4}{5} y + \frac{3}{5} z ).$$
These are easily seen to be rotation matrices with inverses
$$ A^{-1}(x,y,z) := (\frac{3}{5}x - \frac{4}{5} y, \frac{4}{5} x + \frac{3}{5} y, z ); \quad
B^{-1}(x,y,z) := (x, \frac{3}{5}y - \frac{4}{5} z, \frac{4}{5} y + \frac{3}{5} z ).$$

Now we claim that no non-trivial composition of $A, B, A^{-1}, B^{-1}$ gives the identity.  It suffices to show that no non-trivial composition
of the operators $5A$, $5B$, $5A^{-1}$, $5B^{-1}$ gives a linear operator whose coefficients are all divisible by 5.
We now work in the finite field geometry $F_5^3$, where $F_5 = \Z/5\Z$ is the field of order 5.  Then we have
$$ 5A(x,y,z) := (3x + 4y, -4x + 3y, 0); \quad 5B(x,y,z) := (0, 3y + 4z, -4y + 3z)$$
and
$$ 5A^{-1}(x,y,z) := (3x - 4y, 4x + 3y, 0); \quad 5B^{-1}(x,y,z) := (0, 3y - 4z, 4y + 3z).$$
Each of these operators are rank one operators in $F_5^3$:
\begin{align*}
\range(5A) &= \spn( (3,-4,0) ) = \ker(5A^{-1})^\perp\\
\range(5A^{-1}) &= \spn( (3,4,0) ) =  \ker(5A)^\perp\\
\range(5B) &= \spn( (0,3,-4) ) = \ker(5B^{-1})^\perp\\
\range(5B^{-1}) &= \spn( (0,3,4) ) = \ker(5B)^\perp.
\end{align*}
From this we see that any non-trivial combination of $5A$, $5A^{-1}$, $5B$, $5B^{-1}$ (in which $5A$ and $5A^{-1}$ are never
adjacent, and $5B$ and $5B^{-1}$ are never adjacent) will always be a non-zero operator, as desired, because the ranges and kernels are skew.


\end{document}
\endinput