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

*A*

_{1},

*A*

_{2},...,

*A*

_{n}, where none of the subsets overlap, or in set notation, where

*A*

_{i}∩

*A*= Ø whenever

_{j}*i*≠

*j*(

*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

*A*

_{i}to a corresponding

*B*

_{i}. In this translation, the intrinsic properties of the subsets are not altered; they are simply rearranged in space. The resulting sets,

*B*

_{1},...,

*B*

_{n}, can be split into two groups in such a way that

*B*

_{1}∪

*B*

_{2}∪...∪

*B*

_{m}is a ball congruent to the first, and the union of remaining subsets,

*B*

_{m + 1}∪...∪

*B*

_{n}, 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

*F*

_{2}, 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*

^{-1}

*b*and

*bba*

^{-1}

*baa*are members of

*F*

_{2}. We also define

*e*, or the empty string, as the string in

*F*

_{2}with no members. Finally, we define an operation, *, on strings in

*F*

_{2}that combines two strings into one by placing the second directly after the first. Therefore

*ab*

^{-1}*

*b*

^{-1}

*aab*=

*ab*

^{-1}

*b*

^{-1}

*aab*. Additionally, strings are simplified by two rules, where

*x*stands for any string in

*F*

_{2}:

*e**x*=*x**e*=*x**aa*^{-1}=*a*^{-1}*a*=*bb*^{-1}=*b*^{-1}*b*=*e*

*a*

^{-1}

*bab*and

*b*

^{-1}

*a*

^{-1}

*bab*

^{-1}.

*a*

^{-1}

*bab**

*b*

^{-1}

*a*

^{-1}

*bab*

^{-1}=

*a*

^{-1}

*bab*

*b*

^{-1}

*a*

^{-1}

*bab*

^{-1}=

*a*

^{-1}

*bae*

*a*

^{-1}

*bab*

^{-1}=

*a*

^{-1}

*ba*

*a*

^{-1}

*bab*

^{-1}=

*a*

^{-1}

*be*

*bab*

^{-1}=

*a*

^{-1}

*b*

*bab*

^{-1}

The group

*F*

_{2}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

*F*

_{2}. Illustrated are the strings of

*F*

_{2}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*

^{-1}

*b*

^{-1}is illustrated; staring at

*e*, one first proceeds upward, then left, then down. The reader can verify this construction.

The decomposition of

*F*

_{2}requires the use of some new notation. By

*S*(

*a*) denote the set of all strings in

*F*

_{2}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

*F*

_{2}. 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*

^{-1}

*bab*

^{-1}, a member of

*S*(

*a*

^{-1}). Also, strings beginning with

*a*

^{-1}such as

*a*

^{-1}

*bb*can be formed as the combination of

*a*and a suitable string beginning with "

*a*

^{-1}

*a*

^{-1}", in this case

*a*

^{-1}

*a*

^{-1}

*bb*. 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

*a*

*S*(

*a*

^{-1}). The only strings not members of the latter set belong to

*S*(

*a*). Therefore, the group

*F*

_{2}is a union of

*a*

*S*(

*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

*F*

_{2}. In summary,

*F*

_{2}= {

*e*}∪

*S*(

*a*)∪

*S*(

*a*

^{-1})∪

*S*(

*b*)∪

*S*(

*b*

^{-1}) =

*a*

*S*(

*a*

^{-1})∪

*S*(

*a*) =

*b*

*S*(

*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*

*F*

_{2}. One copy of

*F*

_{2}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

*F*

_{2}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:

Post a Comment