The Unapologetic Mathematician

Mathematics for the interested outsider

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:
Product 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:
Product Functoriality 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:
Coproduct 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 John Armstrong | Category theory | | 6 Comments

Why I think undergraduates will need category theory

In the comments to my first category theory post, Peter had something interesting to say. So interesting, in fact, that I decided to promote my response to an actual post.

I said “algebra” rather than “mathematics” in that post for two reasons.

First of all, yes it is a form of algebra, and the theory of small categories is every bit as useful as the theory of groups and rings and such. Categories are “like monoids but more so”, and linear categories are “like rings but more so”. Small categories are great algebraic structures in their own right, but more on that later. As for the metamathematical side, just because other forms of mathematics find such a beautiful expression in an algebraic language doesn’t make the language any less algebra.

Secondly, algebra is already seen in some circles as being further removed from reality than, say, analysis. There does exist the view that analysis is real mathematics, algebra a convenient abstraction for generalizing and streamlining analytic theories, and category theory just abstract nonsense.

As for your comparisons.. what’s so surprising about Brauer groups or Ricci flow (I must confess I’m not familiar with the Kakeya problem)? Bruce Kleiner explained Ricci flow to me in no more than five minutes, and other than all that analytic messiness Perelman worked out it seems perfectly natural that it should work. Brauer groups are even simpler, at least from the categorical viewpoint, although I’m still mystified why people want to work with the decategorification rather than the real thing.

My example of the natural transformation from the identity functor to the double-dual was just that — an example. And I brought it out because that was what gripped me when I first saw it. It’s fascinating (to me) that there’s a language and a definition of what we rhetorically call “natural”.

And why is there this undercurrent (not just in your comment) that mathematics has to be so hard to be interesting? The verification of many fine theorems is perfectly simple once you’ve set them up correctly. Grothendieck himself said he’d rather let a nut open on its own under the influence of the sun and the rain than to go at it with hammer and chisel.

What makes Yoneda’s Lemma so fascinating is not that it’s amazingly difficult, but that it’s both simple and transcendent. It’s what makes Cayley’s theorem go. It’s what makes quite a lot of modern algebraic geometry go. It’s even what makes tensor products go, which I haven’t seen written down, but I’m certain someone else had it figured out long before I stumbled upon it a couple years ago.

Now eventually I’ll be able to get right down and talk more directly about my own work, and that may satisfy you. In fact, it goes back to my first response: tangles form a category, and this allows a directly algebraic attack on knot theory, which I think will eventually become the new foundation of the subject. In fact, knot theory only becomes more and more complex the harder you fight against looking at the category of tangles. When you lay back and enjoy it, the proofs become almost effortless and the meaning becomes clear.

Now, maybe that sort of thing doesn’t appeal to you. Maybe you explicitly (not just implicitly) think that mathematics is supposed to be difficult. But there we would have to disagree. Mathematics is getting too complicated for even people who use it (like physicists) to get in all they need to know without some form of analogizing, and analogies in mathematics are called “functors”. Thinking categorically lays bare the inherent structure of an argument.

I’m not saying that every student will need to use categories in the future. I’m saying that undergraduates being conversant with basic categorical language will become pedagogically necessary in order to get through all the other mathematics they should be learning.

June 11, 2007 Posted by John Armstrong | rants | | 13 Comments