The Unapologetic Mathematician

Mathematics for the interested outsider

Cardinals and Ordinals as Categories

We can import all of what we’ve said about cardinal numbers and ordinal numbers into categories.

For cardinals, it’s actually not that interesting. Remember that every cardinal number is just an equivalence class of sets under bijection. So, given a cardinal number we can choose a representative set S and turn it into a category \mathcal{S}. We let {\rm Ob}(\mathcal{S})=S and just give every object its identity morphism — there are no other morphisms at all in this category. We call this sort of thing a “discrete category”.

For ordinal numbers it gets a little more interesting. First, remember that a preorder is a category with objects the elements of the preorder, one morphism from a to b if a\leq b, and no morphisms otherwise.

It turns out that (small) categories like this are exactly the preorders. Let \mathcal{P} be a small category with a set of objects P and no more than one morphism between any two objects. We define a preorder relation \leq by saying a\leq b if hom_\mathcal{P}(a,b) is nonempty. The existence of identities shows that a\leq a, and the composition shows that if a\leq b and b\leq c then a\leq c, so this really is a preorder.

If now we require that no morphism (other than the identity) has an inverse, we get a partial order. Indeed, if a\leq b and b\leq a then we have arrows f:a\rightarrow b and g:b\rightarrow a. We compose these to get g\circ f:a\rightarrow a and f\circ g:b\rightarrow b. These must be the respective identities because there’s only the one arrow from any object to itself. But we’re also requiring that no non-identity morphism be invertible, so a has to be the same object as b.

Now we add to this that for every distinct pair of objects either \hom_\mathcal{P}(a,b) or \hom_\mathcal{P}(b,a) is nonempty. They can’t both be — that would lead to an inverse — but we insist that one of them is. Here we have total orders, where either a\leq b or b\leq a.

Finally, a technical condition I haven’t completely defined (but I will soon): we require that every nonempty “full subcategory” of \mathcal{P} have an “initial object”. This is the translation of the “well-ordered” criterion into the language of categories. Categories satisfying all of these conditions are the same as well-ordered sets.

Okay, that got a bit out there. We can turn back from the theory and actually get our hands on some finite ordinals. Remember that every finite ordinal number is determined up to isomorphism by its cardinality, so we just need to give definititions suitable for each natural number.

We define the category \mathbf{0} to have no objects and no morphisms. Easy.

We define the category \mathbf{1} to have a single object and its identity morphism. If we take the identity morphisms as given we can draw it like this: \bullet.

We define the category \mathbf{2} to have two objects and their identity morphisms as well as an arrow from one object to the other (but not another arrow back the other way). Again taking identities as given we get \bullet\rightarrow\bullet.

Things start to get interesting at \mathbf{3}. This category has three objects and three (non-identity) morphisms. We can draw it like this:
The composite of the horizontal and vertical arrows is the diagonal arrow.

Try now for yourself drawing out the next few ordinal numbers as categories. Most people get by without thinking of them too much, but it’s helpful to have them at hand for certain purposes. In fact, we’ve already used \mathbf{2}!

Now to be sure that this does eventually cover all natural numbers. We can take our {0} to be the category \mathbf{0}. Then for a successor “function” we can take any category and add a new object, its identity morphism, and a morphism from every old object to the new one. With a little thought this is the translation into categories of the proof that well-ordered finite sets give a model of the natural numbers, and the same proof holds true here.

May 24, 2007 Posted by | Category theory | 6 Comments