Abstract Nonsense

Crushing one theorem at a time

Preordered Sets as Categories, and their Functor Categories (Pt. I)

Point of Post: In this post we discuss the way in which preordered sets are, in spirit, the same as categories whose Hom sets never exceed one in cardinality–we also discuss then the interpretation of already-discussed categorical concepts into the language of preordered sets.

\text{ }


\text{ }

Having a plethora of categorical examples is invaluable in two ways. Firstly, having a wide-array of examples allows us to test our knowledge of categorical concepts, get our “hands dirty” which of course gives us better insight into what the concepts “really mean”. Secondly, it allows us to create even more categorical concepts by combining previously defined ideas.

\text{ }

Preordered Sets as Categories

\text{ }

Let (I,\leqslant) be a preordered set, i.e. \leqslant is a relation on I which is reflexive and transitive (but not necessarily symmetric or antisymmetric, thus generalizing both posets and ordered sets). There is a particularly simple way to make I into a category. Namely, let \mathcal{I} be the “category” whose object class is I and such that given x,y\in I one has that

\text{ }

\text{Hom}_\mathcal{I}(x,y)=\begin{cases}\{k_{x,y}\} & \mbox{if}\quad x\leqslant y\\ \varnothing & \mbox{if}\quad\text{otherwise}\end{cases}

\text{ }

define composition in \mathcal{I} by stating that k_{y,z}\circ k_{x,y}=k_{x,z} whenever this composition is admissible (i.e. whenever x\leqslant y\leqslant z). It’s easy to see that this is a category, the only perhaps unclear thing is why k_{x,x} is the identity arrow of x. To see this, all we have to note is that, when defined, we have the following k_{x,z}\circ k_{x,x}=k_{z,x} and k_{y,y}\circ k_{x,y}=k_{x,y} so that k_{x,x} really is an identity arrow for x. Thus, we see that, with these definitions, \mathcal{I} really is a category. We call this the category induced by (I,\leqslant).

\text{ }

There is actually a way of going backwards, to create a poset from a category with Hom sets which are either empty or singletons. Indeed, suppose conversely that we have a (small) category \mathcal{I} such that \#(\text{Hom}_\mathcal{I}(x,y))\leqslant 1 for all x,y objects in \mathcal{I}. If we define I to be the object set of \mathcal{I} we claim that there is a natural preorder on I from the category structure on \mathcal{I}. Indeed, define \leqslant on I by declaring x\leqslant y if and only if \text{Hom}_\mathcal{I}(x,y) is non-empty. To see that \leqslant really is a preorder we merely note that reflexivity follows from the existence of an identity arrow 1_x\in\text{End}(x) for each x\in I, and transitivity follows from the composibility of an arrow in \text{Hom}_\mathcal{I}(x,y) and an arrow in \text{Hom}_\mathcal{I}(y,z) to get an arrow in \text{Hom}_\mathcal{I}(x,z).

\text{ }

It’s easy to see that there is a kind of “duality” between these two constructions. Indeed, if we start with a preordered set (I,\leqslant), create the corresponding category \mathcal{I}, and then from this category create the corresponding preordered set, we just get (I,\leqslant) again (i.e. we have a “bijection” between preordered sets and categories whose Hom sets have at most one element). Similarly, if we start with a category \mathcal{I} whose Hom sets have at most one element, create the associated preordered set, and from this preordered set create the associated category we end up with the original category we started with. In this way we often forego the distinction between preordered sets and their associated categories–this is in the same vein that we may forego the distinction between monoids and their associated categories.

\text{ }

Remark: There was, as mentioned at one point but not enforced, a blanket assumption the smallness of all categories in the above discussion. If one is willing to accept the notion of relations on classes (possibly proper classes) then the above can be generalized to general categories.

\text{ }

Ok, so we have a new general example of a category to play with, let’s see if we can figure out what some of our previous categorical constructions look like on such categories. For example, what do functors between two preordered sets look like? Well, let’s say we have to preordered sets thought of as categories, call them \mathcal{I}=(I,\leqslant) and \mathcal{S}=(S,\preceq). Then, a functor F:\mathcal{I}\to\mathcal{S} induces a set function F:I\to S, but note that this set function has the property that if x\leqslant y then F(x)\leqslant F(y). Indeed, if x\leqslant y then there is an arrow x\to y and so there exists a corresponding arrow F(x)\to F(y) so that F(x)\preceq F(y). Conversely, it’s easy to see that any set map F:I\to S such that x\leqslant y implies F(x)\preceq F(y) induces a functor F:\mathcal{I}\to\mathcal{S}. Thus, we see that functors F:\mathcal{I}\to\mathcal{S} are nothing more than monotone functions F:I\to S.

\text{ }

What about the product of two preordered sets? How does this relate to the product of categories? Well, letting \mathcal{I} and \mathcal{S} be as above we  see that the object set of \mathcal{I}\times\mathcal{S} is I\times S, so how about the morphisms? Well, we see that given a pair of objects (x,y) and (x',y') in \mathcal{I}\times\mathcal{S} one has, by definition, that an arrow (x,y)\xrightarrow{(f,g)}(x',y') is a pair of arrows x\xrightarrow{f}x' and y\xrightarrow{g}y'. Thus, we see that there is an arrow (x,y)\to(x',y') if and only if x\leqslant x' and y\leqslant y'. Moreover, it’s clear that if an arrow exists then it is unique, for two different arrows between (x,y)\to (x',y') must induce either two different arrows x\to x' or two different arrows y\to y' both of which are impossible. From this we can conclude that \mathcal{I}\times\mathcal{S} is indeed a category coming from a preordered set, and moreover it’s the category coming from the usual product preordered set (I\times S,\leqslant\times\preceq).

\text{ }

Ok, so given a preordered set \mathcal{I}=(I,\leqslant) what does the opposite category \mathcal{I}^\text{op} look like? Since the arrows in \mathcal{I}^\text{op} are just the arrows of \mathcal{I} just reversed, it’s easy to see that \mathcal{I}^\text{op} is a category whose Hom sets have at most one object, and thus arises as the category of a preordered set, but which? I think it’s fairly easy to see that the preordered set from which \mathcal{I}^\text{op} is none other than the preordered set (I,\leqslant_{\text{op}}) where \leqslant_\text{op} is the usual opposite order defined by x\leqslant_\text{op} y if and only if y\leqslant x.

\text{ }

\text{ }


[1] Mac, Lane Saunders. Categories for the Working Mathematician. New York: Springer-Verlag, 1994. Print.

[2] Adámek, Jirí, Horst Herrlich, and George E. Strecker. Abstract and Concrete Categories: the Joy of Cats. New York: John Wiley & Sons, 1990. Print.

[3] Berrick, A. J., and M. E. Keating. Categories and Modules with K-theory in View. Cambridge, UK: Cambridge UP, 2000. Print.

[4] Freyd, Peter J. Abelian Categories. New York: Harper & Row, 1964. Print.

[5] Rotman, Joseph J. Introduction to Homological Algebra. Springer-Verlag. Print.

[6] Herrlich, Horst, and George E. Strecker. Category Theory: An Introduction. Lemgo: Heldermann, 2007. Print.


January 10, 2012 - Posted by | Algebra, Category Theory | , , ,

1 Comment »

  1. […] as being objects in a certain full subcategory of the functor category , where is the category induced by the reverse usual ordering on (the fact that we are doing the reverse of the usual ordering on […]

    Pingback by Chain Complexes « Abstract Nonsense | April 3, 2012 | 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

%d bloggers like this: