1. Non-measurable sets
In these notes I want to present a proof of the Banach-Tarski paradox, a consequence of the axiom of choice that shows us that a naive understanding of the concept of volume can lead to contradictions. A good reference for this topic is the very nice book The Banach-Tarski paradox by Stan Wagon.
The result is one of a family of theorems indicating limitations of any reasonable notion of measure on the real numbers or in Euclidean space, and in this section I include a few examples. We will work with Lebesgue measure. The version of this measure for we denote Actually, we do not need to know much about Lebesgue measure. It suffices that has the following properties (and, really, we will only look at or ):
- is a measure, so is a function with domain a -algebra of subsets of and range and is -additive, i.e., if is a sequence of pairwise disjoint elements of the domain of (i.e., measurable sets), then
- If is the unit -cube, i.e.,
then (Other than we do not really need this fact.)
- is non-atomic, in the sense that each singleton is measurable, and for all
- is invariant under the group of isometries of For example, if for measurable and let
Then is measurable, and We say that is translation invariant. Also, if
then is measurable, and In is not only translation invariant but also invariant under rotations and reflections. In fact, if
for and measurable, then is measurable, and but we won’t be needing this fact.
is our formalization of the notion of length, similarly, and formalize the notions of area and volume.
Theorem 1 There is a subset of that is not measurable.
Proof: We present an argument due to Vitali. On say that iff This is an equivalence relation. Let be a choice set, so is a singleton for each -equivalence class Then
This is a countable union of disjoint measurable sets. By translation invariance (and monotonicity, a consequence of -additivity), if then each of the sets in the union has measure zero as well, which leads to the contradiction
and therefore, if then again a contradiction.
It follows that is not Lebesgue measurable.
Remark 1 Translation invariance is essential here. It is consistent with that Lebesgue measure can be extended to a measure defined on all subsets of
The example above used the axiom of choice explicitly, guaranteeing the existence of the set Another typical use of choice is the existence of a well-ordering of A set of measure zero is called null. Otherwise, it is non-null. Note that a non-null set needs not be measurable. The example below uses a bit more of the properties of and namely, Fubini’s theorem.
Theorem 2 No well-ordering of a non-null sets of reals is measurable (as a subset of ).
Proof: We claim that whenever is non-null and is a well-ordering of then is non-measurable. We proceed by contradiction. Say that is the least ordinal for which there is an enumeration of a non-null set such that is measurable.
For let and For let denote the unique such that
Note that is measurable: By Fubini’s theorem, for almost all and almost all both and are measurable. Since for any then must be measurable as well.
It suffices to show that for some is non-null and measurable. If so, is a measurable well-ordering of is order-type contradicting the minimality of
Now, for almost all is measurable. Thus if no is as claimed, then for almost all we have that is null. Hence,
But for almost all we have has positive measure. Contradiction.
Remark 2 The argument shows that, even if there is an extension of Lebesgue measure to all subsets of the completion of is not defined on all of
2. Tarski’s circle-squaring problem
In order to understand the statement of the Banach-Tarski result, it is convenient to first explain why it is stated for rather than the plane.
I won’t prove this result here. It is a consequence of a more general extension theorem, related to the fact that the group of isometries of the plane is amenable. Its proof requires choice. An obvious consequence of this result is that if a (measurable) figure in the plane has some area and it is cut out into finitely many pieces that are then rearranged into another measurable figure then
In contrast, the Banach-Tarski paradox allows us to divide a sphere the size of a pea into pieces that, when rearranged, make up a sphere the size of the sun. Clearly, this precludes the existence of an extension of Lebesgue measure in as in the Banach-von Neumann result. On the other hand, a version of the paradox can be obtained for . In order to discuss this, I need a few notions.
Definition 4 Two sets in are equidecomposable if one can be partitioned into finitely many disjoint sets (called pieces) that can be rearranged (via isometries) to form a partition of the other.
There is a well-known particular instance of equidecomposability that has been studied in some detail in the context of classical Euclidean geometry.
Definition 5 Two polygons in are equidissectable if, allowing overlap on boundaries, one can be split into finitely many triangles that can be rearranged (via isometries) into the other.
Sometimes one says that the polygons are congruent by dissection.
Theorem 6 (Bolyai-Gerwien) Two polygons are equidissectable iff they have the same area.
Proof: I only present a sketch. One direction is obvious. For the other, first one argues that a polygon is dissectable into triangles. Then, that any triangle is equidissectable with a square. This is done in two stages. First, one easily shows that a triangle is equidissectable with a rectangle. Some care is then needed to see that a rectangle is equidissectable with a square; but this is classical, it only goes a bit beyond constructing the geometric mean of two given numbers. Finally, one shows that two squares are equidissectable with a single square, and then induction completes the proof. The argument for two squares amounts to one of the well-known proofs of the Pythagorean theorem.
The version of the Banach-Tarski paradox in is a generalization of the following strengthening of the Bolyai-Gerwien result:
The proof (that I omit) follows the same outline as the paradox in .
Tarski then asked for the possibility of extending Theorem 7 to other regions. In particular, he asked whether the circle and a square of the same area are equidecomposable. This question remained open until 1990, when M. Laczkovich solved it affirmatively, in his paper Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem, Journal für die reine und angewandte Mathematik, 404 (1990), 77-117. Among his results, I highlight:
Theorem 8 (Laczkovich)
- Any two polygons of the same area are equidecomposable using only translations.
- Let be a piecewise smooth Jordan curve for which there are two positive constants such that the curvature at each point of is between and Then the domain enclosed by is equidecomposable to a square via translations alone.
The number of pieces required in the decomposition is rather large. Laczkovich computes that about pieces are required in the equidecomposition of an arbitrary isosceles right triangle and a square. In contrast, 5 pieces are required for the Banach-Tarski paradox in .
The pieces of the decomposition are also not explicitly definable; in particular, Dubins,Hirsch, and Karush showed that if only Jordan domains are used, then the circle and the square are not equidecomposable.
3. Paradoxical group actions
The full statement of the Banach-Tarski paradox in is as follows:
Theorem 9 Any two bounded subsets of with nonempty interior are equidecomposable.
We will prove a weaker result, namely, that a sphere is equidecomposable with two copies of itself. Recall that denotes the unit sphere in The argument takes three steps. First, we talk about paradoxical group actions and show that the free group on two generators, acts paradoxically on itself. This is then used to show Hausdorff’s paradox, that there is a countable set such that acts paradoxically on We conclude by showing the Banach-Tarski paradox itself, that acts paradoxically on
Recall that a group action is a map from a group into the group of bijections of a set into itself, such that:
- where is the identity of
- For all and
To ease readability, we will follow the usual convention of writing rather than and or even rather than Also, given and write or for
Definition 10 Let the group act on the set We say that acts paradoxically on iff there are pairwise disjoint subsets of
and corresponding elements of
It is easy to check that if acts paradoxically on we can assume moreover that the pieces satisfy that see Fact 1. This explains the name: Note that then we have that is “equidecomposable” with two copies of itself, since and are both equidecomposable with where we are abusing notation, using subsets of rather than of and elements of rather than isometries.
Given a group acting on a set write to denote that that can be partitioned into finitely many pieces,
and that there are (not necessarily distinct) elements of such that, letting for then the are pairwise disjoint and partition
It is easy to verify that is an equivalence relation.
Proof: Verify that the argument for the Schröder-Bernstein theorem gives that if then
A trivial example of a paradoxical action is given by the group acting on via the action for an infinite set. This action is paradoxical, since any infinite is in bijection with two copies of itself. A more interesting example, essential to the argument, is as follows:
Theorem 11 acts paradoxically on itself by left multiplication.
Proof: Let be generators of and consider the following 4 subsets:
Note that are disjoint and partition Moreover,
This gives the result, as
The key tool we use to show that acts paradoxically on the sets in that interest us is the following result. Say that an action of a group on a set is without nontrivial fixed points iff the only element of that fixes a point of is the identity
Theorem 12 If acts on without nontrivial fixed points, then acts paradoxically on
Proof: Fix an action of on without nontrivial fixed points. Using the axiom of choice, let be a choice set picking an element of each orbit Note that for any there is a (unique) such that and therefore there is a such that In fact, there is a unique such Otherwise, there are and such that
and therefore Since is a choice set, then But then since the action of is without nontrivial fixed points.
Let be a paradoxical partition of so Let and By our observation on the paragraph above, and Since we immediately get
4. The Hausdorff paradox
In this section, I prove the following result:
Theorem 13 There is a countable set such that the natural action of the group of isometries of on is paradoxical.
In light of the results from last section, it suffices to find two isometries such that the group they generate is free, and acts on without nontrivial fixed points, for some appropriate countable set
There are many ways of doing this. Following Wagon’s suggestion, let be the counterclockwise rotation around the -axis by an angle of The matrix associated to is easily found to be:
Note that is the transpose of
Now let be the counterclockwise rotation around the -axis by an angle of As with it is easy to see that the matrix associated to is:
Lemma 14 The group generated by is free.
Proof: I sketch the argument. Let be a reduced word in the alphabet We need to show that if is nontrivial (as a word), then it is not the identity (as an isometry). Since iff we may assume that ends in either or We say that is valid.
I claim that
for some integers with and In particular, this shows that does not map into itself, so
The claim is proved by induction on the length of The result is clear if since and is just the first column of that has the required form with and
Suppose now and we know the result for all shorter lengths. We have that or for some valid word We have that for some appropriate integers
where and in the first case, or and in the second case.
In both cases, we have that are integers, and that All that remains is to argue that is not divisible by 3. For this, we consider the word such that or or or Note that is valid in the first and fourth cases. In the second and third cases, is valid unless it is the empty word. In any case, note that for some integers with we have
and unless is the empty word, in which case
From the formulas above, we see respectively that with or with or or In all cases, that now follows from the induction hypothesis, and we are done.
The Hausdorff paradox follows immediately: It suffices to show that there is a countable set such that the natural action of the group on is without nontrivial fixed points. But for any matrix other than the identity, either fixes no vector in or else it fixes exactly two, of the form and This is because either is not an eigenvalue of or else it is an eigenvalue of multiplicity 1: Note that if has multiplicity 3 as an eigenvalue, and it cannot have multiplicity 2, because is the product of the eigenvalues of
Now take as the set of all vectors in that are fixed by some Since is countable, and each contributes at most two vectors to is countable.
5. The Banach-Tarski paradox
We now conclude the proof of the following result:
Theorem 15 (Banach-Tarski) The group of isometries of acts paradoxically on
As mentioned earlier, there is a stronger form of the paradox where any two bounded sets with nonempty interior and equidecomposable. Several additional strengthenings are possible. For example, only 5 pieces are needed to witness the equidecomposition (and 4 do not suffice). Let be the group of isometries of Very recently, Trevor Wilson, then an undergraduate at Caltech, showed that the equidecomposition can be carried out continuously, i.e., say that and are bounded and with nonempty interior. Then there is a partition
and continuous functions
for such that
whenever and and
For the strong version of the Banach-Tarski paradox and the fact that precisely 5 pieces are needed, see Wagon’s book. For the continuous version, see Trevor Wilson, A continuous movement version of the Banach-Tarski paradox: A solution to de Groot’s problem, The Journal of Symbolic Logic, 70 (3), 2005, 946-952.
Proof: In view of the Hausdorff paradox, it suffices to show that, with the group of isometries of we have that whenever is countable. To see this, it suffices to check that there is a rotation such that are pairwise disjoint. because if that’s the case, letting
To find note that there is a line that goes through the origin and misses Let be the set of angles such that for some there is a point such that where is the rotation around of radians.
Clearly, is countable, so there is an angle not in and we can take In effect, we have that for all But then for all as well, and we are done.
Typeset using LaTeX2WP. Here is a printable version of this post.