Motivation
A proof can select one member of one nonempty set by existential instantiation. It can make finitely many such selections by repeating the argument. Neither observation supplies a function making selections from an arbitrary infinite family simultaneously. The axiom of choice is precisely such an additional assertion.
Choice often enters mathematics through a different-looking statement: an independent set extends to a basis, or a partially ordered collection has a maximal object. These are useful because an explicit algorithm for the desired object may be unavailable. Their hypotheses still require checking. In particular, maximal does not mean greatest, and a maximality argument needs upper bounds for chains rather than just pairs.
Definitions
Definition 4.1.1
(Choice functions and the axiom of choice)
For a set-indexed family of nonempty sets, a choice function is a function with domain such that . The axiom of choice (AC) asserts that every such family has one. The indexing family is itself a set; AC does not assert a choice function on the proper class of all nonempty sets.
Definition 4.1.2
(Chains, upper bounds and maximal elements)
A partial order is reflexive, antisymmetric and transitive. A chain is a subset whose members are pairwise comparable. An upper bound of is satisfying for all ; it need not belong to . An element is maximal if implies . It is greatest if for every .
Definition 4.1.3
(Well-ordering principle and Zorn's lemma)
The well-ordering principle says that every set admits a well-order. Zorn's lemma says that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Including the empty chain is harmless once is nonempty; any member is its upper bound.
Theorem/proposition
Theorem 4.1.4
(Hartogs' theorem, in ZF)
For every set , there is an ordinal that does not inject into . One may take the least such ordinal. The theorem does not assume that can be well-ordered.
Theorem 4.1.5
(Choice, well-ordering and Zorn are equivalent over ZF)
AC, the well-ordering principle and Zorn's lemma are equivalent.
Theorem 4.1.6
(Basis extension, using AC)
Let be a vector space over a field and linearly independent. There is a basis of containing .
Proof sketch or proof idea
Proof
(An ordinal beyond every well-order on a subset)
For Hartogs, all well-orders on subsets of form a set: they can be encoded as pairs in . Replacement collects their unique ordinal order types in a set . Let
If injected into , transport its well-order to the image; then . The definition of would give , impossible. Thus at least one ordinal fails to inject into . Separation inside and its well-order gives a least failure . The argument constructs an obstruction ordinal without selecting a well-order on .
Proof
(AC implies well-ordering)
Assume AC. Applied to the nonempty subsets of a nonempty set , it gives a selector . Fix . Recurse for : if there are elements of not previously chosen, choose of that remainder; otherwise use . If the remainder never became empty, all chosen values would be distinct, producing an injection . Hence at some earlier stage all of has been chosen. Before the first such stage the choices are distinct and enumerate by an ordinal. This transports a well-order to . The empty set already has its unique well-order. This proves AC implies well-ordering without assuming a vague instruction to “keep choosing until finished”.
Proof X-ray
Hartogs supplies the stopping bound
The recursion runs along the ordinal , fixed in advance, so no informal “until finished” is needed. Choice enters exactly once, as the single selector on the nonempty subsets of ; after that, each stage is uniquely specified by the earlier values. The default value only keeps the recursion defined after exhaustion.
The key move is a contradiction with the definition of . If the remainder were nonempty at every stage , each value would differ from all earlier ones, giving an injection . Hence some stage has empty remainder. At the least such stage , the values before are distinct and exhaust , so is a bijection that transports the order of .
Proof
(Well-ordering implies Zorn's lemma)
Assume well-ordering, and well-order the set in Zorn's hypothesis. Traverse its elements by transfinite recursion, adding an element to exactly when it is comparable with every previously added element. The resulting is a chain. It is maximal among chains: if is comparable with every member of , it was comparable with all earlier chosen members at its own stage and would have been added. Let be an upper bound of . If , then is comparable with every member of , so belongs to , which forces , a contradiction. Therefore is a maximal element of . This proves well-ordering implies Zorn.
Proof X-ray
Why the upper bound of a maximal chain is maximal
The well-order on turns the traversal into a recursion with one outcome at each stage, so building involves no further choice. The real idea is that is maximal among chains: an element comparable with every member of is already in . Applied to an upper bound , this places in as its greatest member; applied to a hypothetical , it forces . Zorn’s chain hypothesis is used exactly once, for this single chain. The first element of the well-order is always added, so is nonempty because is.
Proof
(Zorn's lemma implies AC)
Assume Zorn and take a family of nonempty sets. Partially order all partial choice functions by extension. This is a set of graphs inside and contains the empty function. The union of a chain is again a partial choice function, since any two assigned values for the same index occur in comparable functions and hence agree. It is an upper bound. A maximal partial choice function cannot omit an index : one member of would extend it at that single index. Thus its domain is , proving AC. Selecting a member of this one does not assume AC in the argument.
Proof
(Basis extension by Zorn's lemma)
For basis extension, order all linearly independent subsets of containing by inclusion. The union of a nonempty chain is independent: any finite relation among vectors of lies in one chain member, since finitely many members of a linearly ordered family have a largest one. That member forces every coefficient to vanish. The empty chain has upper bound . Zorn supplies maximal . If , then is independent, contradicting maximality. Hence spans and is a basis.
Worked examples
Worked example 4.1.7
(Maximal and greatest differ)
In the partial order of proper subsets of by inclusion, and are maximal. Neither is greatest. A maximal basis need not contain every vector; maximality only says that adding any further vector destroys independence. For a nonzero vector space, the entire space is usually highly dependent as a set of vectors, and contains the zero vector in every case.
Counterexample mode
Pairwise upper bounds do not suffice for Zorn
Claim: if every pair of elements of a nonempty partial order has an upper bound, the order has a maximal element. The positive integers ordered by their usual order have an upper bound for every pair, namely their maximum. They have no maximal element. The chain consisting of all positive integers has no upper bound in that partially ordered set. Thus the missing Zorn hypothesis is a genuine obstruction, rather than a technicality.
Worked example 4.1.8
(Finite and canonical choices)
For a finite family of nonempty sets, induction on the family size constructs a choice function in ZF. For any family of nonempty subsets of , choose the least element of each; replacement collects these uniquely specified values. Even an infinite family need not require AC when a common canonical selection rule is available.
Worked example 4.1.9
(Extending a linear functional)
Let be a subspace and linear. Choose a basis of and extend it to a basis of . Assign to and zero to . Unique finite basis expansions define a linear extension . The choice-dependent step is obtaining the bases; once they are fixed, the formula for is uniquely determined. This is an algebraic statement with no continuity assertion.
Worked example 4.1.10
(From a maximal ideal to a field)
The maximal-ideal argument in the exercises has an important payoff. If is a maximal proper ideal in a commutative ring with identity, then is a field. Take a nonzero coset , so . The ideal strictly contains , hence is all of . Thus for some . Reducing modulo gives , so the coset has an inverse. Properness of ensures , as a field requires.
Conversely, if is a field and is an ideal properly containing , pick . The nonzero coset has an inverse , so . Since , subtraction gives , hence . Therefore is maximal. This equivalence explains what the maximal object accomplishes: it produces a quotient in which every nonzero element is invertible.
The choice-dependent existence assertion and the elementary quotient calculation have different roles. Once a particular maximal ideal is given, the field proof needs no new arbitrary choices: for each nonzero coset, the inverse is unique. Similarly, Zorn may prove that a basis exists, while coordinate uniqueness follows by finite independence. Separating these steps helps locate exactly which part of an application rests on AC, rather than labeling the whole algebraic calculation as a use of choice.
Margin Note
Unique answers need no additional arbitrary choices
Existence statements with unique witnesses behave differently from the families in AC. If every input in a set has exactly one output, replacement already collects the outputs and their graph in ZF. No choice is needed to select between alternatives, because there are no alternatives. The unique inverse of a nonzero field element and the unique coordinates relative to a fixed basis illustrate this point.
In contrast, a surjection may have many points in each fiber. Producing a right inverse requires selecting one of them. A well-order on the domain makes the least point a canonical witness; without such a structure, simultaneous selection is a separate problem. Keeping this distinction visible prevents two opposite errors: overlooking AC when representatives are picked without a rule, and unnecessarily invoking AC whenever a proof uses the phrase “for each”. The substantive question is whether the selected values are uniquely specified by the available data, not whether the indexing set is infinite. In particular, the existence of a basis may depend on choice, while the finite coordinate computations after that basis is fixed do not require fresh choices at each step. Marking this boundary clearly makes the axiomatic dependencies of algebraic applications easier to check.
Comparability and finite character
Two more forms of choice appear constantly in practice. The first concerns size: without choice, two sets need not be comparable by injections at all. The second isolates the union argument from the basis proof as a reusable lemma.
Theorem 4.1.11
(Comparability of sizes is equivalent to AC)
Over ZF, the axiom of choice is equivalent to the statement that for any sets and there is an injection or an injection .
Proof
(Compare a set with its Hartogs ordinal)
Assume AC. By the well-ordering principle there are bijections and onto ordinals. Ordinal comparison gives or . In the first case , read through the inclusion , is an injection ; in the second case is an injection .
Conversely, assume comparability and let be any set. Compare with the ordinal from Hartogs' theorem. By definition does not inject into , so there is an injection . Setting exactly when defines a well-order on : it is the membership order of the set of ordinals , pulled back along an injection. Hence every set can be well-ordered, and AC follows from the equivalence theorem. The argument uses comparability only between a set and one ordinal.
Definition 4.1.12
(Families of finite character)
Let be a set. A family has finite character if, for every , exactly when every finite subset of belongs to .
A family of finite character is closed under subsets: if and , every finite subset of is a finite subset of and so lies in ; hence . The linearly independent subsets of a vector space form such a family, because a linear relation involves only finitely many vectors. So do the chains of a partial order, because comparability is a condition on pairs.
Theorem 4.1.13
(Tukey's lemma)
Assume AC, and let be a family of finite character on a set . Every member of is contained in an inclusion-maximal member of . Over ZF, this statement for all families of finite character is equivalent to AC.
Proof
(Finite character makes chain unions admissible)
Fix and let , ordered by inclusion. It is a set by separation inside , and it contains , which also bounds the empty chain. Let be a nonempty chain in and . A finite subset of has each in some member of . These finitely many members are pairwise comparable, so one of them, , contains all the others, and the finite subset lies in . (The empty subset lies in any member.) Closure under subsets puts it in . By finite character , and clearly , so is an upper bound in . Zorn's lemma gives a maximal . If , then , so and . Thus is maximal in .
For the converse, let be a family of nonempty sets and . A subset is the graph of a partial choice function exactly when no two of its pairs share a first coordinate while differing in the second. That is a condition on two-element subsets, so these graphs form a family of finite character, containing . A maximal member is defined at every index, since an index it missed could be added with one element of . It is a choice function.
Worked example 4.1.14
(Every partial order extends to a linear order)
Let be a partial order. Consider the set of all partial orders that contain , ordered by inclusion. The union of a nonempty chain of them is again a partial order containing : reflexivity is inherited, and the two or three pairs involved in any antisymmetry or transitivity check lie in a single member of the chain. The empty chain is bounded by itself. Zorn's lemma gives a maximal .
Suppose some were -incomparable, and put
It contains and is reflexive. For transitivity, take . If both lie in , so does . If only is new, then and , so is a new pair of ; the case where only is new is symmetric. If both are new, then , contradicting incomparability, so that case cannot occur. For antisymmetry, let with . They cannot both lie in . If one of them, say , is new, then and , while the other pair gives or, if it is new as well, and . In each case follows, which is impossible. So is a partial order strictly larger than , contrary to maximality. Hence is a linear order extending . For finite , repeating the one-step extension finitely often proves the result with no choice principle.
Common mistakes
Common mistake
(A chain is not a sequence)
A chain is totally ordered by the given partial order; it need not be a sequence and can be uncountable.
Common mistake
(Taking a union is not yet an upper-bound proof)
“Take the union” is not automatically an upper-bound proof: verify that the union still satisfies the defining property, as finite character did for independence. Closed or complete conditions often fail under unions.
Common mistake
(Zorn gives existence, not uniqueness or independence results)
Zorn produces a maximal element, not uniqueness or a preferred construction. Do not claim AC follows from ZF, or that its negation has been established by these equivalences. Independence and relative-consistency results require additional metamathematics, beyond the proofs here.
Summary
Hartogs provides a set-sized stopping bound. AC turns repeated selection into a well-order; well-ordering constructs maximal chains; Zorn completes partial choice functions. Comparability of sizes and Tukey's lemma are further equivalent forms; the second turns the union argument for independent sets into a general tool. Maximality applications work by checking nonemptiness, all chain upper bounds, and the implication from maximality to the desired property.
Exercises
Quick check
(Prove that every surjection onto a nonempty well-orderable set has a right inverse if its domain is also well-orderable. Identify which well-order actually supplies the selections.)
Solution · Answer
Let be onto and well-order . Each fiber is nonempty, so assign its least element . Replacement gives and . It is the well-order on that chooses fiber elements; no well-order on is needed for this construction. The stated assumption on is therefore stronger than necessary.
Quick check
(In the basis proof, show explicitly why adjoining preserves independence.)
Solution · Answer
A relation with distinct has , since otherwise it expresses as a finite linear combination of . Independence of then forces all . Relations not involving were already controlled.
Quick check
(Use Zorn to prove that every proper ideal of a commutative ring with identity is contained in a maximal proper ideal. State why the chain union remains proper.)
Solution · Answer
Order the proper ideals containing by inclusion; makes the set nonempty. A nonempty chain union is an ideal: any two elements lie together in one chain member, where addition and multiplication by ring elements are available. If the union contained , one member would contain and equal the entire ring, contrary to properness. The empty chain is bounded by . Zorn yields a maximal member; any proper ideal strictly containing it would also contain , contradicting maximality.
Quick check
(Explain why the family of all finite subsets of an infinite set, ordered by inclusion, does not automatically satisfy Zorn's hypothesis.)
Solution · Answer
A chain may have infinite union, which is not a finite subset and hence not a member of the partially ordered set. Already for , the chain has no finite upper bound. Directedness for finite collections is insufficient. For arbitrary infinite in ZF, one should also avoid silently assuming a countable sequence of distinct elements; the explicit example alone disproves the general claim.
Quick check
(Use Tukey's lemma to prove the Hausdorff maximal principle: every chain in a partially ordered set is contained in an inclusion-maximal chain.)
Solution · Answer
A subset is a chain exactly when each of its two-element subsets is, hence exactly when each of its finite subsets is. So the chains form a family of finite character in , and Tukey's lemma extends any chain to a maximal one. Maximal means only that no chain properly contains it. In ordered by inclusion, and are two different maximal chains.
Quick check
(Assuming AC, show that , as a vector space over , has a basis containing both and .)
Solution · Answer
Linear independence over has finite character. The set is independent: if with and , then would be rational, so and then . Tukey's lemma extends to a maximal independent set . As in the basis-extension proof, a vector would make independent, so spans .
Quick check
(Prove in ZF that a set admitting an injection into a well-orderable set is itself well-orderable. Where does this step occur in the comparability proof?)
Solution · Answer
Let be injective and a well-order on . Define when . It is irreflexive and transitive, and linear because forces . A nonempty has nonempty, with least element for exactly one , and this is -least in . In the comparability proof this is the step from the injection to a well-order on , with as the well-ordered set.