Several standard proofs in algebra, analysis, and topology rarely appear without the proviso that they rely on the Axiom of Choice (AC): the proof that every vector space has a basis, that every field has an algebraic closure, of Tychonoff’s theorem, of the Hahn–Banach theorem, etc. (I contend these provisos show up because the easiest proofs of these facts use Zorn’s Lemma, so it’s less easy for the author/lecturer to slip in a choice function covertly than it is with proofs of standard technical lemmas. I’ll address this in part 3 of this series.) The purpose of this post and its (two?) successors is—without describing the set-theoretic machinery (forcing) necessary to prove some of the important results—to summarize those facts about AC that are relevant to the ‘working mathematician’. I expect the series to follow this outline:
- (This post) Preliminaries, basic equivalences;
- Vector spaces and groups: the proofs in ZF that AC if and only if every vector space has a basis, and that AC if and only if every set can be endowed with a group structure.
- “We used AC there?!” and “What happens without AC?” Few proofs here. Just fun facts.
Much of the information in these posts will come from one of the following sources (some of it from the exercises):
- Jech, T. Set Theory. Academic Press, 1978. (That’s right. I use the 1978 edition.)
- Jech, T. The Axiom of Choice. Dover, 2008.
When something (e.g., Blass’s proof that [every vector space has a basis] implies AC) comes from a different source, I will try to remember to indicate that.
A choice function for a set is a function with domain such that for every . (Notice that the range of will consequently be , the set of elements of elements of .) So ‘chooses’ an element from each element of .
- Recall that, if the real numbers are constructed using Dedekind cuts, a real number is the set of rational numbers that are less than . A choice function for therefore assigns to each real number a rational number less than . (Note that iff .)
- Consider the set . A choice function for can be viewed as a function whose graph always remains above the diagonal; that is, for every . It’s interesting to note that there is an obvious choice function for this set, and its existence does not depend on AC: since every element of is a well-ordered set, just define to be the (unique) least element of . Already we start to see the strong connection between the ‘choosing’ a choice function does and the least-element property of well-orderings.
Axiom of Choice (AC). If is a set and , then has a choice function.
AC is often phrased ‘The product of nonempty sets is nonempty’. By thinking for a bit about what a product is, convince yourself that these two formulations are equivalent. (The mathematical statements are identical modulo a technicality (Exercise: what is the technicality?), but their English formulations disunite them.)
I prove two equivalences in this post, each of a mostly set-theoretic nature. The first is Zermelo’s theorem that every set can be well-ordered. Recall that a relation on a set is a well-ordering (I always like to say “a partial order is well”—teehee) if is a partial order, and every subset of has a -minimal element. For instance, the usual order on the set of positive integers is a well-ordering.
Proposition 1. In ZF, AC if and only if every set can be well-ordered.
Proof. First suppose AC and let be a set. By AC there is a choice function on , the set of all nonempty subsets of . Define by induction a sequence :
Set ; for set as long as is nonempty.
(The sequence is using the choice function on to pick elements of one by one, creating a well-ordering of .)
There is a least ordinal such that , so the sequence enumerates . That is, is well-ordered by the order it inherits from the bijection (check that it’s a bijection!) .
Conversely, suppose that every set can be well-ordered and let be a set of nonempty sets. The set can be well-ordered by assumption; define by setting to be the minimal element of . Such an exists since and is unique since is well-ordered by the ordering it inherits as a subset of . Then is a choice function for .
Since AC appears for the ‘working mathematician’ most often under the alias ‘Zorn’s Lemma’, I think it’s nice for every mathematician to see a proof of their equivalence.
Zorn’s Lemma. Let be a nonempty poset. If every chain (i.e., totally ordered subset) in has an upper bound (an element such that for every ), then has a maximal element.
Proposition 2. AC is equivalent to Zorn’s Lemma.
Proof. Assume AC and let be a nonempty poset with the property that every chain in has an upper bound. By Proposition 1, can be well-ordered, say by .
We are going to use the well-ordering of to construct a sequence that eventually picks out a maximal element of . Let be the -minimal element of . Now the set is a chain and so has an upper bound. Let be the -minimal upper bound for that isn’t itself. Then is a chain with an upper bound. Define to be the -minimal upper bound not equal to or . Continue:
For each ordinal (less than the order-type of ) the set is a chain and so has an upper bound. Either ( is a successor ordinal and) the only such upper bound is , or there is an upper bound that doesn’t belong to the set . In the first case, the element is a maximal element of , and we are done. In the second, we define to be the -minimal upper bound for the chain that isn’t itself a member of .
Since the process can’t go on forever, there is some least for which the only upper bound for the chain is ; then is a maximal element of .
Now assume Zorn’s Lemma and let be a nonempty set of nonempty sets. Let be the set of functions that are choice functions for some subset of , and order by inclusion . (Here we are identifying a function with its graph, and so iff the domain of is a subset of the domain of , and .) Evidently is nonempty since is nonempty: for any element of the function belongs to , for instance. A chain in has as an upper bound , the function given by iff there is some in such that . (Exercise: convince yourself that this properly defines a function on since is a chain.) Apply Zorn’s Lemma to conclude that has a maximal element , a function on some subset of . If were a proper subset of and were an element of , then we could extend by taking its union with the function . Since this would contradict the maximality of , it must be that ; that is, is a choice function for .
(I should point out that in the final paragraph of this proof, by “the function ” I mean the function whose domain is and whose range is ; this function is a choice function, since it selects for its only member the only element of .)
I leave the case as an exercise. =^]