Doubling a set

[Swammerdami]

Girls just want to have fun is a song written by Robert Hazard and made famous by Cyndi Lauper. But a little-known fact is that the original lyrics were "Mathematicians just want to have fun!" Hazard just couldn't get the meter to scan properly with the original lyrics.

A rather famous example of doubling a set is to take a solid 3-D ball; divide it into five pieces; operate one of 5 simple distance-preserving (and volume-preserving) transforms on each piece and -- Presto! -- end up with TWO solid balls, each with the same size as the original ball!!

Although the ball-doubling is very famous, there was no million-dollar prize for it as there is for proving Poincare's Conjecture or the Riemann Hypothesis. That's because nobody posed the question "How do you double a ball using volume-preserving transforms?" They never posed the question because it's obviously impossible! Yet "Mathematicians just want to have fun!" and sometimes do "impossible" but fun things before breakfast (though seldom before a cup of coffee).

I plan to compose a few posts on the topic of set doubling. If I don't run out of patience, I may get around to a brief summary of the ball-doubling. But participation by others is welcome. Feel free to Google the "Banach-Tarski Paradox" (ball doubling) and post about it before I do.

We will start with a very simple doubling. But first, let's use an example to define a simple notation for manipulating sets. When placing a set where a number or element should go, we're asking that the expression be evaluated for all elements of the set, with the result forming a new set. To avoid confusion, capital letters will always denote sets.

K = {1,2,3,4,5}​

10⋅K+7 = {17, 27, 37, 47, 57}​

​

We will also work with partitions. When

K = G₁ ⋃ G₂ ⋃ G₃ ⋃ G₄ ⋃ G₅​

and

∀i,j G_i ⋂ G_j = Ø​

we say that (G₁, G₂, G₃, G₄, G₅) is a partition of K

(0,1] denotes the set {x | 0 < x and x ≤ 1} but in keeping with the convention that sets are denoted by capital letters, we write K(0,1] = (0, 1] or more generally

K(a,b] = {x | a < x and x ≤ b}​

Now let's partition K(0,1] into two subsets

K(0,1] = K(0,.5] ⋃ K(.5, 1]​

But each of the subsets can be transformed into a copy of the original set!

2⋅K(0,.5] = K(0,1]​

2⋅K(.5, 1]-1 = K(0,1]​

(In practice we might substitute 2⋅K(.5, 1]+99 = K(0,1]+100 so that we finish with two disjoint copies of the original set.)

This simple doubling already gives us a simple way to double a ball, except for a nitpick. We just partition the ball into its infinitely-many radii; double each radius; offsetting one copy of each such doubled pair; and presto! Two balls. The very center of the ball is troublesome. Do we include it in a radius or not? If we don't include it, the second ball will be missing the single point at its very center.

More formally: Each point in the ball B can be denoted with three coordinates (α,β,r) where r is the distance from the ball's center and (α,β) are the angular coordinates of radius. Now partition the ball of radius-length 1 into these infinitely many radii:

B = {(0,0,0)} ⋃ B(α,β)₁ ⋃ B(α,β)₂ ⋃ B(α,β)₃ ⋃ ...​

where each B(α,β)_i has the form (α_i, β_i, K(0,1]). That is, it is equivalent to the simple K(0,1] = (0, 1] segment we considered above. We showed how to double that above.

We've not handled the very center of ball properly -- we had to separate the singleton {(0,0,0)} -- but let's gloss over that detail for now.

Of course this is NOT the Banach-Tarski Paradox. We've doubled the ball but we did NOT do that with distance-preserving transforms let alone with volume-preserving transforms

Hey! How is that even possible?? If the ball has volume v, then the doubled ball will have volume 2⋅v. The Banach-Tarski ball doubling must be impossible, right?

Spoiler alert: Banach and Tarski will partition the ball into pieces for which the volume, like 0÷0, is undefined! But that will be the least of our worries on the Banach-Tarski roller-coaster ride.


Well, this concludes episode 1. I've probably already made mistakes, and certainly sown confusion. Submit your comments and questions. I hope to compose episode 2 tomorrow.

 

[Swammerdami]

Episode 2a.

It's impossible to double a finite set. (Except the null set!) If a set has 7 elements, any element-by-element transformation will lead to 7 elements, not to the 14 elements needed for a doubling. (Actually the transformed set might have fewer than 7 elements if the transformation is non-injective but that isn't allowed in any of our examples.)

Doubling an infinite set, as we saw in episode 1, is well-known and related to the famous Hilbert's Hotel Paradox. Forms of this paradox were even discussed by at least two geniuses from long-ago: Archimedes and Galileo. Hilton's Hotel operates on a countably infinite set, while episode 1 doubled uncountable sets, but the latter action wasn't more difficult. (Although the distinction between closed and open intervals complicates things.)

But the examples in episode 1 were not constructed to use a  Rigid transformation, that is a transformation that preserves distance and shape. We will impose that restriction throughout the rest of this thread.

Next, in episode 2b we will show how to take a certain infinite set of points in the complex plane; partition it into two parts; and apply a rigid transformation to either part and finish with the original set.

Specifically, we want to find a set of complex numbers S

ℂ = {x+yi | x,y ∈ ℝ}
S ⊆ ℂ​

and a partition of S into two subsets

S = A ⋃ B​

A ⋂ B = Ø​

and two simple transforms f(.) and g(.) such that

f(A) = S​

and

g(B) = S​

In other words, the entirety of S can be derived by one of two simple rigid transforms operating on either one of its two parts.

This is a difficult challenge, though not nearly as ridiculously difficult as the Banach-Tarski Ball-Doubling previously mentioned. I'll reveal a solution in episode 2b, but please feel free to ask for hints to find an answer yourself!

In fact, I'll show the very simple rigid transforms used in the suggested solution. A point in the complex plane can be represented as (x+yi) and can also be represented in polar coordinates as (r, θ). One of the transformations will be a trivial translation, the other a trivial rotation:

f(x+iy) = (x+yi-1)​

g(r, θ) = g(r, θ-1)​

So: Any takers? Any comments or questions? So far, the response to this thread has been enthusiastic but I'm hoping for even more enthusiasm before proceeding!

 

[lpetrich]

Seems like the  Banach–Tarski paradox

The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them without changing their shape. However, the pieces themselves are not "solids" in the usual sense, but infinite scatterings of points. The reconstruction can work with as few as five pieces.

 

[Bomb#20]

A rather famous example of doubling a set is to take a solid 3-D ball; divide it into five pieces; operate one of 5 simple distance-preserving (and volume-preserving) transforms on each piece and <snip>

What does it mean to call a transform "volume preserving" when the thing it's transforming doesn't have a volume?

Feel free to Google the "Banach-Tarski Paradox" (ball doubling) and post about it before I do.

What paradox? There's nothing paradoxical or even counterintuitive* about any of this -- it's just wrong. Who calls the "1 + 1 = 1 Paradox" a paradox or even counterintuitive? You can't double a ball in the way Banach and Tarski try to do it. According to lp's link:

"Unlike most theorems in geometry, the mathematical proof of this result depends on the choice of axioms for set theory in a critical way. It can be proven using the axiom of choice..."​

But the axiom of choice is wrong, so theorems derived from it are wrong.

(* Admittedly, the axiom of choice is intuitively obviously true, but the well-ordering principle is intuitively obviously false, and who can intuitively tell about Zorn’s lemma? )

 

[Swammerdami]

A rather famous example of doubling a set is to take a solid 3-D ball; divide it into five pieces; operate one of 5 simple distance-preserving (and volume-preserving) transforms on each piece and <snip>

What does it mean to call a transform "volume preserving" when the thing it's transforming doesn't have a volume?

It preserves the volume IF the transformee HAS a volume! Similarly, dividing by 2 will halve a number UNLESS that number is already Infinity or NaN.

Feel free to Google the "Banach-Tarski Paradox" (ball doubling) and post about it before I do.

What paradox? There's nothing paradoxical or even counterintuitive* about any of this -- it's just wrong. Who calls the "1 + 1 = 1 Paradox" a paradox or even counterintuitive? You can't double a ball in the way Banach and Tarski try to do it. According to lp's link:

"Unlike most theorems in geometry, the mathematical proof of this result depends on the choice of axioms for set theory in a critical way. It can be proven using the axiom of choice..."​

But the axiom of choice is wrong, so theorems derived from it are wrong.

(* Admittedly, the axiom of choice is intuitively obviously true, but the well-ordering principle is intuitively obviously false, and who can intuitively tell about Zorn’s lemma? )

Don't forget that "Mathematicians just want to have fun!" Let's let them have fun with the Axiom of Choice -- Won't that recreation be more acceptable to their wives than visiting strip clubs? Anyway, the Axiom of Choice, whether "true" or not, HAS been proven to be "consistent." And the WAY that the Axiom of Choice is used to achieve the Banach-Tarski ball doubling seems very nifty!

But meanwhile we're still waiting for Episode 2b, which solves the problem posed in Episode 2a. THAT doubling does NOT require the Axiom of Choice.

 

[Bomb#20]

But meanwhile we're still waiting for Episode 2b, which solves the problem posed in Episode 2a. THAT doubling does NOT require the Axiom of Choice.

Fair point; but the point set you double in problem 2a doesn't have a nonzero Lebesgue measure, which is the part that makes Banach-Tarski seem so amazing.

Episode 2a.
...
Next, in episode 2b we will show how to take a certain infinite set of points in the complex plane; partition it into two parts; and apply a rigid transformation to either part and finish with the original set.

Specifically, we want to find a set of complex numbers S

ℂ = {x+yi | x,y ∈ ℝ}
S ⊆ ℂ​

and a partition of S into two subsets

S = A ⋃ B​

A ⋂ B = Ø​

and two simple transforms f(.) and g(.) such that

f(A) = S​

and

g(B) = S​

In other words, the entirety of S can be derived by one of two simple rigid transforms operating on either one of its two parts.

This is a difficult challenge, though not nearly as ridiculously difficult as the Banach-Tarski Ball-Doubling previously mentioned. I'll reveal a solution in episode 2b, but please feel free to ask for hints to find an answer yourself!

In fact, I'll show the very simple rigid transforms used in the suggested solution. A point in the complex plane can be represented as (x+yi) and can also be represented in polar coordinates as (r, θ). One of the transformations will be a trivial translation, the other a trivial rotation:

f(x+iy) = (x+yi-1)​

g(r, θ) = g(r, θ-1)​

So: Any takers? Any comments or questions? So far, the response to this thread has been enthusiastic but I'm hoping for even more enthusiasm before proceeding!

Solution:

Show

Let point 0 be the origin.
Let point 1 be (1, 0).
Let point 2 be (1, 1). (i.e., the complex number with r=1 and theta=1 radian.)
Let point 3 be (2, 0).
Let point 4 be (1, 2).
Let point 5 be (1, 1) + 1.
...
Let point 2k be point k times e to the i. (i.e., rotate point k one radian around the origin.)
Let point 2k+1 be point k + 1. (i.e., translate point k one unit to the right.)
...
All the odd numbered points recover the original set under transformation f.
All the even numbered points recover the original set under transformation g.

 

[Swammerdami]

Bravo, Mr. Bomb#20! As usual your presentation is much succincter than mine would have been.

Since I'm in charge of Nitpicking here, let me offer two very minor complaints:

(1)

Let point 2k+1 be point k + 1.

This is a bit confusing, especially in fonts with a very thin space character. Also, I think the referees will ask that "Let point 5 be (1, 1) + 1" be rephrased.

(2)
You describe S and its partition S = A ⋃ B. BUT for your solution to be strictly complete, you must prove that A ⋂ B = Ø.
(This will follow quickly from one of the very famous -- and difficult to prove -- theorems.)

 

[Bomb#20]

Since I'm in charge of Nitpicking here, let me offer two very minor complaints:

(1)

Let point 2k+1 be point k + 1.

This is a bit confusing, especially in fonts with a very thin space character.

Sorry, make that "Let (point (2k+1)) be ((point k) + 1).

Also, I think the referees will ask that "Let point 5 be (1, 1) + 1" be rephrased.

Would they find "cos(1) + 1 + sin(1)i" more intuitive? Or perhaps just "eⁱ + 1"? This seems to be a problem that cries out for a newly invented notation. How about this:

Show

Let t = +1
Let r = * eⁱ
Then:
Point 0 = 0
Point 1 = 0t
Point 10 = 0tr
Point 11 = 0tt
Point 100 = 0trr
Point 101 = 0trt
...

(2)
You describe S and its partition S = A ⋃ B. BUT for your solution to be strictly complete, you must prove that A ⋂ B = Ø.
(This will follow quickly from one of the very famous -- and difficult to prove -- theorems.)

Well, intuitively, it seems obvious that the points won't hit each other because pi is transcendental, but I confess I have no idea how to prove it.

 

[Swammerdami]

Since I'm in charge of Nitpicking here, let me offer two very minor complaints:

(1)

Let point 2k+1 be point k + 1.

This is a bit confusing, especially in fonts with a very thin space character.

Sorry, make that "Let (point (2k+1)) be ((point k) + 1).

My nitpick was just so I could joke about hypothetical "very thin spaces."
I thought your solution was fine.

(2)
You describe S and its partition S = A ⋃ B. BUT for your solution to be strictly complete, you must prove that A ⋂ B = Ø.
(This will follow quickly from one of the very famous -- and difficult to prove -- theorems.)

Well, intuitively, it seems obvious that the points won't hit each other because pi is transcendental, but I confess I have no idea how to prove it.

The irrationality of pi is enough to guarantee the rotations by themselves go on endlessly without duplication. However adding the 1's disturbs or complicates that argument. But eⁱ is transcendental and that DOES lead to the required 2-step proof:

(1) Prove that eⁱ is transcendental.
(2) Show that A ⋂ B = Ø follows from (1).

Step 2 is relatively easy.
Step 1 was a major triumph of 19th-century mathematics. In 100 Great Problems of Elementary Mathematics -- a great book by Heinrich Dörrie available as a free on-line pdf -- this proof uses more pages than any of the other 99 Great Problems. This length despite that the proof shown for the Hermite-Lindemann Transcendence Theorem is one that has been simplified over several decades since Hermite's original achievement.

 

[Swammerdami]

Episode 3a.

Bomb#20 has solved Episode 2b. We move on to Episode 3. The next task will be to partition the "free group of rank 2" into two subsets; F₂ = G ⋃ H; transform G & H separately and end up with TWO copies of F₂:

g(G) = F₂​

h(H) = F₂​

so

F₂ = G ⋃ H ⇛ F₂ + F₂​

Bomb has already commented on the structure of a set like F₂:

Let t = +1
Let r = * eⁱ
Then:
Point 0 = 0
Point 1 = 0t
Point 10 = 0tr
Point 11 = 0tt
Point 100 = 0trr
Point 101 = 0trt
...

G = { Ø, t, tr, tt, trr, rtt, ... } is the universe. Here Ø is the empty string -- what Bomb calls "0." But we will reduce confusion by writing e (for empty string) instead of Ø.

We will replace t and r with a and b to emphasize that they are arbitrary operators; in Episode 3 we won't be concerned with any geometric interpretation of these operators: just treat them abstractly.

Finally, instead of generating strings just from a and b, the inverse operators a^-1 and b^-1 are also allowed. The elements of F₂ will be all the finite strings which can be built from a, b, a^-1 and b^-1 subject to the restriction that the string contain no instances of a adjacent to a^-1 nor of b adjacent to b^-1. Like a proton and an anti-proton, an operator and its inverse annihilate each other when they touch.

In Bomb#20's solution for Episode 2, we needed to prove -- via Hermit's Transcendence Theorem -- that no two distinct strings of t and r were equal to each other. But we need not worry about that here: The strings are abstractions and we get to stipulate how they work. We simply stipulate that distinct strings are not equal to each other.

The set F₂ we've just defined is called the Free Group of Rank 2 or the Free Group of Two Generators. It will be used in the Banach-Tarski construction, but we needn't worry about that yet.

Each element of F₂ will begin with a, with b, with a^-1, with b^-1, or be the null string. Let S(a) denote the set of strings which begin with a, and so on:

F₂ = S(a) ⋃ S(b) ⋃ S(a^-1) ⋃ S(b^-1) ⋃ { e }​

Note that

a∙S(a^-1) ⋂ S(a) = Ø​

The a destroys the leading a^-1. But that pair cannot be followed by a -- the leading a^-1 would have destroyed that a already.

That concludes Episode 3a. Your mission now is to show how to "double" F₂. This is shown on Wikipedia pages so if you've read those pages please get a lobotomy to ensure contestants are on equal footing.

The empty string e may be a bit of a nuisance. Do you end up with exactly two copies of it? There's a little trick to address that issue; I'm not sure it's mentioned on Wiki's Banach-Tarski page.

 

[Swammerdami]

Episode 3b

In Episode 3a we introduced

F₂ = S(a) ⋃ S(a^-1) ⋃ S(b) ⋃ S(b^-1) ⋃ { e }​

Note that, since a^-1 can be followed by nothing, by b, by b^-1 or by another a^-1

a∙S(a^-1) = { e } ⋃ S(b) ⋃ S(b^-1) ⋃ S(a^-1)​

which leads directly to

a∙S(a^-1) ⋃ S(a) = F₂​

Similarly

b∙S(b^-1) ⋃ S(b) = F₂​

This leads directly to

F₂ = (S(a)⋃S(a^-1) ⋃ (S(b)⋃S(b^-1) ⋃ { e } ⇛ F₂ + F₂ + { e }​

(Yes, I'm "overloading" the "+" symbol in a weird way. Sue me!)

We've just doubled F₂. EXCEPT that we've finished with THREE copies of the null sting -- the identity, denoted by e (or by "1" since we're treating the group's operator as multiplication) -- instead of TWO, as we would have were the duplication perfect.

In a mathematical proof, there are Key Ideas and Nitpick Workarounds.

How do we get rid of the third copy of the identity element? Does this task depend on a Key Idea, or is it just a Nitpick Workaround? How about the recent complicated and famous proofs of Fermat's FLT conjecture and Poincare's conjecture? Which steps in those proofs were Key Ideas and which were Nitpick Workarounds? Surely the distinction gets very blurred.

Anyway, the challenge for Episode 3c is just a workaround: It is to modify the duplication prescription above to finish with exactly two copies of the null (identity) string, as needed for a perfect duplication.

 

[Swammerdami]

By now it's embarrassingly obvious I'm making this all up as I go. This post provide an Erratum, and what should have been Episode 0.

(Yes, I'm "overloading" the "+" symbol in a weird way. Sue me!)

Notational abuse from my private doodles should never have been published. I wanted to avoid writing "A ⋃ A" to denote A's doubling since of course A ⋃ A = A.

But better would have been something like

F₂ = (S(a)⋃S(a^-1) ⋃ (S(b)⋃S(b^-1) ⋃ { e } ⇛ F₂^* ⋃ F₂^** ⋃ { e }​

Getting from F₂ to F₂^* isn't a problem; for example F₂^* = { (0,f) | f ∈ F₂ }

Episode 0

The problems we consider here are similar to bijections -- the one-to-one and onto mappings Georg Cantor introduced to prove that rationals and integers have the same cardinality, or that the points on a line segment, line, plane or 3-space all have the same cardinality.

Here's one of the most interesting examples of two sets whose equal cardinalities were noticed by Cantor:

• A = [0, 1) = { x | x ∈ ℝ, 0 ≤ x < 1 }
• B = P(ℕ) = { x | x ⊆ {1,2,3,4,5,6,...} }

The points on a line segment are exactly equal in number to the number of subsets of the positive integers! But can you find a bijection from [0, 1) to P(ℕ) ?

If you Google around you'll find
" There are injections both ways (A → B, B → A) so of course there must be a bijection A ↔ B by the  Schröder–Bernstein theorem."
Sure. We know there IS a bijection. But I want to actually see one. (The Wiki article gives a prescription by Julius König to construct a bijection from two injections -- König uses that to prove the Schröder–Bernstein theorem itself -- but its result is too cumbersome.)

A simple approach ALMOST works:
Express the real number as a binary fraction, e.g. 1/7 = .001001001001001... = 2^-3 + 2^-6 + 2^-9 + ...
For the bijection, simply map the real number to the set of positions with a 1-bit in the binary fraction.
1/7 ↔ { 3, 6, 9, 12, 15, ... }

Participation has been lax, so I will pose two challenges:

(1) What is wrong with the bijection just proposed?
(2) Can you fix it?

 

[Swammerdami]

... can you find a bijection from [0, 1) to P(ℕ) ?

A simple approach ALMOST works:
Express the real number as a binary fraction, e.g. 1/7 = .001001001001001... = 2^-3 + 2^-6 + 2^-9 + ...
For the bijection, simply map the real number to the set of positions with a 1-bit in the binary fraction.
1/7 ↔ { 3, 6, 9, 12, 15, ... }

(1) What is wrong with the bijection just proposed?
(2) Can you fix it?

This puzzle is a Nitpick Workaround rather than a Key Idea.

While Georg Cantor was developing set theory, he exchanged letters with Richard Dedekind, one of the greatest 19th-century mathematicians. The earliest letters date from when neither Cantor nor Dedekind even realized that the continuum is a higher infinity than the integers.

In one of the letters, Cantor mentions the problem posed above; identifies the plausible bijection AND its flaw; states that he has NOT found a fix; but also says that -- despite still seeking a proper bijection -- he regards that flaw as an unimportant nitpick. It is fun to read these letters, by a great genius but in the earliest phase of his great discovery.

A few years ago I found those letters on-line. But now, although Google produces dozens of pages that mention those famous letters, I can't find the actual letters, translated or not. Perhaps someone has claimed copyright on these 150 year-old documents.

A bit of Googling did NOT turn up an on-line solution to the "(2) Can you fix it?" above. I was proud to find a workaround myself, and am sure that workaround in some form is well known. But Google shows only "Cantor-Schröder–Bernstein theorem. Yawn!" as though detailed workarounds are uninteresting.

 

[Swammerdami]

This thread attracted little interest, so I should let it go. However there are two pending puzzles posed and I will close these. In this post I offer hints. I'll give Spoilers in a day or two if nobody beats me to it.

For the bijection between the power set of N and the binary fractions, note that a binary fraction will have one of three forms:
(a) a finite number of 1-bits and an infinite number of 0-bits
(b) an infinite number of 1-bits and a finite number of 0-bits
(c) an infinite number of 1-bits and an infinite number of 0-bits
What can you say about cases (a) and (b)?

For the proper duplication of F₂, introduce a set T = {e, a^-1, a^-1a^-1, a^-1a^-1a^-1, ... }

 

[Swammerdami]

There are two pending puzzles (though just "nitpick workarounds") in the thread. I may as well provide closure by showing solutions.

Doubling F₂

T = {e, a^-1, a^-1∙a^-1, a^-1∙a^-1∙a^-1, ... }​

F₂ = S(b) ⋃ S(b^-1) ⋃ S(a) ⋃ T ⋃ (S(a^-1) \ T)​

b^-1∙S(b) ⋃ S(b^-1) ⇛ F₂^*​

a^-1∙S(a) ⋃ a^-1∙T ⋃ (S(a^-1) \ T) ⇛ F₂^**​

Therefore

F₂ ⇛ F₂^* ⋃ F₂^**​

Q.E.D.

 

[Swammerdami]

Bijection between P(ℕ) and [0, 1)

A simple approach ALMOST works:
Express the real number as a binary fraction, e.g. 1/7 = .001001001001001... = 2^-3 + 2^-6 + 2^-9 + ...
For the bijection, simply map the real number to the set of positions with a 1-bit in the binary fraction.
1/7 ↔ { 3, 6, 9, 12, 15, ... }

This fails when the real number has TWO binary representations, e.g.
3/4 = 0.1100000... = 0.1011111...
The workaround is to first double the set of troublesome cases (numbers with a finite number of 0-bits or a finite number of 1-bits in their binary representation).
Replace troublesome x in (0, 0.5) with 2x and represent 2x with a finite number of 0-bits.
Replace troublesome x in [0.5, 1) with 2x-1 and represent 2x-1 with a finite number of 1-bits.
Represent 0 itself -- a special leftover case -- as {1,2,3,4,5,6,...} itself.
Q.E.D.

 

[Swammerdami]

The Banach-Tarski Theorem (aka Banach-Tarski Paradox).

I may as well outline the amazing result. I've put quite a bit of effort into this; please send me a message if you actually read it. I think the "proof" shown at Wikipedia and elsewhere may be incorrect, as I explain below.

A solid ball is divided into a finite number of pieces -- as few as five will suffice -- and some of the pieces are subjected to rigid transforms. After this you have TWO balls, each the same size and shape as the original ball! (Impossible?) A rigid transform can only involve rotation and translation; it preserves shape and size -- no squashing, stretching or shearing permitted. Impossible indeed! If the ball has 1 liter of volume how can a size-preserving transform change that ball into TWO balls, with TWO liters of volume altogether?

Paradox abounds. The Banach-Tarski Theorem is less interesting for its detailed proof than for the philosophical challenges it raises.

I will follow the approach and some of the nomenclature of https://hal.science/hal-01673378/document, although I simplify and reorder some of the material. Other presentations treat D (the "difficult" set) incorrectly or gloss over it altogether.

Now we begin the proof. The first step is most important and most difficult. It will show how to duplicate the uncountably infinite number of points in a sphere.
In the preceding episodes we had one duplication problem where we wanted an angle that was transcendental and another problem where we needed an angle that was just an irrational multiple of pi. For our next construction, we will do rotations in 3D by TWO different angles and we will want simple rational (or almost-rational!) numbers. It will be the very simplicity that guarantees no undesired collisions occur. Rather than dusting off the LaTeX package, I'll just show the two 3-D rotations in a code block:

          (    1  -2√2   0  )                (   3    0    0   )
     a =  (  2√2    1    0  ) ÷ 3       b =  (   0    1  -2√2  ) ÷ 3
          (    0    0    3  )                (   0   2√2   1   )

Recall that in Post #15 we showed how to duplicate F₂(a, b) -- the "free group of two parameters." We were treating a and b as abstractions, but now we will set them to two rotations, as shown above. a rotates around the z-axis, b around the x-axis. For the inverse terms a^-1 and b^-1, simply flip the signs on the terms with √2. If you multiply any sequence of these matrices together you will always get rational numbers in five of the matrix elements, and rational multiples of √2 in the four locations shown. (The rational multiplier might be zero.) This is the first step -- and the only one I'll highlight -- in proving that any two distinct elements of F₂(a, b) remain distinct when these rotations are substituted for a and b.

Note that F₂(a, b) does NOT include all possible rotations. Obviously it cannot: While infinite, F₂ is countable but the number of distinct 3D rotations is uncountable. Given a starting-point or starting rotation m we will call the set F₂(a,b)∙m the "orbit" of m. The set of all rotations is the union of an uncountable collection of such orbits.

But these elements of F₂(a, b) are rotations while what we want are points on the sphere. It is going from the rotations to points that we encounter two difficulties -- the only two significant difficulties in the Banach-Tarski proof.

Suppose that ( xyz, yz, z, e ) are elements of the set of rotations F₂. e (the identity) is mapped to a starting point O₁, and the four rotations map to the four points ( xyz∙O₁, yz∙O₁, z∙O₁, O₁ ). But now suppose that we pick instead O₂ = yz∙O₁ as the starting point. The same points are contained in the generated set: ( x∙O₂, O₂, y^-1∙O₂, z^-1y^-1∙O₂ ). This is the first difficulty: Which starting point do we choose? It doesn't really matter at all -- as just explained, the same "orbit" is generated regardless of which of its elements is selected as the starting-point -- but, because of the way we will manipulate F₂, we do need to make a Choice. So . . . we apply the Axiom of Choice. Voilà !! Next problem.

The second difficulty is that every rotation in F₂(a, b) defines an axis of rotation; the axis has two endpoints where it intersects the sphere, rotating an endpoint by that rotation will leave the point unchanged. That duplication will leave the orbit ill-founded: With one point present TWICE in the set F₂∙m the duplication of F₂∙m will not proceed properly.

The solution is to simply delete the difficult points from the sphere, before we duplicate it. We don't just delete the axis endpoints; we delete the entirety of all orbits containing a difficult point. This will produce a set D of difficult points. D will be the union of a countably infinite collection of orbits, with each orbit countably infinite, but D will still be countable. The residue (S\D) -- points on the sphere not in one of the difficult orbits -- will be uncountable.

If you examine many of the proofs of Banach-Tarski shown on the 'Net, including Wikipedia's, D is set to just the axis endpoints, and not to the entirety of orbits containing those endpoints. I read and re-read in vain trying to understand how they cope with the problem this imposes on the duplication of F₂. Maybe they have a solution to that, but gloss over it. Anyway, I was relieved to find the CORRECT derivation I link to above.

Okay. Because D is countable, there will be an axis of rotation whose endpoints are not in D. Furthermore, there will be a rotation p about that axis such that the sets shown in the following union are disjoint:

E = D ⋃ p∙D ⋃ p²∙D ⋃ p³∙D ⋃ p⁴∙D ...​

Ready? The plan is

• to decompose S (the points of the sphere) into (S\D)
  
  S = (S\E) ⋃ E ⇛ (S\E) ⋃ pE = (S\E) ⋃ (E\D) = (S\D)​
• to partition (S\D) into its (non-difficult) orbits, each of the form F₂(a,b)∙m
• to partition each such orbit into four pieces, and then duplicate the orbit. For brevity let F denote a given F₂(a,b)∙m and let G(x) denote the subset of F which begins with a rotation x. (This decomposition was shown in a previous episode.)
  
  T = {e, a^-1, a^-1∙a^-1, a^-1∙a^-1∙a^-1, ... }​
  F = G(b) ⋃ G(b^-1) ⋃ G(a) ⋃ T ⋃ (G(a^-1) \ T)​
  b^-1∙G(b) ⋃ G(b^-1) ⇛ F^*​
  a^-1∙G(a) ⋃ a^-1∙T ⋃ (G(a^-1) \ T) ⇛ F^**​
  Therefore
  
  F ⇛ F^* ⋃ F^**​
• that duplicates one orbit. We perform this for all the orbits in (S\D). In total (S\D) is divided into only four pieces since the rotations are the same for all orbits.
• (S\D) = (S\E) ⋃ (E\D) ⇛ (S\E) ⋃ p^-1(E\D) = (S\E) ⋃ E = S

And -- drumroll, please! -- the sphere has been completely duplicated! We simply rotated the difficult points away, duplicated what was left, then rotated the difficult points back in!

A ball is simply an uncountable collection of spheres (like the ultra-thin layers of an onion), plus the single point at the very center. We duplicate all the spheres: this is done in one fell swoop since all the rotation angles will be identical for the spheres. We still need to duplicate the single point (O) at the very center, but this will be rather an anti-climax.

Let J = { O } be the singleton set we need to duplicate.
Using the same axis and angle p used above to form set E, find a countably infinite set of points H = { O, p∙O, p²∙O, p³∙O, p⁴∙O, ... } along a circle

H = J ⋃ (H\J) ⇛ J^* ⋃ p^-1∙(H\J) = J^* ⋃ H​

The ball has been duplicated.