Section 10.7 (Optional) The axiom of choice
Consider the following, not terribly controversial, statement
Given a non-empty set \(A\text{,}\) we can pick an element from it.
This is almost trivial. The fact that \(A \neq \es\) is equivalent to the statement \(\exists a \in A\text{.}\) So, we can simply take that element \(a\text{,}\) and we are done.
Let’s turn up the complexity a little:
Given two non-empty sets \(A,B\text{,}\) we can pick one element from each.
This is no harder, since \(A\) is non-empty, we can take \(a \in
A\text{.}\) And since \(B\neq \es\) we can take \(b \in B\text{.}\) And, at this point, we need to start phrasing things a little differently so that we can be a little more formal and a little more careful.
Given two sets \(A,B\) there exists a function \(f:\set{A,B} \to A\cup B\)
That is, our choosing of elements from \(A\) and \(B\) is really just a function that takes us from the collection \(\set{A,B}\) to a specific elements \(a,b \in A\cup
B\text{.}\) Similarly, if such a function exists, then we can use it to choose specific elements. We call such functions choice functions.
Definition 10.7.1. Choice function.
Let \(\mathcal{S}\) be a collection of non-empty sets. Then a choice function on \(\mathcal{S}\) is a function
\begin{equation*}
f: \mathcal{S} \to \bigcup_{X \in S} X
\end{equation*}
so that, for any \(X \in \mathcal{S}\text{,}\) \(f(X) \in X\text{.}\) That is, for any set \(X\) in our collection \(\mathcal{S}\text{,}\) the choice function \(f\) chooses an element \(f(X)=x
\in X\text{.}\)
This definition allows us to rephrase the above statements as
A collection of a single set \(\set{A}\) always has a choice function, and
A collection of two sets \(\set{A,B}\) always has a choice function.
This is quite easily extended to any finite collection of non-empty sets. Note that while the collection must be finite, the sets in the collection can be infinite.
Result 10.7.2.
Let \(\mathcal{S} = \set{A_i \st i \in \set{1,2,\dots,n}}\) be a finite collection of non-empty sets. Then there exists a choice function on \(\mathcal{S}\text{.}\)
Proof.
We prove this by induction.
Let \(\mathcal{S}=\set{A}\) consist of a single non-empty set \(A\text{.}\) Since \(A\) is non-empty, there is some \(a \in A\text{.}\) The function
\begin{equation*}
f:\set{A} \to A \qquad f(A) = a
\end{equation*}
is a choice function on \(\mathcal{S}\text{.}\) Thus the statement is true for \(|\mathcal{S}|=1\text{.}\)
-
Now assume that the statement hold for all collections of \(k\) non-empty sets, and let \(\mathcal{T} = \set{A_i
\st i \in \set{1,2,\dots,k+1}}\text{.}\) Since \(A_{k+1} \neq \es\) there is some \(q \in A_{k+1}\text{.}\)
Then, by assumption, the collection \(\mathcal{S} =
\set{A_i \st i \in \set{1,2,\dots,k}}\) has a choice function \(f\text{.}\) We can then use this to define the required choice function \(g\text{:}\)
\begin{equation*}
g(A_i) = \begin{cases}
f(A_i) \amp i = 1,2,\dots, k \\
q \amp i = k+1
\end{cases}
\end{equation*}
Then, by induction, the statement holds for any finite collection of non-empty sets.
The existence of such choice-functions is intuitively quite obvious. I can always grab an element out from a set, so I can grab an element out from each set in turn. Indeed, it is equivalent to the statement that the Cartesian product of a finite number of non-empty sets is also non-empty.
Result 10.7.3.
Let \(A_1, A_2, \dots, A_n\) be non-empty sets. The the collection \(\set{A_1,\dots,A_n}\) has a choice function if and only if the Cartesian product \(A_1 \times A_2 \times
\cdots \times A_n\) is non-empty.
Proof.
Let the \(A_i\) be as stated. We then prove each implication in turn.
Assume that the collection \(\set{A_1, \dots, A_n}\) has a choice function, \(f\text{.}\) We can use that to select \(f(A_i) = a_i \in A_i\) for \(i=1,2,\dots, n\text{.}\) Hence \((a_1, a_2, \dots, a_n) \in A_1
\times A_2 \times \cdots \times A_n\text{.}\) Thus the product is non-empty.
Similarly, assume that the product \(A_1 \times A_2 \times
\cdots \times A_n \neq \es\text{,}\) and hence there is \((a_1, \dots a_n) \in A_1 \times \cdots \times A_n\text{.}\) We use that element to define
\begin{equation*}
f: \set{A_1, \dots, A_n} \to \cup A_i \qquad f(A_i) = a_i
\end{equation*}
giving the required choice function.
Where things become really very non-trivial, and the consequences very non-intuitive, is when we have infinite collections of sets. Our inductive argument above can’t get us there — it cannot make the leap from large, but finite collections, to infinite collections.
Of course, if we the sets in our infinite collection are nice and have extra structure, then this might be easy. For example,
This last example is very famous and is due to Bertrand Russell
142 . The second half of the example points out that it is far from obvious how to do the same with an infinite collection of pairs of socks.
Indeed, for an infinite collection of non-empty sets, without extra structure, the existence of a choice function is taken as an axiom — the Axiom of Choice.
Axiom 10.7.4. Axiom of choice.
Let \(\mathcal{S}\) be any collection of non-empty sets. Then there exists a choice function on \(\mathcal{S}\text{.}\)
This statement feels so intuitively true, it was used quite implicitly until 1904 when Zermelo realised that the question of the existence of choice functions was not at all trivial. Indeed, it was subsequently shown that Axiom of Choice cannot be proved or disproved using usual set theory
143 . To be more precise, 1938 Kurt Gödel proved that one can not disprove the existence of such a choice function using the standard axioms of set theory, while in 1963 Paul Cohen proved that the existence cannot be proven either. It is now accepted
144 as a standard part of set theory.
The
Axiom of Choice 10.7.4 is equivalent to the statement that the Cartesian product of any collection of non-empty sets is itself non-empty — this seems reasonable and hardly controversial. However, the Axiom of Choice does have some very strange implications.
Well-ordering theorem — every set can be well-ordered. That is, one can define an ordering of the elements of any set so that any subset has a first element! Cantor conjectured this result in 1883 but it was proved Zermelo in 1904. It was in that proof that the Axiom of Choice was first formalised. It is also known as Zermelo’s theorem.
Banach-Tarski paradox — it is possible to decompose a solid ball into finitely many pieces and reassemble them into two solid balls each having the same volume as the original!
It allows you to predict the result of coin tosses — see this
nice article 145 by Matt Baker. The interested reader should also examine a very nice (and somewhat provocative)
paper 146 by Hardin and Taylor push this line of reasoning explaining how you can use the Axiom of Choice to predict future values of real-valued functions
147 .
Here 148 is a nice and more accessible description of the result by Michael O’Connor.
The Axiom of Choice is an extremely interesting and complicated topic, and, well beyond the scope of this text; the interested reader should search-engine their way to more information
149 .
More formally, we pick the lexicographic least word from each subset. Lexicographic ordering is really useful and the interested reader should search-engine their way to more on this topic.
No footnote can even begin to do justice to the many contributions of Russell to logic and mathematics and many other disciplines. The reader should search-engine their way to more information.
By which we mean Zermelo-Fraenkel set theory, which is, roughly speaking, the formalisation of the usual notions of set theory, including those in this text.
By most mathematicians in most contexts. There is, however, an interesting body of research on what happens when the Axiom of Choice is false. Very strange things happen — the interested reader should search engine their way to more information.
https://mattbaker.blog/2015/01/17/spooky-inference-and-the-axiom-of-choice/
https://www.tandfonline.com/doi/abs/10.1080/00029890.2008.11920502
Such as temperatures, stock-market prices, position of balls on roulette tables, etc.
https://xorshammer.com/2008/08/23/set-theory-and-weather-prediction/
There are many articles out there on this topic, but the authors found
this blog to be a very nice discussion of the Axiom of Choice.
