(SR) A Category Theory Primer

Q

QuarkHead

Remedial Math Student
Valued Senior Member
This is a subject I have been learning recently, and one that I really like.

First some history, though my dating may be wildly wrong. Beginning some time in the 1800's, mathematicians sought to categorize areas of mathematics into ever and ever smaller "units" of study. So, it was realized that there were distinct areas of study like monoids, groups, rings, fields, vector spaces, topological spaces etc., each with their own semi-unique properties, defined by the allowable operations on them, and the maps between them.

Then, around 1945, a guy named Saunders Mac Lane asked the simple question: is it possible to come up with a meta-language that will unify all these (by now) different areas of mathematics? He decided that the answer is "yes", and that this language should be called category theory. So let me give a quick definition, and then do some more rambling.

A category $$\mathcal{C}$$ is a collection of mathematical objects with the property that:

for any pair of objects $$X,\;Y \in \mathcal{C}$$, there is a "mapping" $$f:X \to Y$$ where $$f$$ is called a morphism in $$\mathcal{C}$$;

for every object $$X \in \mathcal{C}$$ there is an identity morphism $$\text{id}_X: X \to X$$;

for every $$X,Y,Z \in \mathcal{C}$$, with $$f:X \to Y$$ and $$g:Y \to Z$$, then the composition of morphisms $$(g \cdot f): X \to Z$$ makes sense;

if $$f:W \to X,\; g:X \to Y,\; h: Y \to Z$$, then $$h \cdot (g \cdot f) =(h \cdot g) \cdot f)$$;

if $$ f:X \to Y$$ then $$f \cdot \text{id}_X = f,\;\; \text{id}_Y \cdot f = f$$.

So, first some notational housework; I will always compose morphisms right-to-left. That is, $$g \cdot f$$ means do $$f$$ first, then $$g$$. Notice also that I will sometimes refer to morphisms simply as arrows. You'll see why shortly.

OK, so what are these so-called objects in these so-called categories? Although this question is more profound than it might appear at first sight, for now we can take them to be: a set is an object in a category called Set, whose morphisms are set functions, a group is an object in a category called Grp, whose morphisms are group homomorphisms, a topological space is an object in a category called Top, whose morphisms are continuous functions, and so on.

Notice that, for every category in this sense, I must specificy the exact nature of these morphisms, as they are objects, in this case sets, in the category. This will become clear, if I am allowed to continue.

Notice too that, if this project of generalization is not to be doomed from the outset, we would be wise not to concentrate too closely on the precise definition of our categorical objects; all we really care about are the arrows - the morphisms - hence category theory is sometimes referred to as "arrowology". We would be even wiser not to even think about the elements in these objects (though often it is helpful when constructing proofs).

So, category theory offers us a "function" from one category to another, like this: Let $$ \mathcal{C},\; \mathcal{D}$$ be categories. Then the mapping $$ F: \mathcal{C} \to \mathcal{D}$$ is called a functor.

Now functors are very respectful creatures - they respect everything in sight.

So, if $$ f: X \to Y$$ is a morphism in $$\mathcal{C}$$, and if there is a functor $$F:\mathcal{C} \to \mathcal{D}$$, then $$F(f): F(X) \to F(Y)$$. That is, the functor$$F$$ respects morphisms and their domains and codomains.

It follows that this functor respects the identity: If $$ id_X: X \to X \in \mathcal{C}$$, then $$F(id_X) = id_{F(X)}: F(X) \to F(X) \in \mathcal{D}$$

Functors also respect composition: If $$(g \cdot f): X \to Z \in \mathcal{C}$$ is defined, then $$F(g \cdot f)$$ is also defined, and $$ F(g \cdot f) = F(g) \cdot F(f) \in \mathcal{D}$$

Functors also respect associativity in the obvious way; I shan't insult you by writing this out!

I have a lot more to say on this subject, if anyone is interested, but now I'm going for a beer or five. Then I have to figure out how to offer commutative diagrams.
 
Umm, Ok. No interest? Undaunted, I shall press on for a bit.

Let me first list a few familiar categories;

Set is the category of sets whose morphisms are set functions;

Mon is the category of monoids whose morphisms are monoid homomorphisms;

Grp is the category of groups whose morphisms are group homomorphisms;

K-Vec is the the category of vector spaces over the field K whose morphisms are linear transformations;

and so on.

Notice that we may think of the objects in these categories as structured (or algebraic) sets whose morphisms are structure-preserving maps. Such categories are referred to as concrete categories. So is there another sort of category?

The answer is yes. Consider a set with pre-order. Then, for any pair of elements $$x, y $$ in the set, where $$x \le y$$, then provided only that I allow myself to interpret the relation $$x \le y$$ as $$x \to y$$, then the axioms of category theory allow me to think of a pre-ordered set as a category whose objects are generic set elements in a category called Preord, and whose morphisms are the relation $$\le$$.

Notice that the exact nature of these "generic set elements" aka the categorical objects are pushed aside; we care nothing for them. This category is exclusively concerned with the arrows; it is the category of pre-orders. It is obviously not concrete.

There is a related category, called Pos, the category of partial orders, where all the above applies, but where we may also need to consider the following poset axiom; is $$x \le y$$ and $$y \le x$$ then $$ x = y$$. In strictly category-theoretic terms, we need to interpret this with caution, so I will have to defer this for a bit.
 
Last edited:
Metamaths. Cool :cool:.

Does it apply to models in other domains (business, engineering, linguistics, etc etc etc)?
 
Pete,
the honest answer to your question is that I don't know. I guess any domain that can be written as a deductive system, with rules of inference, for example, may be susceptible to this approach.

It is most certainly true that any system that can be written as a Boolean algebra would be. But I don't know enough about economics, engineering etc to know whether this will apply. It might be fun to try, for those who do understand these areas.

Anyway, I can't decide whether to proceed - this subject hasn't exactly hit the headlines, and from now on it gets sufficiently hard to require high motivation.

Any thoughts, anyone?
 
I think it's enough as is.
No all interesting and thought-provoking topics are conversation-generating. This doesn't diminish their value, only their short-term visibility.
 
Anyway, to proceed. I mentioned the category Preord and the category Pos, preorders and partial orders, respectively. Note that, whereas I can find as many preordered or partially ordered sets as I like, there is only one category Preord, and only one category Pos. This strongly underlines the fact that the objects in these categories are merely tokens, book-keeping devices, if you like. This is true of any category; a category is characterized by the properties of its morphisms and not by those of its objects.

OK. The collection of all morphisms between any pair of objects in any category forms a set. This is called a hom-set, and is realized as follows.

Let $$\mathcal{C}$$ be an arbitrary category, and let $$A,B$$ be objects therein. Then the set of all morphisms $$A \to B$$ is written as $$Hom(A,B)$$.

But $$Hom(A,B)$$ is a set, whereas $$\mathcal{C}$$ is an arbitrary category. I therefore need a functor $$\mathcal{C} \to \text{Set}$$. OK, what follows is crucial to the development of our theory, so I'm going to go through it in excruciating detail.........

I define the functor $$Hom(A,-): \mathcal{C} \to \text{Set}$$ which sends every morphism out of $$A \in \mathcal{C}$$ to the collection of Hom-sets $$Hom(A,B),\; Hom(A,C),\;
Hom(A,D)..... \in \text{Set}$$.

So, suppose that $$k: A \to B,\; f:B \to C, \;g: C \to D \in \mathcal{C}$$. Recalling that composition of morphisms only makes sense if the co-domain of one is the domain of another, I can picture it like this

Hom1.png


So that $$k \in Hom(A,B),\;\; f \cdot k \in Hom (A,C),\;\; g \cdot f \cdot k \in Hom(A,D)$$.

But Hom-sets are sets, so we need a set function - a morphism in Set - that sends each of these Hom-sets onto the "next" in the sequence. Let's say that, for $$f:B \to C \in \mathcal{C}$$, since functors also act respectfully on morphisms, we agree to write our set function as $$ Hom(A,-)(f) \equiv Hom(A,f): Hom(A,B) \to Hom(A,C) \in \text{Set}$$.

In other words

Hom3.png
.

Notice that I have written underneath these arrows an alternative notation: $$Hom(A,f) \equiv f_*$$. This is called the "pushforward" of $$k \in Hom(A,B)$$ to $$f \cdot k \in Hom(A,C)$$, and so on; this is easily seen by "chasing" round my triangular diagram.

Therefore $$ f_*(k) = f \cdot k$$ etc. This last equality defines the functor $$Hom(A,-)$$ to be a covariant hom-functor. Or if you prefer a definition: a hom-functor is covariant iff it sends morphisms in the source category to pushforwards in the target category. (For reasons I'm not clear about, militant category-theorists use source and target in this situation, and domain/co-domain in a restricted sense that eludes me)

Anyhoo, this is already over long, maybe more later.

Incidentally, if these png's don't render for you, let me know. I use Firefox under Linux, it's possible they don't display for other browsers/OSs
 
So. We saw that the image of all morphisms from some fixed object $$A \in \mathcal{C}$$ under the action of some functor $$\mathcal{C} \to \text{Set}$$ induces a pushforward of sets in Set, which in turn defines this functor (we called it $$Hom(A,-)$$ as covariant.

Let's now look at the situation in $$\mathcal{C}$$ where we want to consider all morphisms to a fixed object, say $$A$$. We might think of it like this:

hom3a.png


So how am going to label these arrows as composites of each other, bearing in mind I need the domain of one to be the co-domain of another? The only way to do this is to work right-to-left as follows:

Hom2.png
.

Notice that the composite $$h \cdot g$$, for example requires an anticlockwise rotation of the h-arrow such that the "tail" of h is dragged back along g. I will call this the "pullback" of h along g.

Now the morphisms into $$A \in \mathcal{C}$$ become the hom-sets $$Hom(B,A),\;\;Hom(C,A),$$ etc in Set.

So I define the hom-functor $$Hom(-,A): \mathcal{C} \to \text{Set}$$, where once again $$Hom(-,A)(g) \equiv Hom(g,A)$$, etc are set functions. I write:

Hom4.png


Notice that the pullback $$Hom(g,A) \equiv g^*$$ and, since $$h \in Hom(D,A),\;\;h \cdot g \in Hom(C,A)$$, then by my second triangle diagram, $$g^*(h) = h \cdot g$$ (contrast this with the puhforward where I had $$g_*(h) = g \cdot h$$)

This defines the hom-functor $$Hom(-,A)$$ to be a contravariant hom-functor.

Finally, though I don't time right now to run through it in too much detail, you might like to see how covariant and contravariant hom-functors are related. Here, chew on this:

{permission to upload another image denied. Drat}
 
OK, so here it is, the relation between the covariant and contravariant hom-functors

Hom5-1.png


So here's an easy exercise for anyone following this thread. Given that $$h: D \to A $$ is an element in $$Hom(D,A)$$, and all that has been given so far, show that this diagram commutes. That is, given $$h \in Hom(D,A)$$, then whether you follow the arrows via $$Hom(D,B)$$ or via $$Hom(C,A)$$, you will always land on the same set element in $$Hom(C,B)$$.
 
Very nice explainations. I don't follow it after about the half way point but I got things like "It's the morphisms which are important" point before you specifically stated it. I'll continue to furrow my brow and try to get my head around it.

Have you ever read 'Mathematical Physics' by Geroch. A friend recommended it to me and for £5 from Amazon I got a copy. He does a lot on categories (that being the title of the first chapter!) so I realised I was out of my depth with that purchase, short of a very big effort I don't have much time for.
 
Last edited:
AlphaNumeric said:
Very nice explainations. I don't follow it after about the half way point but I got things like "It's the morphisms which are important" point before you specifically stated it.
Click to expand...
Thank you. You are obviously a lot smarter than me, as it took me a while to see that the structure of a structured set can always be written down in terms of arrows.

Have you ever read 'Mathematical Physics' by Geroch.
Click to expand...
No, maybe I should look out for it.

Anyway, folks, I was unfair to give my last post as an exercise. I show how it's done, as category theory makes heavy use of these commutative diagrams for proof.

Look at my diagram. Suppose $$h: D \to A,\;\; h \in Hom(D,A)$$.

Notice that my horizontal arrows are covariant, my vertical arrows are contravariant. Working along the top, set $$Hom(D,f) = f_*$$ . I find that $$f_*(h) = f \cdot h \in Hom(D,B)$$ as per definition of pushforward.

Now go down the RHS, set $$Hom(g,B) = g^*$$. Then by the definition of pullback, $$g^*(f \cdot h) = (f \cdot h) \cdot g \in Hom(C,B)$$

Now let's go down the LHS. Again, $$Hom(g,A) = g^*, \;\; g^*(h) = h \cdot g \in Hom(C,A)$$.

And along the bottom I will have again $$Hom(C,f) = f_*$$ so that $$f_*(h \cdot g) = f \cdot (h \cdot g)\in Hom(C,B)$$.

So the diagram commutes iff $$ (f \cdot h) \cdot g = f \cdot (h \cdot g)$$. But this equality holds, since, by definition, composition of morphisms is associative
 
Last edited:
OK, I don't want to go into overload; but lemme just make this point clear.

We looked at covariant and contravriant Hom-functors. But it is a fact that any functor $$F: \mathcal{C} \to \mathcal{D}$$ is either covariant or contravariant. This entirely depends on whether the arrows in $$\mathcal{C}$$ are reversed or not in the target category $$\mathcal{D}$$ when considered as images under $$F$$.

This would appear to violate the principle that functors respect domains and codomains. This is not the case, but I don't really want to get into that; if you're interested look into "opposite categories".
 
Well, I'm not sure anyone wnats me continue, so for now I'll content myself with a couple of observations.

I skated over the opposite category, lemme rectify that now in order to make a point.

To each category $$\mathcal{C} \; \ni A,\;B$$ I can associate the category $$\mathcal{C^{opp}}\; \ni A,\; B$$ such that, for every arrow $$f: A \to B \in \mathcal{C}$$ there is a corresponding arrow $$ f^{opp}: B \to A \in \mathcal{C^{opp}}$$.

Then for some covariant functor $$F:\mathcal{C^{opp}} \to \mathcal{D}$$ the images of arrows in $$\mathcal{C^{opp}} $$ are turned around in the target category.

It is merely a notational convenience to define the contravariant functor $$G:\mathcal{C} \to \mathcal{D}$$, where the images of the arrows in the source category are turned around by the functor in the target category. It saves writing all those opps!

Recall also we looked at the pushforward and the pullback. So, the category/opposite category pair and the pushforward/pullback pair are but two examples of a general phenomenon in category theory referred to as duality; every statement, or concept if you prefer, has its dual. If you want me to continue, we will meet some more examples.

Let me also make the following perhaps startling claim: militant category theorists are inclined to view what we Earthlings call equality with some suspicion in that it is unduly restrictive. Rather they seem to feel that identical up to a natural isomorphism is usually more appropriate, and often the best that can hoped for.

So I may as well give you the category-theoretic definition of isomorphism, which should create no difficulties; let $$X,\;Y \in \mathcal{C}$$ with $$f: X \to Y,\;\; g: Y \to X$$.

Then if it is the case that $$g \cdot f = id_X$$ and that $$id_Y = f \cdot g$$ one says that f and g are mutual inverses, $$g = f^{-1}$$, say, and f is an isomorphism. Therefore X and Y are isomorphic as objects.
 
Anyway, just in case you might be thinking that category theory is just for weirdos and hippies, take a look at Alexander Grothendieck (he's seated in the middle), one of the all-time greats in the subject (among other subjects).
 
So I want to say a little about limits. We'll start like this:

Consider some set, pre-ordered by divisibility. That is, $$x \le y$$ iff x divides y. I will write x|y for this condition. If division is defined on our set, for some pair of elements x and y, we may be able to find the highest common denominator hcd(x,y) where, by construction, hcd(x,y)|x and hcd(x,y)|y. So that $$\text{hcd}(x,y) \le x,\;\text{hcd}(x,y) \le y$$.

Now if there is some other element c in our set such that c|x and c|y, then of necessity, c|hcd(x.y). That is, $$c \le \text{hcd}(x,y)$$

Let's generalize to any pre-order. Define the element $$x \wedge y$$ such that $$ x \wedge y \le x,\; x \wedge y \le y$$. Then again if there is some element c such that $$c \le x,\; c \le y$$, then again I will insist this induces the relation $$c \le x \wedge y$$. the creature $$x \wedge y $$ is called the greatest common bound for x and y, or, if we're trying to impress our girlfriends, the infimum of x and y

But we are doing category theory, so let's replace our binary relations with arrows
Let's have a picture of this:
limit0.png


The dashed verical arrow denotes the "necessity" bit of my argument.

Let's generalize even further, and define the category theoretic product $$A \times B$$. Then this is the infimum in a pre-order, it is the Cartesian product in the category of sets, it is the direct product in the category of groups, it is the direct sum in the category of abelian groups, it is the space with the product topology in the category of topological spaces.......... You get the picture.

Now we know that each of these constructions comes equipped with "projections" $$ \pi_A: A \leftarrow A \times B$$ and $$\pi_B:A \times B \rightarrow B$$

In every case, we have the same universal property; iff there are arrows $$f:C \to A $$ and $$ g:C \to B$$, then there is an induced arrow $$\varphi:C \to A \times B$$ like this:
limit1-1.png
such that $$\pi_A \cdot \varphi = f$$ and $$ \pi_B \cdot \varphi = g$$

The induced (dashed) arrow $$\varphi$$can be shown to be a unique isomorphism. Right. In general, in this situation, one is not obliged to restrict to binary products.

Let's see how this works. Generalize the categorical product as follows:

lim3.png


But here I need to know what I mean by the index "i". So I define an index set $$I \ni i,\; j,......$$. As this is an object in Set, I need a functor from Set to whatever category I'm working in, like $$F:I \to \mathcal{C}$$ such that for each $$i,\;j \in I$$ I will have that $$F(i) = A_i \in \mathcal{C}$$.

OK, I have run out of image permissions, luckily for you. But let me just say that these are all examples of categorical limits; let me further remind you that in the "real world" only functions, and functions only, can have limits.
 
Let me expand my las diagram as
lim2.png


So, finally, I define a limit for the functor $$F: \text{Set} \to \mathcal{C},\;i,j \in I \in \text{Set}$$, where $$ F(i) = A_i$$ for all $$A \in \mathcal{C}$$ by the following diagram
lim4.png
oniy if everything in sight commutes.

I wanted to talk about limits to illustrate the duality principle; if there are limits, then there are colimits.

These we extract in the same way, using the category theoretic notion of the coproduct. This is a generalization of the supremum in a preorder, the disjoint union of sets, the free product of groups and of monoids, the disjoint union topology of topological spaces etc. (Some of these constructions may be unfamiliar to you - I am happy to try and explain if anyone wants.)

So we end up with the diagram where arrows in the above are turned around, namely

lim6.png


where again I require everything in sight to commute. This is a colimit for the functor F.

P.S. I used xy-pic for these diagrams. It is available as a free down-load for at least Windows and Linux/Unix. If you want to try it, PM me for installation and usage guidance
 
Last edited:
Another very trendy thread. To those new to category theory and the types of arguments within it, I can't stress enough how handy it is to get to grips with the diagrammatic approach. If you take a little time to master this, then the rest of the subject is much more approachable!
 
You must log in or register to reply here.
Back
Top