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:
\begin{matrix}\bullet&\rightarrow&\bullet\\&\searrow&\downarrow\\&&\bullet\end{matrix}
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.

About these ads

May 24, 2007 - Posted by | Category theory

6 Comments »

  1. [...] kinds of morphisms, subobjects, and quotient objects Last week I was using the word “invertible” as if it was perfectly clear. Well, it should be, more or [...]

    Pingback by Special kinds of morphisms, subobjects, and quotient objects « The Unapologetic Mathematician | May 29, 2007 | Reply

  2. [...] Remember the category with one object and its identity morphism. We draw it as , taking the identity as given. Let’s also consider a category with two objects and two non-identity morphisms, one going in either direction: . Call the objects and , and the four arrows , , , , where goes from to . Then we have and . That is, the two non-identity arrows are inverses to each other, and the two objects are thus isomorphic. [...]

    Pingback by Equivalence of categories « The Unapologetic Mathematician | May 30, 2007 | Reply

  3. [...] initial object of an ordinal number considered as a category is the least element of the [...]

    Pingback by Initial and Terminal Objects « The Unapologetic Mathematician | June 10, 2007 | Reply

  4. [...] category I’m interested in is the ordinal . Remember that this consists of the objects and , with one non-identity arrow . We can make this [...]

    Pingback by An example of an enriched category « The Unapologetic Mathematician | August 15, 2007 | Reply

  5. “we require that every “full subcategory” of \mathcal{P} have an “initial object””

    Every non-empty full subcategory probably?

    Comment by nikita | December 20, 2007 | Reply

  6. Ah, yes.. Of course you’re right.

    Comment by John Armstrong | December 20, 2007 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 366 other followers

%d bloggers like this: