Ordinal

An ordinal is a transitive set well-ordered by membership and represents the order type of a well-order.

A finite ordinal is the order type of a finite well-order; in the von Neumann representation it is one of $0,1,2,\dots$. They are exactly the ordinals $x$ such that $x$ and each member of $x$ are either zero or successor ordinals. If an ordinal is infinite, it either is the nonzero limit $\omega$ or contains $\omega$ as a member, so it fails this test. Thus the finite ordinals give the usual representation of the natural numbers.

A Von Neumann ordinal $x$ is finite exactly when $x$ and every member of $x$ are either zero or successor ordinals. Every finite ordinal has that property. Conversely, an infinite ordinal is either $\omega$, which is a nonzero limit, or is greater than $\omega$ and contains that nonzero limit ordinal. The test can be expressed by a bounded first-order formula: ordinality uses transitivity and membership comparability, and a nonempty ordinal is a successor exactly when it has a greatest member. This defines the class of natural numbers without quantifying over arbitrary infinite inductive sets.

For a limit ordinal $\kappa$, a subset $C\subseteq \kappa$ is club if it is unbounded and contains each limit below $\kappa$ of an increasing sequence from $C$. At an uncountable regular cardinal $\kappa$, intersections of fewer than $\kappa$ club sets are club: above a starting point cycle through the sets and take suprema, using regularity to stay below $\kappa$; closure puts the resulting limit in all of them. Club sets provide the reflecting ranks in worldly cardinals below an inaccessible cardinal.

For a regular uncountable cardinal $\lambda$ and $B:\lambda \to [\lambda {]}^{\omega }$, the limit ordinals closed under all earlier values of $B$ form a club set. Countably iterate bounds for ${\bigcup }_{\alpha <\gamma }B(\alpha )$ to obtain unboundedly many closure points. Regularity keeps each bound and the countable supremum below $\lambda$. Limits of closure points remain closure points.

For $⟨C_{\alpha }:\alpha <\delta ⟩$, its diagonal intersection consists of $\beta <\delta$ belonging to every $C_{\alpha }$ with $\alpha <\beta$. For club sets on a regular uncountable cardinal, this is a club.

A sequence $⟨C_{\delta }⟩$ in which $C_{\delta }$ is closed and unbounded in $\delta$. At a successor ordinal its predecessor is a club singleton. Such sequences define minimal walks along a club sequence.

For an infinite cardinal $\kappa$, the square principle supplies club sets $C_{\zeta }\subseteq \zeta$ at limit $\zeta <{\kappa }^{+}$, with order type at most $\kappa$, coherent at limit points: $C_{\gamma }=C_{\zeta }\cap \gamma$ whenever $\gamma$ is a limit point of $C_{\zeta }$. The bound precludes a single club set threading the entire sequence. For regular uncountable $\kappa$, coherence together with the weaker-looking size clause $\mathrm{cf}(\zeta )<\kappa \Rightarrow |C_{\zeta }|<\kappa$ implies the order-type bound. At $\kappa =\omega$, that clause alone is vacuous and cannot replace the bound.

To walk from $\beta$ to $\alpha <\beta$, start at $\beta$ and repeatedly move from $\delta$ to $\min (C_{\delta }\setminus \alpha )$ until reaching $\alpha$. The strict decrease in ordinals makes the walk finite. Its trace records the successive $C_{\delta }\cap \alpha$.

The tree of restrictions ${\rho }_{\beta }\upharpoonright \alpha$, ordered by extension. For a club sequence on ${\omega }_2$ with club order types at most ${\omega }_1$, the Continuum hypothesis bounds each level by ${\aleph }_1$. Trace injectivity and Fodor lemma exclude a cofinal branch.

If ${\rho }_{\beta }(\alpha )={\rho }_{\gamma }(\alpha )$, then the trace functions agree below $\alpha$. Each shorter trace is reconstructed by locating the first recorded club initial segment that meets $[\xi ,\alpha )$ and continuing the walk from its least such point.

The walks to $\xi <\alpha$ share a unique maximal initial chain of nodes. At the next step the walk to $\xi$ moves into $[\xi ,\alpha )$; the walk to $\alpha$ stays at or above $\alpha$ or has just ended.

A subset of a regular uncountable cardinal number $\kappa$ is stationary if it meets every club set in $\kappa$. Intersecting a stationary set with a club set preserves stationarity. Every member of the club filter is stationary. At a regular infinite $\theta <\kappa$, the stationarity of ordinals of prescribed cofinality supplies important examples.

Every stationary subset of a successor cardinal ${\lambda }^{+}$ can be partitioned into ${\lambda }^{+}$ disjoint stationary subsets. For each $\beta \in [\lambda ,{\lambda }^{+})$ choose a bijection $e_{\beta }:\lambda \to \beta$. For each $\xi <{\lambda }^{+}$, the function $\beta \mapsto e_{\beta }^{-1}(\xi )$ is regressive on the stationary tail with $\beta >\xi$. The Fodor lemma gives a stationary fiber with one value $i_{\xi }<\lambda$. Some value occurs for ${\lambda }^{+}$ many indices, whose fibers are pairwise disjoint. Assign any leftover part of $S$ to one fiber.

A subset $X\subseteq \lambda$ is non-reflecting in the indicated sense if it is not stationary below any $\delta <\lambda$ of uncountable cofinality. The subset itself need not be stationary. Nonreflection is inherited by subsets. With this definition every subset of ${\omega }_1$ is non-reflecting, since all smaller ordinals have countable cofinality.

For a coherent club set sequence, the limit points of $C_{\delta }$ form a club set whenever $\mathrm{cf}(\delta )>\omega$. Along these points, $\mathrm{otp}(C_{\gamma })=\mathrm{otp}(C_{\delta }\cap \gamma )$ strictly increases, so a fixed fiber $E_{\xi }$ meets this a club set at most once and cannot reflect at $\delta$. Under the square principle order-type bound, the fibers with $\xi \le \kappa$ partition all limit ordinals below ${\kappa }^{+}$ into $\kappa$ non-reflecting pieces.

For any nonzero limit ordinal $\delta$, a club set is an unbounded subset closed under limit points below $\delta$. A subset is stationary if it meets every such club set. Statements concerning the completeness of the club filter or Fodor lemma require regular uncountable height; they should not be transferred to arbitrary singular or countable limit ordinals without checking their hypotheses.

For an uncountable regular cardinal $\kappa$, choose cofinal sequences $c_{\alpha }:\omega \to \alpha$ for the stationary set of ordinals of cofinality $\omega$. Above any bound, some fixed coordinate exceeds the bound on a stationary subset; Fodor lemma makes that coordinate constant on a stationary subset. Thus the stationary constant fibers, over all coordinates, have unboundedly many values. Regularity makes one coordinate have $\kappa$ such values. Its fibers are disjoint stationary sets; adding all leftover ordinals to one piece partitions $\kappa$.

A family $(A_{\alpha ,n}{)}_{\alpha <{\omega }_1,n<\omega }$ whose row at $\alpha$ partitions $(\alpha ,{\omega }_1)$ and whose fixed-column cells are pairwise disjoint. Choose injections $e_{\beta }:\beta \to \omega$ and put $A_{\alpha ,n}=\{\beta >\alpha :e_{\beta }(\alpha )=n\}$. This gives a matrix used to split stationary sets into many stationary pieces.

There are ${\aleph }_1$ pairwise disjoint stationary subsets of the nonzero countable limit ordinals. In a Ulam matrix on omega-one, each row partitions a stationary tail into countably many cells, so some cell is stationary. One column contains stationary cells in uncountably many rows, and the column cells are disjoint. Unions indexed by different subsets of ${\omega }_1$ then differ on a stationary set.

A sequence $D_{\alpha }\subseteq \alpha$ guesses every $X\subseteq {\omega }_1$ stationarily often: $\{\alpha :D_{\alpha }=X\cap \alpha \}$ is stationary.

For each index, collect the ground subsets which some condition forces to be the corresponding diamond guess. Distinct forced values have incompatible witnessing conditions, so the countable chain condition for forcing makes this a countable family. Every ground subset is guessed by these families on a ground stationary set, by testing each ground club set. The countable-family diamond equivalence then yields diamond in the ground model. A generic guess need not itself be a ground subset; only values forced equal to one are collected.

For a stationary $S\subseteq {\omega }_1$, a sequence $D_{\alpha }\subseteq \alpha$ indexed by $S$ guesses every $X\subseteq {\omega }_1$ on a stationary subset of $S$.

A sequence $D_{\alpha }\subseteq \alpha$, indexed by a stationary subset $S$ of a regular uncountable cardinal $\lambda$, guesses every $X\subseteq \lambda$ stationarily often: $\{\alpha \in S:D_{\alpha }=X\cap \alpha \}$ is stationary. This extends the usual stationary diamond principle at ${\omega }_1$.

At each $\alpha \in S$, a countable family $E_{\alpha }\subseteq \mathcal{P}(\alpha )$ is supplied. Every $X\subseteq \lambda$ has $X\cap \alpha \in E_{\alpha }$ on a stationary subset of $S$. The countable-family diamond equivalence shows that this apparently weaker prediction is equivalent to a single diamond guess at each index.

Enumerate each countable guessing family and use a bijection $\pi :\lambda \times \omega \to \lambda$ with a club set of prefix-closure points. The $n$th candidate sequence decodes the $n$th component of the $n$th family entry. If all candidates fail, choose counterexample sets $X_n$ and club sets witnessing failure, then code the $X_n$ together using $\pi$. A correct family guess on the common closure club set and all failure club sets decodes to one of the forbidden correct guesses. The singleton-family implication supplies the reverse direction.

At a correctly guessing limit stage of a normal tree construction, make every new level node extend a member of the guessed maximal tree antichain. It follows that the antichain has no later member. This produces a Suslin tree from the stationary diamond principle.

There are cofinal sequences $A_{\delta }\subseteq \delta$ of order type $\omega$ for the countable limit ordinals, such that every uncountable $X\subseteq {\omega }_1$ contains some $A_{\delta }$.

For a stationary $S\subseteq {\omega }_1$, there are cofinal ladders $A_{\delta }\subset \delta$ of order type $\omega$, indexed by limit ordinals in $S$, such that every uncountable $X\subseteq {\omega }_1$ contains one of these ladders. This predicts a contained ladder, whereas stationary diamond principle predicts a whole initial segment.

A function on a set of ordinals with $f(\alpha )<\alpha$ at every nonzero point of its domain. On a stationary subset of a regular uncountable cardinal, Fodor lemma makes it constant on a stationary subset.

A regressive function on a stationary subset of a regular uncountable cardinal is constant on a stationary subset.

If $S\subseteq \kappa$ is stationary and $f(\alpha )\in A_{\alpha }$ for a kappa-filtration, then $f$ is constant on a stationary subset. Restrict to limit indices and use continuity to find a smaller stage containing each value. Fodor lemma fixes that stage on a stationary subset. Its size is less than $\kappa$, so club filter completeness makes one value fiber stationary.

For a regular infinite $\theta <\kappa$, with $\kappa$ a regular uncountable cardinal number, $S_{\theta }^{\kappa }=\{\delta <\kappa :\mathrm{cf}(\delta )=\theta \}$ is stationary. Build a strictly increasing continuous $\theta$-sequence in any club set, and take its supremum. Closure places it in that club and the cofinality of an increasing ordinal supremum gives cofinality $\theta$. In particular the two disjoint sets $S_{\omega }^{{\omega }_2}$ and $S_{{\omega }_1}^{{\omega }_2}$ show that the club filter on ${\omega }_2$ is not an ultrafilter.

On a regular uncountable cardinal number $\kappa$, the club filter consists of all subsets containing a club set. It is a kappa-complete filter by club filter completeness. Its members are stationary sets, although a stationary set need not be a filter member, and a filter member need not itself be closed.

For any regular uncountable cardinal number $\kappa$, the set $\kappa \setminus \{\omega \}$ contains the final-segment club set $[\omega +1,\kappa )$, so belongs to the club filter and is a stationary set. It is not closed, since its finite ordinals have supremum $\omega$, which is missing.

The club filter on a regular uncountable cardinal number $\kappa$ is $\kappa$-complete. Intersections of fewer than $\kappa$ club sets are closed. For unboundedness, repeatedly step past a point of each club and take a countable supremum; regularity keeps all suprema below $\kappa$, and closure puts the final supremum in every club.

An unbounded class in set theory of ordinals is closed if every nonempty set-sized increasing sequence of its members has its supremum in the class. This is the proper-class analogue of a club set. The reflection theorem for definable hierarchies gives such a class for every finite collection of first-order formulas.

The successor of an ordinal $\alpha$ is $\alpha +1=\alpha \cup \{\alpha \}$.

A countable ordinal has a countable set as its underlying set.

These are the ordinals strictly below the first uncountable ordinal.

The order type of a well-order is the unique ordinal isomorphic to it.

Every well-founded extensional relation is uniquely isomorphic to membership on a transitive set.

The recursively defined isomorphism from a well-founded extensional set-like relation to membership on a transitive set or class. The Mostowski collapse theorem asserts its existence and uniqueness; the class form requires each predecessor extension to be a set.

If $X$ has a well-founded extensional inherited membership relation and $T\subseteq X$ is a transitive set, its Mostowski collapse theorem map $\pi$ fixes every member of $T$. The recursion $\pi (x)=\{\pi (y):y\in x\cap X\}$ and well-founded relation induction give this pointwise. If also $T\in X$, then $\pi (T)=T$.

A nonzero ordinal is a limit ordinal when it is not a successor ordinal. Equivalently, it is the supremum of all smaller ordinals.

A function $f:\lambda \to \lambda$ on an ordinal is normal when it is strictly increasing and continuous at limit ordinals: $f(\delta )={\sup }_{\alpha <\delta }f(\alpha )$ for every limit $\delta <\lambda$.

Ordinal addition, multiplication and exponentiation are continuous in their right argument by recursion. For fixed $\beta$, $\beta +\alpha$ is normal for every $\beta$, $\beta \alpha$ for $\beta >0$, and ${\beta }^{\alpha }$ for $\beta \ge 2$. Reversing the roles changes the conclusion: $\alpha +\beta$ is not normal for $\beta >0$, while $\alpha \beta$ and ${\alpha }^{\beta }$ are normal only for fixed $\beta =1$. Large principal-ordinal limits expose the failures of continuity; constant zero or one cases fail strict increase.

For a strictly increasing ordinal class function continuous at limits, start with ${\alpha }_0=0$ and iterate ${\alpha }_{n+1}=f({\alpha }_n)$. If the sequence stabilizes, its stable value is a fixed point. Otherwise its supremum $\alpha$ is a limit and continuity gives $f(\alpha )={\sup }_{n}f({\alpha }_n)={\sup }_n{\alpha }_{n+1}=\alpha$. Starting the iteration above any prescribed ordinal gives arbitrarily large fixed points.

If a normal function on an ordinal begins at a countable value and preserves countability from $\Phi (\xi )$ to $\Phi (\xi +1)$, transfinite induction shows it maps all countable ordinals to countable ordinals. At countable limits this uses countable unions of countable sets, hence axiom of countable choice in the usual proof. Iteration from zero either stabilizes at a countable fixed point or has a countable limit fixed by continuity. Applying this to ${\omega }^{\alpha }$ gives the countable epsilon number ${ϵ}_0$.

Transfinite recursion defines a value at each ordinal from the function of all earlier values.

Given an initial value $a$ and a rule $G$, there is a unique function $F$ on $\omega$ satisfying $F(0)=a$ and $F(n+1)=G(F(n))$.

If a property of an ordinal follows whenever it holds for every smaller ordinal, then it holds for every ordinal.

Ordinal addition is ordered concatenation and is associative but generally not commutative.

For all ordinals $\alpha ,\beta ,\gamma$,This follows by transfinite induction on $\gamma$ from the recursive definition of ordinal addition.

Nonzero ordinals commute under addition precisely when they are positive finite right multiples of a common ordinal. This follows by comparing their Cantor normal forms at the first exponent where they differ.

Ordinal multiplication is defined recursively byfor nonzero limit ordinal $\lambda$. It is associative and left-distributive over ordinal addition, but generally neither commutative nor right-distributive.

For ordinals $\alpha$ and $\delta >0$, there are unique ordinals $q,r$ with the displayed relation. The function $q\mapsto \delta q$ is strictly increasing, continuous at limit ordinals and unbounded. Its first value above $\alpha$ occurs at a successor, giving the largest $q$ with $\delta q\le \alpha$. The ordered tail of $\alpha$ after that initial segment gives $r$, and maximality gives $r<\delta$.

Two ordinals commute under ordinal multiplication if and only if their squares commute. One implication follows from associativity. For the converse, squaring is strictly increasing: $A<B$ implies $A^2\le BA<B^2$. If $\alpha \beta <\beta \alpha$, monotonicity givesa contradiction to commuting squares. Swap the factors to exclude the reverse inequality; zero factors cause no exception.

Ordinal multiplication is distributive in its right argument:Indeed a sequence of copies of $\alpha$ indexed by the concatenation of $\beta$ and $\gamma$ is the concatenation of the two sequences of copies. The other distributive law fails: $(1+1)\omega =\omega$, while $\omega +\omega >\omega$.

Ordinal exponentiation is defined recursively byfor nonzero limit $\lambda$. Transfinite induction gives

The ordinal ${\epsilon }_0$ is the least fixed point of $\alpha \mapsto {\omega }^{\alpha }$. It is the supremum of $1,\omega ,{\omega }^{\omega },{\omega }^{{\omega }^{\omega }},\dots$, and is countable.

For a well-ordered set $X$, let $X^{\prime }$ contain the points whose strict initial segments are nonempty and have no greatest element, and iterate this operation transfinitely, taking intersections at limit stages. Every nonempty derivative loses at least its least element. If no derivative became empty, choosing one point from each successive difference would inject the ordinal supplied by Hartogs theorem for $X$ into $X$, a contradiction.

For an ordinal $\xi$,Thus the derivative index of $\omega$ is one and that of ${\omega }^2$ is two.

For $\alpha <\beta$, the ordinal interval $\beta \setminus \alpha$ is the ordered tail from $\alpha$ inclusive to $\beta$ exclusive.

The first uncountable ordinal ${\omega }_1$ is the set of all countable ordinals.

The first uncountable ordinal has cofinality ${\omega }_1$. Indeed, the supremum of any countable set of countable ordinals is still a countable ordinal, so no countable sequence is cofinal in ${\omega }_1$.

Deleting any countable initial segment from ${\omega }_1$ leaves a well-order of type ${\omega }_1$.

The second uncountable ordinal ${\omega }_2$ is the least ordinal whose cardinal number is strictly larger than that of the first uncountable ordinal ${\omega }_1$. Equivalently, it is the initial ordinal of the successor cardinal ${\aleph }_2$.

Every nonzero ordinal has a unique finite expression ${\omega }^{{\delta }_1}{n}_1+\cdots +{\omega }^{{\delta }_r}{n}_r$ with decreasing exponents and positive finite coefficients.

For every ordinal base $\rho >1$, a nonzero ordinal has a unique finite ordinal addition expansion with strictly decreasing exponents ${\beta }_i$ and coefficients $0<{\xi }_i<\rho$. Choose the largest power at most the remaining ordinal and apply the ordinal division algorithm. The next remainder has smaller leading exponent, so well-foundedness forces termination. Each lower tail is smaller than its preceding power; uniqueness of division consequently fixes the exponent, coefficient and tail successively. For $\rho =\omega$ this is Cantor normal form.

Two ordinals are commensurable when neither is absorbed by adding the other on its left. For positive ordinals, this is equivalent to equality of their leading Cantor normal form exponent. If leading exponents differ, the lower-leading ordinal is absorbed by the higher power of $\omega$. If they agree, either sum adds the two positive leading coefficients and therefore exceeds both original ordinals. Zero is commensurable with no ordinal.

Finite canonical terms built from zero, ordinal sums and powers of omega describe exactly the ordinals below epsilon zero. Syntactic validity and comparison are decidable by recursion through the exponent subterms. Enumerating valid term codes transfers their order to a computable well-order on all natural numbers.

Use the unary Cantor normal form tree norm, counting one root and recursively counting all repeated exponent subterms. There are only finitely many notations of bounded norm. This finite principle bounds all descending sequences whose norms grow at most linearly with the position. Friedman's finite form of Kruskal's theorem implies it through the natural-sum ordinal rank of a finite rooted tree. The Friedman–Smith miniaturization theorem turns this controlled termination principle for standard epsilon-zero notations into the formal consistency statement for Peano arithmetic; the technical ordinal-analysis result is needed in addition to the tree coding. Section 2.2 of formal.hknu.ac.kr/Publi/kruskalJKMS.pdf records the general miniaturization and soundness theorem.

The leading term ${\omega }^{\delta }n$ is the highest-exponent term in Cantor normal form; the remaining tail is strictly below ${\omega }^{\delta }$.

Every nonzero ordinal $\alpha$ has a greatest exponent $\beta$ such that ${\omega }^{\beta }\le \alpha$. It is the leading exponent in the Cantor normal form of $\alpha$, andfor a positive finite integer $n$ and $\gamma <{\omega }^{\beta }$.

Let nonzero ordinals $\xi ,\eta$ have leading exponents $\rho ,\sigma$. If $\eta$ is finite, then $\xi \eta$ has leading exponent $\rho$. If $\eta$ is infinite, so that $\sigma >0$, then $\xi \eta$ has leading exponent $\rho +\sigma$. This follows by multiplying the leading terms in Cantor normal form and using continuity of ordinal multiplication at limit ordinals.

The additively indecomposable ordinals are exactly the powers ${\omega }^{\delta }$.

A nonzero ordinal $\delta$ is additively closed when $\beta +\gamma <\delta$ for all $\beta ,\gamma <\delta$. These are exactly the ordinals ${\omega }^{\alpha }$: sufficiency follows from Cantor normal form, while necessity follows by splitting any leading coefficient or nonzero tail below $\delta$ into two smaller summands.

For every ordinal $\gamma$ and $\lambda ={\omega }^{\alpha }$, there are unique ordinals $\beta ,\delta$ such thatChoose the greatest initial multiple $\lambda \beta \le \gamma$; if its remainder were at least $\lambda$, the next multiple would still fit. Uniqueness follows because every remainder below $\lambda$ lies before $\lambda (\beta +1)$.

An ordinal $\delta >2$ is multiplicatively closed when $\beta \gamma <\delta$ for all $\beta ,\gamma <\delta$. These are exactly

For nonzero $\lambda$, the ordinal ${\omega }^{\lambda }$ is multiplicatively closed exactly when $\lambda$ is additively closed. One direction follows fromFor the other, the leading exponent of an ordinal product shows that products of ordinals below ${\omega }^{\lambda }$ still have leading exponent below $\lambda$.

Ordinal arithmetic defines addition, multiplication and exponentiation of ordinals through order types or transfinite recursion. The usual operations need not be commutative. Natural sum and natural product instead combine Cantor normal forms and are commutative; the Hessenberg natural sum is the natural addition operation.

For a countable limit ordinal, a fundamental sequence is an increasing cofinal sequence of smaller ordinals. Effective choices allow a fast-growing hierarchy to turn limit recursion into recursion at a finite input. Below epsilon zero, write the final term as $\gamma +{\omega }^{\beta }$. For successor $\beta =\delta +1$, take $\gamma +{\omega }^{\delta }(n+1)$; for nonzero limit $\beta$, take $\gamma +{\omega }^{\beta [n]}$. Earlier terms in the Cantor normal form remain fixed.

A fast-growing hierarchy indexes number-theoretic functions by an effective system of ordinal notations. Successor stages iterate the preceding function, while limit stages diagonalize along a chosen fundamental sequence of a limit ordinal. These choices are part of the definition. With the standard Cantor normal form sequences below epsilon zero, each fixed $F_{\alpha }$ for $\alpha <{\epsilon }_0$ is provably total in Peano arithmetic, but the uniform endpoint $F_{{\epsilon }_0}$ is not. Every function provably total in Peano arithmetic is eventually bounded by some lower level. These classification results are proved in epub.ub.uni-muenchen.de/3843/1/3843.pdf .

For the standard fundamental sequences of limit ordinals below epsilon zero, the index order corresponds to eventual, rather than necessarily pointwise, growth. For example, under $\omega [n]=n+1$ and successor iteration $n+1$ times, $F_{\omega }(1)=F_2(1)=7$ whereas $F_3(1)=2047$. Limit stages are diagonal choices, so a larger index can give a smaller value at small arguments.

The Hessenberg natural sum aligns equal exponents in two Cantor normal forms and adds their finite coefficients; unlike ordinal addition it is commutative.

It is the commutative natural addition operation in ordinal arithmetic.

If a well-order is the union of suborders of types $\xi$ and $\eta$, its type is at most $\xi \#\eta$.

If an ordinal is partitioned into two copies of type $\beta$, its type is below $\beta +\beta +\beta$; two copies do not always give a strict bound.