Set Theory

Choice

content/set-theory/choice/choice.tex

% Part: set-theory% Chapter: choice\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{sth}{choice}{Choice}\olimport{introduction}\olimport{tarskiscott}\olimport{hartogs}\olimport{wellorderingproblem}\olimport{countablechoice}\olimport{justifications}\olimport{banach}\olimport{vitali}\OLEndChapterHook\end{document}

content/set-theory/choice/introduction.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{intro}\olsection{Introduction}In \crefrange{sth:cardinals::chap}{sth:card-arithmetic::chap}, wedeveloped a theory of cardinals by treating cardinals as ordinals.That approach depends upon the Axiom of Well-Ordering. It turns outthat Well-Ordering is equivalent to another principle---the Axiom ofChoice---and there has been serious philosophical discussion of itsacceptability. Our question for this chapter are: How is the Axiomused, and can it be justified?\end{document}

content/set-theory/choice/tarskiscott.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{tarskiscott}\olsection{The Tarski--Scott Trick}In \olref[cardinals][cardsasords]{defcardinalasordinal}, wedefined cardinals as ordinals. To do this, we assumed the Axiom ofWell-Ordering. We did this, for no other reason than that it is the``industry standard''.Before we discuss any of the philosophical issues surroundingWell-Ordering, then, it is important to be clear that we \emph{can}depart from the industry standard, and develop a theory of cardinals\emph{without} assuming Well-Ordering. We can still employ thedefinitions of $\cardeq{A}{B}$, $\cardle{A}{B}$ and $\cardless{A}{B}$,as they appeared in \olref[sfr][siz][]{chap}. We will just need a newnotion of \emph{cardinal}.A na\"ive thought would be to attempt to define $A$'s cardinality thus:\[	\Setabs{x}{\cardeq{A}{x}}.\]You might want to compare this with Frege's definition of $\# x Fx$,sketched at the very end of \olref[cardinals][hp]{sec}. And, forreasons we gestured at there, this definition fails. Any singleton setis equinumerous with $\{\emptyset\}$. But new singleton sets areformed at every successor stage of the hierarchy (just consider thesingleton of the previous stage). So $\Setabs{x}{\cardeq{A}{x}}$ doesnot 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).}\begin{defn}[Tarski--Scott]For any formula $\phi(x)$, let$[ x : \phi(x)] $ be the set of all $x$, of least possible rank, suchthat $\phi(x)$ (or $\emptyset$, if there are no $\phi$s).\end{defn}We should check that this definition is legitimate. Working in $\ZF$,\olref[spine][foundation]{zfentailsregularity} guarantees that$\setrank{x}$ exists for every $x$. Now, if there are any entitiessatisfying $\phi$, then we can let $\alpha$ be the least rank suchthat  $(\exists x\subseteq V_\alpha)\phi(x)$, i.e., $(\forall \beta\in \alpha)(\forall x \subseteq V_\beta)\lnot \phi(x)$. We can thendefine $[x : \phi(x)]$ by Separation as $\Setabs{x \inV_{\alpha+1}}{\phi(x)}$. Having justified the Tarski--Scott trick, we can now use it to definea notion of cardinality:\begin{defn}The \textsc{ts}-cardinality of $A$ is $\text{tsc}(A) = [x :\cardeq{A}{x}]$.\end{defn}The definition of a \textsc{ts}-cardinal does not use Well-Ordering.But, even without that Axiom, we can show that\emph{\textsc{ts}-cardinals} behave rather like \emph{cardinals} asdefined in \olref[cardinals][cardsasords]{defcardinalasordinal}.For example, if we restate\olref[cardinals][cardsasords]{lem:CardinalsBehaveRight} and\olref[card-arithmetic][opps]{lem:SizePowerset2Exp} in terms of\textsc{ts}-cardinals, the proofs go through just fine in $\ZF$,without assuming Well-Ordering. Whilst we are on the topic, it is worth noting that we can alsodevelop a theory of ordinals using the Tarski--Scott trick. Where$\tuple{A, <}$ is a well-ordering, let $\text{tso}(A, <) = [\tuple{X,R} : \ordeq{\tuple{A, <}}{\tuple{X, R}}]$. For more on this treatmentof cardinals and ordinals, see \citet[chs.~9--12]{Potter2004}.\end{document}

content/set-theory/choice/hartogs.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{hartogs}\olsection{Comparability and Hartogs' Lemma}That's the plus side. Here's the minus side. Without Choice, thingsget \emph{messy}. To see why, here is a nice result due to\cite{Hartogs1915}:\begin{lem}[\emph{in $\ZF$}]\ollabel{HartogsLemma}For any set $A$, there is an ordinal $\alpha$ such that $\cardnless{\alpha}{A}$\end{lem}\begin{proof}If $B \subseteq A$ and $R \subseteq B^2$, then $\tuple{B, R} \subseteqV_{\setrank{A}+4}$ by\olref[ord-arithmetic][using-addition]{rankcomputation}. So, usingSeparation, consider:\[	C = \Setabs{\tuple{B, R} \in V_{\setrank{A}+5}}{B\subseteq A 	\text{ and $\tuple{B, R}$ is a well-ordering}}\]Using Replacement and\olref[ordinals][ordtype]{thmOrdinalRepresentation}, form the set: \[	\alpha = \Setabs{\ordtype{B, R}}{\tuple{B, R} \in C}.\]By \olref[ordinals][basic]{corordtransitiveord}, $\alpha$ is anordinal, since it is a transitive set of ordinals. After all, if$\gamma \in \beta \in \alpha$, then $\beta = \ordtype{B, R}$ for some$B \subseteq R$, whereupon $\gamma = \ordtype{B_b, R_b}$ for some $b\in B$ by \olref[ordinals][iso]{wellordinitialsegment}, so that$\gamma \in \alpha$. For reductio, suppose there is !!a{injection} $f \colon \alpha \to A$.Then, where:\begin{align*}	B &= \ran{f}\\	R &= \Setabs{\tuple{f(\alpha), f(\beta)} \in A \times A}{\alpha \in \beta}.\end{align*}Clearly $\alpha = \ordtype{B, R}$ and $\tuple{B, R} \in C$. So $\alpha\in \alpha$, which is a contradiction.\end{proof}This entails a deep result:\begin{thm}[\emph{in $\ZF$}]The following claims are equivalent:\begin{enumerate}	\item\ollabel{equivwo} The Axiom of Well-Ordering	\item\ollabel{equivcompare} Either $\cardle{A}{B}$ or	$\cardle{B}{A}$, for any sets $A$ and $B$\end{enumerate}\end{thm}\begin{proof}\emph{\olref{equivwo} $\Rightarrow$ \olref{equivcompare}.} Fix $A$ and$B$. Invoking \olref{equivwo}, there are well-orderings $\tuple{A, R}$and $\tuple{B, S}$. Invoking\olref[ordinals][ordtype]{thmOrdinalRepresentation}, let $f \colon\alpha \to \tuple{A, R}$ and $g \colon \beta \to \tuple{B, S}$ beisomorphisms. By \olref[sth][ordinals][basic]{ordinalsaresubsets}, either $\alpha \subseteq \beta$ or $\beta \subseteq \alpha$. If $\alpha \subseteq \beta$, then $\comp{f^{-1}}{g} \colon A \to B$ is !!a{injection}, and hence$\cardle{A}{B}$; similarly, if $\beta \subseteq \alpha$ then $\cardle{B}{A}$.\emph{\olref{equivcompare} $\Rightarrow$ \olref{equivwo}.} Fix $A$; by\olref{HartogsLemma} there is some ordinal $\beta$ such that$\cardnless{\beta}{A}$. Invoking \olref{equivcompare}, we have$\cardle{A}{\beta}$. So there is some !!{injection} $f \colon A \to\beta$, and we can use this injection to well-order the elements of$A$, by defining an order $\Setabs{\tuple{a, b} \in A \times A}{f(a)\in f(b)}$.\end{proof}\noindentAs an immediate consequence: if Well-Ordering fails, then some setsare \emph{literally incomparable} with regard to their size. So, ifWell-Ordering fails, then transfinite cardinal arithmetic will bemessy. For example, we will have to abandon the idea that if $A$ and$B$ are infinite then $\cardeq{\cardeq{A \disjointsum B}{A \timesB}}{M}$, where $M$ is the larger of $A$ and $B$ (see\olref[card-arithmetic][simp]{cardplustimesmax}). The problem issimple: if we cannot \emph{compare} the size of  $A$ and $B$, then itis nonsensical to ask which is larger.\end{document}

content/set-theory/choice/wellorderingproblem.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{woproblem}\olsection{The Well-Ordering Problem}Evidently rather a lot hangs on whether we accept Well-Ordering. Butthe discussion of this principle has tended to focus on an equivalentprinciple, the Axiom of Choice. So we will now turn our attention tothat (and prove the equivalence). In \citeyear{Cantor1883}, Cantor expressed his support for the Axiomof Well-Ordering, calling it ``a law of thought which appears to me tobe fundamental, rich in its consequences, and particularly remarkablefor its general validity'' (cited in \citeauthor{Potter2004}\citeyear[p.~243]{Potter2004}). But Cantor ultimately became convincedthat the ``Axiom'' was in need of proof. So did the mathematicalcommunity. The problem was ``solved'' by Zermelo in \citeyear{Zermelo1904}. Toexplain his solution, we need some definitions. \begin{defn}A function $f$ is a \emph{choice function} iff $f(x) \in x$ for all $x \in \dom{f}$. We say that $f$ is a \emph{choice function for $A$} iff $f$ is a choice function with $\dom{f} = A \setminus \{\emptyset\}$.\end{defn}Intuitively, for every (non-empty) set $x \in A$, a choice functionfor $A$ \emph{chooses} a particular element, $f(x)$, from $x$. TheAxiom of Choice is then:\begin{axiom}[Choice]	Every set has a choice function.\end{axiom}Zermelo showed that Choice entails well-ordering, and vice versa:\begin{thm}[in $\ZF$]\ollabel{thmwochoice}Well-Ordering and Choice are equivalent.\end{thm}\begin{proof}\emph{Left-to-right.} Let $A$ be a set of sets. Then $\bigcup A$exists by the Axiom of Union, and so by Well-Ordering there is some$<$ which well-orders $\bigcup A$. Now let $f(x) = \text{the $<$-leastmember of }x$. This is a choice function for $A$.\emph{Right-to-left.} Fix $A$. By Choice, there is a choice function,$f$,  for $\Pow{A} \setminus \{\emptyset\}$. Using TransfiniteRecursion, define a function:\begin{align*}	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}\end{align*}The indication to ``stop!'' is just a shorthand for what wouldotherwise be a more long-winded definition. That is, when $A =\funimage{g}{\alpha}$ for the first time, let $g(\delta) = A$ for all$\delta \leq \alpha$. Now, in the first instance, we can only be sure that this defines a \emph{term} (see the remarks after \olref[sth][spine][recursion]{transrecursionschema}); but we will show that we indeed have a function.Since $f$ is a choice function, for each $\alpha$ (when defined) we have $g(\alpha) =f(A \setminus \funimage{g}{\alpha}) \in A \setminus\funimage{g}{\alpha}$; i.e., $g(\alpha) \notin \funimage{g}{\alpha}$.So if $g(\alpha) = g(\beta)$ then $g(\beta) \notin\funimage{g}{\alpha}$, i.e., $\beta \notin \alpha$, and similarly$\alpha \notin \beta$. So $\alpha = \beta$, by Trichotomy. So $g$ is!!{injective}.Next, observe that we do stop!{}, i.e.\ that there is some (least) ordinal $\alpha$ such that $A = g[\alpha]$. For suppose otherwise; then as $g$ is !!{injective} we would have $\cardless{\alpha}{\Pow{A} \setminus \{\emptyset\}}$ forevery ordinal $\alpha$, contradicting \olref[hartogs]{HartogsLemma}. Hence also $\ran{g} = A$.Assembling these facts, $g$ is !!a{bijection} from some ordinal to $A$. Now $g$ can be used to well-order $A$.\end{proof}So Well-Ordering and Choice stand or fall together. But the questionremains: do they stand or fall?\end{document}

content/set-theory/choice/countablechoice.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{countablechoice}\olsection{Countable Choice}It is easy to prove, without any use of Choice/Well-Ordering, that:\begin{lem}[in $\Zminus$]Every finite set has a choice function. \end{lem}\begin{proof}Let $a = \{b_1, \ldots, b_n\}$. Suppose for simplicity that each $b_i\neq \emptyset$. So there are objects $c_1, \ldots, c_n$ such that$c_1 \in b_1, \ldots, c_n \in b_n$. Now by\olref[z][pairs]{prop:pairsconsequences}, the set $\{\langle b_1,c_1\rangle , \ldots, \langle b_n, c_n\rangle\}$ exists; and this is achoice function for~$a$.\end{proof}But matters get murkier as soon as we consider infinite sets. Forexample, consider this ``minimal'' extension to the above:\begin{defish}\emph{Countable Choice.} Every \emph{countable} set has a choice function. \end{defish}This is a special case of Choice. And it transpires that thisprinciple was invoked fairly frequently, without  an obvious awarenessof its use. Here are two nice examples.\footnote{Due to\citet[\S9.4]{Potter2004} and Luca Incurvati.}\begin{ex}Here is a natural thought: for any set $A$, either$\cardle{\omega}{A}$, or $\cardeq{A}{n}$ for some $n \in \omega$. Thisis one way to state the intuitive idea, that every set is eitherfinite or infinite. Cantor, and many other mathematicians, made thisclaim without proving it. Cautious as we are, we proved this in\olref[cardinals][classing]{generalinfinitycharacter}. Butin that proof we were working in $\ZFC$, since we were assuming thatany set $A$ can be well-ordered, and hence that $\card{A}$ isguaranteed to exist. That is: we explicitly assumed Choice.In fact, \citet{Dedekind1888} offered his own proof ofthis claim, as follows:\begin{thm}[in $\Zminus + \text{Countable Choice}$]For any $A$, either $\cardle{\omega}{A}$ or $\cardeq{A}{n}$ for some$n \in \omega$.\end{thm}\begin{proof}Suppose $\cardneq{A}{n}$ for all $n \in \omega$. Then in particularfor each $n < \omega$ there is subset $A_n \subseteq A$ with exactly$\cardexpo{2}{n}$ elements. Using this sequence $A_0, A_1, A_2,\ldots$, we define for each $n$:\[	B_n = A_n \setminus \bigcup_{i < n} A_i.\]Now note the following\begin{align*}	\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}\end{align*}Hence each $B_n$ has at least one member, $c_n$. Moreover, the $B_n$sare pairwise disjoint; so if $c_n = c_m$ then $n = m$. But every $c_n\in A$. So the function  $f(n) = c_n$ is an injection $\omega \to A$.\end{proof}\noindent Dedekind did not flag that he had used Countable Choice. But, did\emph{you} spot its use? Look again. (Really: \emph{look again}.)The proof used Countable Choice twice. We used it once, to obtainour sequence of sets $A_0$, $A_1$, $A_2$, \dots\@ We then used itagain to select our elements $c_n$ from each~$B_n$. Moreover, this useof Choice is ineliminable. \citet[p.~138]{Cohen1966} proved that theresult fails if we have no version of Choice. That is: it isconsistent with $\ZF$ that there are sets which are\emph{incomparable} with~$\omega$.\end{ex}\begin{ex} In \citeyear{Cantor1878}, Cantor stated that a countable union ofcountable sets is countable. He did not present a proof, perhapsindicating that he took the proof to be obvious. Now, cautious as weare, we proved a more general version of this result in\olref[card-arithmetic][simp]{kappaunionkappasize}.  But our proofexplicitly assumed Choice. And even the proof of the less generalresult requires Countable Choice.\begin{thm}[in $\Zminus + \text{Countable Choice}$]If $A_n$ is countable for each $n \in \omega$, then $\bigcup_{n <\omega} A_n$ is countable.\end{thm}\begin{proof}Without loss of generality, suppose that each $A_n \neq \emptyset$. Sofor each $n \in \omega$ there is !!a{surjection} $f_n \colon \omega\to A_n$. Define $f \colon \omega \times \omega \to \bigcup_{n <\omega} A_n$ by $f(m, n) = f_n(m)$. The result follows because $\omega\times \omega$ is countable(\olref[sfr][siz][zigzag]{natsquaredenumerable}) and $f$ is!!a{surjection}.\end{proof}\noindent Did you spot the use of the Countable Choice? It is used to choose oursequence of functions $f_0$, $f_1$, $f_2$, \dots\footnote{A similaruse of Choice occurred in\olref[card-arithmetic][simp]{kappaunionkappasize}, when we gave theinstruction ``For each $\beta \in \cardfont{a}$, fix !!a{injection}$f_\beta$''.} And again, the result fails in the absence of any Choiceprinciple. Specifically, \citet{FefermanLevy1963} proved that it isconsistent with $\ZF$ that a countable union of countable sets hascardinality~$\beth_1$. But here is a much funnier statement of thepoint, from Russell:\begin{quote}  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$ pairs of boots and $\aleph_0$ pairs of socks\dots\@ 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.  \citep[p.~126]{Russell1919}\end{quote}In short, some form of Choice is needed to prove the following: If youhave countably many pairs of socks, then you have (only) countablymany socks. And in fact, without Countable Choice (or somethingequivalent), a countable union of countable sets can fail to becountable. \end{ex}The moral is that Countable Choice was used repeatedly, without muchawareness of its users. The philosophical question is: How could we\emph{justify} Countable Choice? An attempt at an intuitive justification might invoke an appeal to asupertask. Suppose we make the first choice in $\nicefrac{1}{2}$ aminute, our second choice in $\nicefrac{1}{4}$ a minute, \dots, our$n$-th choice in $\nicefrac{1}{2^n}$ a minute, \dots\@ Then within $1$~minute, we will have made an $\omega$-sequence of choices, and defineda choice function. But what, really, could such a thought-experiment tell us? For astart, it relies upon taking this idea of ``choosing'' ratherliterally. For another, it seems to bind up mathematics inmetaphysical possibility. More important: it is not going to give us any justification forChoice \emph{tout court}, rather than \emph{mere} Countable Choice.For if we need \emph{every} set to have a choice function, then we'llneed to be able to perform a ``supertask of arbitrary ordinallength.'' Bluntly, that idea is laughable.\end{document}

content/set-theory/choice/justifications.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{justifications}\olsection{Intrinsic Considerations about Choice}The broader question, then, is whether Well-Ordering, or Choice, orindeed the comparability of all sets as regards their size---itdoesn't matter which---can be justified. Here is an attempted \emph{intrinsic} justification. Back in\olref[z][story]{sec}, we introduced several principlesabout the hierarchy. One of these is worth restating:\begin{enumerate}	\item[] \stagesacc. For any stage $S$, and for any sets which were	formed \emph{before} stage $S$: a set is formed at stage $S$ whose	members are exactly those sets. Nothing else is formed at	stage~$S$. \end{enumerate}In fact, many authors have suggested that the Axiom of Choice can bejustified via (something like) this principle. We will briefly providea gloss on that approach.We will start with a simple little result, which offers \emph{yetanother} equivalent for Choice:\begin{thm}[in $\ZF$]\ollabel{choiceset}Choice is equivalent to the following principle. If the !!{element}sof $A$ are disjoint and non-empty, then there is some $C$ such that $C\cap x$ is a singleton for every $x \in A$. (We call such a $C$ a{choice set} for $A$.)\end{thm}The proof of this result is straightforward, and we leave it as anexercise for the reader. \begin{prob}Prove \olref[sth][choice][justifications]{choiceset}. If you struggle,you can find a proof in \cite[pp.~242--3]{Potter2004}.\end{prob}The essential point is that a choice set for $A$ is just the range ofa choice function for $A$. So, to justify Choice, we can simply try tojustify its equivalent formulation, in terms of the existence ofchoice sets. And we will now try to do exactly that. Let $A$'s !!{element}s be disjoint and non-empty. By \stageshier{}(see \olref[z][story]{sec}), $A$ is formed at some stage~$S$. Notethat all the !!{element}s of $\bigcup A$ are available before stage$S$. Now, by \stagesacc{}, for \emph{any} sets which were formedbefore~$S$, a set is formed whose members are exactly those sets.Otherwise put: every \emph{possible} collections of earlier-availablesets will exist at~$S$. But it is certainly \emph{possible} to selectobjects which could be formed into a choice set for~$A$; that is justsome very specific subset of $\bigcup A$. So: some such choice setexists, as required.Well, that's a \emph{very} quick attempt to offer a justification ofChoice on intrinsic grounds. But, to pursue this idea further, youshould read Potter's (\citeyear[\S14.8]{Potter2004}) neat developmentof it.\end{document}

content/set-theory/choice/banach.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{banach}\olsection{The Banach--Tarski Paradox}We might also attempt to justify Choice, as Boolos attempted tojustify Replacement, by appealing to \emph{extrinsic} considerations(see \olref[replacement][extrinsic]{sec}). After all, adopting Choicehas many desirable consequences: the ability to compare everycardinal; the ability to well-order every set; the ability to treatcardinals as a particular kind of ordinal; etc. Sometimes, however, it is claimed that Choice has \emph{undesirable}consequences. Mostly, this is due to a result by\cite{BanachTarski1924}. \begin{thm}[Banach--Tarski Paradox (in $\ZFC$)]Any ball can be decomposed into finitely many pieces, which can bereassembled (by rotation and transportation) to form two copies ofthat ball.\end{thm}\noindent At first glance, this is a bit amazing. Clearly the two balls have\emph{twice} the volume of the original ball. But rigidmotions---rotation and transportation---do not change volume. So itlooks as if Banach--Tarski allows us to magick new matter intoexistence.It gets worse.\footnote{See \citet[Theorem 3.12]{Wagon2016}.} Similarreasoning shows that a pea can be cut into finitely many pieces, whichcan then be reassembled (by rotation and transportation) to form anentity the shape and size of Big Ben.None of this, however, holds in $\ZF$ on its own.\footnote{ThoughBanach--Tarski can be proved with principles which are strictly weakerthan Choice; see \citet[303]{Wagon2016}.} 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. Inparticular, we don't see why it is any more or less paradoxical thanany of the following results:\footnote{\citet[276--7]{Potter2004},\citet[16]{Weston2003}, \citet[31, 308--9]{Wagon2016}, makesimilar points, using other examples.}\begin{enumerate}	\item There are as many points in the interval $(0,1)$ as in  $\Real$. 	\\\emph{Proof}: consider $\tan(\pi(r-\nicefrac{1}{2})))$.	\item There are as many points in a line as in a square.	\\See \olref[his][set][pathology]{sec} and \olref[his][set][cantorplane]{sec}.	\item There are space-filling curves. 	\\See \olref[his][set][pathology]{sec} and \olref[his][set][hilbertcurve]{sec}.\end{enumerate}None of these three results require Choice. Indeed, we now just regardthem as surprising, lovely, bits of mathematics. Maybe we should adoptthe same attitude to the Banach--Tarski Paradox.To be sure, a technical observation is required here; but it onlyrequires keeping a level head. Rigid motions preserve volume.Consequently, the five\footnote{We stated the Paradox in terms of``finitely many pieces''. In fact, \citet{Robinson1947} proved thatthe decomposition can be achieved with \emph{five} pieces(but no fewer). For a proof, see \citet[pp.~66--7]{Wagon2016}.} piecesinto which the ball is decomposed cannot all be \emph{measurable}.Roughly put, then, it makes no sense to assign a volume to theseindividual pieces. You should think of these as unpicturable,``infinite scatterings'' of points. Now, maybe it is ``weird'' toconceive of such ``infinitely scattered'' sets. But their existenceseems to fall out from the injunction, embodied in \stagesacc{}, thatyou should form \emph{all possible} collections of earlier-availablesets. If none of that convinces, here is a final (extrinsic) argument infavour of embracing the Banach--Tarski Paradox. It immediately entailsthe best math joke of all time:\begin{enumerate}	\item[] \emph{Question}. What's an anagram of ``Banach--Tarski''? 	\item[] \emph{Answer}. ``Banach--Tarski Banach--Tarski''.\end{enumerate}\end{document}

content/set-theory/choice/vitali.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{choice}{vitali}\olsection{Appendix: Vitali's Paradox}To get a real sense of whether the Banach-Tarski construction isacceptable or not, we should examine its \emph{proof}. Unfortunately,that would require much more algebra than we can present here.However, we can offer some quick remarks which might shed some insighton the proof of Banach-Tarski,\footnote{For a much fuller treatment,see \cite{Weston2003} or \cite{Wagon2016}.} by focussing on thefollowing result:\begin{thm}[Vitali's Paradox (in $\ZFC$)]\ollabel{vitaliparadox}Any circle can be decomposed into countably many pieces, which can bereassembled (by rotation and transportation) to form two copies ofthat circle.\end{thm}Vitali's Paradox is much easier to prove than the Banach--Tarski Paradox. We havecalled it ``Vitali's Paradox'', since it follows from Vitali's\citeyear{Vitali1905} construction of an unmeasurable set.  But theset-theoretic aspects of the proof of Vitali's Paradox and theBanach-Tarski Paradox are very similar. The essential differencebetween the results is just that Banach-Tarski considers a\emph{finite} decomposition, whereas Vitali's Paradox considers a\emph{countably infinite} decomposition.  As \citet{Weston2003}puts it, Vitali's Paradox ``is certainly not nearly as striking as theBanach--Tarski paradox, but it does illustrate that geometricparadoxes can  happen even in `simple' situations.'' Vitali's Paradox concerns a two-dimensional figure, a circle. So wewill work on the plane, $\Real^2$. Let $\rotationsgroup$ be the set of(clockwise) rotations of points around the origin by \emph{rational}radian values between $[0,2\pi)$. Here are some algebraic facts about$\rotationsgroup$ (if you don't understand the statement of theresult, the proof will make its meaning clear):\begin{lem}\ollabel{rotationsgroupabelian}$\rotationsgroup$ forms an abelian {group} under composition of functions.\end{lem}\begin{proof}Writing $0_{\rotationsgroup}$ for the rotation by $0$ radians, this isan identity element for $\rotationsgroup$, since$\comp{0_{\rotationsgroup}}{\rho} = \comp{\rho}{0_{\rotationsgroup}} =\rho$ for any $\rho \in \rotationsgroup$.Every element has an inverse. Where $\rho \in \rotationsgroup$ rotatesby $r$ radians, $\rho^{-1} \in \rotationsgroup$ rotates by $2\pi - r$radians, so that $\rho \circ \rho^{-1} = 0_\rotationsgroup$.Composition is associative: $\comp{\rho}{(\comp{\sigma}{\tau})} =\comp{(\comp{\rho}{\sigma})}{\tau}$ for any $\rho, \sigma, \tau \in\rotationsgroup$Composition is commutative: $\comp{\rho}{\sigma} =\comp{\sigma}{\rho}$ for any $\rho, \sigma \in \rotationsgroup$.\end{proof}In fact, we can split our group $\rotationsgroup$in half, and then use either half to recover the whole group:\begin{lem}\ollabel{disjointgroup}There is a partition of $\rotationsgroup$ into two disjoint sets,$\rotationsgroup_{1}$ and $\rotationsgroup_{2}$, both of which are abasis for $\rotationsgroup$. \end{lem}\begin{proof}Let $\rotationsgroup_{1}$ consist of the rotations by rational radianvalues in $[0, \pi)$; let $\rotationsgroup_{2} = \rotationsgroup\setminus \rotationsgroup_1$. By elementary algebra,$\Setabs{\comp{\rho}{\rho}}{\rho \in \rotationsgroup_1} =\rotationsgroup$. A similar result can be obtained for$\rotationsgroup_2$.\end{proof}We will use this fact about groups to establish \olref{vitaliparadox}.Let $\onesphere$ be the unit circle, i.e., the set of pointsexactly~$1$ unit away from the origin of the plane, i.e.,$\Setabs{\tuple{r,s} \in \Real^2}{\sqrt{r^2+s^2}=1}$. We will split$\onesphere$ into parts by considering the following relation on$\onesphere$:\[	r \sim s \emph{ iff }(\exists \rho \in \rotationsgroup)\rho(r) = s.\]That is, the points of $\onesphere$ are linked by this relation iff you can get from one to the other by a rational-valued rotation about the origin. Unsurprisingly:\begin{lem}$\sim$ is an equivalence relation.\end{lem}\begin{proof}Trivial, using \olref{rotationsgroupabelian}. \end{proof}We now invoke Choice to obtain a set, $C$, containing exactly onemember from each equivalence class of $\onesphere$ under $\sim$. Thatis, we consider a choice function $f$ on the set of equivalenceclasses,\footnote{Since $\rotationsgroup$ is !!{enumerable},each !!{element} of $E$ is !!{enumerable}. Since $\onesphere$ is!!{nonenumerable}, it follows from \olref{vitalicover} and\olref[card-arithmetic][simp]{kappaunionkappasize} that $E$ is!!{nonenumerable}. So this is a use of \emph{un}countable Choice.}\[	E = \Setabs{\equivrep{r}{\sim}}{r \in \onesphere},\]and let $C = \ran{f}$. For each rotation $\rho \in \rotationsgroup$,the set $\funimage{\rho}{C}$ consists of the points obtained byapplying the rotation $\rho$ to each point in $C$. These next tworesults show that these sets cover the circle completely and withoutoverlap:\begin{lem}\ollabel{vitalicover}$\onesphere = \bigcup_{\rho \in \rotationsgroup} \funimage{\rho}{C}$.\end{lem}\begin{proof}Fix $s \in \onesphere$; there is some $r \in C$ such that $r \in\equivrep{s}{\sim}$, i.e., $r \sim s$, i.e., $\rho(r) = s$ for some$\rho \in \rotationsgroup$. \end{proof}\begin{lem}\ollabel{vitalinooverlap}If $\rho_1 \neq \rho_2$ then $\funimage{\rho_1}{C} \cap \funimage{\rho_2}{C} = \emptyset$. \end{lem}\begin{proof}Suppose $s \in \funimage{\rho_{1}}{C} \cap \funimage{\rho_{2}}{C}$. So$s = \rho_{1}(r_{1}) = \rho_{2}(r_{2})$ for some $r_{1}, r_{2} \in C$.Hence $\rho^{-1}_2(\rho_1(r_1)) = r_2$, and$\comp{\rho_1}{\rho^{-1}_2} \in \rotationsgroup$, so $r_{1} \simr_{2}$. So $r_1 = r_2$, as $C$ selects exactly one member from eachequivalence class under $\sim$. So $s = \rho_1(r_1) = \rho_2(r_1)$,and hence $\rho_1 = \rho_2$.\end{proof}We now apply our earlier algebraic facts to our circle:\begin{lem}\ollabel{pseudobanachtarski}There is a partition of $\onesphere$ into two disjoint sets, $D_{1}$and $D_{2}$, such that $D_{1}$ can be partitioned into countably manysets which can be rotated to form a copy of $\onesphere$ (andsimilarly for $D_{2}$).\end{lem}\begin{proof}Using $\rotationsgroup_{1}$ and $\rotationsgroup_{2}$ from \olref{disjointgroup}, let:\begin{align*}	D_{1} &= \bigcup_{\rho \in \rotationsgroup_1} \funimage{\rho}{C} & 	D_{2} &= \bigcup_{\rho \in \rotationsgroup_2} \funimage{\rho}{C}\end{align*}This is a partition of $\onesphere$, by \olref{vitalicover}, and $D_1$and $D_2$ are disjoint by \olref{vitalinooverlap}. By construction,$D_1$ can be partitioned into countably many sets,$\funimage{\rho}{C}$ for each $\rho \in R_1$. And these can be rotatedto form a copy of $\onesphere$, since $\onesphere = \bigcup_{\rho \in\rotationsgroup}\funimage{\rho}{C} = \bigcup_{\rho \in\rotationsgroup_1}\funimage{(\comp{\rho}{\rho})}{C}$ by\olref{disjointgroup} and \olref{vitalicover}. The same reasoningapplies to $D_2$. \end{proof}\noindent This immediately entailsVitali's Paradox. For we can generate \emph{two} copies of$\onesphere$ from $\onesphere$, just by splitting it up into countablymany pieces (the various $\funimage{\rho}{C}$'s) and then rigidlymoving them (simply rotate each piece of $D_1$, and first transportand then rotate each piece of $D_2$).Let's recap the proof-strategy. We started with some algebraic factsabout the group of rotations on the plane. We used this group topartition $\onesphere$ 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 maindifference is that the algebraic facts used to prove Banach--Tarskiare significantly more complicated than those used to proveVitali's Paradox. But those algebraic facts have nothing to do withChoice. We will summarise them quickly. To prove Banach--Tarski, we start by establishing an analogue of\olref{disjointgroup}: any \emph{free group} can be split into fourpieces, which intuitively we can ``move around'' to recover two copiesof the whole group.\footnote{The fact that we can use \emph{four}pieces is due to \cite{Robinson1947}. For a recent proof, see\citet[Theorem 5.2]{Wagon2016}. We follow \citet[p.~3]{Weston2003}in describing this as ``moving'' the pieces of the group.} We thenshow that we can use two particular rotations around the origin of$\Real^3$ to generate a free group of rotations, $F$.\footnote{See\citet[Theorem 2.1]{Wagon2016}.} (No Choice yet.) We now regard pointson the surface of the sphere as ``similar'' iff one can be obtainedfrom the other by a rotation in~$F$. We then \emph{use Choice} toselect exactly one point from each equivalence class of ``similar''points. Applying our division of $F$ to the surface of the sphere, asin \olref{pseudobanachtarski}, we split that surface into four pieces,which we can ``move around'' to obtain two copies of the surface ofthe sphere. And this establishes \citep{Hausdorff1914}:\begin{thm}[Hausdorff's Paradox (in $\ZFC$)] The surface of any sphere can be decomposed into finitely many pieces,which can be reassembled (by rotation and transportation) to form twodisjoint copies of that sphere.\end{thm}A couple of further algebraic tricks are needed to obtain the fullBanach-Tarski Theorem (which concerns not just the sphere's surface,but its interior too). Frankly, however, this is just icing on thealgebraic cake. Hence Weston writes:\begin{quote}	  [\ldots] the result on free groups is the \emph{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$ so much as  it is a statement about the complexity of the group [of translations  and rotations in $\Real^3$]. \cite[p.~16]{Weston2003}\end{quote}That is: whether we can offer a \emph{finite} decomposition (as inBanach--Tarski) or a \emph{countably infinite} decomposition (as inVitali's Paradox) comes down to certain group-theoretic facts aboutworking in two-dimension or three-dimensions.Admittedly, this last observation slightly spoils the joke at the endof \olref[banach]{sec}. Since it is  two dimensional,``Banach-Tarski'' must be divided into a countable \emph{infinity} ofpieces, if one wants to rearrange those pieces to form ``Banach-TarskiBanach-Tarski''. To repair the joke, one must write in threedimensions. We leave this as an exercise for the reader.One final comment. In \olref[banach]{sec}, we mentioned that the``pieces'' of the sphere one obtains cannot be \emph{measurable}, butmust be unpicturable ``infinite scatterings''. The same is true of ouruse of Choice in obtaining \olref{pseudobanachtarski}. And this is allworth explaining.Again, we must sketch some background (but this is \emph{just} asketch; you may want to consult a textbook entry on \emph{measure}).To define a measure for a set $X$ is to assign a value $\mu(E) \in\Real$ for each $E$ in some ``$\sigma$-algebra'' on $X$. Details hereare not essential, except that the function $\mu$ must obey theprinciple of countable additivity: the measure of a countable union ofdisjoint sets is the sum of their individual measures, i.e.,$\mu(\bigcup_{n < \omega} X_n) = \sum_{n < \omega}\mu(X_n)$ wheneverthe $X_n$s are disjoint. To say that a set is ``unmeasurable'' is tosay that no measure can be suitably assigned. Now, using our$\rotationsgroup$ from before:\begin{cor}[Vitali]Let $\mu$ be a measure such that $\mu(\onesphere) = 1$, and such that$\mu(X) = \mu(Y)$ if $X$ and $Y$ are congruent. Then$\funimage{\rho}{C}$ is unmeasurable for all $\rho \in\rotationsgroup$. \end{cor}\begin{proof}For reductio, suppose otherwise. So let $\mu(\funimage{\sigma}{C}) =r$ for some $\sigma \in \rotationsgroup$ and some $r \in \Real$. Forany $\rho \in C$, $\funimage{\rho}{C}$ and $\funimage{\sigma}{C}$ arecongruent, and hence  $\mu(\funimage{\rho}{C}) = r$ for any $\rho \inC$. By \olref{vitalicover} and \olref{vitalinooverlap}, $\onesphere =\bigcup_{\rho \in \rotationsgroup}\funimage{\rho}{C}$ is a countableunion of pairwise disjoint sets. So countable additivity dictates that$\mu(\onesphere) = 1$ is the sum of the measures of each$\funimage{\rho}{C}$, i.e.,\[	1 = \mu(\onesphere) = \sum_{\rho \in \rotationsgroup}\mu(\funimage{\rho}{C}) = \sum_{\rho \in \rotationsgroup}r\]But if $r = 0$ then $\sum_{\rho \in \rotationsgroup}r = 0$, and if $r> 0$ then $\sum_{\rho \in \rotationsgroup}r = \infty$. \end{proof}\end{document}