As I mentioned a few posts ago, I recently changed jobs. I left Google, and I’m now working for foursquare. Now that I’m done with the whole job-hunting thing, and things are becoming relatively saner and settling down, I’m trying to get back to blogging.
One thing that I’ve been wanting to spend some time learning about is Topoi theory. Topoi theory is an approach to building logic and mathematics using category theory as a fundamental basis instead of set theory. I’ve been reading the textbook Topoi: The Categorial Analysis of Logic (Dover Books on Mathematics)
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 silly and sarcastic, but it’s also not an entirely bad description. Category theory takes abstraction to an extreme level.
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. Category theory takes the concept function mapping from one set of values to another, and strips it down to itsbarest essentials: the basic concept of something that maps from one thing to some other thing.
The obvious starting point for our exploration of category theory is: what the heck is a category?
To be formal, a category 
-
(or
) is a set of objects. Objects can be anything, so long as they’re distinct, and we can tell them apart. All that we’re going to do is talk about mappings between them – so as long as we can identify them, it doesn’t matter what they really are. We’ll look at categories of sets, of numbers, of topological spaces, and even categories of categories.
-
(or
) is a set of morphisms, also called arrows. Each morphism is a mapping from an object in
and
in
for the set of morphisms from
from
.
-
is the composition operator:
is a binary operation that is the abstraction of function composition;
, and an arrow
,
. It’s got the basic properties of function composition:
- Associativity:
.
- Identity:
.
- Associativity:
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 
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 monomorphism (aka a monic arrow ) is an arrow
. That is,
- An epic (or epimorphism) is an arrow
. This is almost the same as a monic, but it’s from the other side of the composition; instead of
in the definition, it’s
; so an arrow is epic if when another arrow is composed with
- An isomorphism is an arrow
– an isomorphism is, basically, a reversible arrow: there’s a morphism that always reverses the action of an iso arrow.
- An endomorphism is an arrow
where
. It’s sort of like a weak identity arrow.
- 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.
Typo, I think:
I think that should be “logic.”
Probably. It should also be “topos theory”, not “topoi theory”. We don’t say “groups theory”, after all.
No, but I can understand why someone would think that. Category theory looks at what happens if you take the concept of composition and strip it down. That functions are the things we’re most used to composing is incidental.
You define the objects and morphisms as sets, but isn’t part of the point of this that they can be too large to be sets?
Well, yes. But for an initial introduction, it’s easier to talk about them as sets. The fact that they can technically be proper classes is, at this level of introduction, an un-necessary complication.
One thing I don’t quite get: how is an endomorphism not always an automorphism? I mean, if an endomorphism maps objects onto themselves, the endomorphism itself the arrow which reverses the operation?
Imagine the function f(x)=2x on the integers. It maps from the integers to the integers, but it’s not reversible because odd numbers wouldn’t “map back”.
The stereotypical example is that the objects are sets and the morphisms are functions. A function that maps a set onto itself (an endomorphism) is in most cases not the identity, nor is it one-to-one (an isomorphism).
Also don’t be confused by the name ‘objects’, it implies a single item, but usually it’s a set or something larger.
No, no, no! It’s not “usually a set or something larger”. That, in fact, is such a special case that it has a special name: a “concrete category”.
You’re most probably right, since my cat-theory is quite rudimentary. It’s just that I caught Jason making the mistake I nearly made myself when reading Mark’s explanation. You shouldn’t read f:a->b as f(a)=b (single objects) but as mappings between things, and the most obvious example would be sets.
Furthermore, my impression is that the few times I’ve run across category theory, that the objects are almost always (related to) sets. For example:
1) Topological spaces (a set with a topology) with homeo/diffeo morphisms.
2) Group theory (a set with binary operations) with homomorphisms
etc…
Well, try this one: objects are natural numbers, and morphisms from m to n are m-by-n matrices over some ring, with matrix multiplication as composition. It turns out that this is (equivalent to) the “skeletal category” of that of free modules over the ring, so that’s not too different.
Better: any partially ordered set can be seen as category. The objects are the elements of the set, and there is an arrow from a to b if and only if a<=b. The two axioms of a partial order — reflexivity and transitivity — correspond to identities and composition. Functors are especially nice, here; they're order-preserving maps!
As a special case, for any natural number n there is a unique (up to isomorphism) total order on an n-element set, which gives us categories corresponding to the natural numbers. These turn out to be surprisingly useful; functors from the category "1" to a target category pick out objects; functors from "2" to a target category pick out morphisms; functors from "3" to a target category pick out composable pairs of morphisms…
And then there are graph categories, whose representations give rise to all sorts of fancy theoretical computer science things, and tangle diagrams, which turn knot theory into algebra, and…
I know this is a bit of overkill, but getting away from concrete categories is the first step to really understanding that categories are not "metamathematical", though they can be applied to metamathematics. They're another algebraic structure exactly on a par with groups or rings or any of the others.
I hate to write in a way that might indicate I haven’t been paying careful attention to definitions here, but one thing seems to slip me up. So, either it’s a reading error on my part, or loose language has bested me yet again.
1.) you make the point that ‘a set or something larger’ is a special case; viz., ‘concrete category’.
2.) you write, ‘I know this is a bit of overkill, but getting away from concrete categories’.
The only way I can parse this is the plural case in 2 above is *not* ‘concrete category’ as a special case; rather, it’s just discrete categories. Either that, or I’m just completely off the mark.
Sorry in advance!
I think that that was a typo on John’s part.
A concrete category is a category whose objects and arrows are sets; a general category can have either sets or proper classes of objects and arrows.
Ok, if that’s the case then I’m tracking. Otherwise (being precise in reading because, you know, ‘math’) I wasn’t sure I was in the same conversation as everyone else.
Thank you, MarkCC.
There’s a technical definition of a “concrete category”, but the core idea is that it’s one where the objects are “sets with some extra structure” and the morphisms are “functions preserving that structure”. The category of groups is concrete, since a group has an underlying set and a group homomorphism is a function between the underlying sets that preserves the extra group structure.
Category theory was first and most popularly applied to such cases, which gives a lot of people the impression that categories are inherently “meta-algebraic” — they are an extra-abstract tool used to study “regular” algebraic structures like groups, rings, fields, topological spaces, and so on. And it just isn’t so.
Now, as to “a concrete category is a category whose objects and arrows are sets”: this is a small category, not a concrete category.
Consider, for instance, the category of vector spaces. This contains the vector space given by a direct sum of component vector spaces, one for each possible dimension:
Sum_(n in [0,..,∞]) (k^n)
So a basis vector in this vector space is some finite length sequence of elements of the field k.
Here is one linear map from this vector space to itself, which is to say one endomorphism in our category of vector spaces:
For a vector (a,b,c,…,x), we return (b,c,…,x).
For the special vector 0 in k^0, we just return 0 again.
This is an endomorphism of this object, but it is not mono, and it is certainly not iso.
In SET, as I understand things, an epimorphism comes as a surjection and vice versa. So, in SET if a function comes as a surjection, then it comes as an epimorphism. So, consider {1, 2} and {3} with F:1->3, 2->3. F qualifies as a surjection, but it’s not a map from {1, 2} back onto itself or an “endojection”. Also, consider two algebras on {1, 2} with a binary operation B:(1, 1)->1, (1, 2)->1, (2, 1)->1, (2, 2)->1, and one on {3} with a binary operation C:(3, 3)->3. Now
F(1B1)=F1=3, (F1CF1)=(3C3)=3
F(1B2)=F1=3, (F1CF2)=(3C3)=3
F(2B1)=F1=3, (F2CF1)=(3C3)=3
F(2B2)=F1=3, (F2CF2)=(3C3)=3
So, for all x, y F(xBy)=(FxCFx). Thus F consists of a homomorphism in the sense of abstract algebra, and it follows that since F consists of a surjection also, that in the sense of abstract algebra F consists of an epimorphism. But, F is clearly not an endomorphism. I think the word “onto” has tripped you up here. “Onto” just indicates that we have a surjection and nothing more, as the English word might seem to suggest.
Viewing the RSS feed in google reader now gives annoying errors whereever you use latex: “your domain is not authorized to use mathTeX on this server.” Presumably this is some sort of cross-site scripting security, but I used to be able to read the RSS feed just fine. Anyone else having this problem?
It seems to happen when reading the post in something that doesn’t execute JavaScript. I saw the same thing in my browser thanks to NoScript, until I whitelisted scientopia.org to allow the script to execute. As for why mathTeX doesn’t work without scripting enabled, I don’t know.
Whatever the reason, it would be nice if Mark switched to a different TeX system.
In my barely-remembered Category Theory class from 13 years ago, one thing Dr. Schanuel did that was very helpful was to use as two consistent examples throughout the course was two categories: the Category of Sets and Functions, and the Category of Vector Spaces and Linear Transformations.
In the case of Category of Sets and Functions, any function that maps the set of rationals to the set of rationals (such as f (a/b) = a^2/b^3 ) is an endomorphism, but not necessarily an isomorphism ( in this case, f(1/2) = f(-1/2) ). Likewise, it’s entirely possible to define the isomorphism g:{dwarves who aided Snow White}->{days of the week}, but that’s clearly not going to be an endomorphism.
While I appreciate the idea of introducing Obj(C) as a set in the interest of simplicity, the fact that Obj(C) is very often NOT a set is a real issue. (For whatever it’s worth, IIRC the classic book ‘Categories for the Working Mathematician’ also tries to define in terms of sets but does so by limiting the category Set to only a certain set of sets). It sounds silly, but when you’re doing things like trying to define K-theory of a category you have to worry about that sort of thing.
It might be good to clarify how category theory differs from graph theory. I started out thinking of an “object” as a vertex and an “arrow” as an edge from one vertex to another, but that seems to be all wrong. In particular, an “arrow” can’t be defined as the ordered pair of the objects it connects.
Brian: given any graph there’s a “path category” of the graph. The objects are the vertices of the graph, while the morphisms from vertex a to b are the paths (with orientation if the graph is oriented) from a to b.
Exercises:
a) Show that the path category of a graph is small.
b) Show that any morphism of graphs gives rise to a uniquely-defined functor from one path category to the other.
c) Show that the construction of the path category of a graph is a functor from the category of graphs to the category of small categories.
Am I the only one who got a whole lot of ‘your domain is not authorized to use mathTeX on this server’?
Sorry for the trouble. The latex rendering software that we’re using here at Scientopia doesn’t work in RSS readers.
It attempts to use a Javascript rendering mechanism. When that fails, it falls back to a public server. But the public server that it tries to use stopped providing free rendering services. One of these days, I’ll set up a scientopia rendering service on our server – but it’s just not at the top of my priority queue.
If you view the page directly, instead of through RSS, it the tex stuff should render properly. If it doesn’t, please drop me an email, letting me know what browser/OS you’re using, so that I can debug.