The Unapologetic Mathematician

Shh! Don’t tell anybody!

From The n-Category Café, I hear that there’s a secret blogging seminar going on.

June 12, 2007 Posted by | Uncategorized | 1 Comment

Products and Coproducts

Let’s consider the Cartesian product $X\times Y$ of two sets $X$ and $Y$. Classically we think of this as the set of all pairs $(x,y)$ with $x\in X$ and $y\in Y$. But we can also characterize it just in terms of functions.

Specifically, $X\times Y$ comes with two projection functions $\pi_X:X\times Y\rightarrow X$ and $\pi_Y:X\times Y\rightarrow Y$, defined by $\pi_X(x,y)=x$ and $\pi_Y(x,y)=y$. If we take any other set $S$ with functions $f_X:S\rightarrow X$ and $f_Y:S\rightarrow Y$ we can define the function $(f_X,f_Y):S\rightarrow X\times Y$ by $\left[(f_X,f_Y)\right](s)=(f_X(s),f_Y(s))$. Then we see that $\pi_X\circ(f_X,f_Y)=f_X$ and $\pi_Y\circ(f_X,f_Y)=f_Y$. Further, this function from $S$ to $X\times Y$ is the only such function.

Now let’s do away with those nasty elements altogether and draw this diagram:

What does this mean? Well, it’s like the diagram I drew for products of groups. The product of $X$ and $Y$ is a set $X\times Y$ with functions $\pi_X$ and $\pi_Y$ so that for any other set $S$ with functions to $X$ and $Y$ there exists a unique arrow to $X\times Y$ making the diagram commute. Since we’ve written this definition without ever really referring to elements we can just pick it up and drop it into any other category. Many descriptions of categorical products stop here, but let’s push a bit further.

Let’s consider a category $\mathcal{C}$ containing (among others) objects $X$ and $Y$. From this we’re going to build a new category. An object of our category will be a diagram that looks like $X\leftarrow^{f_X}S\rightarrow^{f_Y}Y$ in $\mathcal{C}$. A morphism from $X\leftarrow^{f_X}S\rightarrow^{f_Y}Y$ to $X\leftarrow^{f'_X}S'\rightarrow^{f'_Y}Y$ will be a morphism $S\rightarrow^{g}S'$ in $\mathcal{C}$ so that $f_X=f'_X\circ g$ and $f_Y=f'_Y\circ g$.

Now what’s a product in $\mathcal{C}$? It’s a terminal object of this category we’ve constructed! That is, it’s one of these diagrams so that every other diagram has a unique morphism (as defined above) to it. This definition makes sense in any category $\mathcal{C}$, though the category we build from a given pair of objects may not have a terminal object, so a given pair of objects of $\mathcal{C}$ may not have a product in $\mathcal{C}$. If every pair of objects of $\mathcal{C}$ has a product in $\mathcal{C}$, we say that $\mathcal{C}$ “has products”.

So, the existence of Cartesian products of sets shows that $\mathbf{Set}$ has products. Similarly, $\mathbf{Grp}$ has products, as do $\mathbf{Ring}$, $\mathbf{Gpd}$ (groupoids), $\mathbf{Cat}$ (small categories), and pretty much all our familiar categories from algebra.

What about something like a preordered set $(P,\preceq)$, considered as a category? What would “product” mean, when written in this language? Well, given elements $a$ and $b$ the product $a\times b$ will have arrows to $a$ and $b$, so $a\times b\preceq a$ and $a\times b\preceq b$. Also, for any other element $c$ with $c\preceq a$ and $c\preceq b$ we have $c\preceq a\times b$$c$ has an arrow to both $a$ and $b$, so it has an arrow to $a\times b$. That is, $a\times b$ is a greatest lower bound of $a$ and $b$, and the category has products if and only if every pair of elements has such a greatest lower bound.

And it gets better. If we consider a category $\mathcal{C}$ that has products, the product defines a functor $\times:\mathcal{C}\times\mathcal{C}\rightarrow\mathcal{C}$! If we have arrows $f_1:X_1\rightarrow Y_1$ and $f_2:X_2\rightarrow Y_2$ then I say we’ll have an arrow $f_1\times f_2:X_1\times X_2\rightarrow Y_1\times Y_2$. Indeed, if we consider $f_1\circ\pi_{X_1}:X_1\times X_2\rightarrow Y_1$ and $f_2\circ\pi_{X_2}:X_1\times X_2\rightarrow Y_2$ then we’ll get an arrow from $X_1\times X_2$ to $Y_1\times Y_2$. And this construction preserves compositions and identities. For compositions, start with this diagram:

and draw in the induced arrows $f_1\times f_2$, $g_1\times g_2$, and $(g_1\circ f_1)\times(g_2\circ f_2)$. Then use the uniqueness part of the universal property to show that the composite of the first two must be the same as the third. Do a similar thing to verify that identities are also preserved.

Finally, we can flip all the arrows in what we’ve said to get the dual notion: coproducts. Use this diagram:

and define the coproduct to be an initial object in a certain category of diagrams. Check that in $\mathbf{Set}$ this property is satisfied by disjoint unions. In $\mathbf{Grp}$ coproducts are free products. In a preorder, coproducts are least upper bounds. And, of course, the coproduct defines a functor from $\mathcal{C}\times\mathcal{C}$ to $\mathcal{C}$.

There’s a fair bit to digest here, but it’s worth it. The next few ideas are really very similar. Alternatively, you could take this to mean that if you don’t completely get it now there are a few more examples in the pipe that may help.

June 11, 2007 Posted by | Category theory | 10 Comments

Initial and Terminal Objects

Since the next subject I’ll move into starts with a few simple definitions, I’ll kick it off today. Light fare for a Sunday.

An initial object $I$ in a category $\mathcal{C}$ is one so that $\hom_\mathcal{C}(I,X)$ has exactly one element for each object $X\in\mathcal{C}$. Many of the categories we’ve considered have initial objects. For example:

• The empty set is the initial object of $\mathbf{Set}$, since there’s exactly one function from the empty set to any other set.
• The trivial group is the initial object of $\mathbf{Grp}$, since (again) there’s only one group homomorphism from the trivial group to any other group.
• The initial object of the category $\mathbf{Gpd}$ of groupoids is the empty groupoid with no objects and no morphisms.
• The initial object of an ordinal number considered as a category is the least element of the ordinal.
• More generally, the initial object of any preorder is a minimal element, which is below-or-equal-to every other element.

Not all categories have an initial object. A discrete category, for instance, has none. Neither does a preorder with no minimal element (consider the integers as an ordered set). However, if a category has an initial object it’s unique up to isomorphism. Let’s say that $I_1$ and $I_2$ are both initial. Then there is exactly one arrow $I_1\rightarrow I_2$, and exactly one $I_2\rightarrow I_1$. They compose to give arrows $I_1\rightarrow I_1$ and $I_2\rightarrow I_2$, but again there is only one such arrow in each case: the identity arrows. So these compositions must be the respective identities, and we have an isomorphism.

The dual notion is that of a terminal object $T$ so that every $\hom_\mathcal{C}(X,T)$ has exactly one element. Again, terminal objects are unique up to isomorphism. And again, many of our favorite categories have terminal objects, but not all. Some examples:

• Any set with a single element is a terminal object in $\mathbf{Set}$, since there’s only one function from any other set into it: send all elements of $X$ to the same point.
• The trivial group is also the terminal object of $\mathbf{Grp}$, since there’s only one homomorphism into it from any group.
• It turns out that the trivial group is also the terminal object in $\mathbf{Gpd}$, as you should verify.
• The terminal object of a preorder is an element which is above-or-equal-to every other.

We’ll also use the terms “universal” and “couniversal” for initial and terminal objects, respectively. We’ll see that many constructions we already know — and many we’ll come to know — consist of setting up an apropriate category and finding an initial or a terminal object. We say that such a construction satisfies a universal condition, and the result is well-defined up to isomorphism.

June 10, 2007 Posted by | Category theory | 1 Comment

Groupoids (and more group actions)

A groupoid is the natural extension of a group, considered as a category. A groupoid is a category where each morphism is invertible. If a groupoid has only one object it’s a group.

These structures are the central players in John Baez’ “Tale of Groupoidification”, which started in this issue of This Week’s Finds. They’re also a rather popular subject over at The n-Category Café.

Unfortunately, one of the best examples of a groupoid is still beyond us at this point, but there are others. One nice place groupoids come up is from group actions. In fact, Baez is of the opinion that the groupoid viewpoint is actually more natural than the group action viewpoint, but I think it would be difficult to start teaching from that end.

So how does this work? Let’s say we have a group $G$ and a left action of $G$ on a set $S$. Now let’s build a groupoid from this information. The high-level view is that every single move from one state (element of $S$) to another will be a morphism, and we can compose morphisms if the outgoing state of the first is the incoming state of the second. Now for the details.

We take the objects of our groupoid to be the set $S$, and the morphisms to be the set $G\times S$. The source of a morphism $(g,s)$ will be $s$, and the target will be $g\cdot s$. For each object $s$ we have the identity morphism $(e,s)$, where $e$ is the identity of $G$. If we have two morphisms $(g,s)$ and $(g',s')$, and $g\cdot s=s'$ (so the pair are composable), then we have the composite $(g',s')\circ(g,s)=(g'g,s)$. Note that this still has source $s$, and its target is $(g'g)\cdot s=g'\cdot(g\cdot s)=g'\cdot s'$, as it should be.

Well this is enough to show we have a category, but now we need to show that each morphism has an inverse. If we have a morphism $(g,s)$ going from $s$ to $g\cdot s$, we’ll need the inverse to go from $g\cdot s$ to $s=(g^{-1}g)\cdot s=g^{-1}\cdot(g\cdot s)$. The clear choice is $(g^{-1},g\cdot s)$, and indeed we find that $(g^{-1},g\cdot s)\circ(g,s)=(e,s)$, and $(g,s)\circ(g^{-1},g\cdot s)=(e,g\cdot s)$. Thus we have a groupoid.

This result we call the “action groupoid” or the “weak quotient”, and write $S//G$. Remember that the “real” quotient is the set of orbits of $G$ on $S$ — we consider two elements of $S$ to be “the same” if they are related by an element of $G$. Here we don’t consider them to be the same; we just make them isomorphic. Since we’ve replaced “the same” by “isomorphic”, we call this a “weak” quotient.

Now, an action groupoid is not just any groupoid. For one thing, we’ve got a functor $S//G\rightarrow G$. Just send every single object of $S//G$ to the unique object of $G$, considered as a category. Then send the morphism $(g,s)$ to $g$. We’re sort of folding up the groupoid $S//G$ into the groupoid (with one object) $G$. But here’s the thing: this functor is faithful! Indeed, we see that $\hom_{S//G}(s,s')$ is the set of $g$ so that $s'=g\cdot s$. In particular, it’s a subset of the elements of $G$, and the functor acts on this hom set by the inclusion function of this subset into $G$, which is injective. Even though the functor loses a lot of information (like, which state a given morphism started at) it’s still faithful because “faithful” just pays attention to what happens in each hom set, not what happens to the objects.

It turns out we can find a (somewhat) simpler groupoid $\mathcal{H}$ equivalent to $S//G$ and compatible with this faithful functor. That is, if the functor above is $F:S//G\rightarrow G$, we can find a groupoid $\mathcal{H}$ with functors $E:\mathcal{H}\rightarrow S//G$ and $I:\mathcal{H}\rightarrow G$. The functor $E$ will be an equivalence, $I$ will be faithful, and we’ll have $I=F\circ E$. The really special thing about $H$ is that it will be a collection of groups with no morphisms between any distinct objects.

For the objects of $\mathcal{H}$, take the set of $G$-orbits of $S$. There will be no morphisms between distinct objects, so we just need to specify a group of morphisms on each object. So, given an orbit $O\subseteq S$ pick a point $x\in O$ and let $\hom_\mathcal{H}(O,O)=G_x$ — the stabilizer of $x$. Of course, different representative points may give different stabilizers, but the stabilizers of any two points in the same orbit are isomorphic. For the functor $I$, just send each object of $\mathcal{H}$ to the single object of $G$ and include each hom set into $G$ as a subgroup, just like we did for $F$.

Now we define our equivalence. Since we’ve already picked a representative point in each orbit, let’s just send the object of $\mathcal{H}$ corresponding to that orbit to the object of $S//G$ corresponding to that point. Then we can just send $\hom_\mathcal{H}(O,O)=G_x=\hom_{S//G}(x,x)$ to itself. Clearly this is fully faithful, and it’s also essentially surjective because every point of $S$ is in some $G$-orbit. So we have an equivalence. Also it should be clear that $I=F\circ E$.

In fact, we can adapt this to any groupoid $\mathcal{G}$ with a faithful functor to a group $G$. Just replace “in the same orbit” by “have an arrow between them”. Then chop up the objects of $\mathcal{G}$ into equivalence classes, make each one an object of our new groupoid $\mathcal{H}$, and make the morphisms on an object in $\mathcal{H}$ the “stabilizer” of a representative object from $\mathcal{G}$. It all goes through to give the same sort of factorization.

And then if you push just a little bit harder you can take any discrete groupoid $\mathcal{H}$ (“discrete” = no morphisms between distinct objects) with a faithful functor $\mathcal{H}\rightarrow G$ and puff it up into an action groupoid. In fact, it suffices to show how to do this for a single object in $\mathcal{H}$, since all the others go the same way.

In this case we have a subgroup $H\subseteq G$ and we need to see it as the stabilizer of some $G$ action. We use the set $G/H$ of left cosets of $H$ in $G$. This may not be a group (since $H$ may not be normal), but it’s at least a set, and $G$ certainly acts on it by left-multiplication. What subgroup of $G$ fixes the coset $eH$? Exactly $H$. So, we puff $H$ out into $G/H$ and take its weak quotient by $G$ to get an action groupoid equivalent to $H$.

Putting this all together we see that any groupoid $\mathcal{G}$ with a faithful functor $\mathcal{G}\rightarrow G$ is equivalent to the action groupoid $S//G$ for some $G$-set $S$. And any $G$ action gives an action groupoid with a faithful functor to $G$. The two concepts are essentially the same.

June 9, 2007

Groups and group actions — categorically

The theory of group actions looks really nice when we translate it into the language of categories. That’s what I plan to do today.

We know that a monoid is essentially the same thing as a category with one object, and a group is a special kind of monoid. So any group $G$ can be considered as a category with one object in which every morphism has an inverse. So what’s a (left) group action? Well, it’s descibed by choosing a set $S$ for $G$ to act on, and a homomorphism from $G$ to the group of bijections on $S$. But $S$ is an object in the category $\mathbf{Set}$ of sets, and bijections from $S$ to itself are just the invertible morphisms in $\hom_\mathbf{Set}(S,S)$. What we’re describing here is a functor from $G$ to $\mathbf{Set}$! A (left) action of $G$ is an object of the category $\mathbf{Set}^G$ of (covariant) functors from $G$ to $\mathbf{Set}$. We know it’s a category because $G$ has (for our purposes) just a set of morphisms — it’s small.

Now I was adding these parentheticals above, since there’s also a notion of a right $G$-action. This is pretty much the same, but it satisfies $s\cdot(gh)=(s\cdot g)\cdot h$ instead of $(gh)\cdot s=g\cdot(h\cdot s)$. That is, it switches the order of composition. But we know how to do that! A right $G$-action is a contravariant functor — an object of $\mathbf{Set}^{G^\mathrm{op}}$.

So these actions form categories. What are the morphisms? Since these are functor categories, they’re natural transformations. Let’s say we have (left) actions $A_1:G\rightarrow\mathbf{Set}$ and $A_2:G\rightarrow\mathbf{Set}$, and that $A_1$ and $A_2$ send the single object $\bullet$ of $G$ to the sets $S_1$ and $S_2$, respectively. Now, what’s a natural transformation $\eta:A_1\rightarrow A_2$?

Well, there’s only one object in $G$, so a transformation only has one component: $\eta_\bullet:S_1\rightarrow S_2$. For any morphism (group element) $g\in G$ it must satisfy the naturality condition $\eta_\bullet(g\cdot s)=g\cdot\eta_\bullet(s)$ for all $s\in S_1$. Note that the dot on the left denotes the action of $G$ on $S_1$, and the one on the right denotes that on $S_2$. So we see that $\eta_\bullet$ must be a function which “intertwines” the two actions of $G$. That is, it preserves the $G$-action, just like homomorphisms of monoids preserve the composition and so on — a very natural notion of morphism of $G$-actions indeed! As a special case, a natural transformation from $A_1$ to itself is a permutation of the elements of $S_1$ which commutes with the actions of all the elements of $G$.

Okay, so we can translate this theory into categorical language and it looks pretty. So what? Hold on tight, because now I’m going to hit it with Yoneda’s Lemma (and its meaning).

Since there’s only one object in $G$ we only get one covariant functor $h_\bullet$ and one contravariant functor $h'_\bullet$. The covariant one gives us the group $G$ acting on its set of elements by left-multiplication, and the contravariant one gives the same set with the action of right-multiplication. Now given any other left $G$-action (covariant functor) on $S$ Yoneda’s Lemma tells us that the set $S$ is in bijection with the set of functions $f:G\rightarrow S$ satisfying $f(gh)=g\cdot f(h)$. In particular, we must have $f(g)=f(ge)=g\cdot f(e)$, where $e$ is the identity of the group, so the image of the identity element specifies the function completely. That is, if we have a left $G$-action on a set $S$ then every element $s\in S$ gives us an intertwining function satisfying $f_s(e)=s$, and every intertwining function sends $e$ to some element of $S$, giving us our bijection. A similar situation holds for right $G$-actions.

What about the Yoneda embedding $\mathbf{y}:G\rightarrow\mathbf{Set}^{G^\mathrm{op}}$? Well as we noted above, this sends the single object of $G$ to the set of elements of $G$ acting on itself on the right (because the target is the category of contravariant functors). But $\mathbf{y}$ is a functor, so it sends morphisms of $G$ (group elements) to morphisms of $\mathbf{Set}^{G^\mathrm{op}}$ ($G$-intertwining functions). Specifically, a group element $g$ gets sent to a function $\mathbf{y}(g):G\rightarrow G$ satisfying $\left[\mathbf{y}(g)\right](h_1h_2)=\left[\mathbf{y}(g)\right](h_1)h_2$.

Even better, we can compose these natural transformations! Since $\mathbf{y}$ is a functor we have $\mathbf{y}(g_1g_2)=\mathbf{y}(g_1)\circ\mathbf{y}(g_2)$. Also, $\mathbf{y}(e)$ must be the identity function on $G$$\left[\mathbf{y}(e)\right](h)=h$. Putting this all together, we see that $\left[\mathbf{y}(g)\right](h)=gh$, and indeed multiplying by $g$ on the left commutes with multiplying by another element of $G$ on the right, since group composition is associative! So we have a function sending $G$ to the group of permutations of the elements of $G$, and this function preserves group multiplication and identities. Then it must also preserve inverses, and we have a group homomorphism from $G$ to $\mathrm{Bij}(G)$.

And now for the coup de grâce: the Yoneda embedding $y$ is fully faithful! Firstly, this means that the homomorphism $G\rightarrow\mathrm{Bij}(G)$ is injective — its kernel is trivial — so every group is isomorphic to a subgroup of a permutation group. Secondly, this means that every permutation of the elements of $G$ which commutes with right-multiplication is given by left-multiplication by some element of $G$.

As a coda, we’re always more interested in representable functors than in represented functors, since we only care about things up to isomorphism. It turns out that there’s a special name for representable functors in this setup: torsors. I’ll be mentioning these again, to be sure, but a basic definition is that a $G$-torsor is a (left) $G$-action on a set, which is isomorphic to the action of $G$ on itself by left-multiplication. That link will take you to an excellent explanation (with great examples) by John Baez.

June 8, 2007

Riemann Hypothesis Considered Safe

A few months ago, a preprint on the arXiv claimed to have disproven the Riemann Hypothesis. It’s pretty technical at points, so I wouldn’t blame you for not reading it in detail. I certainly didn’t, preferring to sit back and wait for more expert heads than mine to consider the matter.

And now Bernhard Krötz has, and it’s wrong. That one is a lot easier to read.

What does Yoneda’s Lemma mean?

As I promised, today I’ll try to explain what Yoneda’s Lemma really does for us.

First off, let’s think about functions of two variables. To be very explicit, think of the function $f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ defined by $f(x,y)=xy$. We can turn this into a function of one variable that returns another function. Specifically, if we write $\mathbb{N}^\mathbb{N}$ for the set of functions from the natural numbers to themselves, we can write $\overline{f}:\mathbb{N}\rightarrow\mathbb{N}^\mathbb{N}$, where $\left[\overline{f}(x)\right](y)=xy$. That is, $\overline{f}(3)$ is the function that sends $y$ to $3y$. This method of “Currying” (named for Haskell Curry) a function should be familiar if you’ve worked with functional programming languages like LISP, ML, or Haskell. There’s really a lot to be said about it in general, and I’ll get back to exploring it in more depth another time.

Anyhow, a similar statement goes for functors of more than one variable. Since such functors are “functorial in each variable”, we can stick an object into all but one slot and be left with a functor of the last slot. The thing is, this assignment is itself functorial.

Let’s focus on a functor $F:\mathcal{A}\times\mathcal{B}\rightarrow\mathcal{C}$. Then for any object $A\in\mathcal{A}$ we have a functor $\overline{F}(A)=F(A,\underline{\hphantom{X}}):\mathcal{B}\rightarrow\mathcal{C}$. Now when we change the object $A$ by applying a morphism $\alpha:A_1\rightarrow A_2$ we get a natural transformation $\overline{F}(\alpha):\overline{F}(A_1)\rightarrow\overline{F}(A_2)$. It should have components $\overline{F}(\alpha)_B:F(A_1,B)\rightarrow F(A_2,B)$. The clear choice is $\overline{F}(\alpha)_B=F(\alpha,1_B)$, and indeed this is natural since the morphisms from $\mathcal{A}$ commute with those from $\mathcal{B}$.

Now, strictly speaking this $\overline{F}$ may not be a functor since we only know that $\mathcal{C}^\mathcal{B}$ is a category when at least one of $\mathcal{B}$ and $\mathcal{C}$ is small, but the general idea should be clear.

Now to the situation at hand: we know that any category $\mathcal{C}$ comes equipped with a functor $\hom_\mathcal{C}:\mathcal{C}^\mathrm{op}\times\mathcal{C}\rightarrow\mathbf{Set}$. We apply this Currying operation on each slot to get two “functors” $\mathbf{y}:\mathcal{C}\rightarrow\mathbf{Set}^{\mathcal{C}^\mathrm{op}}$ and $\mathbf{y'}:\mathcal{C}^\mathrm{op}\rightarrow\mathbf{Set}^\mathcal{C}$. Of course, the targets are only sure to be categories when $\mathcal{C}$ (and thus $\mathcal{C}^\mathrm{op}$ as well) is small, but we’ll gloss over that point. What the Yoneda Lemma says is that these functors are fully faithful!

To see this, notice that $\mathbf{y'}$ sends an object $A\in\mathcal{C}^\mathrm{op}$ to the covariant functor $h_A=\hom_\mathcal{C}(A,\underline{\hphantom{X}})$, while $\mathbf{y}$ sends an object $A\in\mathcal{C}$ to the contravariant functor $h'_A=\hom(\underline{\hphantom{X}},A)$. Since the objects of $\mathcal{C}$ and $\mathcal{C}^\mathrm{op}$ are the same, I hope that using $A$ for both won’t be too confusing.

Now let’s take the statement of the (covariant) Yoneda Lemma and apply it to the functor $h_B$ for some object $B\in\mathcal{C}$. It says that $\mathrm{Nat}(h_A,h_B)\cong h_B(A)=\hom_\mathcal{C}(B,A)=\hom_{\mathcal{C}^\mathrm{op}}(A,B)$. But notice that $\mathrm{Nat}(h_A,h_B)$ is $\hom_{\mathbf{Set}^\mathcal{C}}(h_A,h_B)$ — the set of morphisms from $h_A$ to $h_B$ in the functor category $\mathbf{Set}^\mathcal{C}$. Now since $\mathbf{y'}$ is a functor from $\mathcal{C}^\mathrm{op}$ to $\mathbf{Set}^\mathcal{C}$, it acts on the hom sets, sending $\hom_{\mathcal{C}^\mathrm{op}}(A,B)$ to $\hom_{\mathbf{Set}^\mathcal{C}}(\mathbf{y'}(A),\mathbf{y'}(B))$. And the Yoneda Lemma tells us that this is a bijection — the functor $\mathbf{y'}$ is fully faithful!

And the same argument goes through for $\mathbf{y}$. Now we apply the contravariant Yoneda Lemma to see that $\hom_{\mathbf{Set}^{\mathcal{C}^\mathrm{op}}}(\mathbf{y}(A),\mathbf{y}(B))=\mathrm{Nat}(h'_A,h'_B)\cong h'_B(A)=\hom_\mathcal{C}(A,B)$. The functor $\mathbf{y}$ induces a bijection on each hom set, so it’s fully faithful too!

Now remember what the point of fully faithful functors is: they’re all about full subcategories. This means that any (small) category $\mathcal{C}$ can be seen as a full subcategory of $\mathbf{Set}^{\mathcal{C}^\mathrm{op}}$. And full subcategories are nice because they just restrict the objects we’re interested in without throwing out any morphisms between those objects. So, the objects of any category can be seen as a special kind of contravariant $\mathbf{Set}$-valued functor on that category.

And now: which contravariant $\mathbf{Set}$-valued functors on a category $\mathcal{C}$ are so special that they constitute objects of $\mathcal{C}$ under this embedding? Well, as usual in category theory we’re interested in things up to isomorphism, so we should ask, “What contravariant set-valued functors are (naturally) isomorphic to one in the image of $\mathbf{y}$?”

These are just the representable functors.

The representable, contravariant, $\mathbf{Set}$-valued functors on a category $\mathcal{C}$ constitute a full subcategory of all contravariant $\mathbf{Set}$-valued functors on $\mathcal{C}$, which is equivalent to the category $\mathcal{C}$ itself.

And that’s why Yoneda’s Lemma is so amazing.

June 7, 2007 Posted by | Category theory | 15 Comments

Yoneda’s Lemma

Okay, time to roll up our sleeves and get into one of the bits that makes category theory so immensely tweaky: Yoneda’s Lemma.

First, let’s lay out a bit of notation. Given a category $\mathcal{C}$ and an object $A\in\mathcal{C}$ we’ll use $h_A$ to denote the covariant functor represented by $A$ and $h'_A$ to denote the contravariant one. That is, $h_A(B)=\hom_\mathcal{C}(A,B)$ and $h'_A(B)=\hom_\mathcal{C}(B,A)$.

Now given a covariant functor $F:\mathcal{C}\rightarrow\mathbf{Set}$, we’re interested in the set of natural transformations $\mathrm{Nat}(h_A,F)$. Note that not all of these are natural isomorphisms. Indeed, $F$ may not be representable at all. Still, there can be natural transformations going in one direction.

The Yoneda Lemma is this: there is a bijection between $\mathrm{Nat}(h_A,F)$ and $F(A)$.

Seriously.

And the proof is actually pretty clear too. One direction leaps out when you think of it a bit. A natural transformation $\Phi:h_A\rightarrow F$ has components $\Phi_B:\hom_\mathcal{C}(A,B)\rightarrow F(B)$, sending morphisms of $\mathcal{C}$ to elements of certain sets. Now, given any category and any object, what morphism do we know to exist for certain? The identity on $A$! So take $1_A$ and stick it into $\Phi_A$ and we get an element $\Phi_A(1_A)=x_\Phi\in F(A)$. The really amazing bit is that this element completely determines the natural transformation!

So let’s start with a category $\mathcal{C}$, an object $A$, a functor $F:\mathcal{C}\rightarrow\mathbf{Set}$, and an element $x\in F(A)$. From this data we’re going to build the unique natural transformation $\Phi^x:h_A\rightarrow F$ so that $\Phi^x_A(1_A)=x$. We must specify functions $\Phi^x_B:\hom_\mathcal{C}(A,B)\rightarrow F(B)$ so that for every arrow $f:B\rightarrow C$ in $\mathcal{C}$ we satisfy the naturality condition. For now, let’s focus on the naturality squares for morphisms $f:A\rightarrow B$, and we’ll show that the other ones follow. This square is:

$\begin{matrix}\hom_\mathcal{C}(A,A)&\rightarrow&\hom_\mathcal{C}(A,B)\\\downarrow{\Phi^x_A}&&\downarrow{\Phi^x_B}\\F(A)&\rightarrow&F(B)\end{matrix}$

where the horizontal arrows are $\hom_\mathcal{C}(A,f)$ and $F(f)$, respectively. Now this square must commute no matter what we start with in the upper-left corner, but let’s see what happens when we start with $1_A$. Around the upper right this gets sent to $f\in\hom_\mathcal{C}(A,B)$, and then down to $\Phi^x_B(f)$. Around the lower left we first send $1_A$ to $\Phi^x_A(1_A)=x\in F(A)$, which then gets sent to $\left[F(f)\right](x)$. So, in order for these chosen naturality squares to commute for this specific starting value we must define $\Phi^x_B:\hom_\mathcal{C}(A,B)\rightarrow F(B)$ so that $\Phi^x_B(f)=\left[F(f)\right](x)$.

Now I say that these definitions serve to make all the naturality squares commute. Let $f:B\rightarrow C$ be any arrow in $\mathcal{C}$ and write out the square:

$\begin{matrix}\hom_\mathcal{C}(A,B)&\rightarrow&\hom_\mathcal{C}(A,C)\\\downarrow{\Phi^x_B}&&\downarrow{\Phi^x_C}\\F(B)&\rightarrow&F(C)\end{matrix}$

Now, starting with $g\in\hom_\mathcal{C}(A,B)$ we send it right to $f\circ g\in\hom_\mathcal{C}(A,C)$, and then down to $\left[F(f\circ g)\right](x)\in F(C)$. On the other side we send $g$ down to $\left[F(g)\right](x)\in F(B)$, and then right to $\left[F(f)\right](\left[F(g)\right](x))=\left[F(f)\circ F(g)\right](x)=\left[F(f\circ g)\right](x)$. And thus the square commutes.

So, for every natural transformation $\Phi:h_A\rightarrow F$ we have an element $x_\Phi\in F(A)$, for every element $x\in F(A)$ we have a natural transformation $\Phi^x:h_A\rightarrow F$, and these two functions are clearly inverses of each other.

Almost identically, there’s a contravariant Yoneda Lemma, saying that $\mathrm{Nat}(h'_A,F)\cong F(A)$ for every contravariant functor $F$. You can verify that you’ve understood the proof I’ve given above by adapting it to the proof of the contravariant version.

There’s a lot here, and although it’s very elegant it may not be clear why it’s so interesting. I’ll come back tomorrow to try explaining what the Yoneda Lemma means.

June 6, 2007 Posted by | Category theory | 7 Comments

Annoying technology

WordPress’ native anti-spam measure Akismethas gone on the blink. Every comment I try posting to other WordPress sites is getting eaten. In particular, if the Angry Physicist reads this I hope he’ll try finding my recent attempt at commenting in his spam queue.

Anyhow, I’ll be doing some testing here to see if I can even comment on my own weblog. I do know that a few days ago one of my own posts’ trackbacks to an earlier post of mine got flagged, but I’d made numerous comments on other WordPress sites since then. Still, maybe Dr. Kaczynski had the right idea about technology.

[UPDATE]: Fifty tries of commenting last night and marking them as “not spam” and still nothing. WordPress uses this spam catcher which is allowed to capriciously decide that my IP address is a spammer with no notice, recourse for me, or accountability on their part. Akismet is broken and needs to be fixed.

June 6, 2007 Posted by | Uncategorized | 12 Comments

Full and Faithful Functors

We could try to adapt the definitions of epics and monics to functors, but it turns out they’re not really the most useful. Really what we’re most concerned with in transforming one category into another is their morphisms. The more useful notions are best phrased specifically with regard to the hom-sets of the categories involved.

Remember that a functor $F:\mathcal{C}\rightarrow\mathcal{D}$ between two (locally small) categories defines a function for each hom set: $F_{X,Y}:\hom_\mathcal{C}(X,Y)\rightarrow\hom_\mathcal{D}(F(X),F(Y))$. We now apply our standard definitions to these functions.

We say that a functor is “full” if for every pair of objects $X$ and $Y$ in $\mathcal{C}$ the function $F_{X,Y}$ is surjective. Similarly, we say that a functor is “faithful” if each function $F_{X,Y}$ is injective. When we apply these definitions to monoids (considered as categories with one object) we recover monomorphisms and epimorphisms of monoids, so we know we’re on the right track.

Now a subcategory $\mathcal{S}$ of a category $\mathcal{C}$ consists of a subclass of the objects of $\mathcal{C}$ and a subclass of the morphisms of $\mathcal{C}$ so that

• For each arrow in $\mathcal{S}$ both its source and target objects are in $\mathcal{S}$.
• For each object in $\mathcal{S}$ its identity arrow is in $\mathcal{S}$.
• For each pair of composable arrows in $\mathcal{S}$ their composite is in $\mathcal{S}$.

These conditions are enough to ensure that $\mathcal{S}$ is a category in its own right. There is an inclusion functor $I:\mathcal{S}\rightarrow\mathcal{C}$ sending each object and morphism of $\mathcal{S}$ to itself in $\mathcal{C}$. Clearly it’s faithful, since any two distinct arrows in $\mathcal{S}$ are distinct in $\mathcal{C}$.

What if this inclusion functor is also full? Then given any two objects $X$ and $Y$ in $\mathcal{S}$, every morphism $f:X\rightarrow Y$ in $\mathcal{C}$ is included in $\mathcal{S}$. We say that $\mathcal{S}$ is a “full subcategory” of $\mathcal{C}$. In practice, this means that we’ve restricted which objects of $\mathcal{C}$ we care about, but we keep all the morphisms between the objects we keep. For example, the category $\mathbf{Ab}$ of abelian groups is a full subcategory of $\mathbf{Grp}$.

Note that we have not given any conditions on the map of objects induced by a functor. In fact, the (unique) functor from the category $\mathbf{2}$ to the category $\mathbf{1}$ is faithful, even though it appears to lose a lot of information. Indeed, though we identify both objects from $\mathbf{2}$ in the image, the function on each hom-set is injective. Similarly, either functor from $\mathbf{1}$ to $\mathbf{2}$ is full. One condition on the object map that’s useful is that a functor be “essentially surjective”. A functor $F$ has this property if each object $D$ in the target category is isomorphic to an object $F(C)$ in the image of $F$.

Now, let functors $F:\mathcal{C}\rightarrow\mathcal{D}$ and $G:\mathcal{D}\rightarrow\mathcal{C}$ furnish an equivalence of categories. I say that $F$ (and, by symmetry, $G$) is full, faithful, and essentially surjective. Indeed, since $F\circ G\cong1_\mathcal{D}$ we have an isomorphism $F(G(D))\cong D$ for each object $D\in\mathcal{D}$, so $F$ is essentially surjective. The natural isomorphism $\eta:G\circ F\rightarrow 1$ says that for every arrow $f:C_1\rightarrow C_2$ we have $G(F(f))=\eta_{C_2}^{-1}\circ f\circ\eta_{C_1}$. The right side of this equation is a bijection from $\hom_\mathcal{C}(C_1,C_2)$ to $\hom_\mathcal{C}(G(F(C_1)),G(F(C_2)))$, and the left side is the composite $G_{F(C_1),F(C_2)}\circ F_{C_1,C_2}$. If $G$ were not full then the left side could not be always surjective, while if $F$ were not faithful then the right side could not be always injective. Since the right side is always a bijection, $G$ must be full and $F$ must be faithful. By symmetry $G$ is essentially surjective and faithful, and $F$ is full.

On the other hand, if a functor $F:\mathcal{C}\rightarrow\mathcal{D}$ is full, faithful, and essentially surjective, then it is one side of an equivalence of categories. The proof is a bit more involved, but basically it proceeds by building a functor $G$. Since each object of $\mathcal{D}$ is isomorphic to some object in the image of $F$ we pick such an object $F(C)\cong D$ for each $D$ and set $G(D)=C$. Then we have to find mappings of the hom-sets of $\mathcal{D}$ in a coherent way so that the resulting composites $F\circ G$ and $G\circ F$ are naturally isomorphic to the identity functors. I won’t fill in all the details here, but suffice it to say it can be done.

This, then, characterizes equivalences of categories the way injectivity and surjectivity of functions characterize isomorphisms of sets.

June 5, 2007 Posted by | Category theory | 10 Comments