Friday, March 22, 2013

Banach-Tarski Paradox

The Banach-Tarski paradox is a very counterintuitive theorem in geometry that, in effect, states that a three-dimensional ball can be broken up and reassembled in such a way that two identical balls of the same size as the first are formed. This "doubling" of the ball seems contrary to the usual ideas of Euclidean geometry, and is therefore exemplifies the controversy over its underlying assumption, the axiom of choice.

The axiom of choice is one of the most debated topics in mathematics. It is an axiom of set theory, and the debate is whether it is right to assume it, and in what "strength" or version. The axiom itself, put informally, runs thus:

From any collection of nonempty sets, there exists a way to choose exactly one member from each set.

The ability to make such choice seems intuitive enough, but as seen elsewhere on this blog, the assumption of the axiom of choice implies the existence of sets that have no "volume", i.e. their size cannot be measured in any way. And this, as we shall see, is a crucial concept needed to derive the Banach-Tarski paradox.

The "translation" of the paradox into set theoretical concepts involves treating the three-dimensional ball as a set, call it A. We consider a division of the ball as a partition of the set A into the subsets A1, A2,...,An, where none of the subsets overlap, or in set notation, where AiAj = Ø whenever ij (i and j run from 1 to n). In this decomposition, n is finite, and only a finite number of pieces are needed to transform one ball into two. This in itself makes the paradox even more unbelievable.

After the ball is partitioned, each piece would then undergo a translation (some movement in space) and a rotation, taking each subset Ai to a corresponding Bi. In this translation, the intrinsic properties of the subsets are not altered; they are simply rearranged in space. The resulting sets, B1,...,Bn, can be split into two groups in such a way that B1B2∪...∪Bm is a ball congruent to the first, and the union of remaining subsets, Bm + 1∪...∪Bn, is another ball also congruent to the original one. The transformation is illustrated below:



Since Euclidean translations and rotations preserve volume, the Banach-Tarski paradox violates the principle of the additivity of volume, i.e., that the sum of the volumes of two disjoint sets is the volume of their unions. The beginning ball and the (union of) two equivalent balls are composed of the same (translated) pieces, but they have different volumes. The reason this principle is violated is that the sets in question are non-measurable, or cannot be assigned a volume by any measure. Therefore, the idea of volume additivity has no meaning for them. Non-measurable sets, in addition, can only be proved to exist with the axiom of choice or an equivalent statement. We shall assume the existence of these non-measurable sets, but a construction of such a set under the Lebesgue measure can be found here.

The proof of the Banach-Tarski paradox at first does not work directly with the ball, but instead deals with a more abstract group of points. As we shall see, the decomposition of this abstract set can be performed analogously on the ball with slight modifications.

The abstract set in question is called the free group of two generators, or F2, and it refers, in effect, to the set of strings of the symbols a and b, as well as their inverses, a-1 and b-1. For example, the strings aba-1b and bba-1baa are members of F2. We also define e, or the empty string, as the string in F2 with no members. Finally, we define an operation, *, on strings in F2 that combines two strings into one by placing the second directly after the first. Therefore ab-1*b-1aab = ab-1b-1aab. Additionally, strings are simplified by two rules, where x stands for any string in F2:
  1. ex = xe = x
  2. aa-1 = a-1a = bb-1 = b-1b = e
As an example of the above rules, consider the product (under the operation *) of the strings a-1bab and b-1a-1bab-1.

a-1bab*b-1a-1bab-1 = a-1babb-1a-1bab-1 = a-1baea-1bab-1 = a-1baa-1bab-1 = a-1bebab-1 = a-1bbab-1

The group F2 can be visualized in several ways. One is as an infinite "tree" of elements, where points on the tree represent strings and "branches" describe the construction of these strings. Below is one example of such a visualization.



A tree of this type is called a Cayley graph of the group F2. Illustrated are the strings of F2 up to three symbols in length. The segments connecting the strings (black dots) illustrate the addition of a symbol to the right of the existing string. One begins in the center with e, the empty string, and moves right to add an "a" and up to add a "b". Moving oppositely to either of the above directions appends an inverse of the corresponding symbol. Note that tracing a path and then retracing backward produces a symbol adjacent to its inverse, causing cancellation. The construction of the string ba-1b-1 is illustrated; staring at e, one first proceeds upward, then left, then down. The reader can verify this construction.

The decomposition of F2 requires the use of some new notation. By S(a) denote the set of all strings in F2 beginning with the symbol a. Define the expression similarly in the case that a-1, b, and b-1, respectively, are substituted for a. Next, the notation, aS(a-1), for example, refers to the set of strings produced by joining the string "a", with a member of the set S(a-1). Thus there is a string in aS(a) for every string in S(a). It must be made clear, however, that the set S(a) and the other related sets contain only simplified strings. Nowhere in any string in S(a) will there appear a term "aa-1" or "bb-1", as these will have already been cancelled.

Armed with these notions, we can construct the "paradoxical" decomposition of F2. The first step is a simple decomposition involving separating the group into each of four disjoint quadrants, the sets S(a), S(a-1), S(b), and S(b-1), and the set {e}, consisting only of the empty string.

The next operation required is a "shift" of the set S(a-1) by the element a into the set aS(a-1), which, as discussed above, has as members every string obtained by adjoining a, (through the operation *) on the left, to some member of S(a-1). The significance of this shift in relation to the sphere will be apparent later. This shifted set is interesting because, when a is combined with a string beginning with a-1, the two elements cancel. Since, in S(a-1), the second and subsequent symbols of each member are arbitrary, every string beginning with a-1, b, or b-1 is a member of aS(a-1). For example, the string bab-1 is the same as a combined with a-1bab-1, a member of S(a-1). Also, strings beginning with a-1 such as a-1bb can be formed as the combination of a and a suitable string beginning with "a-1a-1", in this case a-1a-1bb. Finally, since a-1 is obviously a member of S(a-1), the string aa-1 = e is therefore a member of aS(a-1). In fact, the only strings that are not included in aS(a-1) (ironically) are those beginning with a! This is because, for this to occur, the second element of a member of S(a-1) would have to be a, and this cannot occur, as all strings in S(a-1) are assumed to be simplified.



The above is another view of the Cayley graph, this time illustrating the quadrant S(a-1) along with the shifted set aS(a-1). The only strings not members of the latter set belong to S(a). Therefore, the group F2 is a union of aS(a-1) and S(a). A similar procedure, substituting b for a, leads to the conclusion that the union of bS(b-1) and S(b) is again F2. In summary,

F2 = {e}∪S(a)∪S(a-1)∪ S(b)∪S(b-1) = aS(a-1)∪S(a) = bS(b-1)∪S(b).

The sets S(a-1) and S(b-1) from the original have been shifted by a and b, respectively, and been incorporated into two other decompositions of the same group F2. One copy of F2 has been made into two. (One might well wonder "what happened to {e}?" It turns out that this piece is simply discarded in the above procedure, but the scheme is modified slightly in application to the ball to correct this subtlety).

The relation between F2 and the three-dimensional ball, as well as other extensions of the paradox, are found in another post.

Sources: http://www.kuro5hin.org/story/2003/5/23/134430/275, Banach-Tarski Paradox on Wikipedia

No comments: