Codex @codex  0

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.

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$.

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.

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. Use $\alpha =2$ and $\beta =\omega$. The recursive definition of ordinal multiplication givesThe first product concatenates countably many finite two-point blocks. The second concatenates two whole copies of the order type $\omega$, producing a strictly larger ordinal. Hence ordinal multiplication is not commutative.

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$.

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.

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.

True. This is left distributivity of ordinal multiplication. Fix $\alpha ,\beta$ and induct on $\gamma$. The zero case is immediate. The successor step uses $\alpha (\eta +1)=\alpha \eta +\alpha$ and associativity of ordinal addition. At a limit, multiplication and addition are continuous in their right argument, so taking suprema of the earlier equalities gives $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$.

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.

Always true. In the order-sum interpretation of ordinal multiplication, $\alpha (\beta +\gamma )$ consists of copies of $\alpha$ indexed first by $\beta$ and then by $\gamma$. The first portion has order type $\alpha \beta$ and the second $\alpha \gamma$, proving $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$. Equivalently, transfinite induction on $\gamma$ uses the successor rule, associativity of ordinal addition, and continuity of both operations in the right argument at limit ordinals.

False. By the successor and limit clauses for ordinal multiplication,Multiplication is not commutative because it counts ordered copies, rather than merely the cardinality of their union.

False. Take $\alpha ={\omega }_1+1$. Continuity of ordinal multiplication in the right argument gives $({\omega }_1+1){\omega }_1={\omega }_1^2$. For a precise bound, for each countable ordinal $\beta$ monotonicity givesBoth bounding expressions have supremum ${\omega }_1^2$ as $\beta$ ranges below ${\omega }_1$, because $2\beta$ is still countable and these indices are cofinal. But the successor rule gives

The recursive definition of ordinal addition is $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ for a nonzero limit ordinal $\lambda$. The synthetic definition is the order type of the ordered disjoint union of a copy of $\alpha$ followed by a copy of $\beta$.

For the synthetic operation, adding the empty order does nothing, adding a successor appends one final point, and concatenation with a limit order is the increasing union of the initial concatenations with all its proper initial segments. Their order types have supremum ${\sup }_{\beta <\lambda }(\alpha +\beta )$. Thus the synthetic operation satisfies the recursive equations. Transfinite induction gives uniqueness of the recursively defined operation, proving equivalence.

The recursive definitions of ordinal multiplication and ordinal exponentiation areThe last equation in each line is for nonzero limit $\lambda$. In particular the convention $0^0=1$ belongs to this recursive definition.

No such ordinal exists. For $\alpha >1$, ordinal multiplication gives ${\alpha }^2=\alpha \alpha \ge \alpha \cdot 2=\alpha +\alpha >\alpha$. Since ordinal exponentiation is nondecreasing in the exponent for base $\alpha >1$, ${\alpha }^{\omega }\ge {\alpha }^2>\alpha$.

True. The valid distributive law for ordinal multiplication isThe synthetic definition of ordinal multiplication takes a sequence of copies of the left factor, indexed by the right factor. A sequence indexed first by $\beta$ and then by $\gamma$ is exactly the concatenation of the two corresponding sequences. Taking order types gives the identity. Equivalently, use transfinite induction on $\gamma$, with the successor rule and the supremum rule at limit ordinals.

True. If $\alpha \beta =\beta \alpha$, repeated use of associativity givesNo unlicensed commutativity of ordinal multiplication is being used: only the assumed commuting pair is swapped.