Ordinal arithmetic

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.