Ordinals and transfinite induction
Use well-ordered transitive sets as order types and distinguish ordinal addition from cardinal counting.
On this page
The question for today
What you’ll understand
- Define ordinals, successor stages, and limit stages in ZF.
- Justify transfinite induction without forming a set of all counterexamples.
- Compute ordinal sums whose order types depend on the order of concatenation.
An ordinal records position in a well-order rather than just the number of objects present. Finite ordinals begin with the empty set and build each successor by adjoining the preceding ordinal. The first infinite ordinal then opens a genuinely different case: a limit with no final predecessor. Transfinite induction extends the least-counterexample method across this structure, while ordinal arithmetic shows why ordering information cannot be replaced by ordinary counting.
Ordinals encode their initial segments
An ordinal is a transitive set well-ordered by membership. Transitivity means that every member of a member is again a member. For ordinals, membership agrees with being a proper initial segment, and any two ordinals are comparable. The successor of an ordinal α is α union its singleton. A nonzero limit ordinal is neither zero nor a successor; it is the union of its smaller ordinals. The set ω of finite ordinals is the least infinite example and has no largest member.
Every well-ordered set has a unique ordinal order type, proved by assigning initial-segment types through well-founded recursion. This concerns a set-sized well-order; the collection Ord of all ordinals is a proper class. If it were a set, its union would be an ordinal at least as large as every member, and taking a successor would contradict the proposed total collection. Ordinal comparison therefore provides a coherent class ordering without providing one set whose elements exhaust that ordering.
Induction is a scheme about formulas
For a fixed formula P, transfinite induction says that if P holds at α whenever it holds at every smaller ordinal, then it holds at every ordinal. A proof need not collect all counterexamples into a set. If a counterexample α exists, examine the counterexamples among α and its predecessors, which lie in the set α+1. Separation and well-ordering give a least one, contradicting the induction premise. This bounded least-counterexample argument keeps the proof within ZF.
One often splits the induction premise into zero, successor, and nonzero limit cases. At a limit stage there is no immediately previous stage, so an argument that invokes only the predecessor does not cover it. Conversely, the limit case may use the entire set of earlier stages, not merely arbitrarily many finite examples. Induction proves that a property persists; recursion defines the objects to which the property will apply. Confusing these roles can hide an unproved existence assertion behind an otherwise sound induction on uniqueness.
Concatenation preserves order, not commutativity
Ordinal addition is the order type obtained by placing a copy of the second well-order after the first. Recursively, α+0 is α, α+(β+1) is the successor of α+β, and addition at a limit is the supremum of the earlier sums. This recursion is continuous in its right argument. Two copies with equal cardinalities can yield different order types because one concatenation has a final element and another does not. A bijection alone cannot settle an ordinal-arithmetic calculation.
For example a finite block placed before an ω-sequence disappears in the resulting order type, while a finite block placed after it remains a visible tail. Both sets are countable, but their last-element behavior differs. The same warning applies to multiplication: ordinal multiplication concatenates ordered copies and is generally noncommutative. Cardinal arithmetic will later ignore order and compare bijections instead. State which operation is intended before manipulating an expression; familiar finite identities do not all survive an infinite limit.
Work it through
Finite blocks before and after a limit
Compute 2+ω, ω+2, and (ω+1)+ω as ordinal sums, explaining the limit step.
For every finite n, 2+n is a finite ordinal. Their supremum as n runs through ω is ω, so the right-limit definition gives 2+ω=ω.
The expression ω+2 appends two points after the ω-block. It has a greatest element, namely ω+1, and is strictly larger than ω.
For each finite n, (ω+1)+n=ω+(n+1). The supremum of these ordinals is ω+ω=ω·2. Thus (ω+1)+ω=ω·2, with no greatest element.
The sums depend on concatenation order: 2+ω=ω, whereas ω+2>ω, even though all these order types are countable.
The living notebook
Explore the model
Interactive lab · modular
A cycle is not an ordinal successor chain
Pause and Reset, then set modulus m = 5 and additive step a = 1. Predict the residues selected by five Steps: 1,2,3,4,0, returning to the start. Reset and set both m = 5 and a = 2; the five residues are 2,4,1,3,0. These finite membership-free cycles show why an ordinal successor process cannot be modeled by wraparound order: ordinals never return to an earlier ordinal after taking successors.
- 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 cyclic indexing picture loses the well-founded order needed for transfinite induction.
Pause & reason
Check your understanding
Your turn
Try it yourself
Compute 2·ω and ω·2 as ordinal products. Which one has a last element, and why does cardinality not distinguish them?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Use the supremum of finite products for the right-limit argument, and view ω·2 as two successive ω-blocks.
Compare with the solution
By right-limit recursion, 2·ω is the supremum of the finite ordinals 2n and hence equals ω. The ordinal ω·2 is ω+ω, which is strictly larger than ω because it contains an initial segment of type ω followed by another nonempty block. Neither has a last element: both end in a limit block. Both are countably infinite as sets, so cardinality alone identifies their sizes but not their order types. The missing order information is exactly what makes the ordinal products different.
Keep the idea
Take it with you
- Ordinals encode well-order types and form a proper class.
- Transfinite induction uses a bounded least-counterexample argument for each formula.
- Ordinal arithmetic retains concatenation order and need not be commutative.
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.