The Axiom of Choice: Statement and Application

Hello! Welcome back to our module on the foundations of mathematics.

In our last lesson, we explored the iterative conception of the set-theoretic universe. We saw how the idea of building sets in cumulative stages provides an intuitive justification for most of the axioms of Zermelo-Fraenkel set theory (ZF). This elegant picture brings order to the universe of sets and avoids contradictions like Russell's paradox.

However, we ended by noting that one axiom, the Axiom of Choice (AC), doesn't seem to follow as directly from this iterative story. Today, we will place this famous and controversial axiom under the microscope. Your learning outcome is to explain the statement of the Axiom of Choice and give an example of its use. Understanding AC is crucial, as it's the "C" in ZFC—the standard axiomatic system for modern mathematics—and its non-constructive nature raises deep philosophical questions that are central to your interests.

1. What is the Axiom of Choice?

At its heart, the Axiom of Choice is about the ability to make selections. The classic analogy, attributed to Bertrand Russell, contrasts choosing from a collection of pairs of shoes with choosing from a collection of pairs of socks.

• For the shoes, you can define a clear rule: "From each pair, choose the left shoe." This rule allows you to construct a set containing one shoe from each pair.
• For the socks, there is no such rule. The left and right socks in a pair are typically indistinguishable. Can you still be sure that a set exists containing one sock from each pair?

The Axiom of Choice asserts that the answer is yes, even without a rule. It guarantees the existence of such a selection set, without telling you how to construct it.

Formal Statements of the Axiom

This intuitive idea can be formalized in several equivalent ways. The most common formulation uses the concept of a "choice function".

As the video explains, a choice function $f$ on a collection of non-empty sets $X$ is a function that "chooses" an element from each set in the collection. Formally:

Axiom of Choice (AC): For any set $X$ whose members are all non-empty sets, there exists a function $f:X\to {\bigcup }_{A\in X}A$ such that for every set $A\in X$, we have $f(A)\in A$.

This is a powerful statement. For any finite collection of sets, you don't need an axiom; you can prove a choice function exists by simply making the finite number of choices one by one. The axiom becomes necessary when dealing with an infinite collection of sets for which you cannot specify a "rule" for making the choices, like with the pairs of socks.

There are other important, equivalent ways to state the axiom that might appeal to your mathematical background:

• Cartesian Product Formulation: The Cartesian product of any non-empty collection of non-empty sets is non-empty. This is very direct: an element of the product is, by definition, a function that picks one element from each set in the collection—precisely a choice function.
• Zermelo's Formulation (Transversals): Any collection of mutually disjoint non-empty sets has a transversal (or choice set)—a set containing exactly one element from each set in the collection.

2. An Example of its Use: The Right Inverse of a Surjection

The best way to understand AC is to see it in action. A classic and clean application is in proving that every surjective function has a right inverse. A right inverse of a function $f:X\to Y$ is a function $g:Y\to X$ such that the composition $f\circ g$ is the identity function on $Y$, i.e., $f(g(y))=y$ for all $y\in Y$.

Let's walk through the proof.

Theorem: If $f:X\to Y$ is a surjective function, then there exists a function $g:Y\to X$ such that $g$ is a right inverse of $f$.

Proof Idea:

1. Since $f$ is surjective, for every element $y\in Y$, we know that its preimage, the set $f^{-1}(y)=\{x\in X\mid f(x)=y\}$, is a non-empty subset of $X$.
2. We want to define our function $g$ by mapping each $y\in Y$ to some element in its preimage set $f^{-1}(y)$.
3. The problem is, which element should we choose? If $f$ is not injective, there might be many elements in $f^{-1}(y)$. We need a systematic way to make a choice for every $y\in Y$ simultaneously.
4. This is exactly the problem AC solves. We have a collection of non-empty sets: $\mathcal{C}=\{f^{-1}(y)\mid y\in Y\}$. The Axiom of Choice asserts that a choice function exists for this collection $\mathcal{C}$.
5. Let's call this choice function $h$. The function $h$ takes a set from $\mathcal{C}$ (like $f^{-1}(y)$) and returns an element from that set.
6. We can now define our right inverse $g$ using this choice function: for each $y\in Y$, let $g(y)=h(f^{-1}(y))$.

This definition works because $h$ guarantees that we have a well-defined, unique output in $X$ for every input $y$ from $Y$. The video you watched earlier contains an excellent animation of this exact proof.

3. The Power and Controversy of Choice

The Axiom of Choice is equivalent to many other powerful statements in mathematics, some of which seem completely unrelated. This is one reason it is so fundamental. Two of the most famous equivalents are:

• The Well-Ordering Theorem: Every set can be well-ordered. (A well-ordering is a total ordering where every non-empty subset has a least element). This seems highly non-intuitive; can you imagine a well-ordering of the real numbers? AC says one exists, even if we can't construct it.
• Zorn's Lemma: A technical statement about partially ordered sets, it is an indispensable tool in abstract algebra, functional analysis, and topology. For instance, the proof that every vector space has a basis relies on it.

The non-constructive nature of AC also leads to some bizarre and counter-intuitive consequences, which fueled the historical controversy surrounding its adoption. The most famous is the Banach-Tarski Paradox, which states that you can decompose a solid ball into a finite number of pieces and, using only rotations and translations, reassemble them into two solid balls, each identical to the original.

The "paradox" is not a logical contradiction but a violation of our geometric intuition. It turns out that the pieces involved are so complex ("non-measurable") that the concept of volume no longer applies to them. Accepting AC means accepting the existence of such sets.

For a long time, the central question was whether AC was consistent with the other axioms of ZF. In 1938, Kurt Gödel proved that if ZF is consistent, then so is ZFC (ZF + AC). Then, in 1963, Paul Cohen proved that if ZF is consistent, so is ZF + (not AC). Together, these results show that AC is independent of the other axioms of set theory. You can choose to accept it or deny it without creating a logical contradiction within the system. Today, the vast majority of mathematicians accept AC because of its immense utility.

Conclusion

Today we've demystified the Axiom of Choice, one of the most important and debated principles in the foundations of mathematics.

Key Takeaways:

• The Axiom of Choice (AC) asserts that for any collection of non-empty sets, a choice function—a function that selects one element from each set—exists.
• It is a non-constructive principle: it guarantees existence without providing a rule for construction. This is why it must be an axiom for infinite collections where no choice rule is definable.
• We saw a direct example of its use in proving that any surjective function must have a right inverse, where AC was needed to make all the choices from the preimage sets simultaneously.
• AC is equivalent to powerful principles like the Well-Ordering Theorem and Zorn's Lemma, but also leads to counter-intuitive results like the Banach-Tarski Paradox.
• It is independent of the other axioms of ZF, meaning it can be neither proved nor disproved from them.

Preview of the Next Lesson:
We have now discussed how sets are built (the iterative conception) and how we can make choices from them (the Axiom of Choice). A natural next question is how to compare the "size" of these sets, especially infinite ones. In the next lesson, we will learn a fundamental technique for doing just that by studying how to construct Cantor's diagonal argument to prove the uncountability of the real numbers.