Motivation
Natural-number induction works because a nonempty set of counterexamples has a least member. The same argument applies to any well-ordered domain, including domains with stages after all finite stages. Ordinals provide canonical names for such positions. Their usefulness comes from the fact that an ordinal contains precisely its earlier positions: membership itself records the order.
An infinite process need not finish by adding one final step. At a limit stage, there is no immediate predecessor. A construction must specify what happens there, usually by collecting the preceding stages. This is where the difference between induction, which proves statements, and recursion, which defines objects, becomes essential.
Definitions
Definition 3.1.1
(Well-order, initial segment and transitive set)
A strict well-order on a set is an irreflexive, transitive linear order in which every nonempty subset of has a least element. A subset is an initial segment if and imply . A set is transitive if implies , equivalently every member of is a subset of .
Definition 3.1.2
(Ordinals, successors and limits)
An ordinal is a transitive set well-ordered by . Write for . The first ordinals are , , and . The successor of is . A nonzero ordinal that is not a successor is a limit ordinal.
Concept lensStructural
Ordinals as transitive sets of transitive sets
With the foundation axiom, an ordinal is exactly a transitive set all of whose members are transitive. In such a set, gives because is transitive, and foundation gives irreflexivity and least elements. For linearity, take an -minimal having an incomparable partner, then a minimal such partner ; comparing members of each with the other gives and , so after all. Without foundation, a set with would satisfy the condition without being an ordinal.
The least inductive set exists: inside one inductive set supplied by infinity, separate the elements belonging to every inductive subset of that set. It is itself inductive and contained in every inductive set, by intersecting that set with the chosen bound. Its elements are exactly the finite von Neumann ordinals. Every finite ordinal has a successor still below , so is a limit ordinal.
Definition 3.1.3
(Supremum of a set of ordinals)
The supremum of a set of ordinals is . This is an ordinal, contains each member of as a subset, and is contained in every ordinal upper bound. Supremum need not be a member of or strictly greater than all its members.
Theorem/proposition
Theorem 3.1.4
(Comparison of ordinals)
For ordinals , exactly one of , , holds. Moreover if and only if . Every member of an ordinal is an ordinal. Every well-ordered set is order-isomorphic to exactly one ordinal.
Theorem 3.1.5
(Transfinite induction)
Let be an ordinal. If a property satisfies
then holds for every . The same principle holds for all ordinals when is a formula and the hypothesis is established for every ordinal.
Theorem 3.1.6
(Set-length transfinite recursion)
Suppose a definable rule assigns a unique set to every set function whose domain is an ordinal. For each ordinal there is exactly one function with domain satisfying
No choice principle is needed: the rule specifies a unique next value. Replacement is used to collect the earlier stages.
Proof sketch or proof idea
Proof
(Initial segments force comparability)
If is an ordinal and , then by transitivity. If , all three positions lie in , whose membership order is transitive, so . Thus is transitive; the well-order restricts to it, so is an ordinal. A proper initial segment of an ordinal is exactly the set of predecessors of its least omitted element , hence .
Now is an initial segment of both ordinals. If it were proper in both, it would equal a member of each; writing that common set as would give , impossible for a strict well-order. Therefore one ordinal is an initial segment of the other. The preceding initial-segment observation proves comparison and the inclusion criterion. Equality and either strict alternative cannot coexist, since a strict well-order has no cycles. A union of ordinals is transitive, and comparison linearly orders its members; any nonempty subset has a least member by first intersecting it with one chosen ordinal member or taking that member if nothing precedes it. This also verifies the supremum assertion.
Proof X-ray
Why one intersection settles comparison
The whole comparison rests on the single set . It is an initial segment of each ordinal, and a proper initial segment of an ordinal is one of its members. If it were proper in both, the set would belong to and to , hence to , contradicting irreflexivity. So it equals one of the two ordinals, which is then an initial segment of the other. No isomorphism between the two orders is ever constructed.
Proof
(Least counterexamples)
For induction on , separation would produce a set of counterexamples if any existed; its least element contradicts the inductive implication. For class-wide induction, one counterexample would yield a least counterexample in , giving the same contradiction. No set of all counterexamples is required.
Proof
(Compatible approximations and replacement)
For recursion, call a function on an approximation when it satisfies the displayed rule below . Two approximations agree on their common domain: a least disagreement would have identical preceding restrictions, so the rule gives identical values there. Induct on to construct an approximation. At zero take the empty function. At a successor extend the unique earlier approximation by its uniquely specified next value. At a limit, replacement collects the unique approximations of smaller lengths, and their union is a function on the limit because they agree. Its restrictions already satisfy the rule. This proves existence and uniqueness, including the crucial set-existence step at limits.
Proof X-ray
Two jobs at a limit stage
The recursion proof has a logical job and a set-existence job. First, uniqueness shows that two partial constructions agree wherever both are defined. This is what makes their union single-valued. Second, replacement collects one uniquely determined approximation for each earlier length. This is what makes the family being united a set. Neither job can substitute for the other.
At a successor there is only one new graph pair to add, but a limit requires every earlier stage at once. If a proposed recursive construction is ambiguous at one stage, compatibility is no longer automatic. If its earlier stages are indexed by all ordinals rather than a fixed ordinal bound, replacement no longer supplies one set of all stages. The theorem avoids both problems by assuming a unique value rule and proving existence separately at each set-sized bound. The resulting definable class-wide notation is useful, but it does not describe a single set function with every ordinal as its domain. When checking a recursion, verify compatibility first, then collection, and only then take the union; this also explains why the limit step needs an argument beyond ordinary successor induction.
Proof
(Classifying well-orders by ordinals)
Finally let be any well-order. Define, by well-founded recursion along this well-order, . The same approximation argument applies, with predecessor initial segments in place of ordinals; replacement collects the displayed values. Induction along shows the values are ordinals and exactly when . The range is therefore a transitive set of ordinals, hence an ordinal, and is the required isomorphism. An isomorphism between ordinals fixes each element by induction, proving uniqueness.
Worked examples
Worked example 3.1.7
(A limit is not a largest finite ordinal)
The sequence has supremum , but no largest term. The ordinal has a last element, namely ; does not. Thus they are not order-isomorphic, although their underlying sets have the same cardinality. An explicit bijection sends the last point to and each finite to .
Worked example 3.1.8
(Ordinal addition remembers order)
Define addition by recursion in its second argument:
for nonzero limits . The order interpretation is a copy of followed by a copy of . Hence , whereas . The first order has no last point, and the second does. Ordinal addition is not commutative; a statement about cardinal addition cannot replace this calculation.
Worked example 3.1.9
(Multiplication also depends on order)
Define , , and use suprema at nonzero limits. Then , but . The latter order has two successive infinite blocks. At their boundary the first block has no last point, but the second block has a first point. Multiplication here places copies of in sequence.
Worked example 3.1.10
(There cannot be a set of all ordinals)
If such a set existed, would be an ordinal. Then would also belong to , forcing , contrary to comparison. One may quantify over all ordinals, but cannot use that entire domain as a replacement input set.
Counterexample mode
Base and successor steps are not enough
Claim: a property that holds at zero and passes from each ordinal to its successor holds for every ordinal. Consider the property “the ordinal is finite”. It holds at zero. Whenever it holds at , it also holds at . Yet it fails at . Thus a base case and a successor implication do not constitute transfinite induction. The full inductive implication must include the limit situation: assuming the property at every predecessor of a limit must force it at that limit. In this example, that implication is false at , exactly as it should be.
Worked example 3.1.11
(Successor and limit steps for the hierarchy)
An actual limit argument often replaces a last step by a union. For the hierarchy , one proves simultaneously that each is transitive and that for . At a successor, transitivity of a set implies , because each member of is a subset of . It also implies that is transitive: if , then , hence , so . At a limit, the union of an increasing family of transitive sets is transitive. Indeed, places in one , and its transitivity puts there too. These checks establish the successor and limit mechanisms, not just an intuitive picture of growing stages.
Worked example 3.1.12
(No first infinite descent)
Suppose were a function from into the ordinals, strictly decreasing at every step. Replacement collects its range as a set of ordinals. This nonempty range has a least element, say , but is a smaller range member, a contradiction. The argument handles a given descending sequence. If an informal discussion says one can repeatedly find a predecessor, converting those existential choices into a sequence is an extra step unless a unique or canonical predecessor rule has been specified.
This also clarifies the direction of the order in recursion. Transfinite recursion may use all values at smaller indices because those indices form a well-founded predecessor set. An equation depending on a future value is a different problem and need not have either a solution or uniqueness. For instance, an equation merely requiring a binary-valued sequence to be constant has two solutions; it is not the uniquely determined next-value rule in the theorem. In both proofs and definitions, state the direction of dependence and the domain first.
Arithmetic as concatenation
The recursive clauses for addition and multiplication are convenient for computing, but the laws one wants to use, such as associativity, cancellation and distributivity, are hard to extract from them directly. They become visible in a picture: is a copy of followed by a copy of , and is copies of laid end to end. This section turns the picture into a theorem and reads the laws off it. The next unit, 3.2 Ordinal exponentiation, Cantor normal form and cofinality, uses these laws freely.
Definition 3.1.13
(Ordered sums and ordered products)
Let and be well-orders. The ordered sum is the set , ordered so that every point tagged precedes every point tagged , while two points with the same tag are compared in or in . The ordered product is the set with when either , or and : the -coordinate is compared first. For a well-order , write for the unique ordinal isomorphic to .
Both orders are linear, and both are well-orders. A nonempty subset of has as least element its least tagged- point if it has one, and otherwise its least tagged- point. For a nonempty subset of , take the least second coordinate that occurs, and then the least such that belongs to the subset. Applying isomorphisms coordinatewise shows that isomorphic summands or factors give isomorphic sums and products. Hence and depend only on and .
Theorem 3.1.14
(Recursive arithmetic computes order types)
For all ordinals ,
Proof
(Both sides obey the same recursion)
Two facts about order types do the work.
(i) If a well-order has a last element , then . An isomorphism of onto an ordinal extends, by , to an isomorphism of onto .
(ii) If a well-order is the union of a set of initial segments, then . Let be the isomorphism. It carries each onto an initial segment of the ordinal . That segment is either the whole ordinal or one of its members, so it is an ordinal, and it equals by uniqueness of order types. The union of these images is , and a union of ordinals is their supremum.
Fix and put . For we have , and is an initial segment of . The order is a copy of , so . The order has last element , and deleting it leaves , so by (i). Let be a nonzero limit. Every point of lies in some with : a point lies in and , and the tagged- points lie in . So (ii) gives . These are the three clauses that define , and induction on gives .
For products put . Since , . The order is followed by the block , which is a copy of . It is therefore isomorphic to , and the sum case gives . At a nonzero limit , each point lies in the initial segment with , so (ii) gives . Induction on again finishes the proof.
Theorem 3.1.15
(Laws of ordinal arithmetic)
For all ordinals :
- and .
- If , then . Hence implies .
- If , then .
- .
- If , there is exactly one ordinal with .
- If and , then . If , then .
- and .
Proof
(Each law is an isomorphism of concatenations)
Two observations about well-orders are used throughout. First, a proper initial segment of a well-order has strictly smaller type: the isomorphism carries onto a proper initial segment of an ordinal, which is a member of that ordinal. Second, if there is a strictly increasing map , then . Composing with the isomorphisms gives a strictly increasing map between ordinals, and the exercise on increasing maps below shows for every , so .
(1) The orders and are copies of , and so are and .
(2) If , then is an initial segment of that omits , so it is proper and has smaller type. If , comparison gives or , and either way the two sums differ.
(3) Since , the inclusion of into is strictly increasing.
(4) Both and consist of a copy of , then a copy of , then a copy of . Explicitly, , and define an isomorphism. Since the type of a sum depends only on the types of the summands, the first order has type and the second has type .
(5) Let with the order of , and let . Every member of lies below every member of , and , so and define an isomorphism . Hence . Uniqueness is the cancellation in (2).
(6) If and , then is an initial segment of that omits . For the second claim, the inclusion of into is strictly increasing.
(7) The assignments and define an isomorphism . In both orders the tag is compared first, then the - or -coordinate, then the -coordinate. Likewise is an isomorphism , because both orders compare first, then , then .
Counterexample mode
The two-sided laws fail
Claim: ordinal arithmetic satisfies the remaining laws of natural-number arithmetic. Each of the following fails.
- Commutativity: , and .
- Cancellation on the right, and strict increase in the left argument: , yet . Similarly .
- Distributivity on the right: , whereas .
In each case material added on the left is absorbed by an infinite block with no last point. In a new first point is followed by a copy of , and the whole order is again of type . The laws that survive are exactly the one-sided ones: (2), (3), (6) and (7).
Worked example 3.1.16
(Computing with the laws)
By law (1) and the recursion, . Hence associativity and give
Next, for every finite . The case is law (1), and
At the limit, . Since , this supremum equals . Distributivity on the right would have predicted , which is strictly larger by law (2). Each block's extra last point is swallowed by the next block.
Common mistakes
Common mistake
(A transitive set alone need not be an ordinal)
A transitive set alone need not be an ordinal: is transitive but its members and are incomparable by membership.
Also, allows equality, whereas does not. Limit proofs must handle all earlier stages; proving only the successor step leaves a genuine gap.
Common mistake
(Ordinal equality is not a bijection)
Do not replace ordinal equality by a bijection. Ordinals classify well-orders up to order-isomorphism; cardinals classify sets up to bijection.
Common mistake
(“Continue indefinitely” is not a recursion)
Recursion is not justified by the phrase “continue indefinitely”: at each limit one must demonstrate that the earlier data form a set and fit together.
Summary
Ordinals encode well-ordered positions by their predecessors. Least-counterexample arguments prove transfinite induction, and compatible approximations plus replacement prove transfinite recursion. Ordered sums and products identify the recursive operations with concatenations of well-orders, and the one-sided laws, subtraction and division are read off from that picture. Limits and noncommutative arithmetic show why infinite order cannot be reduced to finite intuition.
Exercises
Quick check
(Successor suprema)
Prove that the union of a nonempty set of ordinals is a successor ordinal only if that set has a largest member. Is the converse true?
Solution · Answer
If , then , so for some . Thus , giving equality and a largest member. The converse as stated is false: has a largest member but its union is the limit . The union equals the largest member, whose type may be zero, successor or limit.
Quick check
(Absorption by )
Prove for every finite , and compute using the recursion definition.
Solution · Answer
By finite induction is finite for finite , and these values are unbounded in . Their supremum is . Also for finite , by successor recursion. Their supremum is , which by definition is . Thus .
Quick check
(The first hierarchy stages)
Give a transfinite recursion defining the hierarchy , and calculate .
Solution · Answer
Set , and at nonzero limits. Each prescribed value is a unique set, so set-length recursion applies at every ordinal bound. The first values are , , , and the power set of this last two-element set. Explicitly .
Quick check
(Increasing maps dominate the identity)
Prove that every strictly increasing function between ordinals satisfies for .
Solution
Assume inductively for all . Strict increase gives , so every belongs to . Hence and comparison gives . Transfinite induction completes the argument. In particular no ordinal embeds increasingly into a smaller ordinal.
Quick check
(Which ordinals absorb a point on the left?)
Find all ordinals with .
Solution · Answer
They are exactly the ordinals . On finite ordinals the recursion for addition is the natural-number recursion, which is commutative by Constructing the natural, integer and rational numbers; so for finite , . If , law (5) writes for some , and associativity gives .
Quick check
(Division with remainder)
Let . Prove that every ordinal can be written in exactly one way as with .
Solution
Existence. By laws (6) and (1), , so there is a least ordinal with . It is not , since . It is not a limit: otherwise , because each by minimality. So with . Law (5) gives with , and law (2) turns into .
Uniqueness. Suppose with . If , then , a contradiction; the symmetric case is the same. So , and cancellation (2) gives . For example, divided by has quotient and remainder , while has quotient and remainder on division by .