Chapter 18

THE BANACH–TARSKI PARADOX

God exists since mathematics is consistent, and the Devil exists since we cannot prove it.

Andre Weil

The subject matter of this last chapter simply has to rank as the most counterintuitive result in mathematics and is a fitting finalé to a book devoted to mathematical surprise.

Stefan Banach and Alfred Tarski brought to the world an improvement on a paradox devised by the great topologist Felix Hausdorff, the formalized form of which is often replaced by something fanciful such as:

A solid sphere can be dissected into five pieces and the pieces reassembled to form two complete spheres of exactly the same size as the original.

Or, alternatively:

A solid sphere the size of a pea can be dissected into finitely many pieces which can be rearranged using rotations and translations to form a solid sphere the size of the Sun.

To those who have not seen the result(s) before, it must seem as if there is a misprint—or that the author has allowed himself to become a little too carried away. Actually, what has been written above is true and we will attempt to give the reader some flavour of why it is so.

Formalization

We must formalize things, and to that end we define the Euclidean ‘3 ball’ of radius r, B_r, by and agree that a rigid motion of is a transformation R which preserves Euclidean distance (i.e. is such that for all points x, y , |x − y| = |R(x) − R(y)|. Now we can state the results more formally as:

There exists a decomposition of B_r into five pairwise disjoint sets A₁, A₂, A₃, A₄, A₅ (of which the last is a single point) such that there exist rigid motions R₁, R₂, R₃, R₄, R₅ with B_r = R₁(A₁) ∪ R₂(A₂) and B_r = R₃(A₃) ∪ R₄(A₄) ∪ R₅(A₅), where all unions are disjoint.

Or:

For any two distinct positive integers m and n, B_m can be split into a disjoint union of sets A₁, . . ., A_n such that there exist rigid motions R₁, . . ., R_n so that B_n = R₁(A₁) ∪ R₂(A₂) ∪ . . . ∪ R_n(A_n), where all the unions are disjoint.

There is also its most general form in :

Any two bounded subsets of (with nonempty interior) can be dissected and reassembled each to form the other.

Given that these three statements are true (and indeed they are), one must expect a catch (otherwise it would not have taken Jesus Christ to supposedly feed the five thousand with five loaves and eight fishes): the catch is that in this case the proof is non-constructive, it demonstrates existence without revealing how to achieve the aim. It also demonstrates that this is intrinsically a mathematical result and it cannot actually be realized. Put another way, in the decomposition, the pieces will not be measurable and so they will not have reasonable boundaries or a well-defined volume in the accepted sense of the term. More plainly, it is impossible to carry out the dissection since cutting with a knife creates only measurable sets.

The Axiom of Choice

At the heart of the proof of the result lies the axiom of choice. This most deceptive statement, formulated about a century ago by the mathematical logician Ernst Zermelo, simply states that

In any collection of nonempty sets, we can form a new set by choosing a member from each set in that collection.

It seems very obvious that such a thing is possible, but everything depends on what we mean by the word choosing. For example, for any finite collection of nonempty sets we can form a new set by choosing the first element of each of the sets. Moving to infinite sets could be more problematic, but consider the collection of all nonempty subsets of the natural numbers {0, 1, 2, 3, . . .}, then we can form our new set by choosing the smallest element in each set. A little more subtly, consider the collection of all nonempty subintervals of (0, 1), there remains no problem since we can form our new set by choosing the midpoint of each interval. So where is the problem? Actually, so far there isn’t one, since the axiom of choice has not come into play; in each case we had a rule for doing the choosing. Now, for example, take the collection of all nonempty subsets of , in which case there is no consistent procedure for choosing the elements and thereby populating our set from the infinite number of subsets. Now we need that guarantee, provided by the axiom of choice, which simply states that there is some procedure which allows us to choose an element from each set in the collection—and never mind what the procedure is; it gives no indication of how the choosing would be done; it simply guarantees the existence of that choice. Notice also that it is called an axiom; that is, it is an assumption. It has been shown that, if the standard axioms of set theory are consistent without the axiom of choice, they remain so if it is included. This means that we can have one system of mathematical logic in which the axiom features and a completely different one in which it does not (rather like the geometries arising for the parallel postulate, mentioned on page 70).

The axiom has many equivalent forms, some (subjectively) more ‘obviously true’ than others, possibly the most important of which are the well-ordering principle and the considerably more enigmatic Zorn’s Lemma:

The well-ordering principle. A set is said to be well ordered if every subset of it has a first element. The well-ordering principle states that every set can be well ordered (which we came across in the previous chapter).

Zorn’s Lemma. Every partially ordered set in which every totally ordered subset has an upper bound contains at least one maximal element.

We will leave the interested reader to dissect this, but this is enough to appreciate mathematician Jerry Bona’s quip about these entirely equivalent statements:

The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn’s Lemma?

Groups

The axiom of choice is not alone sitting at the heart of the proof of the paradox; that proof also relies fundamentally on the concept of a group, and in particular a free group on two generators and also that of a rotation group—and here is where problems of exposition begin to become overwhelming. It is impossible in such a tiny space to give anything like a representative overview of the fundamental algebraic abstraction of a group, the minimal system required for useful abstract algebra to exist. The definition is itself minimal though, but it efficiently conceals the great significance of the idea: a group G is any set of objects, together with a law of combination (*), which satisfy:

1. For all a, b G, a * b G (closure).

2. For all a G, there exists an element ε G so that a * ε = ε * a = a (identity element).

3. For each a G, there exists an element a⁻¹ G so that a * a⁻¹ = a⁻¹ * a = ε (inverse elements).

4. For all a, b, c G, a * (b * c) = (a * b) * c (associativity).

As the prototype case just consider the set of all integers with * replaced by +, ε by 0 and a⁻¹ by −a.

Notice that the definition does not include the assumption of commutivity, that is, it is not assumed that a * b = b * a, although this might be the case.

A particular case of a group is one which is formed by formally combining any number of abstract symbols (generators), with or without a law or laws which specify how combinations of elements should be simplified; if no such law exists such a group has the name of a free group on however many generators there might be. For example, the free group on two generators a and b consists of all finite strings that can be formed from the five symbols ε, a, a⁻¹, b, b⁻¹ (inverses have to be included) such that no a appears directly next to an a⁻¹ and no b appears directly next to a b⁻¹ (since these must both simplify to ε). Two such strings can be concatenated and simplified to a string of this type by repeatedly making use of the cancellation brought about by combining an element with its inverse wherever possible. For instance, aba⁻¹b⁻¹a concatenated on the right with a⁻¹ba⁻¹b⁻¹a results in

aba⁻¹b⁻¹aa⁻¹ba⁻¹b⁻¹a = aba⁻¹a⁻¹b⁻¹a.

We will represent this group by the letter G; it is such a group that is required for the Banach–Tarski paradox to be established. (For the sake of contrast, a condition that might be placed on a group on two generators might be a way of rewriting the element ba, for example, ba = a²b.)

The Paradox

The group G can be ‘paradoxically decomposed’ as follows. Let S(a) be the set of all strings that start with a and define S(a⁻¹), S(b) and S(b⁻¹) similarly. Since every element of G must either be ε or start with one of these four symbols, it must be the case that

G = {ε} ∪ S(a) ∪ S(a⁻¹) ∪ S(b) ∪ S(b⁻¹),

but notice that G can also be divided into S(a) and the rest of the elements—and that these are all elements which do not begin with a and which can therefore be written as aS(a⁻¹); this means that G can also be written in the form G = aS(a⁻¹) ∪ S(a) and for the same reason G = bS(b⁻¹) ∪ S(b). This seemingly simple observation will bring about the paradox.

Now we realize G as a group of rotations of by choosing two perpendicular axes and defining element a to be a rotation of cos⁻¹ about the first and b to be a rotation of cos⁻¹ about the second—a step which cannot be performed in two dimensions. It is not obvious but these do form our free group on two generators and the paradoxical decomposition above applies to this form of G.

Now apply G to the sphere by taking points on it and rotating them accordingly and collect together all points x₁, x₂ which are such that x₁ = gx₂ for some g G; that is, we partition the sphere into orbits brought about by the action of G, with two points belonging to the same orbit if and only if there is a rotation in G which moves the first point into the second. Now we need that axiom of choice. Use it to pick exactly one point from every orbit and let these points form a set X. It is the case that almost every point in S_r can be reached in exactly one way by applying the proper rotation from G to the proper element from X and, because of this, the paradoxical decomposition of G then yields a paradoxical decomposition of S_r.

Finally, connect every point on S_r with a ray to the origin and so generate an infinite number of spheres; the paradoxical decomposition of S_r then yields a paradoxical decomposition of the solid unit ball—minus the origin, but that is where ε comes in.

And there is the famous Banach–Tarski paradox ‘proved’! There may not be any holes left in the decomposition of the sphere, but there are a number in the details of the above, but they are matters of detail and can be patched up to a complete and rigorous proof.

It is interesting to note that the proof depends on three dimensions (with that group of rotations); while intuitively the two-dimensional case seems to be easier, it is in fact not true that all bounded subsets of the plane with nonempty interior are capable of being dissected one to the other. There is one in particular which does exist though: a circular disc can be cut into finitely many pieces and reassembled to form a square of equal area—the ‘circle-squares’ were in some sense correct after all. The challenge to establish a way of doing this was posed by Tarski in 1925 and it took until 1990 to answer it, when Miklos Laczkovich proved it possible—using about 10⁵⁰ different pieces.

So, the result is not practical, but the late Ralph P. Boas Jr found a use for it in his amusing and eclectic book (published in 1996 by Mathematical Association of America) Lion Hunting and Other Mathematical Pursuits. A Collection of Mathematics, Verse and Stories, in which over thirty different ‘proven’ methods are given to capture a lion. (The book was an expansion of the famous spoof paper ‘A contribution to the mathematical theory of big game hunting’ by one H. Petard, 1938, American Mathematical Monthly 45:446–47.) The one relevant to us is his idea to apply the Banach–Tarski decomposition to the lion, put the pieces back together to form a feline the size of a domesticated cat (from which we may expect only minor harm). Then hunt it fearlessly, capture it and after caging the beast, use the Banach–Tarski decomposition once again to rearrange the pieces into their original configuration!

If nothing else in this book was considered Impossible by the reader, it is hoped that this result might just have saved the author’s day.