Banach–Tarski paradox fails to iterate over all points

Question

The Banach–Tarski Paradox explanation goes along these lines

(1) Take a point on a sphere
(2) Use 2pi/3 rotations to construct a subset of points
(3) After infinite number of rotations you've selected [an infinite] countable set of points on the sphere
(4) For each point not on the set repeat step (2)
(5) Repeat step (4) while there are unprocessed points

Done. [This paradox uses an axiom of choice]

Here is my concern. I am fine with an axiom of choice in the form "for any non-empty set you can always select a member of a set". However, Banach–Tarski Paradox seems to try to do something very different.

It tries to keep selecting points from a continuum set until no more points remain. This is NOT possible. Infinite while loop can only select Countable number of points, while continuum must be selected to iterate over all points on a line or a sphere.

If this selection is possible then we can enumerate all points on (0,1) interval. Is there something in the proof that I am missing?

Answer 1

There are indeed transfinite sequences — more precisely, sequences indexed by ordinal numbers — that enumerate the entire interval $(0,1)$.

Such a sequence can be 'constructed' via transfinite recursion by the method of transfinitely iterating the operation of "pick an element that hasn't been chosen yet, or stop if there are none".

This applies to any set at all; this fact is basically the content of the well-ordering theorem.

(Note: I'm responding to your final paragraphs. Your description of B-T is somewhat incoherent as well, so I'm not entirely sure you understand what it's doing or that your final questions actually pertain to B-T)

Answer 2

Axiom of choice is the following proposition:

Given any collection of disjoint non-empty sets, there exists a set containing exactly one element of each of these sets.

Note that the axiom says nothing about how to obtain this set; it only says that this set exists. Your proposition is the weaker axiom of countable choice (axiom of choice for countably infinite collections).

[Edit:] I have been corrected that the proposition from the original question is the axiom of dependent choice, which is stronger than the axiom of countable choice, but weaker than the full axiom of choice.

I am going to give you a theorem which is easier to understand (but is ultimately based on the same kind of construction): Vitali's proof of existence of non-measurable set of reals.

• Let $\sim$ be the following relation on reals: $x{\sim}y$, if $x-y$ is a rational number.
• This relation splits an interval from $0$ to $1$ to uncountably many equivalence classes, each class being a countable set.
• Assuming axiom of choice, there exists a set containing one element of these sets. This set $V$ is uncountable.
• Create countably many copies of this set, each shifted by some rational number from $-1$ to $+1$. It can be shown that a union of these sets is a superset of an interval from $0$ to $1$, but a subset of an interval from $-1$ to $2$. In addition, the sets are disjoint.
• Lebesgue measure is translation-independent (shifting a set by a constant does not change its measure). In addition (assuming axiom of choice), it is countably additive; given a countably infinite collection of disjoint measurable sets, the measure of the union is equal to the infinite sum of the measures of the individual sets.
• Now what is the measure of the set $V$? If the measure is zero, then the measure of the union is also zero (the series $0+0+0+\ldots$ has sum $0$ - note that a sum is a limit of the sequence of partial sums); and if the measure is not zero, then the measure of the union is infinite.
• This is not possible - as I have said, the union is a subset of an interval of measure $3$ and a superset of an interval of measure $1$. Therefore, the set $V$ is not measurable.

Now Banach-Tarski paradox is based on the similar splitting of the surface of the sphere into uncountably many countable equivalence classes. The equivalence relation is: "Point $X$ can be reached from point $Y$ using a finite sequence of rotations." Each step is a rotation by a specific angle which is not a rational fraction of the whole circle, in the four directions: "Up", "Down", "Left", or "Right". It can be proven that no two sequences of rotations without backtracking will yield the same rotation; the only way to return to the origin (null rotation) is to backtrack the whole sequence. Therefore given a starting point - except for some pathological points, namely points on the axis of rotation or points reachable from them (of these there are countably many), no two sequences of rotation will yield the same point.

Now use the axiom of choice: there exists a set containing one element of each equivalence class. (For now disregard the pathological points.) Apply all the countably many finite sequences of rotations to this set. Any point on the surface which is neither a pathological point nor in the starting set can be reached from the set by exactly one sequence of rotation. Split the destination points into four subsets:

• Points which can be reached by taking a rotation ending with the step "Up".
• Points which can be reached by taking a rotation ending with the step "Down".
• Points which can be reached by taking a rotation ending with the step "Left".
• Points which can be reached by taking a rotation ending with the step "Right".

Now what happens when you take the first set, and rotate it "Down" (backtracking the last step)? Okay, what was the step before that - any of "Up", or "Left", or "Right" (but not "Down" because that would be backtracking). Therefore by backtracking the last step, we turned the first set into copy of the first set, plus the third set, plus the fourth set (plus an extra copy of the starting points). Similarly, when we backtrack the third set, you get the first + second + third set (plus extra starting points).

And now we are basically done - the rotated first set plus the second set yields one copy of the sphere, and the rotated third set plus the fourth set yields the other. (There are some technical details left. First, we have so far handled only the surface of the sphere; but of course we can divide the whole solid ball - except the center - in the same way depending under which point on the surface it is. Second, we have an extra copy of the starting points; we started with one, and got three. Third, we need to handle the pathological points and the center of the sphere.)

For more details on the Banach-Tarski paradox with layman's explanation, I can direct you to the following sites:

• Irregular Webcomic (Make sure to enable the annotations.)
• Vsauce YouTube video on Banach-Tarski paradox