Fun with Functors

Oct 25 2011 Published by under Category Theory

So far, we've looked at the minimal basics of categories: what they are, and how to categorize the kinds of arrows that exist in categories in terms of how they compose with other arrows. Just that much is already enlightening about the nature of category theory: the focus is always on composition.

But to get to really interesting stuff, we need to build up a bit more, so that we can look at more interesting constructs. So now, we're going to look at functors. Functors are one of the most fundamental constructions in category theory: they give us the ability to create multi-level constructions.

What's a functor? Well, it's basically a structure-preserving mapping between categories. So what does that actually mean? Let's be a bit formal:

A functor \(F\) from a category \(C\) to a category \(D\) is a mapping from \(C\) to \(D\) that:

  • Maps each member \(m in Obj(C)\) to an object \(F(m) in Obj(D)\).
  • Maps each arrow \(a : x rightarrow y in Mor(C)\) to an arrow \(F(a) : F(x) rightarrow F(y)\), where:
    • \(forall o in Obj(C): F(1_o) = 1_{F(o)}\). (Identity is preserved by the functor mapping of morphisms.)
    • \(forall m,n in Mor(C): F(n circ o) = F(n) circ F(o)\). (Commutativity is preserved by the Functor mapping of morphisms.)

Note: The original version of this post contained a major typo. In the second condition on functors, the "n" and the "o" were reversed. With them in this direction, the definition is actually the definition of something called a covariant functor. Alas, I can't even pretend that I mixed up covariant and contravariant functors; the error wasn't nearly so intelligent. I just accidentally reversed the symbols, and the result happened to make sense in the wrong way.

That's the standard textbook gunk for defining a functor. But if you look back at the original definition of a category, you should notice that this looks familiar. In fact, it's almost identical to the definition of the necessary properties of arrows!

We can make functors much easier to understand by talking about them in the language of categories themselves. Functors are really nothing but morphisms - they're morphisms in a category of categories.

There's a kind of category, called a small category. (I happen to dislike the term "small" category, but I don't get a say!) A small category is a category whose collections of objects and arrows are sets, not proper classes.

(As a quick reminder: in set theory, a class is a collection of sets that can be defined by a non-paradoxical property that all of its members share. Some classes are sets of sets; some classes are not sets; they lack some of the required properties of sets - but still, the class is a collection with a well-defined, non-paradoxical, unambiguous property. If a class isn't a set of sets, but just a collection that isn't a set, then it's called a proper class.)

Any category whose collections of objects and arrows are sets, not proper classes, are called small categories. Small categories are, basically, categories that are well-behaved - meaning that their collections of objects and arrows don't have any of the obnoxious properties that would prevent them from being sets.

The small categories are, quite beautifully, the objects of a category called Cat. (For some reason, category theorists like three-letter labels.) The arrows of Cat are all functors - functors really just morphisms between categories. Once you wrap you head around that, then the meaning of a functor, and the meaning of a structure-preserving transformation become extremely easy to understand.

Functors come up over and over again, all over mathematics. They're an amazingly useful notion. I was looking for a list of examples of things that you can describe using functors, and found a really wonderful list on wikipedia.. I highly recommend following that link and taking a look at the list. I'll just mention one particularly interesting example: groups and group actions.

If you've been reading GM/BM for a very long time, you'll remember my posts on group theory. In a very important sense, the entire point of group theory is to study symmetry. But working from a set theoretic base, it takes a lot of work to get to the point where you can actually define symmetry. It took many posts to build up the structure - not to present set theory, but just to present the set theoretic constructs that you need to define what symmetry means, and how a symmetric transformation was nothing but a group action. Category theory makes that so much easier that it's downright dazzling. Ready?

Every group can be represented as a category with a single object. A functor from the category of a group to the category of Sets is a group action on the set that is the target of the functor. Poof! Symmetry.

Since symmetry means structure-preserving transformation; and a functor is a structure preserving transformation - well, they're almost the same thing. The functor is an even more general abstraction of that concept: group symmetry is just one particular case of a functor transformation. Once you get functors, understanding symmetry is easy. And so are lots of other things.

And of course, you can always carry these things further. There is a category of functors themselves; and notions which can be most easily understood in terms of functors operating on the category of functors!

This last bit should make it clear why category theory is affectionately known as abstract nonsense. Category theory operates at a level of abstraction where almost anything can be wrapped up in it; and once you've wrapped something up in a category, almost anything you can do with it can itself be wrapped up as a category - levels upon levels, categories of categories, categories of functors on categories of functors on categories, ad infinitum. And yet, it makes sense. It captures a useful, comprehensible notion. All that abstraction, to the point where it seems like nothing could possibly come out of it. And then out pops a piece of beautiful crystal. It's really remarkable.

16 responses so far

  • Brett says:

    Hmm, for some bizarre reason, your MathTeX formulas aren't being rendered, at least on my end. Instead, they're being replaced with a placeholder error message of the form:

    "your domain is not authorized to use MathTeX on this server"

  • Marshall says:

    I get the same problem in my RSS reader (NetNewsWire), but it looks fine when I view it in a browser (Safari/Mac).

    Large red angry boxes.
    It appears to get served from here

    • MarkCC says:

      I'm very sorry for the trouble. At the moment, we're having trouble getting latex images rendered by an external site; I'm not entirely clear on the reason for that error. It should work, and it does work in command-line testing; but when the server tries to do the fetch, it doesn't work. So we're left with rendering equations using a javascript-based plugin - but, obviously, than only works if you're viewing the post with something that will allow the javascript renderer to work. CSS readers don't - so if you view in a CSS reader, you get the red error boxes.

      Unfortunately, I don't have a whole lot of time to debug. (I recently started a new job, and I'm still in the drowning phase of learning everything I need to know.) I'm trying to fix the problem with what time I have, but debugging web systems involving multiple servers is painful at best. As a short-term solution, you should be able to read the equations by viewing the post in a browser. I realize that that is a very suboptimal solution which frustrates readers - but until I have the time to sit down and figure out what the heck is going on, it's the best that I can do.

  • One Brow says:

    My understanding of proper class is that it is used for collections that have become too large to be sets (in particular, too large to sensibly create a power set, too large to be assigned a cardinal number, etc.). For example, the class of all cardinal numbers is a proper class of sets. Thus, referring to the categories as small means they are of a size where they have a cardinality.

    • MarkCC says:

      Yes, I understand that. I just personally dislike a terminology that calls uses the label "small" for things that are, potentially, infinitely large. It's not an incorrect terminology, and it does sort-of make sense once someone explains it to you; but when you first hear it, it's odd.

      • One Brow says:

        I guess I found "If a class isn't a set of sets, but just a collection that isn't a set, then it's called a proper class.", and in particular the "of sets", confusing.

  • "Associativity is preserved"

    Surely you mean *composition* is preserved.

    • MarkCC says:

      Yes! Oy, did I really type that? Yes, I definitely meant composition. Composition is the whole point.

      • Robyn Slinger says:

        And it should be ∀m,n∈Mor(C):F(n∘m)=F(n)∘F(m), too (not "o").

        And: very nice posting! This is the first time I see someone explain clearly what is a class (instead of saying "it's just like sets but it isn't sets", which just changes the terminology and keeps the usual paradoxes).

  • As for the abstraction, and to tie into your previous post, commutative diagrams are functors. Each "diagram schema" is a graph, which gives a category whose objects are the vertices and whose arrows are the edges, and we insist that certain compositions of certain arrows equal certain other arrows, as observed in the graph.

    Then a functor from this toy category -- one which is far from being concrete, incidentally -- to a target category picks out an object of the target for each vertex and a morphism of the target for each edge such that the given equalities must still hold. Voila: commutative diagram!

  • Brandon Wilson says:

    In the above definition for functor, I believe you inadvertently gave the definition for a contravaiant functor, switching around the morshism composition.

  • Every group can be represented as a category with a single object. A functor from the category of a group to the category of Sets is a group action on the set that is the target of the functor. Poof! Symmetry.

    Not quite. A category with a single object only gives us a monoid. A category with a single object with all functors having (both-sided) inverses gives us a group.

    Then, yes, given that you can view any group as such a category, a group action on a set defines a functor from that category to the category Set and vice versa. But that inverses clause is important.

    • True; I'd given Mark the benefit of the doubt that he meant his statement strictly, that every group can be viewed in this way. But it's easy to misinterpret the statement as written to mean the converse, which isn't true.

Leave a Reply