The Unapologetic Mathematician

Mathematics for the interested outsider

Mathematics competitions

I’m about to head off to participate on the “alumni” team in a scrimmage for the Howard County and Baltimore County teams going to the American Regions Math League.

As the term “alumnus” connotes, I did this stuff myself back in high school. To be honest, I thought that it was pretty silly even then. It ends up emphasizing speed and trivia over deep understanding of mathematics. The various Olympiads are better, but still not great. There’s something in the society at large, though, that wants to reduce every single human activity to a contest, and mathematics for high school students is no exception. If I hadn’t already been studying more advanced material on my own, I could easily see ARML beating the enjoyment of mathematics out of me.

Still, some kids like running the races and like memorizing a billion little factoids. If they enjoy it, fine, and it’s close enough to real mathematics to make it worth encouraging. And so I do my part.

May 22, 2007 Posted by | rants | 1 Comment

Functors

As with all the other algebraic structures we’ve considered, we’re interested in the “structure-preserving maps” between categories. In this case, they’re called “functors”.

A functor F from a category \mathcal{C} to a category \mathcal{D} consists of two functions, both also called F. One sends objects of \mathcal{C} to objects of \mathcal{D}, and the other sends morphisms of \mathcal{C} to morphisms of \mathcal{D}. Of course, these are subject to a number of restrictions:

  • If m is a morphism from X to Y in \mathcal{C}, then F(m) is a morphism from F(X) to F(Y) in \mathcal{D}.
  • For every object X of \mathcal{C}, we have F(1_X)=1_{F(X)} in \mathcal{D} — identities are sent to identities.
  • Given morphisms f:X\rightarrow Y and g:Y\rightarrow Z in \mathcal{C}, we have F(g\circ f)=F(g)\circ F(f) in \mathcal{D} — a functor preserves compositions.

It’s tempting at this point to think of a “category of categories”, but unfortunately this gets hung up on the same hook as the “set of sets”. A lot of the intuition goes through, however, and we do have a category \mathbf{Cat} of small categories (with only a set of objects and a set of morphisms) and functors between them.

Every category \mathcal{C} comes with an identity functor 1_\mathcal{C}. This is an example of an “endofunctor” (in analogy with “endomorphism”).

Every category of algebraic structures we’ve considered — \mathbf{Grp}, \mathbf{Mon}, \mathbf{Ring}, R-\mathbf{mod}, etc. — comes with a “forgetful” functor to the category of sets. Remember that a group (for example) is a set with extra structure on top of it, and a group homomorphism is a function that preserves the group structure. If we forget all that extra structure we’re just left with sets and functions again.

To be explicit, there is a functor U:\mathbf{Grp}\rightarrow\mathbf{Set} that sends a group (G,\cdot) to its underlying set G. It sends a homomorphism f:G\rightarrow H to itself, now considered as a function on the underlying sets. It should be apparent that this sends the identity homomorphism on the group G to the identity function on the set G, and that it preserves compositions. The same arguments go through for rings, monoids, R-modules.

In fact, there are other forgetful functors that behave in much the same way. A ring is an abelian group with extra structure, so we can forget that structure to get a functor from \mathbf{Ring} to \mathbf{Ab} — the category of abelian groups. An abelian group, in turn, is a restricted kind of group. We can forget the restriction to get a functor from \mathbf{Ab} to \mathbf{Grp}.

Now for some more concrete examples. Remember that a monoid is a category with one object. So what’s a functor between such monoids? Consider monoids M and N as categories. Then there’s only one object in each, so the object function is clear. We’re left with a function on the morphisms sending the identity of M to the identity of N and preserving compositions — a monoid homomorphism!

What about functors between preorders, considered as categories? Now all the constraints are on the object function. Consider preorders (P,\leq) and (Q,\preceq) as categories. If there is an arrow from a to b in P then there must be an arrow from F(a) to F(b). That is, if a\leq b then F(a)\preceq F(b). Functors in this case are just order-preserving functions.

These two examples show how the language of categories and functors subsumes both of these disparate notions. Preorder relations translate into the existence of certain arrows, which functors must then preserve, while monoidal multiplications translate into compositions of arrows, which functors must then preserve. The categories of (preorders, order-preserving functions) and (monoids, monoid homomorphisms) both find a natural home with in the category of (small categories, functors).

May 22, 2007 Posted by | Category theory | 4 Comments

Categories

Like groups, rings, modules, and other algebraic constructs, we define a category by laying out what’s in it, and how those things relate to each other.

The first difference that gives some people pause is that we don’t start with a set, but a class. Classes are pretty much like sets, but they can be “bigger”. In particular, we sometimes run into technical problems with sets containing other sets, so we introduce classes as things that can hold any sort of sets with no problem. Of course we’ve only pushed back the problem to when we might want to collect classes together, but we’ll burn that bridge when we come to it.

Anyhow, there’s really nothing that bad about basing an algebraic structure on a class. There are perfectly good reasons (we’ll see) for putting a ring structure on a class. In this case we call the result a “large ring”. On the other hand, when every class involved in a category is a set, we call it a “small category”. Seriously, it’s not as big a deal as people seem to think.

Okay, that out of the way; a category \mathcal{C} consists of two classes: the “objects” and the “morphisms”, or sometimes “points” and “arrows”. These are denoted {\rm Ob}(\mathcal{C}) and {\rm Mor}(\mathcal{C}), respectively.

Every morphism m has a “source” and a “target” object: s(m) and t(m). If a morphism m has source a and target b we often write m:a\rightarrow b. The class of all morphisms in \mathcal{C} with source a and target b is written \hom_\mathcal{C}(a,b), or just \hom(a,b) if the category is understood. If all these “hom-classes” are actually sets, we say the category is “locally small”. Most of the categories we consider will be locally small, and I’ll just use this assumption without mentioning it explicitly.

Given any three objects a, b, and c, we have an operation of “composition”: \circ:\hom(b,c)\times\hom(a,b)\rightarrow\hom(a,c). We think of this as taking an arrow from a to b and one from b to c and joining them tip-to-tail to make an arrow from a to c. This composition must be associative — the following diagram commutes:
\begin{matrix}\hom(c,d)\times\hom(b,c)\times\hom(a,b)&\rightarrow&\hom(c,d)\times\hom(a,c)\\\downarrow&&\downarrow\\\hom(b,d)\times\hom(a,b)&\rightarrow&\hom(a,d)\end{matrix}

Also, every object a has an “identity” morphism 1_a:a\rightarrow a so that 1_a\circ m=m for all m\in\hom(b,a) and m\circ1_a=m for all m\in\hom(a,b).

We can see that this looks a lot like the definition of a monoid, and for good reason: a monoid is “just” a (small) category with a single object. Walk through the definitions and say that there’s only one object. You’ll see that every morphism has the same source and target, so they can all be composed with each other. Then we’ve got a set of morphisms equipped with an associative composition with an identity element — a monoid!

The most commonly seen use of categories is to describe other algebraic structures. The standard example here (which will motivate much of our later definitions) is \mathbf{Set}: the category of sets. This has as objects the class of all sets (which can’t itself be a set). The morphisms \hom_\mathbf{Set}(X,Y) are all functions f:X\rightarrow Y.

Similarly, we have the categories \mathbf{Grp} — groups — \mathbf{Ring} — rings with identity — R-\mathbf{mod} — left R-modules — and so on. Each of these categories has as objects the class of all the apropriate algebraic structures, and as morphisms all homomorphisms of those structures.

As a more concrete example, consider a ring R with unit. We construct a small category \mathbf{Mat}_R as follows: take as objects the set \mathbb{N} of natural numbers. The morphisms \hom_{\mathbf{Mat}_R}(m,n) are all m\times n matrices with entries in R. The composition is regular matrix multiplication, and the identity on the object n is the n\times n identity matrix.

Another great example of a category is a preorder. Given a preorder (P,\leq) we take the set of elements P as the objects of our category. Then we say that there is a single morphism in \hom_P(x,y) if x\leq y and no morphisms in the hom-set otherwise. Reflexivity tells us that there is a morphism in \hom(x,x) for every object x which can serve as an identity, and transitivity tells us that if there’s a morphism in \hom(x,y) and one in \hom(y,z), then there’s one in \hom(x,z) which can serve as their composite.

For a good while we’ll be giving a lot of definitions of concepts in the language of categories, usually motivated from the category of sets. Category theory gets a bad rap as involving a lot of definitions, but the language really does streamline a lot of thought about mathematics, so it’s worth picking up a basic fluency. Everything I’ll define in this first series I’ve actually already given good examples of in special cases, so the motivation should be apparent. We’ll see them coming up again and again in later work, which (I hope) will help lead to a comprehension of later mathematical concepts by analogy from the simpler concepts in algebra.

May 22, 2007 Posted by | Category theory | 14 Comments

   

Follow

Get every new post delivered to your Inbox.

Join 392 other followers