Abstract Nonsense

Crushing one theorem at a time

Category Theory: Definition and Examples


Point of Post: The point of this post is to give the axiomatic definition of a category, and explain some of the nuances I’ve picked up. Also, I will give quite a few examples and show that they are indeed categoreis.

Definition

It comes time now to actually define what a category is. So, formally a category is a quadruple \bold{C}=\left(\mathcal{O},\text{Hom},\text{id},\circ\right) consisting of

a) A class \mathcal{O}, whose members are called \bold{C}-objects.

b) A set for \text{Hom}\left(A,B\right)  for each (A,B)\in\mathcal{O}\times\mathcal{O} whose members are referred to as \bold{C}-morphisms.

Remark: It is common to instead of write f\in\text{Hom}\left(A,B\right) to write “A\overset{f}{\longrightarrow}B is a morphism”

c) For each \bold{C}-object a morphism A\overset{\text{id}_A}{\longrightarrow}A

d) A composition law which associates for any morphism A\overset{f}{\longrightarrow}B and any morphism B\overset{g}{\longrightarrow}C a morphism A\overset{g\circ f}{\longrightarrow}C called the composite of f and g

Remark: To me, it seems that we could rephrase this as. For each C-objects (A,B,C) there exists a function

\circ_{(A,B,C)}:\text{Hom}(A,B)\times\text{Hom}(B,C)\to\text{Hom}(A,C):(f,g)\mapsto g\circ f

 

Such that

1) The composition is associative, namely for morphisms A\overset{f}{\longrightarrow}B,B\overset{g}{\longrightarrow} C and C\overset{h}{\longrightarrow}D the equation h\circ(g\circ f)=(h\circ g)\circ f holds true.

2) If A\overset{f}{\longrightarrow}B is a morphism then \text{id}_B\circ f=f\circ \text{id}_A=f

3) The elements of the set \left\{\text{Hom}\left(A,B\right):A,B\text{ are }\bold{C}-\text{objects}\right\} are pairwise disjoint.

Remark: It is common to denote \mathcal{O} as \text{ob}\left(\bold{C}\right) and \displaystyle \bigcup_{A,B\in\mathcal{O}}\text{Hom}\left(A,B\right)=\text{Mor}\left(\bold{C}\right).

Also, if f\in\text{Hom}\left(A,B\right) then we say that A is the domain of f, denoted A=\text{dom}\left(f\right). Similarly, B is called the codomain and is denoted \text{codom}\left(f\right). Note that by assumption c) above we have that for each f\in\text{Mor}\left(\bold{C}\right) we have that \text{dom}\left(f\right) and \text{codom}\left(f\right) are unique. Note though that even if 3) weren’t true we could force the uniqueness by replacing f\in\text{Hom}\left(A,B\right) by \left(A,f,B\right). Thus, in practice we do not show 3)

It is important to notice that g\circ f is defined if and only if \text{codom}\left(f\right)=\text{dom}\left(g\right) in the same sense that if (normal functions) f:\mathbb{R}\to\mathbb{R} and g:\mathcal{C}[0,1]\to\mathcal{C}[0,1] you couldn’t consider g\circ f

Lastly, it is common to write \text{Hom}_{\bold{C}}\left(A,B\right) if more than one categories are involved.

Examples

I’ll now give a few examples and non-examples of these ubiquitous structures and carefully show why each is or isn’t a category keeping with the lettering/number of the axioms above a),…,d),1),2) Note that while the examples may be easily verifiable, most category theory books (the three I’ve seen to be specific) state examples but do not go through a single one.

Example: Define the category \bold{Top} to be the one with

\text{ob}\left(\bold{Top}\right)=\text{Class of all topological spaces},

\text{Hom}\left(A,B\right)=\left\{f:A\to B\mid f\text{ is continuous }\right\},

\text{id}_A is the identity map on A, and if A\overset{f}{\longrightarrow}B and B\overset{g}{\longrightarrow}C are morphisms then  g\circ f is defined as the normal composition of functions.

So, now we need to check that this actually defines a category. So, we need to verify the six axioms (the existence and functional)

a) Clearly \text{ob}\left(\bold{Top}\right) is a class.

b) We also have that for each A,B\in\bold{Top} there is an associated set, namely the set of all continuous functions from A to B

c) For each A\in\text{ob}\left(\bold{Top}\right) we have identified an element, namely the identity map. Note though that just merely saying \text{id}_A\in\text{Hom}\left(A,A\right) isn’t enough. Once you’ve defined \text{Hom}\left(A,A\right) there is actually a question of whether or not \text{id}_A is contained within it. But, it is obviously true that as defined \text{id}_A is a map from A to A and since (as is easily proven) the identity map on any topological space to itself is continuous.

Remark: The above may cause some ambiguity if one does not recall that a topological space is the set (remember we defined an ordered pair of sets as a set) \left(X,\mathfrak{J}\right) where X is a set and \mathfrak{J} is a topology on X. Thus, when we say that the map \text{id}_A:A\to A is continuous, we are being sloppy and should really write \text{id}_A:\left(A,\mathfrak{J}\right)\to\left(A,\mathfrak{J}\right) to indicate that the domain and codomain are not only equal as sets,but equal as topological spaces in the sense that they are imbued with the same topology. In other words, topological space means the set and the topology on it. It is easy to find a set X with different topologies such that the identity map need not be continuous.

This is part of a larger issue. When one gets into category theory one need be precise. Remember that formally a topological space, as I just said, is an ordered pair and the elements of \text{ob}\left(\bold{C}\right) are topological spaces. So, when we write \text{Hom}\left(A,A\right) we are thinking of the A‘s in both slots as being equal as objects of \bold{Top}, i.e. equal as topological spaces. This gets confusing though since we denote arbitrary objects as just capital letters, the same sloppy notation used to identify a topological space with it’s underlying set. The same goes for all structures where the true definitions of them is an ordered tuple but we denote them using only the underlying set.

d) We have defined what it means to compose g,f, when f\in\text{Hom}\left(A,B\right) and g\in\text{Hom}\left(B,C\right) a. Note that clearly if f:A\to B and g:B\to C that g\circ f:A\to C, but for g\circ f\in\text{Hom}\left(A,C\right) we need that g\circ f:A\to B is continuous. But, a simple topological fact is that the composition of continuous maps is continuous. So, in fact g\circ f\in\text{Hom}\left(A,C\right) and the specified mapping is indeed legitimate.

Now, we must show that these identified things satisfy the two functional axioms.

1) We must show that the composition operation, as defined, is associative. But, this is immediate since normal function composition is associative.

2) We must check that for each A,B\in\text{ob}\left(\bold{Top}\right) and each f\in\text{Hom}\left(A,B\right) that \text{id}_B\circ f=f=f\circ\text{id}_A, but this follows immediately since \text{id}_B,\text{id}_A are the identity maps on B,A respectively and \circ is function composition.

Non-Example: The following example is stronger than a mere non-example. We will give three of the four definitions of a category and show that there does not exist a definition of the fourth which transforms it into a category. Thus, creating infinitely many examples of non-categories.

We’ll present this non-example in the categorical sense, namely we’ll define its objects, its morphisms, etc. We do this for purely pedagogical reasons. So, consider \bold{C} where

\text{ob}\left(\bold{C}\right)=\text{Class of all sets}

\text{Hom}\left(A,B\right)=A\times B, and for A,B,C\in\text{ob}\left(\bold{C}\right) we defined

\circ_{(A,B,C)}:\text{Hom}\left(A,B\right)\times\text{Hom}\left(B,C\right)\to \text{Hom}\left(A,C\right):\left((a,b),(b'c)\right)\mapsto (a,c)

We verify the axioms (or at leas those that work)

a) We have certainly chose \bold{C} so that \text{ob}\left(\bold{C}\right) was a class.

b) We have, for each A,B\in\text{ob}\left(\bold{C}\right) defined a set \text{Hom}\left(A,B\right)

d) We have, for each A,B,C\in\text{ob}\left(\bold{C}\right), defined a mapping

\circ_{(A,B,C)}:\text{Hom}\left(A,B\right)\times\text{Hom}\left(B,C\right)\to\text{Hom}\left(A,C\right)

So, now we have to try and prove the two functional axioms.

1) Suppose that A,B,C,D\in\text{ob}\left(\bold{C}\right) and (a,b)\in\text{Hom}\left(A,B\right), (b',c)\in\text{Hom}\left(B,C\right) and (c',d)\in\text{Hom}\left(C,D\right). Then,

(c',d)\left((b',c)\circ (a,b)\right)=(c'd,)\circ (a,b')=(a,d)

and

\left((c',d)\circ (b',c)\right)\circ (a,b)=(b',d)\circ (a,b)=(a,d)

and so \circ is associative.

2) We know show that no matter how one defines \text{id}_A\in\text{Hom}\left(A,A\right) if \text{card }A\geqslant 2 that there exists some f\in\text{Hom}\left(A,A\right) such that f\circ\text{id}_A\ne f. To do this, let (a_1,a_2)=\text{id}_A and f=(a_2,a_3)\in\text{Hom}\left(A,A\right). Then, we note that

f\circ\text{id}_A=(a_3,a_4)\circ (a_1,a_2)=\overbrace{(a_1,a_4)}^{(*)}

But, if it were really an “identity element” we would have that (*)=(a_3,a_4) . Thus, if one choose a_3\in A-\{a_1\} then this equality is untrue and so \text{id}_A cannot be the desired identity element.

Example: Let \bold{Set} be defined as follows:

\text{ob}\left(\bold{Set}\right)=\text{Class of all sets},

\text{Hom}\left(A,B\right)=B^A, \text{id}_A is the identity function, and \circ is normal function composition. So, let us verify the axioms

a) Clearly we have defined \text{ob}\left(\bold{Set}\right) to be a class

b) Also, we have defined \text{Hom}\left(A,B\right) to be a set, namely the set of all functions f:A\to B

c) We have defined, for each A\in\text{ob}\left(\bold{Set}\right) a \text{id}_A, thus the only question is if it is really a morphism A\overset{\text{id}_A}{\longrightarrow}A. But, this is clear since the identity function is a map from A to itself.

d) For each A,B,C\in\text{ob}\left(\bold{Set}\right) we have specified the function

\circ_{(A,B,C)}:\text{Hom}\left(A,B\right)\times\text{Hom}\left(B,C\right)\to\text{Hom}\left(A,C\right)

so the question is whether or not this definition of a function is well-defined. And, it clearly is (we’ll show in the next non-example why this step shouldn’t be omitted when checking whether \bold{C} is a category)

So, we just need to check the functional axioms:

1) Clearly \circ is associative, since it’s regular function composition

2) Also, it’s clear that if f\in\text{Hom}\left(A,B\right) that \text{id}_B\circ f=f\circ\text{id}_A=f since \circ is normal function composition and \text{id}_A,\text{id}_B are the normal identity maps on A,B respectively.

Non-Example: Let us consider some \bold{C} with

\text{ob}\left(\bold{C}\right)=\{(1,\infty)\},

\text{Hom}\left((1,\infty),(1,\infty)\right)=\left\{x^2,\text{id}_{(1,\infty)}\right\},

\text{id}_{(1,\infty)} is the identity function, and \circ is normal function composition

I point out this example for one simple reason. It is easy to verify like all else before that

a) \text{ob}\left(\bold{C}\right) is a class

b) For each two \bold{C}-object there is an associated hom-set

c) For every object A, namely A=(1,\infty), the prescribed \text{id}_{A} is in fact in \text{Hom}\left(A,A\right)

1) The composition operation is clearly associative, being normal function composition.

2) The chosen identity element suffices.

Thus, from the looks of it \bold{C} is going to be a category. But then, you realize that our definition of \circ is not well-defined. Notice that by definition we must have that

\circ_{(A,A,A)}:\text{Hom}\left(A,A\right)\times\text{Hom}\left(A,A\right)\to\text{Hom}\left(A,A\right)

But, take A to be the only thing it can, (1,\infty), and notice that while (x^2,x^2)\in\text{Hom}\left(A,A\right)\times\text{Hom}\left(A,A\right) that x^2\circ x^2=x^4\notin\text{Hom}\left(A,A\right). Thus, the composition function is not well-defined.

The thing being, it’s easy when you prove that something is a category over and over and over again to get used to being “given” the objects, in the contrived sense of the word. Namely, you do an exercise “Prove… is a category”. So, you might take the given four tuple, and prove that it satisfies the two function axioms 1) and 2) paying nary a mind to a),b),c) or d) since in almost every other example they just worked. You need to be diligent, otherwise stupid examples like the above may trip you up. All in all, just because you say a function maps A to B does not mean it does.

Example: Every group \left(G,\star\right) induces a category \bold{C} where \text{ob}\left(\bold{C}\right)=\{G\}\text{Hom}\left(G,G\right)=G, \text{id}_G=e (where e is the identity element of G) and

\circ:\text{Hom}\left(G,G\right)\times\text{Hom}\left(G,G\right)\to\text{Hom}\left(G,G\right):(g,g')\mapsto g\star g'

So, now we need to check that this is actually a category

a) Clearly \text{ob}\left(\bold{C}\right) is a class. (recall informally that any set is a class and “sets of sets” are classes)

b) We need to check that for each A,B\in\text{ob}\left(\bold{C}\right) there is an associated set \text{Hom}\left(A,B\right), but the only A,B\in\text{ob}\left(\bold{C}\right) is G. But, as indicated we have that \text{Hom}\left(G,G\right)=G which is a set.

c) We have identified for every A\in\text{ob}\left(\bold{C}\right) (namely, G) an identity element \text{id}_A (the only choice this time being \text{id}_G=e. Furthermore, we see that \text{id}_A\in\text{Hom}\left(A,A\right) for every A\in\text{ob}\left(\bold{C}\right) (since e\in G)

d) Lastly, we notice that for each A,B,C\in\text{ob}\left(\bold{C}\right) we have defined a mapping

\circ_{(A,B,C)}:\text{Hom}\left(A,B\right)\times\text{Hom}\left(B,C\right)\to\text{Hom}\left(A,C\right)

The reason for this is that there is only one choice for (A,B,C) and that’s (G,G,G) and we’ve defined a mapping

\circ_{(G,G,G)}:\text{Hom}\left(G,G\right)\times\text{Hom}\left(G,G\right)\to\text{Hom}\left(G,G\right)

namely the multiplication map

\star:G\times G\to G:(g,g')\mapsto g\star g'

We now need to check that the four definitions of the tuples (see the actual definition if you don’t understand the tuple reference). Namely

1) We need to check that given any A,B,C\in\text{ob}\left(\bold{C}\right) that the associated map \circ_{(A,B,C)} is associative. But, as said before there is only one such map since there is only one choice for A,B,C namely A=B=C=G. Thus, we must only check that the map \circ_{(G,G,G)} is associative. Notice though that since \circ_{(G,G,G)} is actually the multiplication map \star that for any three morphisms G\overset{f,g,h}{\longrightarrow}G we have that

h\circ(g\circ f)=h\star(g\star f)=(h\star g)\star f=(h\circ g)\circ f

This is because we assumed that \left(G,\star\right) was a group, and so by definition \star is associative.

2) We need to check that for any A,B\in\text{ob}\left(\bold{C}\right) and any morphism A\overset{f}{\longrightarrow}B that \text{id}_B\circ f=f\circ\text{id}_A=f. But, our only choice is A=B=G and so for any f\in\text{Hom}\left(G,G\right) we have that

\text{id}_G\circ f=e\star f=f=f\star e=f\circ\text{id}_G

from where the second axiom follows.

3) Clearly since there is only one hom-set (this is the categorical vernacular for any set of the form \text{Hom}\left(A,B\right)) they are pairwise disjoint

Thus, as defined \bold{C} is, in fact, a category

Remark: Note that this shows that the morphisms need not be functions from A to B as they were in all the preceding examples.

Note also that there was no mention of the fact that G had inverses, the only thing that was important was the associativity of the multiplication and the existence of an identity element. Thus, the above applies equally well for things called monoids which are just sets with an associative binary operation and an identity element. I’m going to do at least one or two posts on them immediately after this one, so I delay their explicit mention until then.

References:

1. Adámek, Jiří, Horst Herrlich, and George E. Strecker. “Categories and Functors.” Abstract and Concrete Categories: the Joy of Cats. New York: Wiley, 1990. Pr

Advertisements

October 7, 2010 - Posted by | Algebra, Category Theory | , ,

5 Comments »

  1. […] intuition about categories, but to set down some of the notation and recurring characters. We have already defined categories (although, somewhat unsatisfactorily, but it will have to do) and motivated […]

    Pingback by Examples of Categories (Revisited) « Abstract Nonsense | November 2, 2011 | Reply

  2. […] of now, with just the bare definition of categories, we have little to work with. From our current standpoint, all morphisms are created […]

    Pingback by Types of Morphisms « Abstract Nonsense | December 27, 2011 | Reply

  3. […] that we know what categories are we’d like to define the appropriate sub notion, of when a smaller category sits inside a […]

    Pingback by Subcategories and Skeleta « Abstract Nonsense | December 27, 2011 | Reply

  4. […] Roughly what we we shall see is that direct systems over a fixed preordered set form a nice little category and limits shall be functors on this category. Moreover, what we shall see is that there is a […]

    Pingback by Category of Directed/Inverse Systems and the Direct/Inverse Limit Functor « Abstract Nonsense | December 27, 2011 | Reply

  5. […] is a simple example of why in general categories aren’t balanced. Indeed, the monos and epis in are the injective and surjective […]

    Pingback by The Exponential and Trigonometric Functions (Pt. II) « Abstract Nonsense | May 5, 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: