proof of Banach-Tarski paradox

We deal with some technicalities first, mainly concerning the properties of equi-decomposability. We can then prove the paradox in a clear and unencumbered line of argument: we show that, given two unit balls $U$ and $U^{\prime}$ with arbitrary origin, $U$ and $U\cup U^{\prime}$ are equi-decomposable, regardless whether $U$ and $U^{\prime}$ are disjoint or not. The original proof can be found in [BT].

Technicalities

Theorem 1.

Equi-decomposability gives rise to an equivalence relation on the subsets of Euclidean space.

Proof.

The only non-obvious part is transitivity. So let $A$ , $B$ , $C$ be sets such that $A$ and $B$ as well as $B$ and $C$ are equi-decomposable. Then there exist disjoint decompositions $A_{1},\ldots A_{n}$ of $A$ and $B_{1},\ldots B_{n}$ of $B$ such that $A_{k}$ and $B_{k}$ are congruent for $1\leq k\leq n$ . Furthermore, there exist disjoint decompositions $B_{1}^{\prime},\ldots,B_{m}^{\prime}$ of $B$ and $C_{1},\ldots C_{m}$ of $C$ such that $B_{l}^{\prime}$ and $C_{l}$ are congruent for $1\leq l\leq m$ . Define

B_{k,l}:=B_{k}\cap B_{l}^{\prime}\text{ for }1\leq k\leq n,1\leq l\leq m.

Now if $A_{k}$ and $B_{k}$ are congruent via some isometry $\theta\colon A_{k}\to B_{k}$ , we obtain a disjoint decomposition of $A_{k}$ by setting $A_{k,l}:=\theta^{-1}(B_{k,l})$ . Likewise, if $B_{l}^{\prime}$ and $C_{l}$ are congruent via some isometry $\theta^{\prime}\colon B_{l}^{\prime}\to C_{l}$ , we obtain a disjoint decomposition of $C_{l}$ by setting $C_{k,l}:=\theta^{\prime}(B_{k,l})$ . Clearly, the $A_{k,l}$ and $C_{k,l}$ define a disjoint decomposition of $A$ and $C$ , respectively, into $n m$ parts. By transitivity of congruence, $A_{k,l}$ and $C_{k,l}$ are congruent for $1\leq k\leq n$ and $1\leq l\leq m$ . Therefore, $A$ and $C$ are equi-decomposable. ∎

Theorem 2.

Given disjoint sets $A_{1},,\ldots A_{n}$ , $B_{1},\ldots B_{n}$ such that $A_{k}$ and $B_{k}$ are equi-decomposable for $1\leq k\leq n$ , their unions $A=\bigcup\limits_{k=1}^{n}A_{k}$ and $B=\bigcup\limits_{k=1}^{n}B_{k}$ are equi-decomposable as well.

Proof.

By definition, there exists for every $k$ , $1\leq k\leq n$ an integer $l_{k}$ such that there are disjoint decompositions

A_{k}=\bigcup\limits_{i=1}^{l_{k}}A_{k,i},\qquad B_{k}=\bigcup\limits_{i=1}^{l% _{k}}B_{k,i}

such that $A_{k,i}$ and $B_{k,i}$ are congruent for $1\leq i\leq l_{k}$ . Rewriting $A$ and $B$ in the form

A=\bigcup\limits_{k=1}^{n}\bigcup\limits_{i=1}^{l_{k}}A_{k,i},\qquad B=\bigcup% \limits_{k=1}^{n}\bigcup\limits_{i=1}^{l_{k}}B_{k,i}

gives the result. ∎

Theorem 3.

Let $A$ , $B$ , $C$ be sets such that $A$ and $B$ are equi-decomposable and $C\subsetneq A$ , then there exists $D\subsetneq B$ such that $C$ and $D$ are equi-decomposable.

Proof.

Let $A_{1},\ldots,A_{n}$ and $B_{1},\ldots B_{n}$ be disjoint decompositions of $A$ and $B$ , respectively, such that $A_{k}$ and $B_{k}$ are congruent via an isometry $\theta_{k}\colon A_{k}\to B_{k}$ for all $1\leq k\leq n$ . Let $\theta\colon A\to B$ a map such that $\theta(x)=\theta_{k}(x)$ if $x\in A_{k}$ . Since the $A_{k}$ are disjoint, $\theta$ is well-defined everywhere. Furthermore, $\theta$ is obviously bijective. Now set $C_{k}:=C\cap A_{k}$ and define $D_{k}:=\theta_{k}(C_{k})$ , so that $C_{k}$ and $D_{k}$ are congruent for $1\leq k\leq n$ , so the disjoint union $D:=D_{1}\cup\cdots\cup D_{n}$ and $C$ are equi-decomposable. By construction, $\theta(C)=D$ . Since $C$ is a proper subset of $A$ and $\theta$ is bijective, $D$ is a proper subset of $B$ . ∎

Theorem 4.

Let $A$ , $B$ and $C$ be sets such that $A$ and $C$ are equi-decomposable and $A\subseteq B\subseteq C$ . Then $B$ and $C$ are equi-decomposable.

Proof.

Let $A_{1},\ldots,A_{n}$ and $C_{1},\ldots C_{n}$ disjoint decompositions of $A$ and $C$ , respectively, such that $A_{k}$ and $C_{k}$ are congruent via an isometry $\theta_{k}$ for $1\leq k\leq n$ . Like in the proof of theorem 3, let $\theta\colon A\to C$ be the well-defined, bijective map such that $\theta(x)=\theta_{k}(x)$ if $x\in A_{k}$ . Now, for every $b\in B$ , let $\mathcal{C}(b)$ be the intersection of all sets $X\subseteq B$ satisfying

•

$b\in X$ ,
•

for all $x\in X$ , the preimage $\theta^{-1}(x)$ lies in $X$ ,
•

for all $x\in X\cap A$ , the image $\theta(x)$ lies in $X$ .

Let $b_{1},b_{2}\in B$ such that $\mathcal{C}(b_{1})$ and $\mathcal{C}(b_{2})$ are not disjoint. Then there is a $b\in\mathcal{C}(b_{1})\cap\mathcal{C}(b_{2})$ such that $b=\theta^{r}(b_{1})=\theta^{s}(b_{2})$ for suitable integers $s$ and $r$ . Given $b^{\prime}\in\mathcal{C}(b_{1})$ , we have $b^{\prime}=\theta^{t}(b_{1})=\theta^{t+s-r}(b_{2})$ for a suitable integer $t$ , that is $b^{\prime}\in\mathcal{C}(b_{2})$ , so that $\mathcal{C}(b_{1})\subseteq\mathcal{C}(b_{2})$ . The reverse inclusion follows likewise, and we see that for arbitrary $b_{1},b_{2}\in B$ either $\mathcal{C}(b_{1})=\mathcal{C}(b_{2})$ or $\mathcal{C}(b_{1})$ and $\mathcal{C}(b_{2})$ are disjoint. Now set

D:=\{b\in B\mid\mathcal{C}(b)\subseteq A\},

then obviously $D\subseteq A$ . If for $b\in B$ , $\mathcal{C}(b)$ consists of the sequence of elements $\ldots,\theta^{-1}(b),b,\theta(b),\ldots$ which is infinite in both directions, then $b\in D$ . If the sequence is infinite in only one direction, but the final element lies in $A$ , then $b\in D$ as well. Let $E:=\theta(D)$ and $F:=B\setminus D$ , then clearly $E\cup F\subseteq C$ .

Now let $c\in C$ . If $c\notin E$ , then $\theta^{-1}(c)\notin D$ , so $\mathcal{C}(\theta^{-1}(c))$ consists of a sequence $\ldots,\theta^{-2}(c),\theta^{-1}(c),\ldots$ which is infinite in only one direction and the final element does not lie in $A$ . Now $\theta^{-1}(c)\in\mathcal{C}(\theta^{-1}(c))$ , but since $\theta^{-1}(c)$ does lie in $A$ , it is not the final element. Therefore the subsequent element $c$ lies in $\mathcal{C}(\theta^{-1}(c))$ , in particular $c\in B$ and $\mathcal{C}(c)=\mathcal{C}(\theta^{-1}(c))\not\subseteq A$ , so $c\in B\setminus D=F$ . It follows that $C=E\cup F$ , and furthermore $E$ and $F$ are disjoint.

It now follows similarly as in the preceding proofs that $D$ and $E=\theta(D)$ are equi-decomposable. By theorem 2, $B=D\cup F$ and $C=E\cup F$ are equi-decomposable. ∎

The proof

We may assume that the unit ball $U$ is centered at the origin, that is $U=\mathbb{B}_{3}$ , while the other unit ball $U^{\prime}$ has an arbitrary origin. Let $S$ be the surface of $U$ , that is, the unit sphere. By the Hausdorff paradox, there exists a disjoint decomposition

S=B^{\prime}\cup C^{\prime}\cup D^{\prime}\cup E^{\prime}

such that $B^{\prime}$ , $C^{\prime}$ , $D^{\prime}$ and $C^{\prime}\cup D^{\prime}$ are congruent, and $E^{\prime}$ is countable. For $r>0$ and $A\subseteq\mathbb{R}^{3}$ , let $r A$ be the set of all vectors of $A$ multiplied by $r$ . Set

B:=\bigcup\limits_{0<r<1}rB^{\prime},\quad C:=\bigcup\limits_{0<r<1}rC^{\prime% },\quad D:=\bigcup\limits_{0<r<1}rD^{\prime},\quad E:=\bigcup\limits_{0<r<1}rE% ^{\prime}.

These sets give a disjoint decomposition of the unit ball with the origin deleted, and obviously $B$ , $C$ , $D$ and $C\cup D$ are congruent (but $E$ is of course not countable). Set

A_{1}:=B\cup E\cup\{0\}

where $0$ is the origin. $B$ and $C\cup D$ are trivially equi-decomposable. Since $C$ and $B$ as well as $D$ and $C$ are congruent, $C\cup D$ and $B\cup C$ are equi-decomposable. Finally, $B$ and $C\cup D$ as well as $C$ and $B$ are congruent, so $B\cup C$ and $B\cup C\cup D$ are equi-decomposable. In total, $B$ and $B\cup C\cup D$ are equi-decomposable by theorem 1, so $A_{1}$ and $U$ are equi-decomposable by theorem 2. Similarly, we conclude that $C$ , $D$ and $B\cup C\cup D$ are equi-decomposable.

Since $E^{\prime}$ is only countable but there are uncountably many rotations of $S$ , there exists a rotation $\theta$ such that $\theta(E^{\prime})\subsetneq B^{\prime}\cup C^{\prime}\cup D^{\prime}$ , so $F:=\theta(E)$ is a proper subset of $B\cup C\cup D$ . Since $C$ and $B\cup C\cup D$ are equi-decomposable, there exists by theorem 3 a proper subset $G\subsetneq C$ such that $G$ and $F$ (and thus $E$ ) are equi-decomposable. Finally, let $p\in C\setminus G$ an arbitrary point and set

A_{2}:=D\cup G\cup\{p\},

a disjoint union by construction. Since $D$ and $B\cup C\cup D$ , $G$ and $E$ as well as $\{0\}$ and $\{p\}$ are equi-decomposable, $A_{2}$ and $U$ are equi-decomposable by theorem 2. $A_{1}$ and $A_{2}$ are disjoint (but $A_{1}\cup A_{2}\neq U$ !).

Now $U$ and $U^{\prime}$ are congruent, so $U^{\prime}$ and $A_{2}$ are equi-decomposable by theorem 1. If $U$ and $U^{\prime}$ are disjoint, set $H:=A_{2}$ . Otherwise we may use theorem 3 and choose $H\subsetneq A_{2}$ such that $H$ and $U^{\prime}\setminus U$ are equi-decomposable. By theorem 2, $A_{1}\cup H$ and $U\cup(U^{\prime}\setminus U)=U\cup U^{\prime}$ are equi-decomposable. Now we have

A_{1}\cup H\subseteq U\subseteq U\cup U^{\prime},

so by theorem 4, $U$ and $U\cup U^{\prime}$ are equi-decomposable.

References

BT St. Banach, A. Tarski, Sur la décomposition des ensembles de points en parties respectivement congruentes, Fund. math. 6, 244–277, (1924).

Title	proof of Banach-Tarski paradox
Canonical name	ProofOfBanachTarskiParadox
Date of creation	2013-03-22 15:19:03
Last modified on	2013-03-22 15:19:03
Owner	GrafZahl (9234)
Last modified by	GrafZahl (9234)
Numerical id	7
Author	GrafZahl (9234)
Entry type	Proof
Classification	msc 51M25
Classification	msc 03E25
Related topic	HausdorffParadox