Shh! Don’t tell anybody!

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

Products and Coproducts

Let’s consider the Cartesian product of two sets and . Classically we think of this as the set of all pairs with and . But we can also characterize it just in terms of functions.

Specifically, comes with two projection functions and , defined by and . If we take any other set with functions and we can define the function by . Then we see that and . Further, this function from to 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 and is a set with functions and so that for any other set with functions to and there exists a unique arrow to 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 containing (among others) objects and . From this we’re going to build a new category. An object of our category will be a diagram that looks like in . A morphism from to will be a morphism in so that and .

Now what’s a product in ? 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 , though the category we build from a given pair of objects may not have a terminal object, so a given pair of objects of may not have a product in . If every pair of objects of has a product in , we say that “has products”.

So, the existence of Cartesian products of sets shows that has products. Similarly, has products, as do , (groupoids), (small categories), and pretty much all our familiar categories from algebra.

What about something like a preordered set , considered as a category? What would “product” mean, when written in this language? Well, given elements and the product will have arrows to and , so and . Also, for any other element with and we have — has an arrow to both and , so it has an arrow to . That is, is a greatest lower bound of and , 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 that has products, the product defines a functor ! If we have arrows and then I say we’ll have an arrow . Indeed, if we consider and then we’ll get an arrow from to . And this construction preserves compositions and identities. For compositions, start with this diagram:

and draw in the induced arrows , , and . 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 this property is satisfied by disjoint unions. In coproducts are free products. In a preorder, coproducts are least upper bounds. And, of course, the coproduct defines a functor from to .

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.

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 in a category is one so that has exactly one element for each object . Many of the categories we’ve considered have initial objects. For example:

• The empty set is the initial object of , since there’s exactly one function from the empty set to any other set.
• The trivial group is the initial object of , since (again) there’s only one group homomorphism from the trivial group to any other group.
• The initial object of the category 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 and are both initial. Then there is exactly one arrow , and exactly one . They compose to give arrows and , 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 so that every 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 , since there’s only one function from any other set into it: send all elements of to the same point.
• The trivial group is also the terminal object of , since there’s only one homomorphism into it from any group.
• It turns out that the trivial group is also the terminal object in , 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.

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 and a left action of on a set . Now let’s build a groupoid from this information. The high-level view is that every single move from one state (element of ) 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 , and the morphisms to be the set . The source of a morphism will be , and the target will be . For each object we have the identity morphism , where is the identity of . If we have two morphisms and , and (so the pair are composable), then we have the composite . Note that this still has source , and its target is , 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 going from to , we’ll need the inverse to go from to . The clear choice is , and indeed we find that , and . Thus we have a groupoid.

This result we call the “action groupoid” or the “weak quotient”, and write . Remember that the “real” quotient is the set of orbits of on — we consider two elements of to be “the same” if they are related by an element of . 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 . Just send every single object of to the unique object of , considered as a category. Then send the morphism to . We’re sort of folding up the groupoid into the groupoid (with one object) . But here’s the thing: this functor is faithful! Indeed, we see that is the set of so that . In particular, it’s a subset of the elements of , and the functor acts on this hom set by the inclusion function of this subset into , 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 equivalent to and compatible with this faithful functor. That is, if the functor above is , we can find a groupoid with functors and . The functor will be an equivalence, will be faithful, and we’ll have . The really special thing about is that it will be a collection of groups with no morphisms between any distinct objects.

For the objects of , take the set of -orbits of . 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 pick a point and let — the stabilizer of . 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 , just send each object of to the single object of and include each hom set into as a subgroup, just like we did for .

Now we define our equivalence. Since we’ve already picked a representative point in each orbit, let’s just send the object of corresponding to that orbit to the object of corresponding to that point. Then we can just send to itself. Clearly this is fully faithful, and it’s also essentially surjective because every point of is in some -orbit. So we have an equivalence. Also it should be clear that .

In fact, we can adapt this to any groupoid with a faithful functor to a group . Just replace “in the same orbit” by “have an arrow between them”. Then chop up the objects of into equivalence classes, make each one an object of our new groupoid , and make the morphisms on an object in the “stabilizer” of a representative object from . 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 (“discrete” = no morphisms between distinct objects) with a faithful functor and puff it up into an action groupoid. In fact, it suffices to show how to do this for a single object in , since all the others go the same way.

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

Putting this all together we see that any groupoid with a faithful functor is equivalent to the action groupoid for some -set . And any action gives an action groupoid with a faithful functor to . The two concepts are essentially the same.

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 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 for to act on, and a homomorphism from to the group of bijections on . But is an object in the category of sets, and bijections from to itself are just the invertible morphisms in . What we’re describing here is a functor from to ! A (left) action of is an object of the category of (covariant) functors from to . We know it’s a category because 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 -action. This is pretty much the same, but it satisfies instead of . That is, it switches the order of composition. But we know how to do that! A right -action is a contravariant functor — an object of .

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 and , and that and send the single object of to the sets and , respectively. Now, what’s a natural transformation ?

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

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 we only get one covariant functor and one contravariant functor . The covariant one gives us the group 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 -action (covariant functor) on Yoneda’s Lemma tells us that the set is in bijection with the set of functions satisfying . In particular, we must have , where is the identity of the group, so the image of the identity element specifies the function completely. That is, if we have a left -action on a set then every element gives us an intertwining function satisfying , and every intertwining function sends to some element of , giving us our bijection. A similar situation holds for right -actions.

What about the Yoneda embedding ? Well as we noted above, this sends the single object of to the set of elements of acting on itself on the right (because the target is the category of contravariant functors). But is a functor, so it sends morphisms of (group elements) to morphisms of (-intertwining functions). Specifically, a group element gets sent to a function satisfying .

Even better, we can compose these natural transformations! Since is a functor we have . Also, must be the identity function on — . Putting this all together, we see that , and indeed multiplying by on the left commutes with multiplying by another element of on the right, since group composition is associative! So we have a function sending to the group of permutations of the elements of , and this function preserves group multiplication and identities. Then it must also preserve inverses, and we have a group homomorphism from to .

And now for the coup de grâce: the Yoneda embedding is fully faithful! Firstly, this means that the homomorphism 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 which commutes with right-multiplication is given by left-multiplication by some element of .

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 -torsor is a (left) -action on a set, which is isomorphic to the action of on itself by left-multiplication. That link will take you to an excellent explanation (with great examples) by John Baez.

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 defined by . We can turn this into a function of one variable that returns another function. Specifically, if we write for the set of functions from the natural numbers to themselves, we can write , where . That is, is the function that sends to . 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 . Then for any object we have a functor . Now when we change the object by applying a morphism we get a natural transformation . It should have components . The clear choice is , and indeed this is natural since the morphisms from commute with those from .

Now, strictly speaking this may not be a functor since we only know that is a category when at least one of and is small, but the general idea should be clear.

Now to the situation at hand: we know that any category comes equipped with a functor . We apply this Currying operation on each slot to get two “functors” and . Of course, the targets are only sure to be categories when (and thus 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 sends an object to the covariant functor , while sends an object to the contravariant functor . Since the objects of and are the same, I hope that using for both won’t be too confusing.

Now let’s take the statement of the (covariant) Yoneda Lemma and apply it to the functor for some object . It says that . But notice that is — the set of morphisms from to in the functor category . Now since is a functor from to , it acts on the hom sets, sending to . And the Yoneda Lemma tells us that this is a bijection — the functor is fully faithful!

And the same argument goes through for . Now we apply the contravariant Yoneda Lemma to see that . The functor 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 can be seen as a full subcategory of . 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 -valued functor on that category.

And now: which contravariant -valued functors on a category are so special that they constitute objects of 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 ?”

These are just the representable functors.

The representable, contravariant, -valued functors on a category constitute a full subcategory of all contravariant -valued functors on , which is equivalent to the category itself.

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

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 and an object we’ll use to denote the covariant functor represented by and to denote the contravariant one. That is, and .

Now given a covariant functor , we’re interested in the set of natural transformations . Note that not all of these are natural isomorphisms. Indeed, 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 and .

Seriously.

And the proof is actually pretty clear too. One direction leaps out when you think of it a bit. A natural transformation has components , sending morphisms of to elements of certain sets. Now, given any category and any object, what morphism do we know to exist for certain? The identity on ! So take and stick it into and we get an element . The really amazing bit is that this element completely determines the natural transformation!

So let’s start with a category , an object , a functor , and an element . From this data we’re going to build the unique natural transformation so that . We must specify functions so that for every arrow in we satisfy the naturality condition. For now, let’s focus on the naturality squares for morphisms , and we’ll show that the other ones follow. This square is:

where the horizontal arrows are and , 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 . Around the upper right this gets sent to , and then down to . Around the lower left we first send to , which then gets sent to . So, in order for these chosen naturality squares to commute for this specific starting value we must define so that .

Now I say that these definitions serve to make all the naturality squares commute. Let be any arrow in and write out the square:

Now, starting with we send it right to , and then down to . On the other side we send down to , and then right to . And thus the square commutes.

So, for every natural transformation we have an element , for every element we have a natural transformation , and these two functions are clearly inverses of each other.

Almost identically, there’s a contravariant Yoneda Lemma, saying that for every contravariant functor . 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.

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.

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 between two (locally small) categories defines a function for each hom set: . We now apply our standard definitions to these functions.

We say that a functor is “full” if for every pair of objects and in the function is surjective. Similarly, we say that a functor is “faithful” if each function 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 of a category consists of a subclass of the objects of and a subclass of the morphisms of so that

• For each arrow in both its source and target objects are in .
• For each object in its identity arrow is in .
• For each pair of composable arrows in their composite is in .

These conditions are enough to ensure that is a category in its own right. There is an inclusion functor sending each object and morphism of to itself in . Clearly it’s faithful, since any two distinct arrows in are distinct in .

What if this inclusion functor is also full? Then given any two objects and in , every morphism in is included in . We say that is a “full subcategory” of . In practice, this means that we’ve restricted which objects of we care about, but we keep all the morphisms between the objects we keep. For example, the category of abelian groups is a full subcategory of .

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 to the category is faithful, even though it appears to lose a lot of information. Indeed, though we identify both objects from in the image, the function on each hom-set is injective. Similarly, either functor from to is full. One condition on the object map that’s useful is that a functor be “essentially surjective”. A functor has this property if each object in the target category is isomorphic to an object in the image of .

Now, let functors and furnish an equivalence of categories. I say that (and, by symmetry, ) is full, faithful, and essentially surjective. Indeed, since we have an isomorphism for each object , so is essentially surjective. The natural isomorphism says that for every arrow we have . The right side of this equation is a bijection from to , and the left side is the composite . If were not full then the left side could not be always surjective, while if were not faithful then the right side could not be always injective. Since the right side is always a bijection, must be full and must be faithful. By symmetry is essentially surjective and faithful, and is full.

On the other hand, if a functor 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 . Since each object of is isomorphic to some object in the image of we pick such an object for each and set . Then we have to find mappings of the hom-sets of in a coherent way so that the resulting composites and 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.