Choice — Read

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

Introduction

In chapters “Cardinals” through “Cardinal Arithmetic”, we developed a theory of cardinals by treating cardinals as ordinals. That approach depends upon the Axiom of Well-Ordering. It turns out that Well-Ordering is equivalent to another principle---the Axiom of Choice---and there has been serious philosophical discussion of its acceptability. Our question for this chapter are: How is the Axiom used, and can it be justified?

The Tarski--Scott Trick

In definition one in chapter “Cardinals”, we defined cardinals as ordinals. To do this, we assumed the Axiom of Well-Ordering. We did this, for no other reason than that it is the “industry standard”.

Before we discuss any of the philosophical issues surrounding Well-Ordering, then, it is important to be clear that we can depart from the industry standard, and develop a theory of cardinals without assuming Well-Ordering. We can still employ the definitions of $\cardeq{A}{B}$ source, $\cardle{A}{B}$ source and $\cardless{A}{B}$ source, as they appeared in chapter “The Size of Sets”. We will just need a new notion of cardinal.

A naïve thought would be to attempt to define $A$ source's cardinality thus:

\Setabs{x}{\cardeq{A}{x}}.

source

You might want to compare this with Frege's definition of $\# x Fx$ source, sketched at the very end of section “Appendix: Hume's Principle” in chapter “Cardinals”. And, for reasons we gestured at there, this definition fails. Any singleton set is equinumerous with $\{\emptyset\}$ source. But new singleton sets are formed at every successor stage of the hierarchy (just consider the singleton of the previous stage). So $\Setabs{x}{\cardeq{A}{x}}$ source does not exist, since it cannot have a rank.

To get around this problem, we use a trick due to Tarski and Scott:Footnote: A reminder: all formulas may have parameters (unless explicitly stated otherwise).

Definition: Tarski--Scott

[Tarski--Scott] For any formula $\phi(x)$ source, let $[ x : \phi(x)]$ source be the set of all $x$ source, of least possible rank, such that $\phi(x)$ source (or $\emptyset$ source, if there are no $\phi$ sources).

We should check that this definition is legitimate. Working in $\ZF$ source, theorem three in chapter “Stages and Ranks” guarantees that $\setrank{x}$ source exists for every $x$ source. Now, if there are any entities satisfying $\phi$ source, then we can let $\alpha$ source be the least rank such that $(\exists x\subseteq V_\alpha)\phi(x)$ source, i.e., $(\forall \beta \in \alpha)(\forall x \subseteq V_\beta)\lnot \phi(x)$ source. We can then define $[x : \phi(x)]$ source by Separation as $\Setabs{x \in V_{\alpha+1}}{\phi(x)}$ source.

Having justified the Tarski--Scott trick, we can now use it to define a notion of cardinality:

Definition two in this chapter

The textscts-cardinality of $A$ source is $\text{tsc}(A) = [x : \cardeq{A}{x}]$ source.

The definition of a textscts-cardinal does not use Well-Ordering. But, even without that Axiom, we can show that textscts-cardinals behave rather like cardinals as defined in definition one in chapter “Cardinals”. For example, if we restate the lemma on Cardinals Behave Right and the lemma on Size Powersettwo Exp in terms of textscts-cardinals, the proofs go through just fine in $\ZF$ source, without assuming Well-Ordering.

Whilst we are on the topic, it is worth noting that we can also develop a theory of ordinals using the Tarski--Scott trick. Where $\tuple{A, <}$ source is a well-ordering, let $\text{tso}(A, <) = [\tuple{X, R} : \ordeq{\tuple{A, <}}{\tuple{X, R}}]$ source. For more on this treatment of cardinals and ordinals, see Michael Potter (2004), chs. 9–12.

Comparability and Hartogs' Lemma

That's the plus side. Here's the minus side. Without Choice, things get messy. To see why, here is a nice result due to Friedrich Hartogs (1915):

Lemma: in set theory Z F

[in $\ZF$ source] For any set $A$ source, there is an ordinal $\alpha$ source such that $\cardnless{\alpha}{A}$ source

Proof

If $B \subseteq A$ source and $R \subseteq B^2$ source, then $\tuple{B, R} \subseteq V_{\setrank{A}+4}$ source by lemma four in chapter “Ordinal Arithmetic”. So, using Separation, consider:

C = \Setabs{\tuple{B, R} \in V_{\setrank{A}+5}}{B\subseteq A \text{ and $\tuple{B, R}$ is a well-ordering}}

source

Using Replacement and theorem five in chapter “Ordinals”, form the set:

\alpha = \Setabs{\ordtype{B, R}}{\tuple{B, R} \in C}.

source

By corollary four in chapter “Ordinals”, $\alpha$ source is an ordinal, since it is a transitive set of ordinals. After all, if $\gamma \in \beta \in \alpha$ source, then $\beta = \ordtype{B, R}$ source for some $B \subseteq R$ source, whereupon $\gamma = \ordtype{B_b, R_b}$ source for some $b \in B$ source by lemma three in chapter “Ordinals”, so that $\gamma \in \alpha$ source.

For reductio, suppose there is an injection $f \colon \alpha \to A$ source. Then, where:

B &= \ran{f}\\ R &= \Setabs{\tuple{f(\alpha), f(\beta)} \in A \times A}{\alpha \in \beta}.

source

Clearly $\alpha = \ordtype{B, R}$ source and $\tuple{B, R} \in C$ source. So $\alpha \in \alpha$ source, which is a contradiction.

This entails a deep result:

Theorem: in set theory Z F

[in $\ZF$ source] The following claims are equivalent:

The Axiom of Well-Ordering
Either $\cardle{A}{B}$ source or $\cardle{B}{A}$ source, for any sets $A$ source and $B$ source

Proof

item 1 of theorem “in set theory Z F” in chapter “Choice” $\Rightarrow$ source item 2 of theorem “in set theory Z F” in chapter “Choice”. Fix $A$ source and $B$ source. Invoking item 1 of theorem “in set theory Z F” in chapter “Choice”, there are well-orderings $\tuple{A, R}$ source and $\tuple{B, S}$ source. Invoking theorem five in chapter “Ordinals”, let $f \colon \alpha \to \tuple{A, R}$ source and $g \colon \beta \to \tuple{B, S}$ source be isomorphisms. By proposition five in chapter “Ordinals”, either $\alpha \subseteq \beta$ source or $\beta \subseteq \alpha$ source. If $\alpha \subseteq \beta$ source, then $\comp{f^{-1}}{g} \colon A \to B$ source is an injection, and hence $\cardle{A}{B}$ source; similarly, if $\beta \subseteq \alpha$ source then $\cardle{B}{A}$ source.

item 2 of theorem “in set theory Z F” in chapter “Choice” $\Rightarrow$ source item 1 of theorem “in set theory Z F” in chapter “Choice”. Fix $A$ source; by lemma “in set theory Z F” in chapter “Choice” there is some ordinal $\beta$ source such that $\cardnless{\beta}{A}$ source. Invoking item 2 of theorem “in set theory Z F” in chapter “Choice”, we have $\cardle{A}{\beta}$ source. So there is some injection $f \colon A \to \beta$ source, and we can use this injection to well-order the elements of $A$ source, by defining an order $\Setabs{\tuple{a, b} \in A \times A}{f(a) \in f(b)}$ source.

noindent As an immediate consequence: if Well-Ordering fails, then some sets are literally incomparable with regard to their size. So, if Well-Ordering fails, then transfinite cardinal arithmetic will be messy. For example, we will have to abandon the idea that if $A$ source and $B$ source are infinite then $\cardeq{\cardeq{A \disjointsum B}{A \times B}}{M}$ source, where $M$ source is the larger of $A$ source and $B$ source (see theorem two in chapter “Cardinal Arithmetic”). The problem is simple: if we cannot compare the size of $A$ source and $B$ source, then it is nonsensical to ask which is larger.

The Well-Ordering Problem

Evidently rather a lot hangs on whether we accept Well-Ordering. But the discussion of this principle has tended to focus on an equivalent principle, the Axiom of Choice. So we will now turn our attention to that (and prove the equivalence).

In 1883, Cantor expressed his support for the Axiom of Well-Ordering, calling it “a law of thought which appears to me to be fundamental, rich in its consequences, and particularly remarkable for its general validity” (cited in Michael Potter 2004, p. 243). But Cantor ultimately became convinced that the “Axiom” was in need of proof. So did the mathematical community.

The problem was “solved” by Zermelo in 1904. To explain his solution, we need some definitions.

Definition three in this chapter

A function $f$ source is a choice function iff $f(x) \in x$ source for all $x \in \dom{f}$ source. We say that $f$ source is a choice function for $A$ source iff $f$ source is a choice function with $\dom{f} = A \setminus \{\emptyset\}$ source.

Intuitively, for every (non-empty) set $x \in A$ source, a choice function for $A$ source chooses a particular element, $f(x)$ source, from $x$ source. The Axiom of Choice is then:

Axiom: Choice

[Choice] Every set has a choice function.

Zermelo showed that Choice entails well-ordering, and vice versa:

Theorem: in set theory Z F

[in $\ZF$ source] Well-Ordering and Choice are equivalent.

Proof

Left-to-right. Let $A$ source be a set of sets. Then $\bigcup A$ source exists by the Axiom of Union, and so by Well-Ordering there is some $<$ source which well-orders $\bigcup A$ source. Now let $f(x) = \text{the$ source< $-least member of }x$ source. This is a choice function for $A$ source.

Right-to-left. Fix $A$ source. By Choice, there is a choice function, $f$ source, for $\Pow{A} \setminus \{\emptyset\}$ source. Using Transfinite Recursion, define a function:

g(0) &= f(A)\\ g(\alpha) &= \begin{cases} \text{stop!{}} &\text{if }A = \funimage{g}{\alpha}\\ f(A \setminus \funimage{g}{\alpha}) & \text{otherwise}\\ \end{cases}

source

The indication to “stop!” is just a shorthand for what would otherwise be a more long-winded definition. That is, when $A = \funimage{g}{\alpha}$ source for the first time, let $g(\delta) = A$ source for all $\delta \leq \alpha$ source. Now, in the first instance, we can only be sure that this defines a term (see the remarks after theorem “General Recursion” in chapter “Stages and Ranks”); but we will show that we indeed have a function.

Since $f$ source is a choice function, for each $\alpha$ source (when defined) we have $g(\alpha) = f(A \setminus \funimage{g}{\alpha}) \in A \setminus \funimage{g}{\alpha}$ source; i.e., $g(\alpha) \notin \funimage{g}{\alpha}$ source. So if $g(\alpha) = g(\beta)$ source then $g(\beta) \notin \funimage{g}{\alpha}$ source, i.e., $\beta \notin \alpha$ source, and similarly $\alpha \notin \beta$ source. So $\alpha = \beta$ source, by Trichotomy. So $g$ source is injective.

Next, observe that we do stop!, i.e.\ that there is some (least) ordinal $\alpha$ source such that $A = g[\alpha]$ source. For suppose otherwise; then as $g$ source is injective we would have $\cardless{\alpha}{\Pow{A} \setminus \{\emptyset\}}$ source for every ordinal $\alpha$ source, contradicting lemma “in set theory Z F” in chapter “Choice”. Hence also $\ran{g} = A$ source.

Assembling these facts, $g$ source is a bijection from some ordinal to $A$ source. Now $g$ source can be used to well-order $A$ source.

So Well-Ordering and Choice stand or fall together. But the question remains: do they stand or fall?

Countable Choice

It is easy to prove, without any use of Choice/Well-Ordering, that:

Lemma: in set theory Z minus

[in $\Zminus$ source] Every finite set has a choice function.

Proof

Let $a = \{b_1, \ldots, b_n\}$ source. Suppose for simplicity that each $b_i \neq \emptyset$ source. So there are objects $c_1, \ldots, c_n$ source such that $c_1 \in b_1, \ldots, c_n \in b_n$ source. Now by the proposition on pairsconsequences, the set $\{\langle b_1, c_1\rangle , \ldots, \langle b_n, c_n\rangle\}$ source exists; and this is a choice function for $a$ source.

But matters get murkier as soon as we consider infinite sets. For example, consider this “minimal” extension to the above:

Definition four in this chapter

Countable Choice. Every countable set has a choice function.

This is a special case of Choice. And it transpires that this principle was invoked fairly frequently, without an obvious awareness of its use. Here are two nice examples.Footnote: Due to Michael Potter (2004), §9.4 and Luca Incurvati.

Example one in this chapter

Here is a natural thought: for any set $A$ source, either $\cardle{\omega}{A}$ source, or $\cardeq{A}{n}$ source for some $n \in \omega$ source. This is one way to state the intuitive idea, that every set is either finite or infinite. Cantor, and many other mathematicians, made this claim without proving it. Cautious as we are, we proved this in theorem one in chapter “Cardinals”. But in that proof we were working in $\ZFC$ source, since we were assuming that any set $A$ source can be well-ordered, and hence that $\card{A}$ source is guaranteed to exist. That is: we explicitly assumed Choice.

In fact, Richard Dedekind (1888) offered his own proof of this claim, as follows:

Theorem: in set theory Z minus plus Countable Choice

[in $\Zminus + \text{Countable Choice}$ source] For any $A$ source, either $\cardle{\omega}{A}$ source or $\cardeq{A}{n}$ source for some $n \in \omega$ source.

Proof

Suppose $\cardneq{A}{n}$ source for all $n \in \omega$ source. Then in particular for each $n < \omega$ source there is subset $A_n \subseteq A$ source with exactly $\cardexpo{2}{n}$ source elements. Using this sequence $A_0, A_1, A_2, \ldots$ source, we define for each $n$ source:

B_n = A_n \setminus \bigcup_{i < n} A_i.

source

Now note the following

\card{\bigcup_{i < n}A_n} &\leq \card{A_0} + \card{A_1} + \ldots + \card{A_{n-1}}\\ &=1 + 2 + \ldots + 2^{n-1}\\ & = 2^n - 1\\ & < 2^n = \card{A_n}

source

Hence each $B_n$ source has at least one member, $c_n$ source. Moreover, the $B_n$ sources are pairwise disjoint; so if $c_n = c_m$ source then $n = m$ source. But every $c_n \in A$ source. So the function $f(n) = c_n$ source is an injection $\omega \to A$ source.

noindent Dedekind did not flag that he had used Countable Choice. But, did you spot its use? Look again. (Really: look again.)

The proof used Countable Choice twice. We used it once, to obtain our sequence of sets $A_0$ source, $A_1$ source, $A_2$ source, dots We then used it again to select our elements $c_n$ source from each $B_n$ source. Moreover, this use of Choice is ineliminable. Paul J. Cohen (1966), p. 138 proved that the result fails if we have no version of Choice. That is: it is consistent with $\ZF$ source that there are sets which are incomparable with $\omega$ source.

Example two in this chapter

In 1878, Cantor stated that a countable union of countable sets is countable. He did not present a proof, perhaps indicating that he took the proof to be obvious. Now, cautious as we are, we proved a more general version of this result in proposition four in chapter “Cardinal Arithmetic”. But our proof explicitly assumed Choice. And even the proof of the less general result requires Countable Choice.

Theorem: in set theory Z minus plus Countable Choice

[in $\Zminus + \text{Countable Choice}$ source] If $A_n$ source is countable for each $n \in \omega$ source, then $\bigcup_{n < \omega} A_n$ source is countable.

Proof

Without loss of generality, suppose that each $A_n \neq \emptyset$ source. So for each $n \in \omega$ source there is a surjection $f_n \colon \omega \to A_n$ source. Define $f \colon \omega \times \omega \to \bigcup_{n < \omega} A_n$ source by $f(m, n) = f_n(m)$ source. The result follows because $\omega \times \omega$ source is countable (proposition “Enumerability of pairs of natural numbers” in chapter “The Size of Sets”) and $f$ source is a surjection.

noindent Did you spot the use of the Countable Choice? It is used to choose our sequence of functions $f_0$ source, $f_1$ source, $f_2$ source, dotsFootnote: A similar use of Choice occurred in proposition four in chapter “Cardinal Arithmetic”, when we gave the instruction “For each $\beta \in \cardfont{a}$ source, fix an injection $f_\beta$ source”. And again, the result fails in the absence of any Choice principle. Specifically, Solomon Feferman and Azriel Levy (1963) proved that it is consistent with $\ZF$ source that a countable union of countable sets has cardinality $\beth_1$ source. But here is a much funnier statement of the point, from Russell:

This is illustrated by the millionaire who bought a pair of socks whenever he bought a pair of boots, and never at any other time, and who had such a passion for buying both that at last he had $\aleph_0$ source pairs of boots and $\aleph_0$ source pairs of socksdots Among boots we can distinguish right and left, and therefore we can make a selection of one out of each pair, namely, we can choose all the right boots or all the left boots; but with socks no such principle of selection suggests itself, and we cannot be sure, unless we assume the multiplicative axiom [i.e., in effect Choice], that there is any class consisting of one sock out of each pair. (Bertrand Russell, 1919, p. 126)

In short, some form of Choice is needed to prove the following: If you have countably many pairs of socks, then you have (only) countably many socks. And in fact, without Countable Choice (or something equivalent), a countable union of countable sets can fail to be countable.

The moral is that Countable Choice was used repeatedly, without much awareness of its users. The philosophical question is: How could we justify Countable Choice?

An attempt at an intuitive justification might invoke an appeal to a supertask. Suppose we make the first choice in $\nicefrac{1}{2}$ source a minute, our second choice in $\nicefrac{1}{4}$ source a minute, dots, our $n$ source-th choice in $\nicefrac{1}{2^n}$ source a minute, dots Then within $1$ source minute, we will have made an $\omega$ source-sequence of choices, and defined a choice function.

But what, really, could such a thought-experiment tell us? For a start, it relies upon taking this idea of “choosing” rather literally. For another, it seems to bind up mathematics in metaphysical possibility.

More important: it is not going to give us any justification for Choice tout court, rather than mere Countable Choice. For if we need every set to have a choice function, then we'll need to be able to perform a “supertask of arbitrary ordinal length.” Bluntly, that idea is laughable.

Intrinsic Considerations about Choice

The broader question, then, is whether Well-Ordering, or Choice, or indeed the comparability of all sets as regards their size---it doesn't matter which---can be justified.

Here is an attempted intrinsic justification. Back in section “The Story in More Detail” in chapter “Steps towards Z”, we introduced several principles about the hierarchy. One of these is worth restating:

stagesacc. For any stage $S$ source, and for any sets which were formed before stage $S$ source: a set is formed at stage $S$ source whose members are exactly those sets. Nothing else is formed at stage $S$ source.

In fact, many authors have suggested that the Axiom of Choice can be justified via (something like) this principle. We will briefly provide a gloss on that approach.

We will start with a simple little result, which offers yet another equivalent for Choice:

Theorem: in set theory Z F

[in $\ZF$ source] Choice is equivalent to the following principle. If the elements of $A$ source are disjoint and non-empty, then there is some $C$ source such that $C \cap x$ source is a singleton for every $x \in A$ source. (We call such a $C$ source a choice set for $A$ source.)

The proof of this result is straightforward, and we leave it as an exercise for the reader.

Exercise one in this chapter

Prove theorem “in set theory Z F” in chapter “Choice”. If you struggle, you can find a proof in Michael Potter (2004), pp. 242–3.

The essential point is that a choice set for $A$ source is just the range of a choice function for $A$ source. So, to justify Choice, we can simply try to justify its equivalent formulation, in terms of the existence of choice sets. And we will now try to do exactly that.

Let $A$ source's elements be disjoint and non-empty. By stageshier (see section “The Story in More Detail” in chapter “Steps towards Z”), $A$ source is formed at some stage $S$ source. Note that all the elements of $\bigcup A$ source are available before stage $S$ source. Now, by stagesacc, for any sets which were formed before $S$ source, a set is formed whose members are exactly those sets. Otherwise put: every possible collections of earlier-available sets will exist at $S$ source. But it is certainly possible to select objects which could be formed into a choice set for $A$ source; that is just some very specific subset of $\bigcup A$ source. So: some such choice set exists, as required.

Well, that's a very quick attempt to offer a justification of Choice on intrinsic grounds. But, to pursue this idea further, you should read Potter's (2004, §14.8) neat development of it.

The Banach--Tarski Paradox

We might also attempt to justify Choice, as Boolos attempted to justify Replacement, by appealing to extrinsic considerations (see section “Extrinsic Considerations about Replacement” in chapter “Replacement”). After all, adopting Choice has many desirable consequences: the ability to compare every cardinal; the ability to well-order every set; the ability to treat cardinals as a particular kind of ordinal; etc.

Sometimes, however, it is claimed that Choice has undesirable consequences. Mostly, this is due to a result by Stefan Banach and Alfred Tarski (1924).

Theorem: Banach--Tarski Paradox (in set theory Z F C)

[Banach--Tarski Paradox (in $\ZFC$ source)] Any ball can be decomposed into finitely many pieces, which can be reassembled (by rotation and transportation) to form two copies of that ball.

noindent At first glance, this is a bit amazing. Clearly the two balls have twice the volume of the original ball. But rigid motions---rotation and transportation---do not change volume. So it looks as if Banach--Tarski allows us to magick new matter into existence.

It gets worse.Footnote: See Grzegorz Tomkowicz and Stan Wagon (2016), Theorem 3.12. Similar reasoning shows that a pea can be cut into finitely many pieces, which can then be reassembled (by rotation and transportation) to form an entity the shape and size of Big Ben.

None of this, however, holds in $\ZF$ source on its own.Footnote: Though Banach--Tarski can be proved with principles which are strictly weaker than Choice; see Grzegorz Tomkowicz and Stan Wagon (2016), 303. So we face a decision: reject Choice, or learn to live with the “paradox”.

We're going to suggest that we should learn to live with the “paradox”. Indeed, we don't think it's much of a paradox at all. In particular, we don't see why it is any more or less paradoxical than any of the following results:Footnote: Michael Potter (2004), 276–7, Tom Weston (2003), 16, Grzegorz Tomkowicz and Stan Wagon (2016), 31, 308–9, make similar points, using other examples.

There are as many points in the interval $(0,1)$ source as in $\Real$ source. \ OL_INLINE_000019@@: consider $\tan(\pi(r-\nicefrac{1}{2})))$ source.
There are as many points in a line as in a square. \See section “Pathologies” in chapter “History and Mythology of Set Theory” and section “Cantor on the Line and the Plane” in chapter “History and Mythology of Set Theory”.
There are space-filling curves. \See section “Pathologies” in chapter “History and Mythology of Set Theory” and section “Appendix: Hilbert's Space-filling Curves” in chapter “History and Mythology of Set Theory”.

None of these three results require Choice. Indeed, we now just regard them as surprising, lovely, bits of mathematics. Maybe we should adopt the same attitude to the Banach--Tarski Paradox.

To be sure, a technical observation is required here; but it only requires keeping a level head. Rigid motions preserve volume. Consequently, the fiveFootnote: We stated the Paradox in terms of “finitely many pieces”. In fact, Raphael Robinson (1947) proved that the decomposition can be achieved with five pieces (but no fewer). For a proof, see Grzegorz Tomkowicz and Stan Wagon (2016), pp. 66–7. pieces into which the ball is decomposed cannot all be measurable. Roughly put, then, it makes no sense to assign a volume to these individual pieces. You should think of these as unpicturable, “infinite scatterings” of points. Now, maybe it is “weird” to conceive of such “infinitely scattered” sets. But their existence seems to fall out from the injunction, embodied in stagesacc, that you should form all possible collections of earlier-available sets.

If none of that convinces, here is a final (extrinsic) argument in favour of embracing the Banach--Tarski Paradox. It immediately entails the best math joke of all time:

Question. What's an anagram of “Banach--Tarski”?
Answer. “Banach--Tarski Banach--Tarski”.

Appendix: Vitali's Paradox

To get a real sense of whether the Banach-Tarski construction is acceptable or not, we should examine its proof. Unfortunately, that would require much more algebra than we can present here. However, we can offer some quick remarks which might shed some insight on the proof of Banach-Tarski,Footnote: For a much fuller treatment, see Tom Weston (2003) or Grzegorz Tomkowicz and Stan Wagon (2016). by focussing on the following result:

Theorem: Vitali's Paradox (in set theory Z F C)

[Vitali's Paradox (in $\ZFC$ source)] Any circle can be decomposed into countably many pieces, which can be reassembled (by rotation and transportation) to form two copies of that circle.

Vitali's Paradox is much easier to prove than the Banach--Tarski Paradox. We have called it “Vitali's Paradox”, since it follows from Vitali's 1905 construction of an unmeasurable set. But the set-theoretic aspects of the proof of Vitali's Paradox and the Banach-Tarski Paradox are very similar. The essential difference between the results is just that Banach-Tarski considers a finite decomposition, whereas Vitali's Paradox considers a countably infinite decomposition. As Tom Weston (2003) puts it, Vitali's Paradox “is certainly not nearly as striking as the Banach--Tarski paradox, but it does illustrate that geometric paradoxes can happen even in `simple' situations.”

Vitali's Paradox concerns a two-dimensional figure, a circle. So we will work on the plane, $\Real^2$ source. Let $\rotationsgroup$ source be the set of (clockwise) rotations of points around the origin by rational radian values between $[0,2\pi)$ source. Here are some algebraic facts about $\rotationsgroup$ source (if you don't understand the statement of the result, the proof will make its meaning clear):

Lemma three in this chapter

$\rotationsgroup$ source forms an abelian group under composition of functions.

Proof

Writing $0_{\rotationsgroup}$ source for the rotation by $0$ source radians, this is an identity element for $\rotationsgroup$ source, since $\comp{0_{\rotationsgroup}}{\rho} = \comp{\rho}{0_{\rotationsgroup}} = \rho$ source for any $\rho \in \rotationsgroup$ source.

Every element has an inverse. Where $\rho \in \rotationsgroup$ source rotates by $r$ source radians, $\rho^{-1} \in \rotationsgroup$ source rotates by $2\pi - r$ source radians, so that $\rho \circ \rho^{-1} = 0_\rotationsgroup$ source.

Composition is associative: $\comp{\rho}{(\comp{\sigma}{\tau})} = \comp{(\comp{\rho}{\sigma})}{\tau}$ source for any $\rho, \sigma, \tau \in \rotationsgroup$ source

Composition is commutative: $\comp{\rho}{\sigma} = \comp{\sigma}{\rho}$ source for any $\rho, \sigma \in \rotationsgroup$ source.

In fact, we can split our group $\rotationsgroup$ source in half, and then use either half to recover the whole group:

Lemma four in this chapter

There is a partition of $\rotationsgroup$ source into two disjoint sets, $\rotationsgroup_{1}$ source and $\rotationsgroup_{2}$ source, both of which are a basis for $\rotationsgroup$ source.

Proof

Let $\rotationsgroup_{1}$ source consist of the rotations by rational radian values in $[0, \pi)$ source; let $\rotationsgroup_{2} = \rotationsgroup \setminus \rotationsgroup_1$ source. By elementary algebra, $\Setabs{\comp{\rho}{\rho}}{\rho \in \rotationsgroup_1} = \rotationsgroup$ source. A similar result can be obtained for $\rotationsgroup_2$ source.

We will use this fact about groups to establish theorem “Vitali's Paradox (in set theory Z F C)” in chapter “Choice”. Let $\onesphere$ source be the unit circle, i.e., the set of points exactly $1$ source unit away from the origin of the plane, i.e., $\Setabs{\tuple{r,s} \in \Real^2}{\sqrt{r^2+s^2}=1}$ source. We will split $\onesphere$ source into parts by considering the following relation on $\onesphere$ source:

r \sim s \emph{ iff }(\exists \rho \in \rotationsgroup)\rho(r) = s.

source

That is, the points of $\onesphere$ source are linked by this relation iff you can get from one to the other by a rational-valued rotation about the origin. Unsurprisingly:

Lemma five in this chapter

$\sim$ source is an equivalence relation.

Proof

Trivial, using lemma three in chapter “Choice”.

We now invoke Choice to obtain a set, $C$ source, containing exactly one member from each equivalence class of $\onesphere$ source under $\sim$ source. That is, we consider a choice function $f$ source on the set of equivalence classes,Footnote: Since $\rotationsgroup$ source is enumerable, each element of $E$ source is enumerable. Since $\onesphere$ source is non-enumerable, it follows from lemma six in chapter “Choice” and proposition four in chapter “Cardinal Arithmetic” that $E$ source is non-enumerable. So this is a use of uncountable Choice.

E = \Setabs{\equivrep{r}{\sim}}{r \in \onesphere},

source

and let $C = \ran{f}$ source. For each rotation $\rho \in \rotationsgroup$ source, the set $\funimage{\rho}{C}$ source consists of the points obtained by applying the rotation $\rho$ source to each point in $C$ source. These next two results show that these sets cover the circle completely and without overlap:

Lemma six in this chapter

$\onesphere = \bigcup_{\rho \in \rotationsgroup} \funimage{\rho}{C}$ source.

Proof

Fix $s \in \onesphere$ source; there is some $r \in C$ source such that $r \in \equivrep{s}{\sim}$ source, i.e., $r \sim s$ source, i.e., $\rho(r) = s$ source for some $\rho \in \rotationsgroup$ source.

Lemma seven in this chapter

If $\rho_1 \neq \rho_2$ source then $\funimage{\rho_1}{C} \cap \funimage{\rho_2}{C} = \emptyset$ source.

Proof

Suppose $s \in \funimage{\rho_{1}}{C} \cap \funimage{\rho_{2}}{C}$ source. So $s = \rho_{1}(r_{1}) = \rho_{2}(r_{2})$ source for some $r_{1}, r_{2} \in C$ source. Hence $\rho^{-1}_2(\rho_1(r_1)) = r_2$ source, and $\comp{\rho_1}{\rho^{-1}_2} \in \rotationsgroup$ source, so $r_{1} \sim r_{2}$ source. So $r_1 = r_2$ source, as $C$ source selects exactly one member from each equivalence class under $\sim$ source. So $s = \rho_1(r_1) = \rho_2(r_1)$ source, and hence $\rho_1 = \rho_2$ source.

We now apply our earlier algebraic facts to our circle:

Lemma eight in this chapter

There is a partition of $\onesphere$ source into two disjoint sets, $D_{1}$ source and $D_{2}$ source, such that $D_{1}$ source can be partitioned into countably many sets which can be rotated to form a copy of $\onesphere$ source (and similarly for $D_{2}$ source).

Proof

Using $\rotationsgroup_{1}$ source and $\rotationsgroup_{2}$ source from lemma four in chapter “Choice”, let:

D_{1} &= \bigcup_{\rho \in \rotationsgroup_1} \funimage{\rho}{C} & D_{2} &= \bigcup_{\rho \in \rotationsgroup_2} \funimage{\rho}{C}

source

This is a partition of $\onesphere$ source, by lemma six in chapter “Choice”, and $D_1$ source and $D_2$ source are disjoint by lemma seven in chapter “Choice”. By construction, $D_1$ source can be partitioned into countably many sets, $\funimage{\rho}{C}$ source for each $\rho \in R_1$ source. And these can be rotated to form a copy of $\onesphere$ source, since $\onesphere = \bigcup_{\rho \in \rotationsgroup}\funimage{\rho}{C} = \bigcup_{\rho \in \rotationsgroup_1}\funimage{(\comp{\rho}{\rho})}{C}$ source by lemma four in chapter “Choice” and lemma six in chapter “Choice”. The same reasoning applies to $D_2$ source.

noindent This immediately entails Vitali's Paradox. For we can generate two copies of $\onesphere$ source from $\onesphere$ source, just by splitting it up into countably many pieces (the various $\funimage{\rho}{C}$ source's) and then rigidly moving them (simply rotate each piece of $D_1$ source, and first transport and then rotate each piece of $D_2$ source).

Let's recap the proof-strategy. We started with some algebraic facts about the group of rotations on the plane. We used this group to partition $\onesphere$ source into equivalence classes. We then arrived at a “paradox”, by using Choice to select elements from each class.

We use exactly the same strategy to prove Banach--Tarski. The main difference is that the algebraic facts used to prove Banach--Tarski are significantly more complicated than those used to prove Vitali's Paradox. But those algebraic facts have nothing to do with Choice. We will summarise them quickly.

To prove Banach--Tarski, we start by establishing an analogue of lemma four in chapter “Choice”: any free group can be split into four pieces, which intuitively we can “move around” to recover two copies of the whole group.Footnote: The fact that we can use four pieces is due to Raphael Robinson (1947). For a recent proof, see Grzegorz Tomkowicz and Stan Wagon (2016), Theorem 5.2. We follow Tom Weston (2003), p. 3 in describing this as “moving” the pieces of the group. We then show that we can use two particular rotations around the origin of $\Real^3$ source to generate a free group of rotations, $F$ source.Footnote: See Grzegorz Tomkowicz and Stan Wagon (2016), Theorem 2.1. (No Choice yet.) We now regard points on the surface of the sphere as “similar” iff one can be obtained from the other by a rotation in $F$ source. We then use Choice to select exactly one point from each equivalence class of “similar” points. Applying our division of $F$ source to the surface of the sphere, as in lemma eight in chapter “Choice”, we split that surface into four pieces, which we can “move around” to obtain two copies of the surface of the sphere. And this establishes (Felix Hausdorff, 1914):

Theorem: Hausdorff's Paradox (in set theory Z F C)

[Hausdorff's Paradox (in $\ZFC$ source)] The surface of any sphere can be decomposed into finitely many pieces, which can be reassembled (by rotation and transportation) to form two disjoint copies of that sphere.

A couple of further algebraic tricks are needed to obtain the full Banach-Tarski Theorem (which concerns not just the sphere's surface, but its interior too). Frankly, however, this is just icing on the algebraic cake. Hence Weston writes:

[…] the result on free groups is the key step in the proof of the Banach-Tarski paradox. From this point of view, the Banach-Tarski paradox is not a statement about $\Real^3$ source so much as it is a statement about the complexity of the group [of translations and rotations in $\Real^3$ source]. Tom Weston (2003), p. 16

That is: whether we can offer a finite decomposition (as in Banach--Tarski) or a countably infinite decomposition (as in Vitali's Paradox) comes down to certain group-theoretic facts about working in two-dimension or three-dimensions.

Admittedly, this last observation slightly spoils the joke at the end of section “The Banach--Tarski Paradox” in chapter “Choice”. Since it is two dimensional, “Banach-Tarski” must be divided into a countable infinity of pieces, if one wants to rearrange those pieces to form “Banach-Tarski Banach-Tarski”. To repair the joke, one must write in three dimensions. We leave this as an exercise for the reader.

One final comment. In section “The Banach--Tarski Paradox” in chapter “Choice”, we mentioned that the “pieces” of the sphere one obtains cannot be measurable, but must be unpicturable “infinite scatterings”. The same is true of our use of Choice in obtaining lemma eight in chapter “Choice”. And this is all worth explaining.

Again, we must sketch some background (but this is just a sketch; you may want to consult a textbook entry on measure). To define a measure for a set $X$ source is to assign a value $\mu(E) \in \Real$ source for each $E$ source in some “ $\sigma$ source-algebra” on $X$ source. Details here are not essential, except that the function $\mu$ source must obey the principle of countable additivity: the measure of a countable union of disjoint sets is the sum of their individual measures, i.e., $\mu(\bigcup_{n < \omega} X_n) = \sum_{n < \omega}\mu(X_n)$ source whenever the $X_n$ sources are disjoint. To say that a set is “unmeasurable” is to say that no measure can be suitably assigned. Now, using our $\rotationsgroup$ source from before:

Corollary: Vitali

[Vitali] Let $\mu$ source be a measure such that $\mu(\onesphere) = 1$ source, and such that $\mu(X) = \mu(Y)$ source if $X$ source and $Y$ source are congruent. Then $\funimage{\rho}{C}$ source is unmeasurable for all $\rho \in \rotationsgroup$ source.

Proof

For reductio, suppose otherwise. So let $\mu(\funimage{\sigma}{C}) = r$ source for some $\sigma \in \rotationsgroup$ source and some $r \in \Real$ source. For any $\rho \in C$ source, $\funimage{\rho}{C}$ source and $\funimage{\sigma}{C}$ source are congruent, and hence $\mu(\funimage{\rho}{C}) = r$ source for any $\rho \in C$ source. By lemma six in chapter “Choice” and lemma seven in chapter “Choice”, $\onesphere = \bigcup_{\rho \in \rotationsgroup}\funimage{\rho}{C}$ source is a countable union of pairwise disjoint sets. So countable additivity dictates that $\mu(\onesphere) = 1$ source is the sum of the measures of each $\funimage{\rho}{C}$ source, i.e.,

1 = \mu(\onesphere) = \sum_{\rho \in \rotationsgroup}\mu(\funimage{\rho}{C}) = \sum_{\rho \in \rotationsgroup}r

source

But if $r = 0$ source then $\sum_{\rho \in \rotationsgroup}r = 0$ source, and if $r > 0$ source then $\sum_{\rho \in \rotationsgroup}r = \infty$ source.

Source disclosures

TR073-SAR-001: Source TeX caveat. The tangent formula has one extra closing parenthesis. The frozen formula and source anchor are preserved; the listener reading supplies the unambiguous scope without silently changing the source. source

Reading preferences

Source file content/set-theory/choice/choice.tex

Source file content/set-theory/choice/introduction.tex

Introduction

Source file content/set-theory/choice/tarskiscott.tex

The Tarski--Scott Trick

Definition: Tarski--Scott

Definition two in this chapter

Source file content/set-theory/choice/hartogs.tex

Comparability and Hartogs' Lemma

Lemma: in set theory Z F

Proof

Theorem: in set theory Z F

Proof

Source file content/set-theory/choice/wellorderingproblem.tex

The Well-Ordering Problem

Definition three in this chapter

Axiom: Choice

Theorem: in set theory Z F

Proof

Source file content/set-theory/choice/countablechoice.tex

Countable Choice

Lemma: in set theory Z minus

Proof

Definition four in this chapter

Example one in this chapter

Theorem: in set theory Z minus plus Countable Choice

Proof

Example two in this chapter

Theorem: in set theory Z minus plus Countable Choice

Proof

Source file content/set-theory/choice/justifications.tex

Intrinsic Considerations about Choice

Theorem: in set theory Z F

Exercise one in this chapter

Source file content/set-theory/choice/banach.tex

The Banach--Tarski Paradox

Theorem: Banach--Tarski Paradox (in set theory Z F C)

Source file content/set-theory/choice/vitali.tex

Appendix: Vitali's Paradox

Theorem: Vitali's Paradox (in set theory Z F C)

Lemma three in this chapter

Proof

Lemma four in this chapter

Proof

Lemma five in this chapter

Proof

Lemma six in this chapter

Proof

Lemma seven in this chapter

Proof

Lemma eight in this chapter

Proof

Theorem: Hausdorff's Paradox (in set theory Z F C)

Corollary: Vitali

Proof

Source disclosures