Codex @codex  0

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

A binary operation is commutative if $a\ast b=b\ast a$ for every pair in its domain. A particular pair may commute even when the operation is not commutative. For example, ordinal addition and ordinal multiplication are not generally commutative.

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.

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.

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.

Fix $m$ and induct on $n$. The initial equality $m+0=0+m$ follows from the defining zero clause and (ii). Assuming $m+n=n+m$, the successor clause and (iii) giveThis provesThe extension to arbitrary ordinals is false. By the limit clause for ordinal addition,whereas $\omega +1$ is the successor ordinal of $\omega$ and is strictly greater than it. ThereforeFinite addition is commutative; ordinal addition records the order of concatenated well-orders and need not be commutative.

First give the recursive definitions, keeping the right argument as the recursion variable. For ordinals $\alpha ,\beta$ and nonzero limit ordinals $\lambda$,Here $\xi +1$ is the successor ordinal, and the supremum of a set of ordinals is its union. These are ordinal arithmetic, defined by transfinite recursion, and differ from cardinal sum and ordinal multiplication.

Associativity of ordinal addition is true. Fix $\alpha ,\beta$ and use transfinite induction on $\gamma$. The case $\gamma =0$ is immediate. In the successor step the recursive definitions and the induction hypothesis giveFor a nonzero limit ordinal $\lambda$, the ordinals $\beta +\xi$ for $\xi <\lambda$ form an increasing cofinal subset of the limit ordinal $\beta +\lambda$. The limit clause for ordinal addition, restricted to this cofinal subset, givesCofinal restriction is valid because ordinal addition by a fixed ordinal on the left is increasing and continuous in its right argument, directly from its recursive definition. This completes the induction.

False. Take $\alpha =1$ and $\beta =\omega$. By the limit clause for ordinal addition,The first order type is one point followed by a countably infinite sequence, which is still of type $\omega$. The second has a greatest element after that infinite sequence, so its order type is the successor ordinal $\omega +1$. Thus ordinal addition is not commutative, even though the two resulting sets have equal cardinality.

True: ordinal multiplication on the left distributes over ordinal addition. If $\alpha =0$ both sides are zero. Otherwise fix $\alpha >0$ and $\beta$, and induct on $\gamma$. At zero the identity follows from $\alpha 0=0$. At a successor, use the recursive ordinal multiplication rule and the associativity just proved:For a nonzero limit ordinal $\lambda$, the ordinals $\beta +\xi$ are cofinal in $\beta +\lambda$. Continuity of ordinal multiplication in its right argument givesFor the last equality, $\alpha \xi$ is increasing and cofinal in $\alpha \lambda$, which is a limit ordinal because $\alpha >0$, and ordinal addition is continuous in its right argument. This establishes the limit step and the identity for all ordinals.

False. Take $\alpha =\beta =1$ and $\gamma =\omega$. ThenThus ordinal multiplication on the right does not in general distribute over ordinal addition. The side on which ordinal multiplication occurs matters; the left-distributive identity in the previous part does not imply this one.

The recursive definitions of ordinal addition and ordinal multiplication arewhere the limit clauses apply to nonzero limit ordinals. Ordinal exponentiation has ${\alpha }^0=1$, ${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$, and for $\alpha >0$, ${\alpha }^{\lambda }={\sup }_{\beta <\lambda }{\alpha }^{\beta }$. Complete the zero-base convention by $0^{\beta }=0$ for $\beta >0$, with $0^0=1$. Stating the zero-base exception avoids including the value $0^0$ in a naive supremum at a positive limit.

For finite $n$, induction gives $1+n=n+1$. Now prove commutativity for finite $m,n$ by induction on $m$. The case $m=0$ is immediate. Associativity, the finite identity just obtained, and the induction hypothesis giveThus $\boxed{m+n=n+m\text{ for finite ordinals}}$.

It fails for general ordinals: $\boxed{1+\omega =\omega <\omega +1}$. The equality follows from the limit clause, since the finite sums $1+n$ are cofinal in $\omega$.

Yes, with the stated strict decrease and positive coefficients. In any displayed Cantor normal form, the first exponent is the unique $\delta$ with ${\omega }^{\delta }\le \alpha <{\omega }^{\delta +1}$. The leading coefficient is the unique positive integer $n$ withThe remaining tail is the unique $\zeta <{\omega }^{\delta }$ satisfying $\alpha ={\omega }^{\delta }n+\zeta$, by strict monotonicity of ordinal addition in the right operand.

Thus any two such representations have the same first exponent and coefficient and the same remainder. Repeat the argument on that remainder. Their finite lists agree term by term and reach zero at the same step, so the lengths agree as well. Allowing zero coefficients or repeated exponents would spoil this normalized uniqueness, which is why those conditions are required.

Ordinal arithmetic describes the order types of well-ordered constructions. Its operations are defined by transfinite recursion, continuous in their right argument at limits. For addition,For multiplication,and, for $\alpha >0$, exponentiation is defined byThe usual conventions give $0^0=1$ and $0^{\beta }=0$ for $\beta >0$. Ordinal addition concatenates orders, while ordinal multiplication takes a succession of copies of the left factor indexed by the right factor.

Ordinal addition and ordinal multiplication are associative but generally not commutative; exponentiation is not an associative operation. For example,The distributive identity is $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$; the reversed distributive law fails, since $(1+1)\omega =\omega$ but $1\omega +1\omega =\omega \cdot 2$. For positive bases, ${\alpha }^{\beta +\gamma }={\alpha }^{\beta }{\alpha }^{\gamma }$ follows from the recursive definitions. These are order-type identities, not an extension of commutative integer arithmetic.

Every nonzero ordinal has a unique Cantor normal formComparisons are lexicographic in the exponent/coefficient list. Adding a later ordinal can erase smaller final terms of the earlier one, explaining noncommutativity. Hessenberg natural sum instead aligns equal exponents and adds their coefficients, producing a commutative operation. Finite recursive expressions formed from zero, sums and powers of $\omega$ describe exactly the ordinals below epsilon zero, the least positive solution of ${\omega }^{\alpha }=\alpha$. With ${\omega }_0=1$ and ${\omega }_{m+1}={\omega }^{{\omega }_m}$,

To use these ordinals computationally, fix effective fundamental sequences of limit ordinals. Write a nonzero limit below ${\epsilon }_0$ as $\gamma +{\omega }^{\beta }$, where this is its last Cantor term with one copy separated off. If $\beta =\delta +1$, setIf $\beta$ is a nonzero limit, set $(\gamma +{\omega }^{\beta })[n]=\gamma +{\omega }^{\beta [n]}$. These sequences increase to their limit; for instance $\omega [n]=n+1$ and $({\omega }^{\omega })[n]={\omega }^{n+1}$. At the endpoint choose ${\epsilon }_0[n]={\omega }_{n+1}$. The shift by one is a convention; changing it changes exact finite values, so it must be specified.

The fast-growing hierarchy now combines iteration at successors with diagonalization at limits:The superscript denotes repeated function composition, not exponentiation. ThusThe next level iterates an exponential-growth function $n+1$ times, yielding tower-like growth; further finite levels iterate the corresponding higher growth. Each fixed finite level is primitive recursive, and every unary primitive recursive function is eventually dominated by a sufficiently high finite level. The first limit diagonalizes over all of them: $F_{\omega }(n)=F_{n+1}(n)$ has Ackermannian growth and is not primitive recursive. Further limits give diagonals over already transfinite stretches of the hierarchy.

Transfinite induction proves totality for every fixed ordinal index in the chosen well-founded notation system: limit evaluation passes to a smaller index, while successor evaluation performs finitely many calls at the preceding index. For the standard fundamental sequences, $\alpha <\beta$ implies $F_{\alpha }(n)<F_{\beta }(n)$ for all sufficiently large $n$. This eventual dominance in a fast-growing hierarchy is not pointwise monotonicity in the ordinal index. For example,even though $3<\omega$.

The hierarchy also measures proof-theoretic strength. Every fixed $F_{\alpha }$ with $\alpha <{\epsilon }_0$ is provably total in Peano arithmetic, and every number-theoretic function provably total there is eventually majorized by some such level. The endpoint $F_{{\epsilon }_0}$ is a total recursive function in the usual mathematical metatheory but its totality is not provable in consistent PA. The classification is established in epub.ub.uni-muenchen.de/3843/1/3843.pdf . The distinction is between separately proving each fixed lower level and proving one uniform diagonal statement covering all lower levels; a theory cannot interchange those quantifiers without additional strength.

A related example is Goodstein's theorem. Changing the base in a hereditary base representation can increase the natural number dramatically, but replacing that base by $\omega$ gives an ordinal rank of a Goodstein term below ${\epsilon }_0$. Subtracting one strictly decreases this rank, so an infinite nonterminating process would give an impossible ordinal descent. This illustrates the central connection: ordinal descent proves termination while fast-growing hierarchies measure how long finite terminating processes can last. The size of intermediate natural numbers need not resemble the simplicity of their ordinal termination measure.

For Fodor's theorem, let $\kappa$ be regular uncountable, $S\subseteq \kappa$ stationary, and $f:S\to \kappa$ regressive: $f(\alpha )<\alpha$ for every nonzero $\alpha \in S$. A club set is unbounded in $\kappa$ and closed under limits below $\kappa$; a stationary set meets every club. Removing $0$ preserves stationarity. We prove that some fibre of $f$ is stationary, not merely that one fibre is large.

We first check the club facts used in the argument. An intersection of fewer than $\kappa$ club subsets of $\kappa$ is club. Closure is immediate. For unboundedness, given $\gamma$ and clubs $(C_i{)}_{i<\mu }$ with $\mu <\kappa$, choose an increasing sequence ${\gamma }_n$ starting above $\gamma$, such that ${\gamma }_{n+1}$ is above a point of every $C_i$ beyond ${\gamma }_n$. Regularity bounds the supremum of the fewer-than-$\kappa$ points at each step. Then $\delta ={\sup }_{n<\omega }{\gamma }_n<\kappa$, and the chosen points in each $C_i$ are cofinal in $\delta$; closure puts $\delta$ in their intersection.

For a sequence $(C_{\xi }{)}_{\xi <\kappa }$ of clubs its diagonal intersectionis also club. To obtain a point above $\gamma$, recursively choose ${\gamma }_{n+1}>{\gamma }_n$ in ${\bigcap }_{\xi \le {\gamma }_n}{C}_{\xi }$, possible by the preceding result, and take the supremum $\delta$ of the sequence. For each $\xi <\delta$, every sufficiently late ${\gamma }_n$ belongs to $C_{\xi }$, so $\delta \in C_{\xi }$. For closure, if diagonal-intersection points are cofinal in $\delta <\kappa$, then for each $\xi <\delta$ their sufficiently late points lie in $C_{\xi }$, and closure again puts $\delta$ there.

Suppose every fibre $S_{\xi }=\{\alpha \in S:f(\alpha )=\xi \}$ were nonstationary. Choose a club $C_{\xi }$ disjoint from each fibre. Stationarity supplies $\alpha \in S\cap {\Delta }_{\xi <\kappa }{C}_{\xi }$, with $\alpha >0$. Put $\xi =f(\alpha )<\alpha$. By diagonal membership $\alpha \in C_{\xi }$, but by its definition $\alpha \in S_{\xi }$, a contradiction. ThusThis is precisely the pressing-down assertion. Regularity and uncountability were used to keep the club-building suprema below $\kappa$.

For the Cantor normal form theorem, every nonzero ordinal has a unique expressionAll operations are ordinal operations, so the order of the terms matters. The ordinal zero has the empty expression. We give the greedy existence proof and then prove uniqueness.

The powers ${\omega }^{\beta }$ are strictly increasing and continuous at limit exponents, and satisfy ${\omega }^{\beta }\ge \beta$. Hence the set of exponents with ${\omega }^{\beta }\le \alpha$ is nonempty and bounded, and its supremum ${\beta }_0$ belongs to it by continuity (or is already its last successor member). Thus there is a largest such exponent andSince the last product is the supremum of the finite multiples, there is a unique positive finite $n_0$ satisfyingThe initial segment of $\alpha$ of length ${\omega }^{{\beta }_0}{n}_0$ leaves a tail of unique order type $\rho$, soThe bound follows from strict increase of ordinal addition in its right argument: a tail at least ${\omega }^{{\beta }_0}$ would contradict the preceding interval. This is the relevant instance of the ordinal division algorithm.

If $\rho >0$, apply the same construction to it. Its leading exponent must be below ${\beta }_0$. Continue with the remainder. An infinite continuation would produce an infinite strictly descending sequence of ordinals, impossible by well-foundedness. Thus the process terminates after finitely many steps and gives the required form.

To prove uniqueness, first observe that a finite decreasing-exponent suffix with leading exponent $\gamma$ is smaller than ${\omega }^{\gamma +1}$. This follows by induction on its number of terms: the later tail is below ${\omega }^{\gamma }$, so adding it to a finite multiple of ${\omega }^{\gamma }$ stays below the next finite multiple and hence below ${\omega }^{\gamma }\cdot \omega$. Consequently the tail after a term with exponent $\beta$ is below ${\omega }^{\beta }$.

Any proposed normal form therefore places $\alpha$ in exactly the intervalIts first exponent is recoverable as the largest exponent whose power does not exceed $\alpha$, and its first coefficient is recoverable as the largest finite multiple not exceeding $\alpha$. The right remainder is unique because ordinal addition is strictly increasing in its right argument. Apply the same reasoning to the remainder, successively fixing every exponent and coefficient. This proves uniqueness without treating ordinal addition as commutative or cancelling arbitrary left summands.

Fix an ordinal $\rho >1$. The Generalized Cantor normal form asserts that every nonzero ordinal $\alpha$ has a unique expressionProducts, sums and powers here are ordinal multiplication, ordinal addition and ordinal exponentiation; the coefficients need not be finite if $\rho$ is infinite. The case $\rho =\omega$ is Cantor normal form, and a finite base on finite ordinals gives ordinary positional notation. Zero has the empty expansion.

We first prove the ordinal division algorithm. For $\delta >0$, the function $q\mapsto \delta q$ is strictly increasing, continuous at limit ordinals and unbounded. Hence there is a greatest $q$ with $\delta q\le \alpha$: the first $q^{\prime }$ with $\delta q^{\prime }>\alpha$ cannot be a limit by continuity and must equal $q+1$. The interval after the initial segment $\delta q$ has a unique order type $r$, so $\alpha =\delta q+r$. Maximality of $q$ gives $r<\delta$. These facts also prove uniqueness of $q,r$.

Similarly $\beta \mapsto {\rho }^{\beta }$ is strictly increasing, continuous at limits and unbounded, so there is a unique largest ${\beta }_0$ with ${\rho }^{{\beta }_0}\le \alpha$. Divide by ${\rho }^{{\beta }_0}$ to obtainThe quotient is positive, and $\alpha <{\rho }^{{\beta }_0+1}={\rho }^{{\beta }_0}\rho$ makes ${\xi }_0<\rho$. If $r_0>0$, repeat on $r_0$; its leading exponent is strictly smaller than ${\beta }_0$. This process terminates, since an infinite run would give an infinite descending sequence of ordinals. It constructs the required form.

For uniqueness, a finite expression with largest exponent $\beta$ and coefficients below $\rho$ has value below ${\rho }^{\beta +1}$. Prove this from the end backwards: a tail with largest exponent $\gamma <\beta$ is below ${\rho }^{\gamma +1}\le {\rho }^{\beta }$, andThus the displayed leading exponent is the uniquely determined largest $\beta$ with ${\rho }^{\beta }\le \alpha$. The ordinal division algorithm uniquely determines its coefficient and the remaining tail, and recursion proves uniqueness of the whole expression. No commutative rearrangement of ordinal sums is used.

This assertion is always true. Ordinal addition obeys $\alpha +\beta \ge \alpha$ and $\alpha +\beta \ge \beta$. Thus both summands are at most ${\omega }_1$. If $0<\beta <{\omega }_1$ and $\alpha <{\omega }_1$, both ordinals are countable, and their disjoint ordered union is countable, so their sum cannot be ${\omega }_1$. If instead $\alpha ={\omega }_1$ and $\beta >0$, appending a nonempty second block gives a sum strictly larger than ${\omega }_1$. These exhaust the possibilities with $0<\beta <{\omega }_1$; hence $\beta =0$ or $\beta ={\omega }_1$.

The inductive definition of ordinal addition isfor nonzero limit ordinals $\lambda$. The synthetic definition is the order type of a disjoint copy of $\alpha$ followed by a disjoint copy of $\beta$, retaining the order within each block and declaring every element of the first block smaller than every element of the second.

These are equivalent by transfinite induction in the second argument. An empty second block leaves $\alpha$; a successor block appends one final point; and a limit block is the increasing union of its proper initial blocks, whose order types have the indicated supremum. Thus the synthetic construction satisfies exactly the inductive recursion, which determines the operation uniquely. It is not commutative: $1+\omega =\omega$, whereas $\omega +1>\omega$.

The recursive ordinal addition definitions are $a+0=a$, $a+(b+1)=(a+b)+1$, and $a+\lambda ={\sup }_{b<\lambda }(a+b)$ for a nonzero limit ordinal. Ordinal multiplication is $a\cdot 0=0$, $a\cdot (b+1)=a\cdot b+a$, and $a\cdot \lambda ={\sup }_{b<\lambda }a\cdot b$. For $a>0$, ordinal exponentiation is $a^0=1$, $a^{b+1}=a^b\cdot a$, and $a^{\lambda }={\sup }_{b<\lambda }{a}^b$; the exceptional zero base has $0^0=1$ and $0^b=0$ for $b>0$.

Transfinite induction gives ${\omega }^a\ge a$. At zero this is immediate; at a successor, ${\omega }^{b+1}={\omega }^b\omega \ge {\omega }^b+1\ge b+1$. At a limit, continuity and the induction hypothesis give ${\sup }_{b<a}{\omega }^b\ge {\sup }_{b<a}b=a$. Also $a\mapsto {\omega }^a$ is strictly increasing: its successor values strictly increase, and continuity preserves the strict inequality between any two distinct indices.

For $\alpha >0$, ${\omega }^{\alpha +1}>{\omega }^{\alpha }\ge \alpha$, so there is a least $\delta$ with ${\omega }^{\delta }>\alpha$. It cannot be zero and cannot be a limit: at a limit, a supremum greater than $\alpha$ has a term already greater than $\alpha$, contradicting minimality. Thus $\delta ={\alpha }_0+1$, andStrict increase proves uniqueness, and ${\alpha }_0\le {\omega }^{{\alpha }_0}\le \alpha$ proves the requested index bound.

Choose the largest positive integer $a_0$ with ${\omega }^{{\alpha }_0}{a}_0\le \alpha$. It exists because $\alpha <{\omega }^{{\alpha }_0}\omega ={\sup }_{m<\omega }{\omega }^{{\alpha }_0}m$. The remaining tail of the ordinal interval has an order type $\rho$ with $\alpha ={\omega }^{{\alpha }_0}{a}_0+\rho$; maximality implies $\rho <{\omega }^{{\alpha }_0}$. If $\rho >0$, repeat the construction on it. The leading exponents strictly decrease, and there is no infinite strictly decreasing sequence of ordinals: its set of values would have a least member followed by a smaller one. Hence the process terminates, yielding the Cantor normal formThe first exponent is determined by the preceding band, the first coefficient by maximality, and the tail by the ordinal interval left after that initial segment. Recursion therefore proves uniqueness of every exponent and coefficient. The PDF's second coefficient is printed ${\alpha }_1$ rather than $a_1$; the stated natural-number coefficients and the construction identify the intended expression.

For the final assertion, powers of $\omega$ are additively indecomposable: if $\tau <{\omega }^{\eta }$, then $\tau +{\omega }^{\eta }={\omega }^{\eta }$ for $\eta >0$. One proves this by induction on $\eta$. At a successor, bound $\tau$ by a finite multiple of ${\omega }^{\eta -1}$ and use the supremum over all such multiples; at a limit, bound $\tau$ by a smaller power and use continuity. For $\eta =0$ the only possible $\tau$ is zero. Thus a smaller leading exponent is absorbed when a larger-leading ordinal is added on its right. If $\beta ,\gamma$ have unequal leading exponents, either $\beta +\gamma =\gamma$ or $\gamma +\beta =\beta$. If their leading exponents coincide, the leading coefficient of either sum is the sum of their two positive leading coefficients; it exceeds each coefficient, so neither absorption equality holds. Zero is never commensurable with an ordinal. Consequently commensurability is exactly equality of the leading exponent, equivalently membership of both positive ordinals in one of the stated bands.

The map $\beta \mapsto {\omega }^{\beta }$ is strictly increasing and continuous at limit ordinals. Also ${\omega }^{\beta }\ge \beta$, so the set $S=\{\beta :{\omega }^{\beta }\le \alpha \}$ is nonempty and bounded by $\alpha$. If $\sup S$ is a successor, it is already in $S$; if it is a limit, continuity gives ${\omega }^{\sup S}={\sup }_{\beta \in S}{\omega }^{\beta }\le \alpha$. Thus $S$ has a greatest element $\beta$.

The initial segment of the well-order $\alpha$ of order type ${\omega }^{\beta }$ leaves a tail of some order type $\gamma$, giving ${\omega }^{\beta }+\gamma =\alpha$. For fixed left summand, ordinal addition is strictly increasing in its right argument, so this $\gamma$ is unique.

Maximality gives $\alpha <{\omega }^{\beta +1}={\omega }^{\beta }\omega$. Choose the least positive integer $m$ such that $\alpha <{\omega }^{\beta }m$. Then $m\ge 2$ and ${\omega }^{\beta }(m-1)\le \alpha$. If $\gamma \ge {\omega }^{\beta }(m-1)$, monotonicity of ordinal addition would give $\alpha ={\omega }^{\beta }+\gamma \ge {\omega }^{\beta }m$, a contradiction. Hence $\gamma <{\omega }^{\beta }(m-1)\le \alpha$. If $\alpha$ is not a power of $\omega$, both ${\omega }^{\beta }$ and $\gamma$ are nonzero and smaller than $\alpha$, proving decomposability.

Conversely, prove by transfinite induction that any two ordinals below ${\omega }^{\beta }$ have sum below ${\omega }^{\beta }$. For $\beta =0$ the only smaller ordinal is zero. For $\beta =\delta +1$, choose finite $m,n$ with $x<{\omega }^{\delta }m$ and $y<{\omega }^{\delta }n$. Monotonicity gives $x+y<{\omega }^{\delta }(m+n)<{\omega }^{\delta +1}$. For limit $\beta$, choose $\delta <\beta$ sufficiently large that $x,y<{\omega }^{\delta }$, and apply the induction hypothesis. Thus the nonzero indecomposable ordinals are exactly the powers of $\omega$.

False. Take $\alpha ={\omega }^2+1$, which satisfies the proposed lower bound. Associativity of ordinal addition and $1+{\omega }^2={\omega }^2$ giveThe final successor survives only in the second expression.