Cardinals and the Axiom of Choice
Distinguish bijective size from order type and identify exactly where well-ordering and simultaneous selections use Choice.
On this page
The question for today
What you’ll understand
- Define initial ordinals as cardinals for well-orderable sets.
- Relate Choice, well-ordering, and Zorn’s lemma over ZF.
- Check explicit finite selections and countable bijections without attributing them to full Choice.
Cardinality forgets the order information retained by ordinals. Two sets have the same size when a bijection connects them, but identifying every size with a least ordinal requires that every set can be well-ordered. The Axiom of Choice supplies exactly that extra principle. Its equivalent formulations are powerful because they turn existence of individual choices or upper bounds into a global object, while explicit finite constructions often need no such additional axiom.
Initial ordinals represent well-orderable sizes
In ZF, two sets are equinumerous if there exists a bijection between them. Cantor–Bernstein proves that injections in both directions suffice, without assuming Choice. A cardinal, in the ordinal convention used here, is an ordinal not bijective with any smaller ordinal. Every well-orderable set has a unique such cardinal as its size. Without Choice, not every set must be well-orderable, so this convention cannot silently assign an initial ordinal to every arbitrary set.
The finite cardinals and ω are initial ordinals, followed by the aleph sequence. The ordinal ω+ω has cardinality ω even though it is a different order type. Hartogs' theorem, already in ZF, assigns to each set A a least ordinal that does not inject into A. It does not provide a well-order of A. This distinction matters when importing a cardinal-arithmetic proof: arguments using a least ordinal representative for an arbitrary input set have already assumed an appropriate well-orderability principle.
Equivalent choice principles have quantified hypotheses
Choice states that every set-indexed family of nonempty sets has a function selecting one member from each indexed set. It does not require the family members to be disjoint. Over ZF it is equivalent to the well-ordering theorem and to Zorn's lemma. In Zorn's formulation, a nonempty partially ordered set in which every chain has an upper bound in that same partially ordered set has a maximal element. A maximal element need not be a greatest element comparable above every other point.
A well-order supplies a choice function by selecting least elements. Conversely a choice principle can drive a transfinite selection process until a set is exhausted, with Hartogs' theorem preventing an endlessly new sequence indexed by every ordinal. This explains the connection without presenting the sketch as a complete proof of all equivalences. In applications, verify that the candidate partial objects form a set and that unions of chains stay inside it; otherwise an appeal to Zorn may conceal the central missing hypothesis.
Explicit constructions can be stronger evidence than a label
A finite family of nonempty sets admits a choice function by finite induction, with no full Choice axiom. An infinite family can also have an explicit selection rule, such as taking the least natural number in each nonempty subset of ω. These examples do not prove the general axiom. Countable Choice, Dependent Choice, and unrestricted Choice are separate statements over ZF, and a proof that needs one should not be described as requiring all of them without examining its actual quantifiers.
Under ZFC, infinite well-ordered cardinal arithmetic simplifies: adding or multiplying an infinite cardinal by itself does not enlarge it. Exponentiation is different, because Cantor's diagonal argument makes the power set strictly larger than its original set. These claims concern existence of bijections or nonexistence of surjections, not numerical growth observed in a finite display. Finite multiplication is still ordinary multiplication; identifying a finite cycle with a finite image is useful for checking a proposed map, but cannot establish an infinite-cardinal theorem.
Work it through
Separate a selection from an infinite bijection
Choose one element from each of A₀={0,2}, A₁={1,3}, A₂={2,4}, and exhibit a bijection from ω×{0,1} to ω.
The least-element rule gives c(0)=0, c(1)=1, and c(2)=2. Each selected value lies in the specified set; overlap between different family members causes no problem.
Define f(n,i)=2n+i. If 2n+i=2m+j with i,j∈{0,1}, parity gives i=j and then n=m, proving injectivity.
Every natural number has a unique quotient and remainder on division by two, so it equals 2n+i for one pair. Thus f is surjective and a bijection.
Both constructions are explicit in ZF. The infinite bijection proves two countable copies are countable; it does not prove Choice for arbitrary families.
The living notebook
Explore the model
Interactive lab · modular
Check whether a finite assignment is bijective
Pause and Reset, then set modulus m = 12 and additive step a = 5. Predict that the first twelve residues visit all twelve labels once, since gcd(12,5)=1. Reset and set both m = 12 and a = 4; the orbit is only 0,4,8 with period three. On paper compare the maps n↦5n and n↦4n modulo twelve. This checks finite injectivity and image size; it does not decide Choice or infinite cardinal arithmetic.
- Residue r0
- 0
- Orbit period · m/gcd(m,a)
- 12
- Distinct residues visited
- 1 of 12
Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA claimed correspondence needs injectivity and surjectivity, not merely an assignment rule.
Pause & reason
Check your understanding
Your turn
Try it yourself
For the set of all finite partial choice functions on a fixed infinite family of nonempty sets, does taking the union of a chain always stay in that partially ordered set? Explain the issue and give a suitable larger set of partial objects.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
A chain can have domains of increasing finite sizes. Distinguish a partial choice function from a finite partial choice function.
Compare with the solution
No. A chain of finite partial functions may have an infinite union, so its upper bound need not remain finite. Instead take all partial choice functions whose domains are arbitrary subsets of the index set. Their graphs lie in a suitable power set of the product of the index set with the union of the family, so the collection is a set. A chain union is again a partial choice function because comparable graphs agree on overlap. Under Zorn’s lemma a maximal such function exists, and a missing coordinate could be filled using one witness, so maximality forces full domain.
Keep the idea
Take it with you
- Cardinals as initial ordinals represent well-orderable sizes; Choice makes this universal.
- Choice, well-ordering, and Zorn’s lemma are equivalent over ZF with their full hypotheses.
- Finite choices and explicit countable bijections do not establish unrestricted Choice.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.