PlanetMath: proof of Banach-Tarski paradox

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of Banach-Tarski paradox

(Proof)

We deal with some technicalities first, mainly concering 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 and with arbitrary origin, and $U\cup U'$ are equi-decomposable, regardless whether and 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

be sets such that

and

as well as

and

are equi-decomposable. Then there exist disjoint decompositions $A_1,\ldots A_n$ of

and $B_1,\ldots B_n$ of

such that

and

are congruent for $1\leq k\leq n$ . Furthermore, there exist disjoint decompositions $B_1',\ldots,B_m'$ of

and $C_1,\ldots C_m$ of

such that

and

are congruent for $1\leq l\leq m$ . Define

$\displaystyle B_{k,l}:=B_k\cap B_l'$ for $\displaystyle 1\leq k\leq n, 1\leq l\leq m.$

Now if

and

are congruent via some isometry $\theta\colon A_k\to B_k$ , we obtain a disjoint decomoposition of

by setting $A_{k,l}:=\theta^{-1}(B_{k,l})$ . Likewise, if

and

are congruent via some ismometry $\theta'\colon B_l'\to C_l$ , we obtain a disjoint decomposition of

by setting $C_{k,l}:=\theta'(B_{k,l})$ . Clearly, the $A_{k,l}$ and $C_{k,l}$ define a disjoint decomposition of

and

, respectively, into

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,

and

are equi-decomposable. $\qedsymbol$

Theorem 2 Given disjoint sets $A_1,,\ldots A_n$ , $B_1,\ldots B_n$ such that and are equi-decomposable for $1\leq k\leq n$ , their unions $A=\bigcup\limits _{k=1}^nA_k$ and $B=\bigcup\limits _{k=1}^nB_k$ are equi-decomposable as well.

Proof. By definition, there exists for every

, $1\leq k\leq n$ an integer

such that there are disjoint decompositions

$\displaystyle 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

and

in the form

$\displaystyle 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. $\qedsymbol$

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

Proof. Let $A_1,\ldots,A_n$ and $B_1,\ldots B_n$ be disjoint decompositions of

and

, respectively, such that

and

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

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

and

are congruent for $1\leq k\leq n$ , so the disjoint union $D:=D_1\cup\cdots\cup D_n$ and

are equi-decomposable. By construction, $\theta(C)=D$ . Since

is a proper subset of

and $\theta$ is bijective,

is a proper subset of

. $\qedsymbol$

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

Proof. Let $A_1,\ldots,A_n$ and $C_1,\ldots C_n$ disjoint decompositions of

and

, respectively, such that

and

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 ,
for all $x\in X\cap A$ , the image $\theta(x)$ lies in .

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

and

. Given $b'\in\mathcal {C}(b_1)$ , we have $b'=\theta^t(b_1)=\theta^{t+s-r}(b_2)$ for a suitable integer

, that is $b'\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

$\displaystyle 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

, 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 . Now $\theta^{-1}(c)\in\mathcal {C}(\theta^{-1}(c))$ , but since $\theta^{-1}(c)$ does lie in , it is not the final element. Therefore the subsequent element 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 and are disjoint.

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

The proof

We may assume that the unit ball

is centered at the origin, that is $U=\mathbb{B}_3$ , while the other unit ball

has an arbitrary origin. Let

be the surface of

, that is, the unit sphere. By the Hausdorff paradox, there exists a disjoint decomposition

$\displaystyle S=B'\cup C'\cup D'\cup E'$

such that

and $C'\cup D'$ are congruent, and

is countable. For

and $A\subseteq\mathbb{R}^3$ , let

be the set of all vectors of

multiplied by

. Set

$\displaystyle B:=\bigcup\limits _{0<r<1}rB',\quad C:=\bigcup\limits _{0<r<1}rC',\quad D:=\bigcup\limits _{0<r<1}rD',\quad E:=\bigcup\limits _{0<r<1}rE'.$

These sets give a disjoint decomposition of the unit ball with the origin deleted, and obviously

and $C\cup D$ are congruent (but

is of course not countable). Set

$\displaystyle A_1:=B\cup E\cup\{0\}$

where 0 is the origin.

and $C\cup D$ are trivially equi-decomposable. Since

and

as well as

and

are congruent, $C\cup D$ and $B\cup C$ are equi-decomposable. Finally,

and $C\cup D$ as well as

and

are congruent, so $B\cup C$ and $B\cup C\cup D$ are equi-decomposable. In total,

and $B\cup C\cup D$ are equi-decomposable by theorem 1, so

and

are equi-decomposable by theorem 2. Similarly, we conclude that

and $B\cup C\cup D$ are equi-decomposable.

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

$\displaystyle A_2:=D\cup G\cup\{p\},$

a disjoint union by construction. Since

and $B\cup C\cup D$ ,

and

as well as $\{0\}$ and $\{p\}$ are equi-decomposable,

and

are equi-decomposable by theorem 2.

and

are disjoint (but $A_1\cup A_2\neq U$ !).

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