Sunday, August 2, 2009

Fun with Functors

We again begin this post with citations. The interested reader can refer to:

  • Saunders Mac Lane, Categories for the Working Mathematician Graduate Texts in Mathematics (vol 5) Springer-Verlag, Second Edition (1998);
  • John Baez, Some Definitions Everyone Should Know from Fall 2004 seminar.
  • Saunders Mac Lane and Ieke Moerdijk, Sheaves in Geometry and in Logic: A First Introduction to Topos Theory Springer-Verlag (1992).
We'll then proceed to the notion of functors. We introduced the morphism as a structure-preserving mapping between mathematical objects. What if we take those objects to be categories? That's precisely what a functor is! More formally:

Definition 1 Given categories $C,D$ a "functor" $F:C\to{D}$ consists of:
  • a function $F:Ob(C)\to Ob(D)$;
  • for any pair of objects $x,y\in Ob(C)$, a function $F:\hom(x,y)\to\hom(F(x),F(y))$
such that
  • $F$ preserves identities: for any object $x\in C$, $F(1_{x})=1_{F(x)}$;
  • $F$ preserves composition: for any pair of morphisms $f:x\to{y}$, $g:y\to{z}$ in $C$, we have $F(fg)=F(f)F(g)$.

It's straightforward to introduce the notion of composition of functors and identity functors. They are done in "the obvious way" (i.e. composition of functors results in a functor whose object function consists of the composed object functions, and morphism function consists of the composed morphism function, etc.).

So...what do functors do?! Really in a nutshell, they assign information to each object and information-preserving-morphism to each morphism. This is still kinda abstract, so lets break it down to a catch phrase:

*** functors are mathematical procedures. ***

For example, consider the functor $\mathcal{P}:\mathbf{Set}\to\mathbf{Set}$ the powerset functor. It does what you think it does, it eats in a set $X$ and it spits out its power set $\mathcal{P}(X)$; for each function $f:X\to{Y}$ it eats in, it spits out a function between the corresponding powersets $\mathcal{P}:\mathcal{P}(X)\to\mathcal{P}(Y)$.

There is also a broad class of functors that can "forget" aspects of a mathematical object, we can forget stuff, structure, and properties...or we can forget structure, and properties...or we can forget properties. In general, whenever we use the term "forgetful functor", we mean a functor $U:C\to\mathbf{Set}$ which gives us the set underlying a mathematical object.

Definition 2. A "Concrete Category" $(C,U)$ consists of
  • a category $C$;
  • a (faithful) functor $U:C\to\mathbf{Set}$

We can think of objects of $(C,U)$ as being a set "with some structure". Some examples of concrete categories would be Mon, Rng, Grp, and so on.

Sheaves as Generalization of Vector Fields

On the other hand, we have a notion of having a topological space as a category. We have, from basic vector calculus, the notion of assigning a vector to each point in space. We can generalize this notion by assigning some information to each open subset of a topological space, i.e. each object of the category $O(X)$ of open subsets in the topology $\mathcal{T}$ of $X$. (Note the morphisms of $O(X)$ are inclusion mappings.)

So now the question is: how oh how do we assign information to each object of $O(X)$? It's trivial, we consider the functor $F:O(X)\to(C,U)$ where $(C,U)$ is a concrete category. Since we haven't introduced it yet, lets take a moment to consider $(C,U)$ as a concrete category. It consists of a category $C$ and a "forgetful functor" $U:C\to\mathbf{Set}$ which basically tells us that the objects of $C$ are sets equipped with some structure which is "forgotten" when we consider $U(C)$.

So to recap: $(C,U)$ as a concrete category consists of "sets equipped with structure" and a functor $U$ which gives us the underlying set. We assign information to the open subsets of a topological space $(X,\mathcal{T})$ by considering the topological space as a category $O(X)$ and then we use a functor $F:O(X)\to(C,U)$ to assign to each open subset some object of $C$ in a "nice way".

More precisely, the "nice way" is such that upon restrictions of open subsets of $X$ we get consistent information. So when we consider the subset $v\subseteq u\subseteq X$, we demand a morphism $res_{v,u}:F(u)\to F(v)$ in the category $C$. This morphism $res_{V,U}$ is called the restriction morphisms and they are such that:

  1. For every open set $u$ of $O(X)$, the restriction morphism $res_{u,u}:F(u)\to{F(u)}$ is precisely the identity morphism;
  2. if we have three open sets $w\subseteq v\subseteq u$, then $res_{w,v}\circ{}res_{v,u}=res_{w,u}$.
When this happens, we have a bit of a surprise: we have $F$ be called a "presheaf". We can formally define it in our favorite algorithmic way:

Definition 3. A "presheaf on $X$ with values in $C$" consists of
  • a functor $F:O(X)^{op}\to(C,U)$ from the dual of $O(X)$ (i.e. $O(X)$ with the arrows reversed) to a concrete category $(C,U)$ which assigns
    1. for each open set $u\subseteq{X}$, it assigns an object $F(u)$ of $C$;
    2. for each inclusion of open sets $v\subseteq{u}$, it assigns a morphism $res_{v,u}:F(u)\to{F(v)}$ in $C$ called the "restriction morphism"
such that
  • for each open set $u\subseteq{X}$, the restriction morphism $res_{u,u}:F(u)\to{F(u)}$ is the identity $1_{F(u)}$;
  • if $w\subseteq{v}\subseteq{u}$ are open subsets of $X$, then $res_{w,v}\circ{}res_{v,u}=res_{w,u}$.

Notice: we a mild specification of "consistency on overlapping subsets". When we impose a stronger demand and some more properties, we'll turn a presheaf into a sheaf. We won't get to this, however, since it is far beyond the scope of this entry.

A presheaf assigns information in a way that's basically a generalization of vector fields, or should be intuitively considered as such. It gives us the intuition of the functor as assigning information to each object of a category in a way that's "consistent on overlaps".

Functors are my Hom-Boy

Recall that a category C has defined for any pair of objects $x,y\in\mathbf{C}$ a set $\hom(x,y)$ of morphisms from $x$ to $y$. So...what happens if we choose some fixed object $x_{0}\in\mathbf{C}$, and consider $\hom(x_{0},-)$ as a morphism?

Well it has to eat in objects from C. It spits out a set of morphisms. How does it behave on morphisms? Let $f:y\to{y^{\prime}}$ be some morphism in C, we expect our $\hom(x_{0},-)$ "morphism" to take the domain and the codomain to sets, it would seem logical that the morphism becomes a function of these sets. That is, $\hom(x_{0},f):\hom(x_{0},y)\to\hom(x_{0},y^{\prime})$ is a function.

Or, pithily, hom induces a functor $\hom(x_{0},-):\mathbf{C}\to\mathbf{Set}$(!)

Is this wild allegation true?! Lets see, if it satisfies the properties of a natural transformation, then it must be one.

Does it preserve the identity? Well, $\hom(x_{0},1_{y}):\hom(x_{0},y)\to\hom(x_{0},y)$, so that's a check on that.

Does it preserve composition of morphisms? If $f:y\to{z}$ and $g:z\to{w}$, then $g\circ{f}:y\to{w}$. We see that $\hom(x_{0},g\circ{f}):\hom(x_{0},y)\to\hom(x_{0},w)$ in the "obvious way", i.e. it's $\hom(x_{0},g)\circ\hom(x_{0},f)$. So that's check.

That means that $\hom(x_{0},-):\mathbf{C}\to\mathbf{Set}$ is indeed a functor.

The observant reader might ask "But what if we don't fix the first slot, so we have hom(-,-); what is that?" We can view it as a sort of generalization of the inner product for categories. It's actually a "bifunctor" from $\mathbf{C}^{op}\times\mathbf{C}\to\mathbf{Set}$ where Cop is the dual category to C. The reader knowledgeable in linear algebra should immediately see a parallel to the current situation, and we can think of functors as "operators" (later on we will see that we can define "adjoint functors" this way.) There is one exception: instead of "scalars" we have objects in Set, which is weird!


  1. Wow you write all of these in one day?
    Just want to let you know that you can also use xypic package (it's been long time I didn't touch category theory :) )
    Your restriction map can be described by this commutative diagram.

  2. Sorry there is some typo up there

  3. It probably shouldn't be as impressive as it might seem, I'm doing research on the subject of category theory in quantum physics (hence my choice of outline here!).

    I'd be in a bad state if I couldn't do all these in one day...

    The diagram you've doodled (the second one) merely reiterates one of the main points of category theory: given any two morphisms $f:x\to{y}$, $g:y\to{z}$, we can always compose them. We just insist that when they so happen to be restriction morphisms that they result in a restriction when composed.

    This is important in insisting "consistency on overlaps", the sort of locality condition for presheaves. It then allows us to do geometry-type stuff with categories :)

  4. After thinking about it for a bit, when I get to commutative diagrams I think I'd prefer to use metapost then convert it to a png, since metapost gives me a lot of freedom. Plus conversion is trivial with the "convert" program on Linux :)

  5. (Addendum: that link I gave is now broken, after playing around with the html for a few days I've got the table of contents working -- see the top of the page below the title -- and the basic plan is outlined in the Introduction.)