To get started, what is category theory?
Back in grad school, I spent some time working with a thoroughly insane guy named John Case who was the new department chair. When he came to the university, he brought a couple of people with him, to take temporary positions. One of them was a category theorist whose name I have unfortunately forgotten. That was the first I’d ever heard of cat theory. So I asked John what the heck this category theory stuff was. His response was “abstract nonsense”. I was astonished; a guy as wacky and out of touch with reality as John called something abstract nonsense? It turned out to be a classic quotation, attributed to one of the founders of category theory, Norman Steenrod. It’s not an entirely bad description.
Category theory is one of those fields of mathematics that fascinates me: where you take some fundamental concept, and abstract it down to its bare essentials in order to understand just what it really is, what it really means. Just like group theory takes the idea of an algebraic operation, strip it down to the bare minimum, and discovering the meaning of symmetry; category theory looks at what happens if you take the concept of a function as a mapping from one thing to another, and strip it down to the bare minimum, and see what you can discover?
The fundamental thing in category theory is an arrow, also called a morphism. A morphism is an abstraction of the concept of homomorphism, which I talked about a bit when I was writing about group theory. We take that concept of a function mapping from one set of values to another, and strip it down: the basic concept is something that provides a map from one thing to some other thing – and that’s all we want.
In classic style, we’ll define a category C as a tuple: (O, M, º), where:
- O, or Obj(C), is a set of objects. Objects are anything – we don’t care. Anything that we can define maps over.
- M, or Mor(C) is a set of arrows or morphisms. Every arrow has a unique source and a unique target, both of which are objects in M. Given two objects a and b in O, we also write Mor(a,b) for the set of morphisms from a to b. To talk about a specific morphism from a to b, we write it as “name : a → b”; as in “f : int → int”.
- º is a binary operation that is the abstraction of function composition; º is a mapping from (Mor(a,b), Mor(b,c)) to Mor(a,c). It’s got the basic properties of function composition:
- Associativity: (∀ f : a → b, g : b → c, h : c → d) h º (g º f) = (h º g) º f
- Identity: (∀ a,b ∈ O(C)) (exists 1a, 1b ∈ Mor(C)) (∀ f : a → b) 1b º f = f = f º 1a.
One neat little trick to simplify things is that we can actually throw away Obj(C), and replace it with the set of identity morphisms: since there is exactly one identity morphism per object, there’s no real need to distinguish between the identity morphism and the object. It’s a nice trick because it means that we have nothing but morphisms all the way down; but it’s really just a trick. We can talk about Obj(C); or Id(C); but we still need to be able to talk about the objects in some way, whether they’re just a subset of the morphisms, or something distinct.
Now, we get to something about category theory that I really don’t like. Category theory is front-loaded with rather a lot of definitions about different kinds of morphisms and different kinds of categories. The problem with that is that these definitions are very important, but we don’t have enough of the theory under our belts to be able to get much of a sense for why we should care about them, or what their intuitive meaning is. But that’s the way it goes sometimes; you have to start somewhere. It will make sense eventually, and you’ll see why these definitions matter.
There are a lot of special types of morphisms, defined by properties. Here’s the basic list:
- A monic (or monomorphism) is an arrow f : a → b such that (∀ g1 , g2: x → a) f º g1 = f º g2 ⇒ g1 = g2. (That is, if any two arrows composed with f in f º g end up at the same object only if they are the same.)
- An epic (or epimorphism) is an arrow f : a → b such that (∀ g1 , g2: b → x) g1 º f = g2 º f ⇒ g1 = g2. (This is almost the same as a monic, but it’s from the other side of the composition; instead of (f º g) in the definition, it’s (g º f).)
- An isomorphism is an arrow f : a → b such that (∃ g : b → a) f º g = 1b ∧ g º f = 1a.
- An endomorphism is an arrow f : a → b such that a = b.
- An automorphism is an arrow that is both an endmorphism and an isomorphism.
One last definition, just because it gives me a chance to point out something useful about category theory. A functor is a morphism in the category of all categories. What that means is that it’s a structure-preserving mapping between categories. It’s neat in a theoretical way, because it demonstrates that we’re already at a point where we’re seeing how category theory can make it easier to talk about something complicated: we’re using it to describe itself! But the concept of functor also has a lot of applications; in particular, the module system of my favorite programming language makes extensive use of functors.
In Ocaml, a module is something called a structure, which is a set of definitions with constrained types. One of the things you often want to be able to do is to write a piece of code in a way that allows you to make it parametric on some other structure. The way you do that is to write a functor: a “function” from a structure to a structure. For example, to implement a generic binary tree, you need a type of values that you’ll put in the tree; and an operation to compare values. The way you do that is to write a functor which takes a structure defining a type and a comparison operator, and mapping it to a structure which is an implementation of a binary tree for that type and comparison.
The Ocaml functor is a category theoretic functor: category theory provides an easy way to talk about the concept of the compile-time “function” from structure to structure.
Thanks so much! I’ve been vaguely obsessed with cat theory ever since I got interested in the semantics of programming languages; cat theory seems to crop up all over the place in that field. You’ve done fantastic job of boiling down and summarizing the basics, especially the definitions of the different kinds of morphisms.
Quite a task you’ve undertaken! I’m looking forward to following it. Perhaps I’ll understand it better than the other times I’ve looked at category theory (in an Algebraic Topology course and in an Abstract Algebra course.) The book I picked up that has helped me some is Hilton and Stammbach’s “A Course in Homological Algebra” from Springer-Verlag’s GTM series. I’m sure your examples from programming will be lost on me, but I’ll stick with it.
Thanks again, and good luck!
One of the nuisances of category theory is that you have to be careful about saying things like “the category of all categories” — you have to start talking about small categories (in this case, the category of all small categories), otherwise you run into a Russell’s Paradox type of problem.
I think you missed one of the most important definition in category theory. It is the natural transformations, the thingiez that go between functors. Among natural transformations, the thingiez that are invertible are more important.
Category theory is all about isomorphism; the beauty here is that we can just forget about the equality of thingiez and all we need is just that the thingiez that are equal up to an isomorphisim.
I feel stupid – what does a big V symbolise?
∀ is the quantifier symbol meaning “for all”;
∃ is the quantifier symbol meaning “there exists”;
∧ is “logical and”; ∨ is “logical or”.
Please continue with more on this. Category theory was one of the topics I seriously struggled with in graduate school, and it was never explained to me what it was or why it said anything useful – whenever I heard category theory referred to elsewhere it was always either incomprehensible gobbledegook or tautologies.
I suppose an actual course on category theory might have helped, but the assumption seemed to be that everyone knew basic category theory when walking in the door, and no one in the department was actually interested in category theory enough to teach it. The brief overview of category theory in Lang didn’t help either. I mean, knowing enough group theory you at least know why you’d want to distinguish the special types of morphisms that you do above, but I’m still stuck on why you’d want to abstract away the interesting Obj(C) bits – the groups, rings, and fields. It seems to me that anything interesting you’d want to say about a category depends strongly on the nature of the elements of Obj(C); so strongly, that I don’t see what we get with CT.
I tried taking another stab at category theory after wrapping my head around what a Monad did in Haskell, and getting comfortable using and creating them, having heard that the name “Monad” came out of CT. However, my newfound understanding of the Haskell concept helped me not a bit.
“One last definition, just because it gives me a chance to point out something useful about category theory.”
I think that functors are, unarguably, the most useful thing about category theory, since they unify all the categorical notions of limits of diagrams and various other important beasties.
Yay! Maybe if I keep reading I’ll finally understand Haskell. I feel stupid too: What does ‘1b’ symbolize?
David:
1b is the identity morphism for the object b: the unique morphism such that for all other arrows f, if f : a → b, then 1b º f = f.
“Category theory is front-loaded with rather a lot of definitions about different kinds of morphisms and different kinds of categories.”
I learned CT pretty early on in my mathematical learning, but it took until the final year of my undergrad course until I found applications of it. And really, when it comes to basic-intermediate category theory, it’s not the theory that’s useful, more the general descriptive language. That’s my opinion anyway – the really cool aspects of it are not in the pure theory itself but rather as it applies to other areas. And you can use it to look at and think about so many elementary mathematical subjects in a fairly fresh way (topological constructions, object-oriented programming, algebras, combinatorics), with the notable exception of stuff near analysis (with the exception of Lawvere’s pretty funky paper relating the existence of extensions of Lipschitz functions to the existence of ends and coends for functors).
Until you get on to the more advanced stuff – then it’s all cool in a whole bunch of intrinsic ways : )
And I’d say that in terms of cool stuff at the start, it’s universal constructions that are the most useful (in terms of conceptual time-saving). Maybe limits. Anyway.
Anyway,
Stephen
(oh yeah, just to disclaim: I’m not a category theorist, so I’d double check everything I say before believing it).
It seems to me (as someone who knows practically no category theory) that you have left out a few concrete examples of functors that would make the idea immediately obvious.
My understanding is that a functor is a way to associate a structure of some type with a structure of another type.
The simplest case is to associate an integer with a structure, and the simplest case of that is to associate a integer (the cardinality of a set) with a finite set.
Slightly more interesting (because it uses more of the structure) is to associate an integer with a manifold (the dimension of the manifold).
Both of these are so obvious they probably seem trivial. A slighly less trivial case is to associate a different integer with a manifold — the genus of the manifold (you know, the standard business of spheres vs torus vs “two-handled toruses” and so on).
This third example starts to give some justification as to why this stuff might be useful.
If we can map a structure of some type (a manifold. a group, whatever) to a structure of some other type (in all three cases above this was an integer, but in more advanced cases we might, say, map a manifold onto a group) then
* we might have a nice way to categorize when certain theorems are or are not valid for that structure — for example certain theorems about manifolds are valid for genus 0 but not for genus non-zero
* if we are trying to figure out if some structure is isomorphic to some other structure, and our [appropriately constructed] functor maps them to two distinct entities, then they can’t be isomorphic. Of course if they are mapped onto the same entity, then it’s back to the drawing board.
So my entirely biased and ignorant view is that the category theory is simply some background terminology, that the more advanced category theory qua category theory is not very interesting, and that the real magic and interest is in devising ever more new and unexpected functor (eg the subjects of cohomology and cohomotopy).
Sort of, but the examples you give aren’t really appropriate –you can say that the integers form a category and define morphisms appropriately, but it’s not a very useful category, and the functors you would obtain in your examples are not informative.
This isn’t really true. Category theory is a high-level form of generalization, and can be extremely useful in that regard. There are plenty of examples where problems become easier by considering them in more generality (I think Grothendieck was of this philosophy).
For example, we can consider abelian categories; many of the categories we wish to consider (modules, groups, commutative rings, etc.) are such. Now with certain theorems, you can prove the result separately in each category, or you can show that it holds for all abelian categories. Of course, there aren’t too many theorems that hold at such high levels of generality, but you do get some results you want this way.
As far as high-level category theory goes, there is a subset of the algebraic topologists interested in, for example, n-categories (which it’s still not entirely clear how to define correctly, last I heard). My former office mate was one of those.
The importance of categories, I see it, comes from two things. The first is that they let you abstract structure, so you can prove things abstractly and immediately know that they will apply universally. More importantly, categories provides a framework for understanding how objects relate to each other. I don’t know how successful this will turn out, but here’s a shot at an explanation of what that means in practice. If you pick an object in a category, you can look at the set of all maps into that object. Thus, if the fixed object is A, then to any object B you have the set Mor(B,A). This is a (contravariant) functor from your category to the category of sets. In a sense, rather than studying the object A, this functor is telling you how everything else relates to A. Then, there’s a neat result called Yoneda’s lemma which tells you that by studying such functors (and natural transformations between them), you know everything about A itself. With this in hand, you can start looking at arbitrary functors to the category of sets and ask if they’re equivalent to a functor given by a particular object in the category. This leads to all sorts of cool stuff like limits and universality.
A cool (to me, at least) illustration of both of these things is to ask what does it mean for a set to be a group. One way to answer this is that there exist various maps like a product : G X G -> G and an inverse G -> G that have relations that can be expressed in terms of certain diagrams. Once we’ve done this, however, we can see that we used almost no properties of set other than the existence of the product of sets. Thus, we can define a “group object” in any category that has such a product (with some nice properties that I’m eliding).
We can also try to do things in terms of functors as above. Look at the functor to the category of sets given by the set G. Then, given a set A, we associate the set of functions from A to G. But, because G is a group, we can multiply such function. In fact, these function, ie, Mor(A,G), for a group. Thus (with a teeny bit more work), instead of a functor to sets, we have a functor to the category of groups. We can define a group, then, to be an object whose associated functor to sets is really a functor to groups. Then, we can say that a group object in any category is a contravariant functor to the category of groups such that, when thought of as a functor to sets (by forgetting the group structure) it is equivalent to the usual functor to sets descibed in the first paragraph.
Whew. So, what’s neat about this? Yoneda’s lemma tells us that these two definitions are exactly the same thing. And, really, there was nothing all that special about groups here; we can do this for almost anything. Of course, I don’t know any use for this outside of rather abstract mathematics, but if you made it through all of that, I bet you thought it was at least a little cool, too. Or maybe not.
First up, thanks for the great articles on category theory. I’m just starting to head my head around the topic and your clear and concise posts have been great for helping me understand the motivation behind this “abstract nonsense”. This makes grokking the rather dry definitions that much easier.
Also, I couldn’t help but notice your mention of John Case in your opening paragraph. I think you studying with him in grad school makes us academic cousins of sorts. If you look at his academic genealogy page you’ll see that he was the supervisor of Arun Sharma, one of my PhD supervisors. Small world!
My name is thiagarajan.I am doing my final year undergrad.
I have a question about the definition of isomorphism.
I gather,1b is a ‘function’ which maps b to itself(1b:b->b) and f o g is a composition of functions f and g.In one of the previous comments you mention ^ is used as “logical and” operator.What does the logical and of two functions mean? Is there something that i am missing in that definition??
ok,i understood what it means…
function f maps a to b and g maps b to a.So their composition f o g maps a to a and similarly g o f maps b to b.
feeling pretty stupid right now…
I have a question about the definition of monic and epic.
When we define a monic as f . g1:A->B = f . g2:A->B,how should we look at B?? Many arrows can be defined from a set of real numbers to a set of real numbers.if g1 and g2 are two such arrows,does f . g1:A->B = f . g2:A->B hold??
In the second part of your definition:
M, or Mor(C) is a set of arrows or morphisms. Every arrow has a unique source and a unique target, both of which are objects in M.
Don’t you mean “both of which are objects in O”?
How is the binary operation defined when Mor(a,b) and Mor(b,c) are nonempty but Mor(a,c) is empty?
I have recently started reading your blog and I like it very much. Thank you for this wonderful job.
Although, there is very little chance that anybody would notice this, but I am a bit stuck at the concept of morphisms and compositions.
The first thing I want to ask is that is morphism a mapping from a single object to a single object only?
Secondly, in defining composition, you say about identities:
(∀ f : a → b) 1b º f = f = f º 1a.
so, is it correct to say:
1a º f = f = f º 1b
What I mean to say, is composition commutative wrt identities?
Nice blog there, I just have one question:
When defining a category, doesn’t one need to define arrow equality before defining everything else? That is shouldn’t one say what (=) means when one says 1b º f = f? The whole notion of composition, identity, commutative diagrams are based on arrow equality, yet I see no requirement for defining it.
Keep up the good work!