# Is there a categorification of (infinite) ordinal arithmetic?

## Background for the curious reader:

An ordinal $\beta$ is a transitive set in the sense that $\alpha\in\beta$ implies $\alpha\subset\beta$. Any ordinal is naturally well-ordered under $\in$ (so any subset of it has a least element), and any well-order is isomorphic to an ordinal. In fact, any class (naively, collection) of ordinals is itself well-ordered under the relation $\in$. This fact allows for the usage of transfinite induction and transfinite recursion.

We have three types of ordinals: the empty set $0=\emptyset=\{\}$, successor ordinals $S(\alpha)=\alpha\cup\{\alpha\}$ where $\alpha$ is an ordinal, and limit ordinals, which are all the other ones. Finite ordinals are either $0$ or successors, the set $\omega=\{0,1,2,\dots\}$ is a limit ordinal. A limit ordinal $\alpha$ has the property that $\alpha=\sup_{\beta<\alpha}\{\beta\}=\bigcup_{\beta<\alpha}\beta$.

## My question

Ordinal arithmetic can be defined recursively as follows:

1. $\alpha+0=\alpha$, $\alpha+S(\beta)=S(\alpha+\beta)$, $\alpha+\sup_{\gamma<\beta}\{\gamma\}=\sup_{\gamma<\beta}\{\alpha+\gamma\}$;
2. $\alpha\cdot0=\alpha$, $\alpha\cdot S(\beta)=\alpha\cdot\beta+\alpha$, $\alpha\cdot\sup_{\gamma<\beta}\{\gamma\}=\sup_{\gamma<\beta}\{\alpha\cdot\gamma\}$;
3. $\alpha^0=1$, $\alpha^{S(\beta)}=\alpha^\beta\cdot\alpha$, $\alpha^{\sup_{\gamma<\beta}\{\gamma\}}=\sup_{\gamma<\beta}\{\alpha^\gamma\}$.

Alternatively, one can define:

1. $\alpha+\beta$ is the unique ordinal isomorphic to the disjoint union $\{0\}\times\alpha\cup\{1\}\times\beta$ given the lexicographic order.
2. $\alpha\cdot\beta$ is the unique ordinal isomorphic to the Cartesian product $\beta\times\alpha$ given the lexicographic order.

As the disjoint union and Cartesian product are simply the categorical coproduct and the categorical product, I wonder if there is some way to actually categorify these alternate definitions. Additionally, I am not aware of any non-recursive version of exponentiation, so I would be curious if a categorical formulation of addition and product of ordinals also allows for a categorical (hence non-recursive) formulation of exponentiation.

-
What do you mean exactly by categorifying these definitions? What are you looking for? –  Martin Brandenburg May 5 '13 at 10:58
I want the sum, product, and exponential to be objects in some category that includes all the ordinals, and which satisfy some universal properties in some category. The question is which category and which properties? –  Vladimir Sotirov May 8 '13 at 20:15
Vladimir, just a thought: if we view ordinals as being elements of the skeleton category of totally ordered sets, perhaps coproducts of ordinals coincide with the usual ordinal sum. I could be wrong, though. Good question, by the way. –  user18921 Jul 1 '13 at 14:04

We can define $\alpha^\beta$ to be the order type of the set of functions from $\beta$ to $\alpha$ of finite support (finitely many non-$0$ function values), ordered in reverse lexicographic order--that is, if $f,g:\beta\to\alpha$ have finite support and are distinct functions, and if $\xi$ is the greatest ordinal in $\beta$ for which $f(\xi)\neq g(\xi)$, then we say $f<g$ if $f(\xi)<g(\xi)$.

I'm not well-versed in category theory, so I can't answer your other questions, but I can give you that much.

-

Your question is quite vague, therefore I don't know if this is what you want. But I think this is a neat "all-in-one" description of ordinal operations, which in fact come down to operations on well-orderings.

The category of well-orderings has no coproducts (basically because there is no way how to decide the relations between the summands). But there are "directed coproducts" (I don't know if this construction has a canonical name):

Let $S$ be a well-ordering. For every $s \in S$ let $X_s$ be a well-ordering. Consider their underlying sets and take their disjoint union $X = \coprod_{s \in S} X_s = \bigcup_{s \in S} \{s\} \times X_s$. Endow this set with the following well-order: We have $(s,x) < (s',x')$ when $s < s'$ or ($s=s'$ and $x < x'$ in $X_s$). We may write $$X = \coprod\limits_{s \in S}^{\longrightarrow} X_s$$ for this well-ordering in order to indicate the direction induced by $S$. It is not a colimit in the usual sense (but perhaps the category theorists can tell you if it is a weighted colimit?). But it enjoys the obvious universal property within the category of well-orderings and increasing maps: Morphisms $X \to Y$ correspond 1:1 to families of morphisms $f_s : X_s \to Y$ that satisfy the property

$\forall s,s' \in S (s < s' \Rightarrow \forall x \in X_s \forall x' \in X_{s'} \,(f_s(x) < f_{s'}(x'))).$

Here are two examples:

• If $S=\{0<1\}$, then we have just two well-orderings $X_0,X_1$, and we get $X_0 \stackrel{\longrightarrow}{\sqcup} X_1$. This categorifies the ordinal sum.

• If $X_s=Y$ is constant, then we get $S \times Y$ with the lexicographic well-ordering. This categorifies the ordinal product.

Similarily, one can define and construct "directed products", which categorifies ordinal exponentiation.

-
The papers "An Extended Arithmetic" and "Generalized Arithmetic" by Birkhoff might be related to that. –  Martin Brandenburg May 16 '13 at 14:45