Motivation
The equations and already show that infinite order retains information that cardinality forgets. Exponentiation organizes that information into larger blocks. Cantor normal form then expresses every nonzero ordinal as a finite sum of decreasing powers of , with positive finite coefficients.
Finite here needs interpretation. The number of terms is finite, but their exponents can themselves be large ordinals. Repeatedly expanding those exponents need not produce a finite written expression. Cofinality asks a different question: how many positions are needed to approach an ordinal from below? An ordinal can be very large while admitting a short cofinal sequence. Keeping order arithmetic, cardinal size and cofinality separate makes these statements compatible.
Definitions
Definition 3.2.1
(Ordinal exponentiation)
For a positive ordinal , exponentiation is defined in its exponent by
at nonzero limits. We use for the normal-form theorem. Multiplication and addition are ordinal operations. Thus places copies of in order; the coefficient is on the right.
Definition 3.2.2
(Cantor normal form)
A Cantor normal form is
where is positive finite and each is a positive natural number. Zero is represented by the empty sum.
Definition 3.2.3
(Cofinal subsets and cofinality)
A subset of an ordinal is cofinal if every is at most some member of . Define to be the least initial ordinal for which some function has cofinal range. It exists because is well-orderable. Put ; a successor has cofinality one, using its greatest predecessor. A nonzero limit has no finite cofinal subset, so its cofinality is infinite.
Definition 3.2.4
(Regular and singular cardinals)
An infinite initial ordinal is regular if , and singular otherwise. These adjectives concern cardinals, not an arbitrary ordinal merely because its cofinality is smaller than its order type. No choice principle is assumed unless stated explicitly.
We use elementary arithmetic facts justified by ordered concatenation: addition is associative, nondecreasing in its first argument, and strictly increasing and continuous in its second. Its three-block associativity is the canonical order-isomorphism that changes parentheses without changing any position. Finite multiples satisfy , and .
Theorem/proposition
Theorem 3.2.5
(Powers of and additive indecomposability)
The function is strictly increasing, continuous at nonzero limits and satisfies . For every , if , then . For this also gives
Theorem 3.2.6
(Existence and uniqueness of Cantor normal form)
Every nonzero ordinal has exactly one Cantor normal form. The construction repeatedly removes a largest power of , a uniquely determined positive finite coefficient and a strictly smaller remainder. It terminates after finitely many removals because it would otherwise produce an infinite descending sequence of exponents.
Concept lensAlgorithmic
Comparing ordinals through their normal forms
Normal forms also give a comparison procedure. To compare two nonzero ordinals, compare leading exponents; if they agree, compare leading coefficients; if both agree, compare the remainders in the same way. This is correct because the leading exponent and coefficient place an ordinal in the interval from up to, but excluding, , and on equal leading terms strict increase in the second summand transfers the comparison to the remainders. Thus , although the left side has more terms.
Theorem 3.2.7
(Cofinality is a regular cardinal)
For every nonzero limit ordinal , admits a strictly increasing cofinal map and satisfies . These statements hold in ZF. They do not assert that every ordinal, or every infinite cardinal, is regular.
Proof sketch or proof idea
Proof
(Increase, continuity and indecomposability)
Successor powers strictly increase because a positive ordinal followed by another copy of itself is larger, and contains at least two copies. At a limit, every earlier power is below a still later power in the defining supremum. Transfinite induction then gives : successors increase by at least one, and limits dominate every earlier index.
Prove additive indecomposability by induction on . At zero the only smaller ordinal is zero. At , put . Since , bound and for positive finite . Then
At a limit, both ordinals lie below one common earlier power; apply that earlier induction hypothesis. For , the ordinal is a limit. Continuity of addition and the just-proved bound give . The reverse inequality follows from monotonicity in the first argument and . This proves absorption.
The hypothesis that the right summand is a power of cannot be weakened to its being a limit ordinal.
Counterexample mode
A limit ordinal need not absorb smaller summands
Claim: if is a nonzero limit and , then . Take and . Left distributivity of finite multiples gives , and , so absorption fails. Closure under addition fails too: but is not below . The theorem applies to ; here lies strictly between and and is not such a power.
Proof
(Division by the leading power)
Now fix . There is a least with : the bound supplies a set-sized search. This is neither zero nor a limit, because at a limit all previous powers at most would have supremum at most . Write . Thus
Put . There is a unique positive finite with , by taking the first finite multiple larger than . The initial segment of has a well-ordered tail of some unique type , so . Strict increase in the second argument makes the tail unique. Its type is below , or the next multiple would already lie below .
Repeat on a nonzero remainder. Its leading exponent is strictly smaller, because the remainder is below the previous leading power. If the process never stopped, ordinary recursion would give a strictly descending sequence of ordinals; the range of that sequence has a least member, contradicted by its successor term. Hence the expansion is finite.
For uniqueness, in any proposed normal form the tail after the leading term is below its leading power. Each lower term is below that power, since its exponent is smaller, and additive indecomposability keeps a finite sum below it. The whole form therefore identifies exactly the interval between consecutive powers and then the interval between consecutive finite multiples. The uniquely determined leading exponent, coefficient and remainder agree with the construction. Repeating on the finite tail proves uniqueness.
Proof X-ray
Which sequence the termination proof forbids
The descending sequence in the proof is the list of leading exponents of successive remainders. It is not a sequence obtained by repeatedly expanding the exponent inside one term. That second procedure can return to the same ordinal at a fixed point, as the example shows. The first procedure must strictly decrease at each nonfinal step because each new remainder is below the preceding power. Its values are uniquely specified by the division argument, so ordinary recursion supplies a sequence if the procedure never stops; no dependent choices are being assumed. This identifies exactly the infinite descent excluded by the least-element argument.
Proof
(An increasing cofinal map of minimal length)
For cofinality, choose a cofinal witnessing the least initial ordinal . Since is a limit, is infinite, and an infinite initial ordinal is a limit ordinal: an infinite successor ordinal is equinumerous with its predecessor by shifting its first positions and the extra point. Every has cardinality below . Therefore the values indexed by cannot already be cofinal in , or a smaller cardinal would witness cofinality.
Construct by recursion
The earlier range has cardinality below and hence is bounded in . Since is a limit, the displayed successor supremum is still below . Thus the construction stays in its target, is strictly increasing and is cofinal because it dominates . If a smaller cardinal had a cofinal map , then would be cofinal in , using the monotonicity of . This contradicts minimality of . Since the identity map is cofinal in , its cofinality is exactly . No enumeration choices for an arbitrary family of sets entered this argument.
Proof X-ray
How minimality of the cofinality is used twice
The recursion takes the larger of the given value and a running bound strictly past all earlier values. Minimality of is used twice. First, each earlier range is indexed by some of smaller cardinality, so it is bounded in , and because is a limit the running bound stays inside . Second, a shorter cofinal map into , composed with the increasing , would give a shorter cofinal map into . Domination of supplies cofinality; the added successor supplies strict increase.
Worked examples
Worked example 3.2.8
(Adding normal forms removes a lower tail)
Let and . Absorption gives
In the first expression, the tail disappears when the right summand's begins. In the second, the entire left summand is below and disappears. The largest left-hand block does not disappear in the first calculation. Normal forms make the order of operations visible rather than turning addition into coefficient-wise arithmetic.
The explorer below lets you enter two ordinals below in Cantor normal form, add or multiply them in either order, and see which lower terms are absorbed and whether the order of the operands matters.
Worked example 3.2.9
(Ordinal powers and cardinal powers answer different questions)
The ordinal power is , since the finite powers are unbounded among the natural numbers. In cardinal notation, counts all binary functions on , equivalently all subsets of , and is uncountable by Cantor's theorem. The same-looking exponent notation describes an ordered recursive limit in one case and a set of functions in the other. A bare exponent symbol must be read in its declared setting.
Worked example 3.2.10
(A finite normal form can contain a fixed-point exponent)
Let , and . The sequence is strictly increasing. Continuity and its cofinality give
It is the least positive fixed point: any positive with bounds , then every by induction, and hence . The conventional notation is . Its normal form has one term, . Thus “finite normal form” does not say that recursively expanding every exponent yields a finite expression built only from natural numbers. Its displayed cofinal sequence also gives .
Worked example 3.2.11
(A singular cardinal with a specified cofinal sequence)
Define , let be the next initial ordinal after (whose existence follows from Hartogs), and put . This supremum is an initial ordinal: any smaller ordinal lies below some and cannot have the size of the whole supremum. The displayed sequence is cofinal, while no finite subset is cofinal in a limit ordinal. Hence , so this cardinal is singular. The sequence is specified by unique ordinal rules, with no arbitrary simultaneous choices.
Common mistakes
Common mistake
(Malformed normal forms)
Coefficients in normal form multiply on the right, and exponents decrease strictly. Leaving a zero coefficient or equal consecutive exponents is not a canonical form. Nor does normal form imply that ordinal arithmetic is commutative or that an ordinal is determined by its cardinality.
Common mistake
(Cofinality is not monotone)
Cofinality is not monotone under taking larger ordinals: has cofinality , while has cofinality one.
Common mistake
(A cofinal map need not be increasing)
A cofinal map need not initially be increasing; the theorem constructs an increasing one at minimal cardinal length. Finally, distinguishing an explicit sequence of ordinals from a sequence of arbitrary enumeration choices is essential when working in ZF.
Summary
Powers of are increasing, continuous and additively indecomposable. Successive leading-power divisions give a unique finite Cantor normal form. Cofinality measures a different feature of a limit, and its minimal cardinal is regular even when the original cardinal is singular. Choice assumptions must still be stated in additional regularity arguments.
Exercises
Quick check
(Sums of normal forms in both orders)
Compute both orders of the sum of and .
Solution · Answer
Writing the first ordinal as and the second as , , because is absorbed by . Also , because . Neither calculation adds corresponding finite tails after an absorbed term.
Quick check
(Two cofinalities equal to )
Give cofinal maps showing and . Explain why finite lengths cannot suffice.
Solution · Answer
The maps and have the required cofinal ranges by the definitions of multiplication and exponentiation at the limit . Both target ordinals are nonzero limits, so a finite range has a greatest member and misses larger predecessors. Their cofinalities are therefore exactly .
Quick check
(Termination without a uniform bound)
Why does the normal-form construction always stop, although there is no fixed finite bound on its number of terms? Give examples with arbitrarily many terms.
Solution · Answer
Nontermination would give a genuine function on with strictly descending ordinal values, impossible by the least-element property. The finite normal forms have terms for every finite . A termination proof for each input need not give one finite bound valid for all inputs.
Quick check
(Increasing cofinal sequences)
Show that is unchanged if a cofinal subset of is replaced by a cofinal increasing sequence of its minimal cardinal length. Which construction in the proof supplies the sequence?
Solution · Answer
By definition some cofinal map on exists, and no smaller cardinal has one. The recursively constructed running bound is strictly increasing, remains below , and dominates that map. Thus it has exactly the same minimal domain cardinal. The argument needs no choice of separate enumerations for the earlier ranges: a range is already the image of its given ordinal index set.
Quick check
(A singular cardinal)
Why does the singularity of not contradict the regularity theorem for cofinalities?
Solution · Answer
The theorem applied to identifies its cofinality as the regular cardinal . It does not identify with . Indeed the gap between them is exactly what “singular” means here. The specified aleph sequence makes both statements hold simultaneously.