42.03.05 · mathematical-logic / set-theory-forcing

The Axiom of Choice and Its Equivalents

shipped3 tiersLean: none

Anchor (Master): Kunen 2011 *Set Theory* (College Publications) Ch. I §12 and the independence remarks in Ch. IV-VII (Cohen forcing) and the Fraenkel-Mostowski permutation models; Jech 1973 *The Axiom of Choice* (North-Holland) Ch. 1-5 (equivalents, weak forms ACω and DC, the Banach-Tarski paradox, Vitali sets, independence); Herrlich 2006 *Axiom of Choice* (Springer LNM 1876) for the disasters-with-and-without panorama

Intuition Beginner

Imagine you own infinitely many pairs of socks and you want to grab exactly one sock from each pair. With shoes this is simple: take the left shoe from every pair, and you are done with a single uniform rule. Socks are different. The two socks in a pair are identical, so there is no rule like "take the left one." You can still believe a selection exists — surely you could reach into each pair and pull one out — but you cannot write down a recipe that names your pick in every pair at once. The Axiom of Choice is exactly the assumption that such a simultaneous selection always exists, even when no rule describes it.

For finitely many pairs you never need the axiom: pick from the first, then the second, and stop. The trouble starts only with infinitely many collections, where "keep picking" never finishes. The axiom says the finished result is there anyway, as a single object that chooses one element from each set at once.

This sounds modest, and most working mathematicians use it without a second thought. What makes it remarkable is that it is equivalent to several statements that look completely different: that every collection can be lined up in a row with a first element, a next element, and so on past infinity; and that certain step-by-step building processes always reach a stopping point you cannot improve. In this unit you meet the axiom, three of its famous disguises, and a glimpse of why some of its consequences are strange.

Visual Beginner

The axiom of choice is a selection: from each box in a family of nonempty boxes, it hands you exactly one item, all at once. The picture shows three of infinitely many boxes and the selected element circled in each.

   box A        box B        box C        ...  (infinitely many boxes)
  +-------+    +-------+    +-------+
  | . (o) |    | (o) . |    | . . (o)|     o = the element the
  | .   . |    |  .  . |    | (o). . |         choice function picks
  +-------+    +-------+    +-------+
      |            |            |
      v            v            v
   pick a_A     pick a_B     pick a_C      ...  one pick per box, all at once

   the OUTPUT is a single function:  box  -->  one element of that box

Read it left to right. Each box is a nonempty set; the choice function reaches into every box and returns one of its members. For finitely many boxes you could just point at picks one box at a time. The content of the axiom is that the function exists even when there are infinitely many boxes and no uniform rule tells you which member to take.

family of boxes	is a choice function guaranteed without the axiom?
finitely many nonempty boxes	yes, pick one at a time
pairs of shoes (left/right)	yes, the rule "take the left" works
pairs of identical socks	not by any rule; the axiom asserts one exists
every nonempty set of reals	not in general; the axiom asserts one exists

The key idea: a choice function is one object that selects from every box simultaneously, and the axiom is the promise that this object is always available.

Worked example Beginner

Let us see the axiom in action on a small family, and then see why a slightly bigger family forces the issue. Write a choice function for a family as a rule that returns one member of each set in the family.

Step 1. Take the family of three sets ${1, 2}$ , ${5, 6, 7}$ , and ${8}$ . A choice function picks one number from each. One valid choice is: from ${1, 2}$ take $1$ ; from ${5, 6, 7}$ take $5$ ; from ${8}$ take $8$ . So the choice function outputs the three numbers $1, 5, 8$ .

Step 2. Notice we did not need any axiom here. There are only three sets, so we just made three picks by hand and finished. Every finite family can be handled this way.

Step 3. Now make the family infinite but still ruled: for each whole number $n$ , take the set ${n, - n}$ , giving ${1, - 1}$ , ${2, - 2}$ , ${3, - 3}$ , and so on forever. A simple rule selects from every one of these at once: "take the positive member." That rule outputs $1, 2, 3, \dots$ , one pick per set, with no axiom needed, because the rule names the pick.

Step 4. Finally, break the rule. Split the real number line into groups where two numbers go in the same group when their difference is a fraction. Each group is nonempty, but the groups have no order and no labels, so there is no describable rule like "take the positive one" or "take the smallest." Here a hand-written recipe runs out. The axiom of choice steps in and asserts that a selection across all the groups exists anyway.

What this tells us: when a rule names your pick, you never need the axiom; when the sets are too featureless for any rule, the axiom is the only thing that delivers a simultaneous selection.

Check your understanding Beginner

Exercise (easy, multiple-choice).

For which family below does a simple naming rule give a choice function with no need for the axiom?

The groups of real numbers that differ by a fraction
Each set $\{n, -n\}$ for $n = 1, 2, 3, \dots$, using "take the positive member"
An unlabeled, unordered collection of identical-looking pairs
A family where the sets carry no describable structure at all

Hint

Look for the option where a sentence actually names which member to pick.

Answer

B. The rule "take the positive member" names a pick in every set ${n, - n}$ , so a choice function is written down directly. Feedback-correct: when a rule names the selection, the axiom is unnecessary. Feedback-wrong: options A, C, and D describe featureless families where no naming rule applies, which is exactly where the axiom is needed.

Formal definition Intermediate+

All of the following takes place inside ZF (cross-ref 42.03.01); the only primitive is $\in$ , and ordinals, well-orders, and transfinite recursion are as developed in 42.03.02. A choice function on a family $F$ of sets is a function $f$ with domain $F$ such that $f (X) \in X$ for every nonempty $X \in F$ .

The Axiom of Choice (AC) is the sentence: every family of nonempty sets has a choice function. Three equivalent formulations are standard ^{[Kunen Ch. I §12]}: every set of nonempty pairwise-disjoint sets has a transversal (a set meeting each member in exactly one point); every surjection $g : A ↠ B$ has a right inverse $s : B \to A$ with $g \circ s = id_{B}$ ; and the Cartesian product $\prod_{i \in I} X_{i}$ of nonempty sets is nonempty.

A partial order $(P, \leq)$ is a reflexive, antisymmetric, transitive relation. A chain is a subset linearly ordered by $\leq$ . An element $m \in P$ is maximal if no $p \in P$ has $m < p$ . A chain $C$ is bounded above if some $u \in P$ has $c \leq u$ for all $c \in C$ ; a poset is chain-bounded when every chain (the empty chain included, so $P \neq = \emptyset$ ) has an upper bound.

The four principal equivalents of AC, all stated over ZF, are:

Well-Ordering Theorem (WO). Every set admits a well-ordering: a linear order in which every nonempty subset has a least element.
Zorn's Lemma (ZL). Every chain-bounded partial order has a maximal element.
Hausdorff Maximal Principle (HMP). In every partial order, each chain is contained in a $\subseteq$ -maximal chain.
Cardinal Comparability (CC). For any two sets $A, B$ , either $A$ injects into $B$ or $B$ injects into $A$ .

A family $A$ of sets has finite character if $X \in A$ exactly when every finite subset of $X$ belongs to $A$ . The Teichmüller-Tukey Lemma (TT) states that every nonempty family of finite character has a $\subseteq$ -maximal member; it is the form of the maximal principle tuned to the existence of bases, maximal ideals, and ultrafilters.

A weaker relative is the Boolean Prime Ideal theorem (BPI), equivalently the Ultrafilter Lemma: every Boolean algebra has a prime ideal, equivalently every filter on a set extends to an ultrafilter. Among the fragments analysis uses, Countable Choice (ACω) asserts a choice function for every countable family of nonempty sets, and Dependent Choice (DC) asserts that for any entire relation $R$ on a nonempty set ( $\forall x \exists y x R y$ ) there is a sequence $(x_{n})_{n < ω}$ with $x_{n} R x_{n + 1}$ for all $n$ . The strict implications $AC \Rightarrow DC \Rightarrow AC_{ω}$ hold and neither reverses ^{[Jech AC Ch. 2]}.

Counterexamples to common slips Intermediate+

"Choice functions always require the axiom." For a family of nonempty sets of natural numbers, "take the least element" is a choice function definable in ZF with no appeal to AC. The axiom is needed only when the members carry no definable selector — a well-ordering of the union supplies one uniformly, which is precisely why WO implies AC.
"Zorn's Lemma needs the maximum of a chain, not merely an upper bound." The upper bound of a chain need not lie in the chain; Zorn requires only that some element of $P$ dominate the chain. Demanding the bound be the chain's maximum would be false in most applications (the union of a chain of subspaces bounds it but is rarely in the chain).
"BPI is just AC for Boolean algebras, hence equivalent to it." BPI is strictly weaker: it holds in the basic Cohen model where AC fails, yet it already yields the Ultrafilter Lemma, the compactness theorem for first-order logic, and Hahn-Banach. The gap is the content of the Halpern-Läuchli and Halpern-Lévy independence results.
"Countable choice suffices for everything in analysis." DC, not ACω, is what underwrites the equivalence of sequential and topological continuity on general metric spaces and the existence of choice sequences in the Baire-category and completeness arguments; ACω alone is too weak for some of these, and full AC is needed for a basis of every vector space.

Key theorem with proof Intermediate+

The organising theorem of the subject is that the four headline statements are one statement in four costumes: a fixed choice function can be run along the ordinals to well-order any set, a well-ordering instantly yields choice functions and maximal elements, and a maximal element feeds back a choice function. The proof exhibits a cycle of implications.

Theorem (equivalence of AC, WO, ZL). Over ZF, the following are equivalent: (i) the Axiom of Choice; (ii) the Well-Ordering Theorem; (iii) Zorn's Lemma ^{[Kunen Ch. I §12]}.

Proof. We show (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i).

(i) $\Rightarrow$ (ii). Let $A$ be a set; by AC fix a choice function $f$ on $P (A) ∖ {\emptyset}$ , so $f (S) \in S$ for every nonempty $S \subseteq A$ . Pick a set $* \in / A$ . Define a class function $G$ on ordinals by transfinite recursion (cross-ref 42.03.02): given the values already assigned below $α$ , set $$ a_\alpha = G(\langle a_\beta : \beta < \alpha\rangle) = \begin{cases} f\big(A \setminus {a_\beta : \beta < \alpha}\big) & \text{if } A \setminus {a_\beta : \beta < \alpha} \neq \varnothing,\[2pt]

& \text{otherwise.} \end{cases} $$ While the enumerated part omits some element of $A$ , the recursion picks a fresh element $a_{α} \in A$ , and these are pairwise distinct (each $a_{α}$ lies outside ${a_{β} : β < α}$ ). By Hartogs' theorem there is an ordinal $ℵ (A)$ that does not inject into $A$ (the proof below in the Advanced section), so the injection $α \mapsto a_{α}$ cannot run through all of $ℵ (A)$ without hitting the value $*$ . Let $θ$ be the least ordinal with $a_{θ} = *$ ; then $A = {a_{β} : β < θ}$ and $β \mapsto a_{β}$ is a bijection $θ \to A$ , transporting the ordinal order on $θ$ to a well-ordering of $A$ .

(ii) $\Rightarrow$ (iii). Let $(P, \leq)$ be chain-bounded; assume for contradiction it has no maximal element, so every $p \in P$ has a strict successor. Well-order $P$ as ${p_{ξ} : ξ < μ}$ by (ii). Build a chain by recursion: having chosen an increasing chain $C_{α} = {c_{β} : β < α}$ , let $u_{α}$ be an upper bound (chain-boundedness), and set $c_{α}$ to be the $\leq$ -least-indexed $p_{ξ}$ strictly above $u_{α}$ — one exists because $u_{α}$ is not maximal. Each $c_{α}$ strictly exceeds all earlier $c_{β}$ , so $ξ \mapsto$ (index of $c_{ξ}$ ) is a strictly increasing class function from $On$ into the set of indices $μ$ , impossible since $On$ is a proper class (Burali-Forti, cross-ref 42.03.02). Hence $P$ has a maximal element.

(iii) $\Rightarrow$ (i). Let $F$ be a family of nonempty sets. Consider the poset $P$ of partial choice functions on $F$ — functions $g$ with $dom (g) \subseteq F$ and $g (X) \in X$ — ordered by inclusion of graphs. The union of a chain of partial choice functions is again one (single-valuedness is preserved along a chain), so every chain is bounded above by its union; $P$ is chain-bounded and nonempty (the empty function lies in it). By ZL it has a maximal element $g^{*}$ . If some $X_{0} \in F$ were outside $dom (g^{*})$ , picking any $x \in X_{0}$ (which exists, $X_{0} \neq = \emptyset$ ) extends $g^{*}$ by the pair $(X_{0}, x)$ , contradicting maximality. So $dom (g^{*}) = F$ and $g^{*}$ is a choice function. $□$

Bridge. The equivalence is the foundational reason the cardinal and ordinal machinery of 42.03.02 and 42.03.03 applies to arbitrary sets rather than only to manifestly well-orderable ones: the Well-Ordering Theorem is exactly what lets every set inherit an ordinal length, so the counting theorem assigns it a cardinal. This is exactly the cycle a working mathematician invokes whenever a maximal object is summoned, since Zorn's Lemma is the face of AC dual to direct construction — instead of enumerating along the ordinals one bounds chains and reads off a maximum. The Hartogs aleph, run through Zermelo's recursion, generalises ordinary induction past every infinite stage, and the whole argument builds toward cardinal comparability, where Hartogs again forces one of two sets to inject into the other. Putting these together, the central insight is that a single choice function, fed into transfinite recursion, manufactures a well-ordering, and a well-ordering manufactures every other selection in sight; this circle appears again in the constructible universe 42.03.06, whose internal well-ordering makes AC a theorem rather than an axiom.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Using Zorn's Lemma, prove that every vector space $V$ over a field $k$ has a basis.

Hint

Order the linearly independent subsets of $V$ by inclusion; bound chains by unions.

Answer

Let $P$ be the set of linearly independent subsets of $V$ , ordered by $\subseteq$ . It is nonempty ( $\emptyset \in P$ ). Let $C \subseteq P$ be a chain and $W = ⋃ C$ . Any finite ${w_{1}, \dots, w_{n}} \subseteq W$ lies in a single member of the chain (each $w_{i}$ comes from some member, and a chain is linearly ordered, so the largest of those finitely many members contains all), hence is linearly independent; a dependence among finitely many vectors would be a dependence inside that member. So $W$ is linearly independent, $W \in P$ , and $W$ bounds $C$ . By Zorn, $P$ has a maximal element $B$ . If $B$ did not span $V$ , some $v \in / span (B)$ would make $B \cup {v}$ linearly independent, contradicting maximality. Hence $B$ spans and is independent: a basis. Rubric: full credit for the finite-character argument bounding chains and the maximality-forces-spanning step.

Exercise 5 (medium, symbolic).

Prove that every commutative ring $R$ with $1 \neq = 0$ has a maximal ideal, using Zorn's Lemma.

Hint

Order the proper ideals by inclusion; the union of a chain of proper ideals stays proper because it omits $1$ .

Answer

Let $P$ be the set of proper ideals of $R$ (ideals $I \neq = R$ , equivalently $1 \in / I$ ), ordered by $\subseteq$ . It is nonempty since $(0) \in P$ . Let $C$ be a chain in $P$ and $J = ⋃ C$ . $J$ is an ideal: for $a, b \in J$ they lie in a common member of the chain (linear order), so $a - b \in J$ , and $r a \in J$ for $r \in R$ . Moreover $1 \in / J$ , since $1$ lies in no member of $C$ ; hence $J$ is proper and bounds $C$ . By Zorn, $P$ has a maximal element $m$ , a maximal proper ideal — a maximal ideal. (The same argument with two-sided ideals handles noncommutative $R$ .) Rubric: full credit for ideal-hood of the union, properness via $1 \in / J$ , and the Zorn conclusion.

Exercise 6 (hard, symbolic).

Prove the Hausdorff Maximal Principle from Zorn's Lemma, and conversely derive Zorn from Hausdorff.

Hint

For HMP from ZL, apply Zorn to the poset of chains ordered by inclusion. For the converse, a maximal chain in a chain-bounded poset has a bound that is forced to be its maximum.

Answer

HMP from ZL: fix a partial order $(P, \leq)$ and a chain $C_{0}$ . Let $C$ be the set of chains of $P$ containing $C_{0}$ , ordered by $\subseteq$ . The union of a $\subseteq$ -chain of chains is again a chain (any two elements lie in a common member, hence are comparable), so $C$ is chain-bounded; by ZL it has a maximal element, a chain $\supseteq C_{0}$ maximal among chains. Conversely, ZL from HMP: let $(P, \leq)$ be chain-bounded. By HMP take a maximal chain $M$ (extending the empty chain). It has an upper bound $u \in P$ by chain-boundedness. Then $u \in M$ : were $u \in / M$ , then $M \cup {u}$ would be a strictly larger chain ( $u$ dominates all of $M$ ), contradicting maximality of $M$ . So $u$ is the maximum of $M$ , and $u$ is maximal in $P$ : any $p > u$ would give $M \cup {p}$ a larger chain. Rubric: full credit for both directions, especially the forced membership $u \in M$ .

Exercise 7 (hard, symbolic).

Prove the Ultrafilter Lemma from the Boolean Prime Ideal theorem: every filter $F$ on a set $S$ extends to an ultrafilter.

Hint

Work in the Boolean algebra $P (S)$ . A filter corresponds to the complement of an ideal; a prime/maximal ideal yields an ultrafilter.

Answer

Work in the Boolean algebra $B = P (S)$ with $\land = \cap$ , $\lor = \cup$ , complement $A^{c} = S ∖ A$ . A filter $F$ on $S$ (closed under finite intersection and supersets, $\emptyset \in / F$ ) corresponds to the dual ideal $I_{F} = {A : A^{c} \in F}$ , a proper ideal of $B$ . By BPI, $B$ has a prime ideal $J \supseteq I_{F}$ (BPI gives a prime ideal extending any proper ideal: apply BPI to the quotient $B / I_{F}$ , or use the maximal-ideal form, prime = maximal in a Boolean algebra). The dual $U = {A : A^{c} \in J}$ is then an ultrafilter: it is a filter extending $F$ , and for every $A$ , since $J$ is prime exactly one of $A, A^{c}$ lies in $J$ , so exactly one of $A^{c}, A$ lies in $U$ , the defining ultrafilter dichotomy. Rubric: full credit for the filter-ideal duality, the BPI extension, and primeness giving the $A$ -or- $A^{c}$ dichotomy.

Advanced results Master

The Hartogs aleph is the engine that converts a choice function into a well-ordering and forces cardinal comparability; the maximal principles are the chain-bounding reformulation; and the independence results mark the boundary the whole circle respects.

Theorem 1 (Hartogs' theorem; ZF). For every set $A$ there is a least ordinal $ℵ (A)$ that does not inject into $A$ ^{[Jech AC Ch. 2]}. The well-orderable subsets of $A$ carry well-orderings whose order types form a set of ordinals $W$ by Replacement (each type is the image of an injection from an ordinal into $A$ , and the collection of such injections is a subset of $P (ω \times A \times A)$ cut out by Separation); $ℵ (A) = sup {γ + 1 : γ \in W}$ is an ordinal, and it cannot inject into $A$ lest it appear in $W$ and exceed itself. Hartogs' theorem needs no choice — it is the choice-free reservoir of ordinals that Zermelo's recursion exhausts, and it is exactly what makes the enumeration $β \mapsto a_{β}$ terminate.

Theorem 2 (cardinal comparability is equivalent to AC). Over ZF, AC holds if and only if any two sets are $\leq$ -comparable by injection ^{[Kunen Ch. I §12]}. AC gives WO, so any two sets become well-orderable, hence comparable as ordinals project to comparable cardinals. Conversely, given comparability, compare an arbitrary $A$ with its Hartogs ordinal $ℵ (A)$ : since $ℵ (A)$ does not inject into $A$ , comparability forces $A$ to inject into $ℵ (A)$ , and an injection of $A$ into an ordinal transports the ordinal's well-ordering back to $A$ — so $A$ is well-orderable, and WO (hence AC) follows.

Theorem 3 (Tychonoff's theorem is equivalent to AC). The statement "every product of compact topological spaces is compact" is equivalent to AC over ZF (Kelley) ^{[Jech AC Ch. 2]}. Tychonoff $\Rightarrow$ AC because the one-point compactifications $X_{i}^{+} = X_{i} \cup {\infty_{i}}$ of nonempty sets with the cofinite-plus-point topology are compact, and a point of the nonempty compact product $\prod X_{i}^{+}$ avoiding every $\infty_{i}$ on a suitable closed slice yields a choice function. The Tychonoff theorem restricted to Hausdorff spaces drops in strength to exactly BPI — the ultrafilter-convergence proof of compactness needs only an ultrafilter on each index, not a full choice function, which is why the Hausdorff case sits at the BPI level.

Theorem 4 (independence of AC from ZF). If ZF is consistent, so is $ZF + \neg AC$ ^{[Jech AC Ch. 4-5]}. Two methods establish this. The Fraenkel-Mostowski permutation models build a model of ZF with atoms in which a group of atom-permutations acts and one restricts to hereditarily symmetric sets; choosing the group so that an infinite set of atoms (e.g. Russell's "socks", a family of unordered pairs) has no symmetric choice function gives $\neg AC$ , though atoms keep this from being a model of full ZF. Cohen's symmetric extension transplants the construction into pure ZF: forcing adds a denumerable set of mutually generic reals, and the symmetric submodel fixed by a group of automorphisms of the forcing contains the set but no well-ordering of it, so AC fails while ZF holds. The full forcing apparatus is developed in 42.03.06; here it is recorded that $\neg AC$ is consistent and that the consistency of $ZF$ already yields the consistency of $ZFC$ via Gödel's $L$ , the converse arrow co-produced in 42.03.06.

Theorem 5 (pathologies of full AC). AC yields a non-Lebesgue-measurable set and the Banach-Tarski paradox ^{[Jech AC Ch. 1]}. Vitali's set picks one representative from each coset of $Q$ in $R$ — a choice function on the quotient $R / Q$ — and its rational translates partition $[0, 1)$ into countably many congruent pieces, an arrangement no countably additive translation-invariant measure can assign a consistent value, so the set is non-measurable. Banach-Tarski sharpens this: using a free non-abelian subgroup of the rotation group $SO (3)$ and a choice of orbit representatives, the unit ball decomposes into finitely many pieces reassembled by rigid motions into two unit balls. Both proofs are choice-driven and both fail under the competing axiom of determinacy, where every set of reals is Lebesgue measurable.

Synthesis. The foundational reason the axiom of choice organises the transfinite is that one choice function, threaded through the transfinite recursion of 42.03.02, is exactly enough to well-order an arbitrary set, and a well-ordering extracts every other selection — this is the central insight that makes WO, ZL, HMP, TT, and cardinal comparability a single principle wearing five faces. Hartogs' aleph, the choice-free reservoir of ordinals, closes the loop: it terminates Zermelo's enumeration and forces comparability, so the appearance of an ordinal too large to inject powers both the well-ordering proof and Theorem 2. Zorn's Lemma is the face dual to enumeration, replacing the climb up the ordinals by the bounding of chains, and it is the form the rest of the corpus silently uses — bases, maximal ideals, algebraic closures, and Tychonoff are each a chain-bounding argument, while the Boolean Prime Ideal theorem is the strictly weaker fragment that already buys the ultrafilter lemma, compactness, and Hahn-Banach. Putting these together, AC is at once indispensable and double-edged: it makes cardinal arithmetic total and the hierarchy choice-respecting through $L$ 42.03.06, yet it manufactures the Vitali set and the Banach-Tarski decomposition. The bridge is that AC is independent of ZF — consistent to assume and consistent to deny — so this unit fixes the principle the rest of the corpus assumes, while 42.03.06 establishes that assuming it costs nothing in consistency, an independence that appears again in every theorem the corpus proves under the silent ZFC contract.

Full proof set Master

Proposition 1 (Hartogs' aleph; full proof). For every set $A$ there is an ordinal $ℵ (A)$ admitting no injection into $A$ , and a least such ordinal exists.

Proof. Call a pair $(B, R)$ a well-ordering on $A$ if $B \subseteq A$ and $R \subseteq B \times B$ well-orders $B$ . Each such $R$ is an element of $P (A \times A)$ , so the collection $W$ of all well-orderings on $A$ is a set by Separation. The order type $otp (B, R)$ is an ordinal (counting theorem, 42.03.02), and by Replacement $W = {otp (B, R) : (B, R) \in W}$ is a set of ordinals; it is an initial segment of $On$ , since a type's predecessors are types of initial segments of the same well-order. Let $ℵ (A) = sup W = ⋃ W$ , the least ordinal above every element of $W$ . If $ℵ (A)$ injected into $A$ by $j$ , then $j$ transports the ordinal well-order of $ℵ (A)$ onto $j [ℵ (A)] \subseteq A$ , exhibiting $ℵ (A)$ as the type of a well-ordering on $A$ , so $ℵ (A) \in W$ , whence $ℵ (A) < ℵ (A)$ , impossible. Leastness: any smaller ordinal $γ < ℵ (A)$ lies in $W$ , so is a type of a well-ordering on $A$ and does inject into $A$ . Hence $ℵ (A)$ is the least non-injecting ordinal. $□$

Proposition 2 (Bourbaki-Witt; ZL from a choice function without ordinals). Let $(P, \leq)$ be chain-bounded and $f : P \to P$ a function with $f (p) \geq p$ for all $p$ . Then $f$ has a fixed point. Consequently every chain-bounded poset has a maximal element.

Proof. Fix any $p_{0} \in P$ . Call $T \subseteq P$ admissible if $p_{0} \in T$ , $f [T] \subseteq T$ , and the supremum of every chain in $T$ that has one lies in $T$ . The intersection $M$ of all admissible sets is admissible and is the least admissible set. One shows $M$ is a chain by proving every $m \in M$ is comparable to all of $M$ : the set of such $m$ is itself admissible (the verification uses that for an "extreme" point $c$ with no element strictly between $c$ and $f (c)$ , every $x \in M$ satisfies $x \leq c$ or $x \geq f (c)$ , established by admissibility of ${x : x \leq c or x \geq f (c)}$ ). Since $M$ is a chain in the chain-bounded $P$ it has an upper bound, and being admissible it contains the supremum $u$ of $M$ . Then $f (u) \in M$ and $f (u) \leq u$ , while $f (u) \geq u$ by hypothesis, so $f (u) = u$ : a fixed point. For the maximality consequence, suppose $(P, \leq)$ chain-bounded had no maximal element; using a choice function on $P$ (AC) define $f (p)$ to be a chosen strict upper bound of $p$ , contradicting the fixed point $f (u) = u > u$ . Thus a maximal element exists. $□$

Proposition 3 (Teichmüller-Tukey from Zorn). Every nonempty family $A$ of finite character has a $\subseteq$ -maximal member.

Proof. Order $A$ by $\subseteq$ . Let $C \subseteq A$ be a chain and $U = ⋃ C$ . Every finite $F \subseteq U$ lies in a single member of the chain (each point of $F$ comes from some member; finitely many members in a chain have a largest containing all), so $F \in A$ by membership in that member together with finite character downward. Since every finite subset of $U$ is in $A$ , finite character gives $U \in A$ , so $U$ bounds $C$ in $A$ . By Zorn, $A$ has a maximal element. $□$

Proposition 4 (DC implies ACω; the implication is strict). Dependent Choice implies Countable Choice. The converse fails relative to ZF.

Proof. Let $(X_{n})_{n < ω}$ be nonempty sets; we produce a choice function. Let $S$ be the set of finite sequences $(x_{0}, \dots, x_{k - 1})$ with $x_{i} \in X_{i}$ , including the empty sequence, and define $s R s^{'}$ when $s^{'}$ extends $s$ by one term, $s^{'} = s^{⌢} ⟨ y ⟩$ with $y \in X_{∣ s ∣}$ . Each $s$ has an $R$ -successor (since $X_{∣ s ∣} \neq = \emptyset$ ), so $R$ is entire on the nonempty $S$ . By DC there is a sequence $s_{0} R s_{1} R \dots$ ; its terms cohere into a function $g$ with $g (n) \in X_{n}$ , a choice function for the family. Strictness: a Cohen-style symmetric model satisfies ACω while failing DC, as DC implies the existence of an infinite $ω$ -branch through certain trees that the model omits; this is recorded in ^{[Jech AC Ch. 8]}. Rubric for the forward direction is the tree-of-partial-choices construction; the strictness is cited, not reproved here. $□$

Proposition 5 (Vitali set; non-measurability under AC). Under AC there is a set $V \subseteq [0, 1)$ that is not Lebesgue measurable.

Proof. Define $x \sim y$ on $[0, 1)$ by $x - y \in Q$ . The equivalence classes partition $[0, 1)$ ; by AC choose one representative from each class, collecting them into $V$ . Enumerate $Q \cap [0, 1) = {q_{n} : n < ω}$ and let $V_{n} = (V + q_{n}) mod 1$ , the translation of $V$ by $q_{n}$ modulo $1$ . The $V_{n}$ are pairwise disjoint (two representatives differing by a rational would be $\sim$ -equivalent, hence equal) and their union is all of $[0, 1)$ (every $x$ is $\sim$ to its class representative, so differs from it by some $q_{n}$ ). If $V$ were measurable with measure $m$ , translation invariance gives each $V_{n}$ measure $m$ , and countable additivity forces $\sum_{n} m = μ ([0, 1)) = 1$ . But $\sum_{n} m$ is $0$ if $m = 0$ and $\infty$ if $m > 0$ , never $1$ — a contradiction. So $V$ is not measurable. $□$

Connections Master

Ordinals and transfinite recursion 42.03.02 are the machinery this unit runs: Zermelo's well-ordering proof is a transfinite recursion along $On$ driven by a fixed choice function, and the Burali-Forti fact that $On$ is a proper class is what forces the recursion to terminate inside any target set. The counting theorem of 42.03.02, assigning each well-order a unique ordinal type, is what lets the Well-Ordering Theorem deliver an ordinal length for every set; without the ordinal recursion of that unit, AC could not be cashed out as well-ordering, and the equivalence circle would have no engine.
Cardinals and cardinal arithmetic 42.03.03 depend on this unit for totality: a cardinal is an initial ordinal, and the assignment of a cardinality to an arbitrary set requires that the set be well-orderable, which is exactly the Well-Ordering Theorem proved here. The equivalence of AC with cardinal comparability (Theorem 2) is the precise statement that the cardinal $\leq$ -order is linear if and only if choice holds — under $\neg AC$ there are incomparable cardinalities and infinite Dedekind-finite sets, so the clean $ℵ$ -arithmetic of 42.03.03 is a choice-dependent luxury this unit underwrites.
The constructible universe $L$ and forcing 42.03.06 complete the foundational picture in both directions. Gödel's $L$ carries a definable well-ordering built by recursion along the ordinals, so $ZF + (V = L) ⊢ AC$ , giving the arrow $Con (ZF) \to Con (ZFC)$ co-produced as 42.03.06; conversely Cohen's symmetric extensions, the forcing technique also developed in 42.03.06, establish $Con (ZF) \to Con (ZF + \neg AC)$ . Together these make AC independent of ZF, so this unit fixes a principle that the rest of the corpus may assume freely precisely because 42.03.06 shows the assumption is consistency-neutral.

Historical & philosophical context Master

The axiom was isolated by Ernst Zermelo in 1904 to prove that every set can be well-ordered ^{[Zermelo 1904]}, answering a problem Cantor had posed. Zermelo's Auswahlaxiom — a simultaneous selection of one element from each member of a family of nonempty sets — drew immediate fire from the French analysts Borel, Baire, and Lebesgue, and from Peano, who objected to asserting the existence of a function specified by no rule. Zermelo's 1908 second proof recast the argument through the theory of " $Θ$ -chains," the kernel of the later Bourbaki-Witt tower, and was published alongside his first axiomatisation of set theory, partly to make the use of choice explicit and defensible.

The equivalents accumulated over the following decades: Felix Hausdorff stated his maximal-chain principle in Grundzüge der Mengenlehre (1914); Kazimierz Kuratowski (1922) and Max Zorn (1935) gave the maximal-element form now bearing Zorn's name, Zorn emphasising its use in algebra to avoid explicit transfinite recursion; Oswald Teichmüller (1939) and John Tukey (1940) formulated the finite-character version. Friedrich Hartogs had proved in 1915, without any choice, that every set is dominated by an ordinal — the result that powers cardinal comparability's equivalence with AC. The non-measurable set is due to Giuseppe Vitali (1905) and the paradoxical decomposition to Stefan Banach and Alfred Tarski (1924).

The independence of AC from ZF was settled in two stages. Abraham Fraenkel (1922) and Andrzej Mostowski (1939) built permutation models with atoms refuting AC, and Kurt Gödel (1938) proved the consistency of AC by constructing $L$ . Paul Cohen's 1963 invention of forcing produced symmetric models of $ZF + \neg AC$ in pure set theory ^{[Jech AC Ch. 5]}, closing the question and confirming that the axiom is neither provable nor refutable from the other axioms of Zermelo-Fraenkel set theory.

Bibliography Master

@book{kunen2011set,
  author    = {Kunen, Kenneth},
  title     = {Set Theory},
  series    = {Studies in Logic},
  volume    = {34},
  publisher = {College Publications},
  year      = {2011}
}

@book{jech1973axiom,
  author    = {Jech, Thomas},
  title     = {The Axiom of Choice},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {75},
  publisher = {North-Holland},
  year      = {1973}
}

@article{zermelo1904beweis,
  author  = {Zermelo, Ernst},
  title   = {Beweis, dass jede Menge wohlgeordnet werden kann},
  journal = {Mathematische Annalen},
  volume  = {59},
  year    = {1904},
  pages   = {514--516}
}

@article{zermelo1908neuer,
  author  = {Zermelo, Ernst},
  title   = {Neuer Beweis f{\"u}r die M{\"o}glichkeit einer Wohlordnung},
  journal = {Mathematische Annalen},
  volume  = {65},
  year    = {1908},
  pages   = {107--128}
}

@article{hartogs1915problem,
  author  = {Hartogs, Friedrich},
  title   = {{\"U}ber das Problem der Wohlordnung},
  journal = {Mathematische Annalen},
  volume  = {76},
  year    = {1915},
  pages   = {438--443}
}

@article{zorn1935remark,
  author  = {Zorn, Max},
  title   = {A remark on method in transfinite algebra},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {41},
  year    = {1935},
  pages   = {667--670}
}

@article{vitali1905problema,
  author  = {Vitali, Giuseppe},
  title   = {Sul problema della misura dei gruppi di punti di una retta},
  journal = {Tipografia Gamberini e Parmeggiani, Bologna},
  year    = {1905}
}

@article{banach1924decomposition,
  author  = {Banach, Stefan and Tarski, Alfred},
  title   = {Sur la d{\'e}composition des ensembles de points en parties respectivement congruentes},
  journal = {Fundamenta Mathematicae},
  volume  = {6},
  year    = {1924},
  pages   = {244--277}
}

@article{godel1938consistency,
  author  = {G{\"o}del, Kurt},
  title   = {The consistency of the axiom of choice and of the generalized continuum-hypothesis},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {24},
  year    = {1938},
  pages   = {556--557}
}

@article{cohen1963independence,
  author  = {Cohen, Paul J.},
  title   = {The independence of the continuum hypothesis},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {50},
  year    = {1963},
  pages   = {1143--1148}
}

Prerequisites

42.03.02

Tier anchors

beginner: Halmos 1960 *Naive Set Theory* (Van Nostrand) §15-17 (choice functions, Zorn's lemma, well-ordering by hand); Hrbacek-Jech 1999 *Introduction to Set Theory* 3e (Marcel Dekker) Ch. 8 (the axiom of choice for a first informal pass)
intermediate: Kunen 2011 *Set Theory* (College Publications) Ch. I §12 (the Axiom of Choice, choice functions, the Well-Ordering Theorem and Zermelo's proof, Zorn's Lemma, the Hausdorff and Teichmüller-Tukey maximal principles, cardinal comparability) and Ch. I §10-11 for the ordinal/cardinal background the equivalence proofs run on
master: Kunen 2011 *Set Theory* (College Publications) Ch. I §12 and the independence remarks in Ch. IV-VII (Cohen forcing) and the Fraenkel-Mostowski permutation models; Jech 1973 *The Axiom of Choice* (North-Holland) Ch. 1-5 (equivalents, weak forms ACω and DC, the Banach-Tarski paradox, Vitali sets, independence); Herrlich 2006 *Axiom of Choice* (Springer LNM 1876) for the disasters-with-and-without panorama

References

Kunen, K. — Set Theory · College Publications, Studies in Logic 34 (2011, revised edition). Chapter I §12 develops the Axiom of Choice and its equivalents: AC is stated as the assertion that every family of nonempty sets indexed by a set has a choice function (equivalently every set of nonempty pairwise-disjoint sets has a transversal, equivalently every surjection splits), and the Well-Ordering Theorem (every set admits a well-ordering) is proved equivalent to AC by Zermelo's transfinite-recursion argument running a fixed choice function along the ordinals (Hartogs' theorem supplying an ordinal too large to inject, forcing the enumeration to exhaust the set); Zorn's Lemma (a partially ordered set in which every chain has an upper bound has a maximal element) is proved equivalent via the Bourbaki-Witt fixed-point argument on the tower of a choice function, and the Hausdorff Maximal Principle (every chain extends to a maximal chain) and the Teichmüller-Tukey Lemma (every set of finite character has a maximal element) are derived in the same circle; cardinal comparability (any two cardinals are ≤-comparable) is shown equivalent to AC via Hartogs' aleph. The chapter records the standard applications — every vector space has a basis, every field has an algebraic closure, every unital ring with $1 eq 0$ has a maximal ideal, Tychonoff's theorem — and isolates the Boolean Prime Ideal theorem / ultrafilter lemma as a strictly weaker fragment.
Jech, T. — The Axiom of Choice · Studies in Logic and the Foundations of Mathematics 75, North-Holland (1973). The monograph is the standard reference for the whole web of choice principles: Chapters 1-2 develop AC, the Well-Ordering Theorem, Zorn's Lemma, the Hausdorff and Teichmüller-Tukey maximal principles, the Kuratowski-Zorn circle, and cardinal comparability, with the full equivalence proofs over ZF; Chapter 2 also treats the ultrafilter / Boolean Prime Ideal theorem and locates it strictly between ZF and ZFC; Chapters 3-5 develop the permutation models of Fraenkel and Mostowski and the symmetric-extension / Cohen forcing technique establishing the independence of AC from ZF and the relative strengths of the weak forms (countable choice ACω, dependent choice DC), together with the consequences a model of ¬AC can exhibit, including the failure of cardinal comparability and the existence of infinite Dedekind-finite sets; the Banach-Tarski paradox and the existence of non-Lebesgue-measurable sets are recorded as consequences of full AC that fail under the determinacy/measurability alternatives.
Zermelo, E. — Beweis, dass jede Menge wohlgeordnet werden kann · *Mathematische Annalen* 59 (1904), 514-516, with the second proof and the reply to critics in *Mathematische Annalen* 65 (1908), 107-128. Zermelo's 1904 note isolates the choice principle (the *Auswahlaxiom*: a simultaneous selection of one element from each member of a family of nonempty sets) and uses it to prove the Well-Ordering Theorem, that every set can be well-ordered, by building an increasing transfinite sequence of 'γ-sets' along a fixed choice function until the set is exhausted; the 1908 second proof recasts the argument through the theory of 'Θ-chains' (the kernel of what is now the Bourbaki-Witt tower argument) and answers the objections of Borel, Baire, Lebesgue, and Peano to the use of an arbitrary unspecified selection, framing the controversy over non-constructive existence that the axiom still carries.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m