PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] 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 $ U$ and $ U'$ with arbitrary origin, $ U$ and $ U\cup U'$ are equi-decomposable, regardless whether $ U$ and $ U'$ 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',\ldots,B_m'$ of $ B$ and $ C_1,\ldots C_m$ of $ C$ such that $ B_l'$ and $ C_l$ 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 $ A_k$ and $ B_k$ are congruent via some isometry $ \theta\colon A_k\to B_k$, we obtain a disjoint decomoposition of $ A_k$ by setting $ A_{k,l}:=\theta^{-1}(B_{k,l})$. Likewise, if $ B_l'$ and $ C_l$ are congruent via some ismometry $ \theta'\colon B_l'\to C_l$, we obtain a disjoint decomposition of $ C_l$ by setting $ C_{k,l}:=\theta'(B_{k,l})$. Clearly, the $ A_{k,l}$ and $ C_{k,l}$ define a disjoint decomposition of $ A$ and $ C$, respectively, into $ nm$ 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. $ \qedsymbol$


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}^nA_k$ and $ B=\bigcup\limits _{k=1}^nB_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
$\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 $ A$ and $ B$ 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 $ 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$. $ \qedsymbol$


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'\in\mathcal {C}(b_1)$, we have $ b'=\theta^t(b_1)=\theta^{t+s-r}(b_2)$ for a suitable integer $ t$, 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 $ 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. $ \qedsymbol$


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'$ 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
$\displaystyle S=B'\cup C'\cup D'\cup E'$    

such that $ B'$, $ C'$, $ D'$ and $ C'\cup D'$ are congruent, and $ E'$ is countable. For $ r>0$ and $ A\subseteq\mathbb{R}^3$, let $ rA$ be the set of all vectors of $ A$ multiplied by $ r$. 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 $ B$, $ C$, $ D$ and $ C\cup D$ are congruent (but $ E$ is of course not countable). Set
$\displaystyle 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'$ is only countable but there are uncountably many rotations of $ S$, 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 $ 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

$\displaystyle 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'$ are congruent, so $ U'$ and $ A_2$ are equi-decomposable by theorem 1. If $ U$ and $ U'$ are disjoint, set $ H:=A_2$. Otherwise we may use theorem 3 and choose $ H\subsetneq A_2$ such that $ H$ 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

$\displaystyle A_1\cup H\subseteq U\subseteq U\cup U',$    

so by theorem 4, $ U$ and $ U\cup U'$ are equi-decomposable.

Bibliography

BT
ST. BANACH, A. TARSKI, Sur la décomposition des ensembles de points en parties respectivement congruentes, Fund. math. 6, 244-277, (1924).



"proof of Banach-Tarski paradox" is owned by GrafZahl.
(view preamble)

View style:

See Also: Hausdorff paradox

Keywords:  Banach, Tarski

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: point, rotations, vectors, countable, Hausdorff paradox, unit sphere, surface, infinite, sequence, inclusion, image, preimage, intersection, proper subset, disjoint union, bijective, well-defined, map, integer, unions, congruence, isometry, congruent, transitivity, Euclidean space, subsets, equivalence relation, disjoint, equi-decomposable, origin, unit balls, argument, line, clear, paradox, properties

This is version 3 of proof of Banach-Tarski paradox, born on 2005-05-28, modified 2005-05-29.
Object id is 7123, canonical name is ProofofBanachTarskiParadox.
Accessed 2020 times total.

Classification:
AMS MSC03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)
 51M25 (Geometry :: Real and complex geometry :: Length, area and volume)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)