unnatural projections

Research in Mathematics: A Postmortem

April 30, 2009 by nbloomf

Yesterday I found out that my first research paper, coauthored with Cameron Wickham at Missouri State University, was accepted for publication in Communications in Algebra. The work that resulted in that paper was my first experience with a serious research project, and so I’m feeling pretty good today.

While this experience is still fresh on my mind, I’d like to sit down and reflect on a few things I’ve learned about the process of doing research in mathematics. The details of the project aren’t important here- I’m writing about research, not the project. Of course all of this is coming from one young person’s limited experience, and your mileage may vary.

REU (Research Experience for Undergraduates) programs are a fantastic idea. I got involved with research at an REU my first summer out of college. In case you aren’t familiar with REUs, they are like super math camp for adults. They are usually a two month summer program that brings together undergraduate students from all over to work on a handful of research problems with faculty. An REU is to mathematicians what an internship is to other professionals; it allows you to see what the work is like before committing yourself to the career. That REU was where I met Cameron Wickham and this research project started.
Research is an incredibly effective way to learn a lot in a short amount of time. Mathematics tends to be a pretty dry subject. Trying to just read through a book is, except for a select few, not an effective way to really grok mathematics. Even taking a class can only help you so much. But having a problem to work on really makes the material come alive. You wouldn’t try to learn to draw without drawing, or to write without writing. In the same way, I don’t think you can really learn mathematics without doing mathematics.
It’s very important to know other researchers in (and out of!) your area. I learned this from my advisor and coauthor, since he was the one with all the contacts. At least three of the papers that our results relied on were unpublished at the time we were writing; we got them as preprints directly from their authors. If we had had to wait for these results to be published, it would have set us back by up to a year, maybe more. In this respect the internet is a great tool for bringing together people in relatively small and widely spread out communities. But you already knew that.
Research is far more fulfilling than class work. There is no comparison. As a not-yet-Ph.D.-candidate grad student, I still have to take classes that involve sitting in a room with a dozen other people, silently listening to lectures, and handing in homework assignments. Having tasted research, I’m having trouble with this more passive mode of learning. Research requires you to interact with material, to be critical and to ask questions in lots of directions at once, even questions that (gasp!) go beyond the scope of the course. Believe it or not, research trains you to evaluate theorems based on their usefulness. Not every teacher appreciates this in class. Fellow students don’t always appreciate this, either. In class, you’re always learning stuff that was nailed down in the past. Sometimes a long time in the past. But with research you’re trying to beat down new paths, and every once in a while, for a brief moment, you learn some little thing that probably noone else in the world knows. It really makes you feel like an explorer, and the great thing is that the more you learn, the more questions you have. The frontier will never be completely conquered. Don’t get me wrong; classes are important. They’re just not nearly as much fun.
The initial investment of time is steep, but your effort compounds. This project took a year and a half to go from choosing the goal to submitting the manuscript. Granted, in that time I had to get up to speed on a lot of commutative algebra, was a grad student, taught a couple of classes, moved to another state, bought a house, and had a baby (well, my wife did). So it wasn’t a year and a half of solid work. But still, that’s a long time to stay focused on a goal. But now I have several ideas for where the research can go in the future. In fact Cameron and I have already started working on a second paper, which is progressing much more quickly than the first due to the experience we gained.
You will experience false starts, bad ideas, and embarrassment. But it doesn’t matter. I can’t even remember how many wrong ideas I had while working on this project. I would rush into a meeting one week with a new idea, only to have to admit the next week that it didn’t work. Several times I completely misunderstood some fundamental thing, and my advisor would discreetly try to convince me that I was wrong. The important thing is to be able to honestly recognize when you are wrong and fix it.

To conclude, I would strongly recommend that undergraduate math students give research a try. I’ll be honest- it’s not for everyone. Not all students thrive in that kind of ambiguous and open ended setting. But if you enjoy it, research is a very rewarding activity.

Posted in Math, Miscellany | 1 Comment »

Categorical Breadcrumbs: Products from another angle

February 10, 2009 by nbloomf

In this post, we’re going to look at product objects again, this time in a slightly different way. At the risk of giving away the punch line, we’re going to see that a product $A \sqcap B$ can be realized as a terminal object in a particular category.

Let $\mathcal{C}$ be a category, and fix two objects $A$ and $B$ in $\mathcal{C}$ . I’m going to call a triple $(X,\varphi_1,\varphi_2)$ , where $\varphi_1 : X \rightarrow A$ and $\varphi_2 : X \rightarrow B$ , a preproduct. This word isn’t standard, but it will be useful for now.

Suppose $(X, \varphi_1, \varphi_2)$ and $(Y, \psi_1, \psi_2)$ are preproducts. A preproduct homomorphism is a map $\alpha : X \rightarrow Y$ such that $\varphi_1 = \psi_1 \circ \alpha$ and $\varphi_2 = \psi_2 \circ \alpha$ . That is, the following diagram commutes.

Now note a few things about preproducts.

The composition of preproduct homomorphisms is a preproduct homomorphism. Suppose $(X,\varphi_1,\varphi_2)$ , $(Y,\psi_1,\psi_2)$ , and $(Z,\chi_1,\chi_2)$ are preproducts, and that $\alpha : X \rightarrow Y$ and $\beta : Y \rightarrow Z$ are preproduct homomorphisms. Then we have $\varphi_1 = \psi_1 \circ \alpha$ and $\varphi_2 = \psi_2 \circ \alpha$ and $\psi_1 = \chi_1 \circ \beta$ and $\psi_2 = \chi_2 \circ \beta$ . Then $\varphi_1 = \chi_1 \circ \beta \circ \alpha$ and $\varphi_2 = \chi_2 \circ \beta \circ \alpha$ , and so the following diagram commutes.
If $(X,\varphi_1,\varphi_2)$ is a preproduct, $\mathsf{id}_X$ is a preproduct homomorphism. This can be seen by noting that the following diagram commutes.
$\mathsf{id}_X$ acts like an identity morphism on preproduct homomorphisms. I’ll let you convince yourself of this.

By the above discussion, the classes of preproducts and of preproduct homomorphisms form the objects and morphisms of a category which I’ll call $\mathcal{D}$ .

Suppose a terminal object exists in $\mathcal{D}$ . That is, we have a preproduct that is the target of a unique morphism from every other preproduct. Translating back into $\mathcal{C}$ , that means we have a triple $(X, \pi_1, \pi_2)$ such that, for every other triple $(Z, \varphi_1, \varphi_2)$ there is a unique morphism $\theta : Z \rightarrow X$ such that $\varphi_1 = \pi_1 \circ \theta$ and $\varphi_2 = \pi_2 \circ \theta$ . That is precisely the definition of a product in $\mathcal{C}$ !

We could do a similar thing with coproducts, turning them into an initial object in an appropriate category. But we’re not going to do that. Instead, we’re going to introduce some concepts in the next few posts that will allow us to perform this trick in great generality. To do this, we’ll need to understand natural transformations and functor categories. But first we’ll take a look at exponential objects. I should warn you that it only gets more abstract from here.

Posted in Breadcrumbs | Leave a Comment »

Categorical Breadcrumbs: What is a group?

February 7, 2009 by nbloomf

We all know what a group is – a set with an associative binary operator, identity element, and inverses. At least, that’s the definition most people remember. (Among those people who remember such things.

) In this post we’re going to play the generalization game; we’re going to try to rewrite the definition of group in purely categorical terms.

For now, we’ll play inside the category $\textsc{Set}$ . There, a group is a

set $G$ with an
associative binary operator $\star : G \times G \rightarrow G$ and an
identity element $e \in G$ (so $e \star g = g \star e = g$ ) and such that
for every $g \in G$ there is an element $g^{-1}$ such that $g \star g^{-1} = g^{-1} \star g = e$ .

Remember that in $\textsc{Set}$ , the cartesian product is the categorical product. So we can write the operator as $\star : G \sqcap G \rightarrow G$ . But how can we express that $\star$ is associative using balls and arrows? Try the following commutative diagram.

If we chase elements around the diagram, this says that

So we’ve encoded the fact that $\star$ is associative using only categorical ideas. Can we do the same for the identity element? Here we have a problem, because in general it doesn’t make sense to talk about elements of an object. However, note that for every element $x$ of a set $X$ , there is a unique morphism $\underline{x} : \{ \ast \} \rightarrow X$ such that $\underline{x}(\ast) = x$ . Likewise, functions from $\{ \ast \}$ correspond to single elements of $X$ . So rather than dealing with $e$ itself, lets define a function $\underline{e} : \{ \ast \} \rightarrow G$ . This trick was used in this post to prove that left cancellable set functions are injective. What diagram appropriately captures the essence of identityhood? Try this one.

You can chase some elements through this diagram to verify that it encodes the fact that $e$ is an identity element – however, it doesn’t explicitly mention $e$ . Now what about inverses? First, let’s turn the “inverse” operator into a function $v : G \rightarrow G$ with $g \stackrel{v}{\mapsto} g^{-1}$ . Also, note that $\{ \ast \}$ is terminal in $\textsc{Set}$ , so we have a unique arrow $0 : G \rightarrow \{ \ast \}$ . Then the condition that every element has a left and right inverse is equivalent to demanding that the following diagram commute.

Where $\Delta$ is the diagonal map. And so, we’ve rewritten the group axioms in the language of categories. I’ll collect the definition here for skimming.

Definition. Suppose $\mathcal{C}$ is a category with a terminal object $X$ . A group object in $\mathcal{C}$ (or just group) is a tuple $(G,\star,\varepsilon,\nu)$ where $G$ is an object, $\star : G \sqcap G \rightarrow G$ , $\varepsilon : X \rightarrow G$ , and $\nu : G \rightarrow G$ such that the following diagrams commute.

To belabor the point, we can now talk about groups in a way that is completely independent of sets. The ordinary groups we usually deal with are simply group objects in $\textsc{Set}$ . Group objects in $\textsc{Top}$ are topological groups. I don’t know of any examples right now, but it is possible that lots of other interesting instances of these generalized groups are out there waiting to be found. But we can see now that what we thought was a group was really just a very specific example of a more general concept.

As you might expect, we can generalize a good bit of group theory to group objects. For example, we can define homomorphisms as follows.

Definition. Suppose $(G,\star,\varepsilon,\nu)$ and $(H,\diamond,\delta,\eta)$ are group objects. A group object homomorphism (or simply group homomorphism) is an arrow $\varphi : G \rightarrow H$ such that the following diagram commutes.

It is straightforward to show that $\mathsf{id}_G$ is always a group homomorphism and that the composition of two group homomorphisms is a group homomorphisms. And so the classes of group objects and of group object homomorphisms in $\mathcal{C}$ are the balls and arrows of a category I’ll call $\mathcal{C}_{\mathsf{grp}}$ .

We can show that left and right multiplication are homomorphisms.

We can play a similar game with other kinds of algebraic structures. I won’t clutter up this post with that discussion, but keep in mind that the most basic, useful, and (in some ways) important structure we can generalize in this way is a monoid: a set with an associative binary operator and identity element. I’ll devote a whole post to that later.

Now here’s a question that’s got me really thinking: what is the dual of a $\mathcal{C}$ -group? A cogroup, if you will. Does such a thing have any interesting uses? What would it look like in the category of sets? I don’t know the answers to these questions at the moment, but I’ll definitely look into it. If you have any ideas, please leave a comment.

Posted in Breadcrumbs | Leave a Comment »

Categorical Breadcrumbs: Distributive Categories

February 7, 2009 by nbloomf

In the last couple of posts, we’ve looked at products and coproducts in arbitrary categories. We saw that both products and coproducts are essentially associative, essentially commutative, and have “identity objects” – terminal and initial objects, respectively. Today we’re going to see that sometimes, but not always – products and coproducts satisfy a distributive law.

First, note that by the properties of products and coproducts, if all the objects exist then the following diagram commutes.

We will define $\mathsf{undistL} = \lbrack \varphi_1, \varphi_2 \rbrack$ ; a map $\mathsf{undistR} : (B \sqcap A) \sqcup (C \sqcap A) \rightarrow (B \sqcup C) \sqcap A$ may be defined analogously. If $\mathsf{undistL}$ is an isomorphism for all objects $A,B,C$ , then we say $\mathcal{C}$ is distributive, and we define $\mathsf{distL} = \mathsf{undistL}^{-1}$ .

Examples

$\textsc{Set}$ is distributive.

Note that in a distributive category, product and coproduct act like times and plus in a ring. For this reason, if a category is product- and coproduct-closed and distributive, we sometimes use $\times$ and $+$ rather than $\sqcap$ and $\sqcup$ to denote products and coproducts.

As an example, consider the category of sets. In this category, objects are isomorphic precisely when they are equipollent (when they have the same cardinality). And so every finite set is isomorphic to $\lbrack k \rbrack = \{ \ast_1, \ast_2, \ldots, \ast_k \}$ for some $k$ . It isn’t hard to show that $\lbrack a \rbrack \times \lbrack b \rbrack \cong \lbrack ab \rbrack$ and $\lbrack a \rbrack + \lbrack b \rbrack \cong \lbrack a+b \rbrack$ , where of course we distinguish between integer addition and coproduct and between integer multiplication and product.

We will see distributive categories again later, once we’ve seen limits and continuous functors. It turns out that the analogy of $\sqcap$ and $\sqcup$ to ring operators is quite fruitful, and in fact has some nice applications to data structures in functional languages.

Posted in Breadcrumbs | Leave a Comment »

Categorical Breadcrumbs: More on Morphisms II

February 5, 2009 by nbloomf

In this post, we’re going to take a time out to prove some theorems about how products and coproducts interact with different kinds of morphisms.

Theorem. If $\varphi$ and $\psi$ are retractable and the products exist, then $\varphi \sqcap \psi$ is retractable.

Proof. Suppose $\varphi^\prime \circ \varphi = \mathsf{id}_A$ and $\psi^\prime \circ \psi = \mathsf{id}_B$ . Then the following diagram commutes.

Then we have

$\begin{array}{rcl} \pi_1^\prime \circ (\varphi \sqcap \psi) & = & \varphi \circ \pi_1 \\ \varphi^\prime \circ \pi_1^\prime \circ (\varphi \sqcap \psi) & = & \varphi^\prime \circ \varphi \circ \pi_1 \\ \pi_1 \circ (\varphi^\prime \sqcap \psi^\prime) \circ (\varphi \sqcap \psi) & = & \pi_1. \end{array}$

The last equation is solved uniquely. Since $\pi_1 \circ \mathsf{id}_{A \sqcap B} = \pi_1$ , then, $(\varphi^\prime \sqcap \psi^\prime) \circ (\varphi \sqcap \psi) = \mathsf{id}_{A \sqcap B}$ . So $\varphi \sqcap \psi$ is retractable. $\square$

Theorem. If $\varphi$ and $\psi$ are sectionable and the products exist, then $\varphi \sqcap \psi$ is sectionable.

Proof. Suppose $\varphi \circ \varphi^\prime = \mathsf{id}_{A^\prime}$ and $\psi \circ \psi^\prime = \mathsf{id}_{B^\prime}$ . Then the following diagram commutes.

Then we have the following.

$\begin{array}{rcl} \pi_1 \circ (\varphi^\prime \circ \psi^\prime) & = & \varphi^\prime \circ \pi_1^\prime \\ \varphi \circ \pi_1 \circ (\varphi^\prime \circ \psi^\prime) & = & \varphi \circ \varphi^\prime \circ \pi_1^\prime \\ \pi_1^\prime \circ (\varphi \sqcap \psi) \circ (\varphi^\prime \sqcap \psi^\prime) & = & \mathsf{id}_{A^\prime} \circ \pi_1^\prime \\ \pi_1^\prime \circ (\varphi \sqcap \psi) \circ (\varphi^\prime \sqcap \psi^\prime) & = & \pi_1^\prime. \end{array}$

The last equation is solved uniquely. Since $\pi_1^\prime \circ \mathsf{id}_{A^\prime \sqcap B^\prime} = \pi_1^\prime$ , then, $(\varphi \sqcap \psi) \circ (\varphi^\prime \sqcap \psi^\prime) = \mathsf{id}_{A^\prime \sqcap B^\prime}$ , and so $\varphi \sqcap \psi$ is sectionable. $\square$

Theorem. If $\varphi$ and $\psi$ are iso and the products exist, then $\varphi \sqcap \psi$ is iso and $(\varphi \sqcap \psi)^{-1} = \varphi^{-1} \sqcap \psi^{-1}$ .

Proof. This follows from the previous two results, since $\varphi \sqcap \psi$ is both retractable and sectionable and the sections and retractions of isomorphisms are all equal. $\sqcap$

Theorem. If $\varphi : A \rightarrow A^\prime$ and $\psi : B \rightarrow B^\prime$ , the products $(A \sqcap B, \pi_1, \pi_2)$ and $(A^\prime \sqcap B^\prime, \pi_1^\prime, \pi_2^\prime)$ exist, and $\varphi \sqcap \psi$ and $\pi_1$ ( $\pi_2$ ) are epic, then $\varphi$ ( $\psi$ ) is epic.

Suppose $\alpha$ and $\beta$ exist so that the following diagram commutes.

Suppose without loss of generality that $\pi_1^\prime$ is epic. Then we have the following.

$\begin{array}{rcl} \alpha \circ \varphi & = & \beta \circ \varphi \\ \alpha \circ \varphi \circ \pi_1 & = & \beta \circ \varphi \circ \pi_1 \\ \alpha \circ \pi_1^\prime \circ (\varphi \sqcap \psi) & = & \beta \circ \pi_1^\prime \circ (\varphi \sqcap \psi) \\ \alpha & = & \beta \end{array}$

And so $\varphi$ is epic. Similarly, if $\pi_2^\prime$ is epic, $\psi$ is epic. $\square$

Theorem. If $\varphi : A \rightarrow A^\prime$ and $\psi : B \rightarrow B^\prime$ , the products $(A \sqcap B, \pi_1, \pi_2)$ and $(A^\prime \sqcap B^\prime, \pi_1^\prime, \pi_2^\prime)$ exist, and $\varphi$ and $\pi_1$ ( $\psi$ and $\pi_2$ ) are monic, then $\varphi \sqcap \psi$ is monic.

Proof. Suppose we have morphisms $\alpha$ and $\beta$ such that the following diagram commutes.

Suppose without loss of generality that $\varphi$ and $\pi_1$ are monic. Then we have

$\begin{array}{rcl} (\varphi \sqcap \psi) \circ \alpha & = & (\varphi \sqcap \psi) \circ \beta \\ \pi_1^\prime \circ (\varphi \sqcap \psi) \circ \alpha & = & \pi_1^\prime \circ (\varphi \sqcap \psi) \circ \beta \\ \varphi \circ \pi_1 \circ \alpha & = & \varphi \circ \pi_1 \circ \beta \\ \pi_1 \circ \alpha & = & \pi_1 \circ \beta \\ \alpha & = & \beta. \end{array}$

And so $\varphi \sqcap \psi$ is monic. $\square$

I’m going to introduce a definition; this is not at all standard, but it’ll make my life easier. I’ll say a category is projection-epic if every canonical projection is an epimorphism. Clearly we have the following.

Theorem. If $\mathcal{C}$ is projection-epic, the products exist, and $\varphi \sqcap \psi$ is epic, then $\varphi$ and $\psi$ are epic.

Now I’ll just state the dual versions of these theorems – again, we don’t need to write proofs because, in a sense, we already wrote them.

Theorem. If $\varphi$ and $\psi$ are retractable and the coproducts exist, then $\varphi \sqcup \psi$ is retractable.

Theorem. If $\varphi$ and $\psi$ are sectionable and the coproducts exist, then $\varphi \sqcup \psi$ is sectionable.

Theorem. If $\varphi$ and $\psi$ are iso and the coproducts exist, then $\varphi \sqcup \psi$ is iso and $(\varphi \sqcup \psi)^{-1} = \varphi^{-1} \sqcup \psi^{-1}$ .

Theorem. If $\varphi : A \rightarrow A^\prime$ and $\psi : B \rightarrow B^\prime$ , the coproducts $(A \sqcup B, \iota_1, \iota_2)$ and $(A^\prime \sqcup B^\prime, \iota_1^\prime, \iota_2^\prime)$ exist, and $\varphi \sqcup \psi$ and $\iota_1^\prime$ ( $\iota_2^\prime$ ) are monic, then $\varphi$ ( $\psi$ ) is monic.

Theorem. If $\varphi : A \rightarrow A^\prime$ and $\psi : B \rightarrow B^\prime$ are epimorphisms, the coproducts $(A \sqcup B, \iota_1, \iota_2)$ and $(A^\prime \sqcup B^\prime, \iota_1^\prime, \iota_2^\prime)$ exist, and one of $\iota_1$ and $\iota_2$ is epic, then $\varphi \sqcup \psi$ is epic.

Analogous to the definition of projection-epic above, I’ll call a category injection-monic if every canonical injection is a monomorphism. We have the dual theorem:

Theorem. If $\mathcal{C}$ is injection-monic, the coproducts exist, and $\varphi \sqcup \psi$ is monic, then $\varphi$ and $\psi$ are monic.

To give a quick application of these ideas, consider the following one-liner:

Theorem. If $A \cong A^\prime$ , then $A \sqcap B \cong A^\prime \sqcap B$ .

Proof. Suppose $\varphi$ is the given isomorphism. Then $\varphi \sqcap \mathsf{id}_B$ is iso.

This theorem says that as an operator, $\sqcap$ is essentially well defined. That’s a handy property! We could have proven this theorem by chasing diagrams back in the discussion about products, but by now we’ve got enough machinery built up that it is quite trivial. Of course, I’ll state the dual:

Theorem. If $A \cong A^\prime$ , then $A \sqcup B \cong A^\prime \sqcup B$ .

We can also show that the universal maps of products and coproducts have a “factorization” property.

Theorem. Provided the statement makes sense, $\lceil \varphi \circ \theta, \psi \circ \theta \rceil = \lceil \varphi, \psi \rceil \circ \theta$ .

Proof. We have that $\lceil \varphi, \psi \rceil$ is the unique morphism such that $\pi_1 \circ \lceil \varphi, \psi \rceil = \varphi$ , and $\lceil \varphi \circ \theta, \psi \circ \theta \rceil$ is the unique morphism such that $\pi_1 \circ \lceil \varphi \circ \theta, \psi \circ \theta \rceil = \varphi \circ \theta$ . But we also have $\pi_1 \circ \lceil \varphi, \psi \rceil \circ \theta = \varphi \circ \theta$ , and so $\lceil \varphi \circ \theta, \psi \circ \theta \rceil = \lceil \varphi, \psi \rceil \circ \theta$ . $\square$

It follows from the definitions that $\mathsf{Opp}\ \lceil \varphi, \psi \rceil = \lfloor \mathsf{Opp}\ \varphi, \mathsf{Opp}\ \psi \rfloor$ and $\mathsf{Opp}\ \lfloor \varphi, \psi \rfloor = \lceil \mathsf{Opp}\ \varphi, \mathsf{Opp}\ \psi \rceil$ . So dually,

Theorem. Provided the statement makes sense, $\lfloor \theta \circ \varphi, \theta \circ \psi \rfloor = \theta \circ \lfloor \varphi, \psi \rfloor$ .

Alright. The theorems we proved in this post are the kind of nuts-and-bolts tools that will make our lives easier later, both when solving specific problems and when working with more complicated ideas.

Posted in Breadcrumbs | Leave a Comment »

What is Frugality?

February 5, 2009 by nbloomf

Unless you’ve been under a rock for the last year (or in graduate school

) you’re probably aware that the global economy is tanking. Big shocker, right? These days, saving money is all the rage. Actually, depending on when you lost your job, it was all the rage a long time ago.

I am a mathematician, not an economist. I have no idea what the real triggers of the current crisis were or if it could have been avoided. As much as I’d like to, I can’t honestly blame the thing on Ronald Reagan or George W. Bush from within my area of expertise. However, I do know that the whole thing would hurt a lot less if more people were less dependent on their economic status quo. Americans spend too much and save too little, and when the squeeze hits there’s no room in the budget to cope without affecting your lifestyle. That is, unless you decide to pursue a lifestyle of simplicity and careful planning. Our grandparents and great-grandparents called this being frugal.

Being frugal means:

Thinking about how you spend your money and your time.
Eliminating waste.
Reducing your dependence on material things.
Prioritizing your needs and wants, and making decisions accordingly.
Best of all, being frugal means not having to worry about money. Being mindful is not the same as worrying!

My wife Stacie and I have always unofficially make frugality a lifestyle, for several reasons. We’ve always tried to save money and avoided buying unnecessary stuff. But recently I was on the john reading a golf magazine when I read the following statement:

If you’re not using statistics, you don’t really want to get better.

I’ve been mulling this over for a while since. The statement was made in the context of improving your golf game, but it occurred to me that this attitude applies to virtually every other endeavor – in particular, to living frugally. If we really want to get serious about using our money wisely – and surviving the crunch – we’ve got to measure ourselves. And so that is what we’re going to do. Heck, I’m a trained scientist! Gathering and interpreting quantitative data is what we do. I don’t know why this never occurred to me before.

If this interests you, keep an eye on this blog. I’ll be poring over our budget, looking for effective and creative ways to cut waste and measuring how well they work for me. Hopefully some of the ideas can help you too.

Posted in Frugality | Leave a Comment »

Categorical Breadcrumbs: Coproducts

February 5, 2009 by nbloomf

In the last post, we generalized the direct product of sets to arbitrary categories, and called it the categorical product (or simply product). In the process, we were able to unify lots of different theorems from around mathematics that would otherwise need to be proved one at a time. Today we’re going to talk about the dual notion, called a coproduct.

Remember that given a statement expressed in terms of the category axioms, we can obtain the dual statement by reversing all the morphisms (switching $\mathsf{dom}$ and $\mathsf{cod}$ ) and reversing the order of composition. And so, doing this, we obtain the definition of coproduct.

Definition. Given objects $A$ and $B$ in a category $\mathcal{C}$ , a coproduct of $A$ and $B$ is a triple $(Z, \iota_1, \iota_2)$ , where $Z$ is an object, $\iota_1 : A \rightarrow Z$ , and $\iota_2 : B \rightarrow Z$ . Moreover, given any other triple $(X, \varphi_1, \varphi_2)$ where $\varphi_1 : A \rightarrow X$ and $\varphi_2 : B \rightarrow X$ , there is a unique morphism $\theta : Z \rightarrow X$ such that $\varphi_1 = \theta \circ \iota_1$ and $\varphi_2 = \theta \circ \iota_2$ . That is, there is a unique $\theta$ such that the following diagram commutes.

We will sometimes use $\lbrack \varphi_1, \varphi_2 \rbrack$ (or $\lfloor \varphi_1, \varphi_2 \rfloor$ ) to denote the unique map that makes the coproduct diagram commute. Before we try to figure out what the coproduct means, let’s review some of the theorems we get for free – the duals of the theorems proved about products.

If a coproduct of $A$ and $B$ exists, it is unique up to isomorphism. We call this object $A \sqcup B$ , and the maps $\iota_1$ and $\iota_2$ we call canonical injections. If all coproducts exist we say $\mathcal{C}$ is coproduct closed.
Given $\varphi : A \rightarrow A^\prime$ and $\psi : B \rightarrow B^\prime$ , where the coproducts $(A \sqcup B, \iota_1, \iota_2)$ and $(A^\prime \sqcup B^\prime, \iota_1^\prime, \iota_2^\prime)$ exist, we denote by $\varphi \sqcup \psi$ the unique map such that $(\varphi \sqcup \psi) \circ \iota_1 = \iota_1^\prime \circ \varphi$ and $(\varphi \sqcup \psi) \circ \iota_2 = \iota_2^\prime \circ \psi$ .
If all compositions make sense and coproducts exist, $(\varphi^\prime \sqcup \psi^\prime) \circ (\varphi \sqcup \psi) = (\varphi^\prime \circ \varphi) \sqcup (\psi^\prime \circ \psi)$ .
If the coproduct exists, $\mathsf{id}_A \sqcup \mathsf{id}_B = \mathsf{id}_{A \sqcup B}$ .
If all the coproducts exist, $(A \sqcup B) \sqcup C \cong A \sqcup (B \sqcup C)$ . We’ll call the maps that exhibit this isomorphism $\mathsf{assocR}_\sqcup$ and $\mathsf{assocL}_\sqcup$ .
If the coproducts exist, $A \sqcup B \cong B \sqcup A$ . We’ll call the map that exhibits this $\mathsf{comm}_\sqcup$ .
If $X$ is initial and the coproduct exists, $A \sqcup X \cong A$ .
If $\mathcal{C}$ is coproduct closed, then given a fixed object $X$

we have a functor $X \sqcup -$ with object part $A \mapsto X \sqcup A$ and morphism part $\varphi \mapsto \mathsf{id}_X \sqcup \varphi$ . Similarly, $- \sqcup X$ is a functor.

The above facts mean that if a category is small and coproduct closed and has an initial object $X$ , then it is essentially a commutative monoid under $\sqcup$ .

Examples

In $\textsc{Set}$ , the coproduct of $A$ and $B$ is a not-so-common operator called the disjoint union or the tagged union, defined as $A \uplus B = (\{0\} \times A) \cup (\{1\} \times B)$ . The injections are $a \stackrel{\iota_1}{\mapsto} (0,a)$ and $b \stackrel{\iota_2}{\mapsto} (1,b)$ .

Remember that if the product exists we have the unique diagonal map $\Delta : X \rightarrow X \sqcap X$ . Similarly, if the coproduct exists, we will let $\nabla$ denote the unique map $\lbrack \mathsf{id}_X, \mathsf{id}_X \rbrack$ . In the category of sets, for example, this map just strips away the tag: $(0,x) \stackrel{\nabla}{\mapsto} x$ and $(1,x) \stackrel{\nabla}{\mapsto} x$ .

This discussion of coproducts is a lot shorter than the previous post on products because we didn’t have to prove anything. Such is the power of duality.

We’re going to explore how products and coproducts interact with each other, but first we’ll examine more closely how $\sqcup$ and $\sqcap$ operate on morphisms.

Posted in Breadcrumbs | Leave a Comment »

Categorical Breadcrumbs: Products

February 4, 2009 by nbloomf

In a previous post, we generalized injective and surjective set maps to arbitrary categories. In this post, we will generalize another common operator on several different structures: the direct product. Remember that the direct product of sets $A$ and $B$ is the set of pairs $(a,b)$ where $a \in A$ and $b \in B$ . Direct products are a basic way to construct new groups, rings, monoids, modules, et cetera, from old ones. It turns out that we can translate the really important bits about products into categorical language. As motivation, doing this will unify lots of proofs. For example, the direct product of sets is “associative” in an appropriate sense, and so is that of groups, rings, monoids, and so on. If we can prove that the categorical product is associative in an appropriate sense, then we just have to show that the direct product of sets corresponds to the categorical product in whatever category we’re working in and the theorem is free.

I’ll warn you at the beginning: the definitions and proofs that follow may be hard to understand at first because we’re working at such a high level of abstraction. There are lots of examples to keep it concrete, but at this point you’ll have to take my word for it that the effort will pay off later in a big way.

Definition. Given objects $A$ and $B$ of a category $\mathcal{C}$ , a product of $A$ and $B$ is a triple $(Z, \pi_1, \pi_2)$ where $\pi_1 : Z \rightarrow A$ , $\pi_2 : Z \rightarrow B$ , and given any other object $X$ and morphisms $\varphi_1 : X \rightarrow A$ and $\varphi_2 : X \rightarrow B$ there exists a unique morphism $\theta : X \rightarrow Z$ such that $\varphi_1 = \pi_1 \circ \theta$ and $\varphi_2 = \pi_2 \circ \theta$ . That is, there is a unique $\theta$ such that the following diagram commutes:

That definition may seem hopelessly abstract, so let’s see an example.

Example

Consider sets $A$ and $B$ in $\textsc{Set}$ . We’re going to show that the direct product $A \times B$ and the “coordinate projections” $\mathsf{fst}$ and $\mathsf{snd}$ given by $(a,b) \mapsto a$ and $(a,b) \mapsto b$ , respectively, are a categorical product of $A$ and $B$ . Suppose we have $X$ and $\varphi_1 : X \rightarrow A$ and $\varphi_2 : X \rightarrow B$ . Then the map $\theta : X \rightarrow A \times B$ given by $x \mapsto \left( \varphi_1(x), \varphi_2(x) \right)$ makes the product diagram commute and is unique; so the direct product is the categorical product in $\textsc{Set}$ .
(More to come)

Note that in general a product of two objects may not exist. In some categories, all products exist; these are very nice categories. I will call a category having all products product closed; this is not standard, but I haven’t been able to find another word for this concept. So far I’ve been talking about “a” product of two objects rather than “the” product, because the definition says nothing about $Z$ being unique. In fact it isn’t unique; for example, in the category of sets both $A \times B$ and $B \times A$ satisfy the definition of product, and these two sets certainly aren’t equal. However: the product is unique up to isomorphism, and almost all of the time this is good enough.

Theorem. If a product of two objects $A$ and $B$ exists in a category $\mathcal{C}$ , then it is unique up to isomorphism.

Proof. Suppose $(Z, \pi_1, \pi_2)$ and $(Z^\prime, \pi_1^\prime, \pi_2^\prime)$ are products of $A$ and $B$ . Then there exists a unique morphism $\theta : Z \rightarrow Z^\prime$ such that $\pi_1 = \pi_1^\prime \circ \theta$ and $\pi_2 = \pi_2^\prime \circ \theta$ . Likewise, there is a unique $\theta^\prime : Z^\prime \rightarrow Z$ such that $\pi_1^\prime = \pi_1 \circ \theta^\prime$ and $\pi_2^\prime = \pi_2 \circ \theta^\prime$ . That is, the following diagram commutes.

Note that $\pi_1 = \pi_1^\prime \circ \theta = \pi_1 \circ \theta^\prime \circ \theta$ , and that $\theta^\prime \circ \theta$ is the unique morphism that satisfies this equation. Since we also have $\pi_1 = \pi_1 \circ \mathsf{id}_Z$ , it must be the case that $\theta^\prime \circ \theta = \mathsf{id}_Z$ . Similarly, $\pi_1^\prime = \pi_1 \circ \theta^\prime = \pi_1^\prime \circ \theta \circ \theta^\prime$ , and since $\theta \circ \theta^\prime$ is the unique morphism satisfying this equation and $\pi_1^\prime = \pi_1^\prime \circ \mathsf{id}_{Z^\prime}$ , we have $\theta \circ \theta^\prime = \mathsf{id}_{Z^\prime}$ . So $\theta^\prime$ is both a retraction and a section for $\theta$ , hence $\theta$ is iso. $\square$

The essential uniqueness of products allows us to speak of the product of two objects rather than simply a product, and justifies the following special notation: if the product of $A$ and $B$ exists in $\mathcal{C}$ , we denote this object by $A \sqcap_\mathcal{C} B$ . As usual, we omit subscripts when no confusion results. We will also always use $\pi_1$ and $\pi_2$ for the maps $A \sqcap B \rightarrow A$ and $A \sqcap B \rightarrow B$ , respectively, and will call these maps canonical projections. I will tend to use the same symbols for all natural projections, as long as it isn’t too confusing. That is, I’ll treat $\pi_1$ and $\pi_2$ like polymorphic functions, even though this isn’t strictly correct. Finally, given an object $X$ with maps $\varphi_1 : X \rightarrow A$ and $\varphi_2 : X \rightarrow B$ , we denote with $\langle \varphi_1, \varphi_2 \rangle$ (or $\lceil \varphi_1, \varphi_2 \rceil$ ) the unique map $X \rightarrow A \sqcap B$ that makes the product diagram commute.

Suppose we have maps $\varphi : A \rightarrow C$ and $\psi : B \rightarrow D$ , and the products $A \sqcap B$ and $C \sqcap D$ exist. Then there is a unique morphism $\theta$ that makes the following diagram commute.

We will call this unique morphism $\varphi \sqcap \psi$ ; to be explicit, $\varphi \sqcap \psi = \langle \varphi \circ \pi_1, \psi \circ \pi_2 \rangle$ . Note that we’ve turned $\sqcap$ into an operator on morphisms, and not simply on objects. We’ll address this again toward the end of this post. Just for kicks, let’s see how $\sqcap$ interacts with $\circ$ .

Theorem. If all products exist and all compositions make sense, then $(\varphi^\prime \sqcap\psi^\prime) \circ (\varphi \sqcap \psi) = (\varphi^\prime \circ \varphi) \sqcap (\psi^\prime \circ \psi)$ .

Proof. By definition, $\varphi \sqcap \psi$ and $\varphi^\prime \sqcap \psi^\prime$ are the unique maps that make the following diagram commutes.

However, $(\varphi^\prime \circ \varphi) \sqcap (\psi^\prime \circ \psi)$ also makes the (outer portion of the) diagram commute, and so we have that $(\varphi^\prime \circ \varphi) \sqcap (\psi^\prime \circ \psi) = (\varphi^\prime \sqcap \psi^\prime) \circ (\varphi \sqcap \psi).$ $\square$

Theorem. If the product exists, $\mathsf{id}_A \sqcap \mathsf{id}_B = \mathsf{id}_{A \sqcap B}$ .

Proof. By definition, $\mathsf{id}_A \sqcap \mathsf{id}_B$ is the unique morphism such that the following diagram commutes:

However, $\mathsf{id}_{A \sqcap B}$ also makes this diagram commute. So $\mathsf{id}_A \sqcap \mathsf{id}_B = \mathsf{id}_{A \sqcap B}.$ $\square$

As hideously complicated as the categorical product is, it does have some nice familiar properties: essential commutativity and essential associativity. (Note – “essential” means “up to isomorphism”.) As I mentioned in the intro, the next couple of proofs subsume a huge number of theorems about specific kinds of structure that, in the absence of categories, must be proved one at a time.

Theorem. If the products exist, $A \sqcap B \cong B \sqcap A$ .

Proof. By definition, $\langle \pi_2, \pi_1 \rangle$ and $\langle \pi_2^\prime, \pi_1^\prime \rangle$ are the unique maps such that the following diagram commutes.

So we have $\pi_1 \circ \langle \pi_2^\prime, \pi_1^\prime \rangle \circ \langle \pi_2, \pi_1 \rangle = \pi_1$ , and the bracketed maps solve this equation uniquely. Since $\pi_1 \circ \mathsf{id}_{A\sqcap B} = \pi_1$ , we have $\mathsf{id}_{A \sqcap B} = \langle \pi_2^\prime, \pi_1^\prime \rangle \circ \langle \pi_2, \pi_1 \rangle$ . A similar argument shows that $\langle \pi_2^\prime, \pi_1^\prime \rangle$ and $\langle \pi_2, \pi_1 \rangle$ are mutual inverses, and so $A \sqcap B \cong B \sqcap A$ . $\square$

The following theorem allows us to drop parentheses from finite products.

Theorem. If the products exist, $(A \sqcap B) \sqcap C \cong A \sqcap (B \sqcap C)$ .

Proof. Suppose all the products exist and that $p_1, p_2, q_1, q_2$ , etc., are the canonical projections as in the following commutative diagram; the bracket maps exist and are unique by the universal property of products.

Now note that

$\begin{array}{rcl} r_2 \circ p_1 & = & s_1 \circ \langle r_1 \circ p_1, p_2 \rangle \\ & = & s_1 \circ q_2 \circ \langle r_2 \circ p_1, \langle r_2 \circ p_1, p_2 \rangle \rangle \\ & = & r_2 \circ \langle q_1, s_2 \circ q_2 \rangle \circ \langle r_2 \circ p_1, \langle r_2 \circ p_1, p_2 \rangle \rangle \\ & = & r_2 \circ p_1 \circ \langle \langle q_1, s_2 \circ q_2 \rangle, s_2 \circ q_2 \rangle \circ \langle r_2 \circ p_1, \langle r_2 \circ p_1, p_2 \rangle \rangle. \end{array}$

Moreover, $\langle \langle q_1, s_2 \circ q_2 \rangle, s_2 \circ q_2 \rangle \circ \langle r_2 \circ p_1, \langle r_2 \circ p_1, p_2 \rangle \rangle$ is the unique morphism that satisfies this equality. Since we also have $r_2 \circ p_2 = r_2 \circ p_1 \circ \mathsf{id}_{(A \sqcap B) \sqcap C}$ , we have

$\langle \langle q_1, s_2 \circ q_2 \rangle, s_2 \circ q_2 \rangle \circ \langle r_2 \circ p_1, \langle r_2 \circ p_1, p_2 \rangle \rangle = \mathsf{id}_{(A \sqcap B) \sqcap C}.$

A similar calculation shows that these two maps are in fact inverses of one another, and hence $(A \sqcap B) \sqcap C \cong A \sqcap (B \sqcap C).$ $\square$

We will call the maps $(A \sqcap B) \sqcap C \rightarrow A \sqcap (B \sqcap C)$ and $A \sqcap (B \sqcap C) \rightarrow (A \sqcap B) \sqcap C$ constructed in the above proof $\mathsf{assocR_\sqcap}$ and $\mathsf{assocL_\sqcap}$ , respectively. The following theorem says that terminal objects act like identity elements under $\sqcap$ .

Theorem. If the product exists and $X$ is terminal, then $A \sqcap X \cong A$ .

Proof. Since $X$ is terminal, there is a unique morphism $0_A : A \rightarrow X$ . Moreover, the following diagram commutes.

So we have $\pi_1 \circ \langle \mathsf{id}_A, 0_X \rangle = \mathsf{id}_A$ . Moreover, $\langle \mathsf{id}_A, 0_X \rangle \circ \pi_1 = \mathsf{id}_{A \sqcap X}$ . So $A \cong A \sqcap X$ . $\square$

By the previous theorems, if $\mathcal{C}$ is a small, product closed category with a terminal object, then it is “essentially” a commutative monoid under $\sqcap$ . We have to demand that $\mathcal{C}$ be small, since the usual definition of monoid begins with “let $M$ be a set…”.

Above, we showed that $\sqcap$ can operate on both objects and morphisms. Can it be made a functor? Let’s see. Suppose $\mathcal{C}$ is a category such that all products exist, and fix an object $X \in \mathcal{C}$ . For every object $A \in \mathcal{C}$ and morphism $\varphi \in \mathcal{C}$ , define $F A = X \sqcap A$ and $F \varphi = \mathsf{id}_X \sqcap \varphi$ . As we proved earlier, we have

$\begin{array}{rcl} F \mathsf{id}_A & = & \mathsf{id}_X \sqcap \mathsf{id}_A \\ & = & \mathsf{id}_{X \sqcap A} \\ & = & \mathsf{id}_{F A} \end{array}$

and

$\begin{array}{rcl} F \varphi \circ F \psi & = & (\mathsf{id}_X \sqcap \varphi) \circ (\mathsf{id}_X \sqcap \psi) \\ & = & (\mathsf{id}_X \circ \mathsf{id}_X) \sqcap (\varphi \circ \psi) \\ & = & \mathsf{id}_X \sqcap (\varphi \circ \psi) \\ & = & F(\varphi \circ \psi). \end{array}$

And so this $F$ is a functor. We’ll call it $X \sqcap -$ , where as usual the hyphen is a slot that tells us how the functor operates on objects. In fact, $X \sqcap - : \mathcal{C} \rightarrow \mathcal{C}$ is an endofunctor. Similarly, $- \sqcap X$ is an endofunctor.

Suppose the product $X \sqcap X$ exists. We have the identity map $\mathsf{id}_X : X \rightarrow X$ , and so a unique map $\langle \mathsf{id}_X, \mathsf{id}_X \rangle$ exists. This map is useful enough that we will give it its own symbol: $\Delta$ . This is the greek upper case letter delta, for diagonal, because in the category of sets, for example, we have $x \stackrel{\Delta}{\mapsto} (x,x)$ . We will see this map a lot in later posts.

As a final note, given a finite collection of objects $A_i$ , we can construct the finite product $\prod A_i$ so long as the products exist pairwise. The essential associativity of $\sqcap$ means that it doesn’t matter what order we do this in.

Remember that every categorical object has a dual; in the next post, we’ll talk about the dual of a product.

Posted in Breadcrumbs | Leave a Comment »

Categorical Breadcrumbs: Diagrams

February 2, 2009 by nbloomf

If you’ve ever encountered categories before, and are reading these posts in sequence, you may be wondering why I haven’t mentioned commutative diagrams yet. Well, it’s because I wanted to introduce them in the right way, and that requires we know about functors first. (Also, I was trying to figure out how to publish decent diagrams on WordPress.

) Diagrams, those funny pictures you see in books on categories and advanced algebra, are the subject of today’s post.

As we move forward, we will start using more and more complicated substructures of categories. In that setting, it will become very unwieldy to express everything solely in terms of function composition and equality. We’d like to be able to draw some pictures as visual aids, but they need to be consistent and correct. One way to do this is to simply draw all the objects in question and then connect them with morphisms, as if we were drawing a directed graph. To give a somewhat silly example, the composition law of categories is the axiom that given two morphisms $\varphi : A \rightarrow B$ and $\psi : B \rightarrow C$ , there is a composite morphism $\psi \circ \varphi : A \rightarrow C$ that is equivalent to “ $\psi$ after $\varphi$ “. We can also express this by saying that there is a unique map $\psi \circ \varphi$ such that the following diagram commutes:

Intuitively, a diagram is a collection of objects connected by some morphisms. We say that a diagram commutes if any two paths that start at the same object and end at the same object are equal as (possibly composite) morphisms. For example, rather than saying $\beta \circ \alpha = \beta^\prime \circ \alpha^\prime$ , we can say that the following diagram commutes:

Formally, a diagram in $\mathcal{C}$ is a functor $D : \mathcal{I} \rightarrow \mathcal{C}$ where $\mathcal{I}$ , called the index category, is small. (Remember: a category is small if its object class is a set.) A diagram commutes if its index category is induced by a poset: this gives us the requirement that if two morphisms share a domain and codomain, then they must be equal. Note that in a category whose morphisms are set maps, we test equality of functions by having them act on an element; in a general category we don’t have elements and have to use other methods to test equality of arrows. The vast majority of diagrams that we deal with will be finite, but not all are.

While studying categories and abstract algebra we will use commutative diagrams often, because they are (1) a concise and suggestive method of visualizing lots of morphisms at once and (2) prettier to look at than unbroken chunks of text. In practice, we will seldom pull out the formal definition of commutative diagram. However it is nice to know that this convenient visual notation can be made rigorous; every diagram could be expressed purely in terms of objects and morphisms if we really wanted to. (The formal definition will be used when we talk about limits, but forget about that for now.)

When using diagrams it will be convenient to be able to graphically represent properties such as epi and mono. We accomplish this by using a hooked arrow $A \hookrightarrow B$ to denote monomorphisms, and a double-headed arrow $A \twoheadrightarrow B$ to denote epimorphisms. The hooked arrow is meant to look like the subset relation $\subset$ , as in categories with set-like objects a monomorphism provides an “injective copy” of the domain inside the codomain. (Again, this will be made more rigorous when we talk about kernels.)

The proliferation of diagrams as proof aids in category theory has earned it the nickname “comic book mathematics”. It is easy at first to be confused or intimidated by them, but just keep in mind that most of the time diagrams are simply a convenient way of saying that two morphisms are equal. They also make it easier to remember the definitions of some other categorical objects; for example, I can never remember what a product (to be defined later) is with compositions and equality alone, but I always remember what the associated diagram looks like.

Posted in Breadcrumbs | 1 Comment »

Categorical Breadcrumbs: Functors

January 29, 2009 by nbloomf

The notion of homomorphism – structure preserving map – is central to modern mathematics. In many cases, more important than individual objects are the ways we can transform one object into another. Modeling our thought with categories brings this aspect to the forefront; in fact, in defining categories we could have identified each object $X$ with its identity morphism $\mathsf{id}_X$ and dispensed with the objects altogether. And so, with this in mind, it is natural to ask; what are the structure preserving “functions” between categories? We have to be careful about language here, because functions are only defined between sets and categories are pairs of classes. Instead we’re going to use the funny word functor.

The only structure categories have in general consists of (1) identity morphisms and (2) function composition. And so, we’d like functors to preserve these in a useful way.

Definition. Let $\mathcal{C}$ and $\mathcal{D}$ be categories. A functor $F : \mathcal{C} \rightarrow \mathcal{D}$ associates to every object $X \in \mathsf{Obj}_\mathcal{C}$ a unique object $F X \in \mathsf{Obj}_\mathcal{D}$ and to every morphism $\varphi \in \mathsf{Mor}_\mathcal{C}$ with $\varphi : X \rightarrow Y$ a unique morphism $F \varphi \in \mathsf{Mor}_\mathcal{D}$ with $F \varphi : F X \rightarrow F Y$ such that for all objects $X$ and morphisms $\varphi$ and $\psi,$

$F \mathsf{id}_X = \mathsf{id}_{F X}$ .
$F (\varphi \circ \psi) = F \varphi \circ F \psi$ .

It is customary to leave out parentheses when no confusion results, so we write (for example) $F \varphi$ rather than $F(\varphi)$ . To paraphrase Simon Peyton Jones, functor application is so important in category theory that we denote it using the quietest possible syntax: nothing at all. Parentheses are only used to alter the precedence of an operator; functor application has a higher precedence than composition, which explains the placement of parentheses in part (2).

To give an example, given a category $\mathcal{C}$ , define $\mathsf{Id} : \mathcal{C} \rightarrow \mathcal{C}$ by $X \mapsto X$ and $\varphi \mapsto \varphi$ . This clearly satisfies the functor properties, and so we call this the identity functor. We can think of $\mathsf{Id}$ as the prototypical functor, from which we generalize the definition of functor.

Definition. Let $\mathcal{C}$ and $\mathcal{D}$ be categories. A contravariant functor $F : \mathcal{C} \rightarrow \mathcal{D}$ associates to every object $X \in \mathsf{Obj}_\mathcal{C}$ a unique object $F X \in \mathsf{Obj}_\mathcal{D}$ and to every morphism $\varphi \in \mathsf{Mor}_\mathcal{C}$ with $\varphi : X \rightarrow Y$ a unique morphism $F \varphi : F Y \rightarrow F X$ such that for all objects $X$ and morphisms $\varphi$ and $\psi$ ,

$F \mathsf{id}_X = \mathsf{id}_{F X}$ .
$F (\varphi \circ \psi) = F \psi \circ F \varphi$ .

Sometimes we use the adjective “covariant” to distinguish ordinary functors from contravariant functors. The prototypical contravariant functor is $\mathsf{Opp} : \mathcal{C} \rightarrow \mathsf{Opp}\ \mathcal{C}$ . Note that every contravariant functor $F : \mathcal{C} \rightarrow \mathcal{D}$ is equal to a covariant functor $F^\prime : \mathcal{C} \rightarrow \mathsf{Opp}\ \mathcal{D}$ .

Examples

From any category whose objects are “sets with structure”, such as $\textsc{Grp}$ , $\textsc{Mon}$ , et cetera, we have a forgetful functor which throws away all or part of the structure. We will use the name $\mathsf{Forg}$ for all such functors; the signature should make it clear what the source and target of the functor are in each context. For instance, $\mathsf{Forg} : \textsc{Grp} \rightarrow \textsc{Set}$ , $\mathsf{Forg} : \textsc{Ring} \rightarrow \textsc{Grp}$ , and so on.
The powerset $\mathcal{P}(X)$ of any set $X$ is again a set. We can take a set map $\varphi : X \rightarrow Y$ and define $\mathcal{P}\ \varphi : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ by $\mathcal{P}\ \varphi(A) = \varphi[A]$ . It isn’t hard to show that the map $\mathcal{P} : \textsc{Set} \rightarrow \textsc{Set}$ defined in this way is a functor.
The collection of all functions between two sets is itself a set. So if we fix a set $X \in \textsc{Set}$ , then $\mathsf{Hom}(X,A)$ is an object of $\textsc{Set}$ for all sets $A$ . Can we define a functor that acts on objects as $F A = \mathsf{Hom}(X,A)$ ? Let’s see. First, how would it need to act on functions? We want to take a function $\varphi : A \rightarrow B$ and turn it into a function $F \varphi : \mathsf{Hom}(X,A) \rightarrow \mathsf{Hom}(X,B)$ . Given a function $A \rightarrow B$ and a function $X \rightarrow A$ , there is a natural way to produce a function $X \rightarrow B$ : compose them. That is, $(F \varphi)\alpha = \varphi \circ \alpha$ . Note then that for all $\alpha \in \mathsf{Hom}(X,A)$ , we have $(F \mathsf{id}_A) \alpha = \mathsf{id}_A \circ \alpha = \alpha$ and so $F \mathsf{id}_A = \mathsf{id}_{F A}$ . Moreover,

$\begin{array}{rcl} \left[ F(\varphi \circ \psi) \right] (\alpha) & = & \varphi \circ \psi \circ \alpha \\ & = & \varphi \circ \left[ F \psi \right] (\alpha) \\ & = & \left[ F \varphi \right] \left[ (F \psi) (\alpha) \right] \\ & = & \left[ F \varphi \circ F \psi \right] (\alpha), \end{array}$

and so $F(\varphi \circ \psi) = F \varphi \circ F \psi$ . So this $F$ is a functor. We usually denote this functor by $\mathsf{Hom}(X,-)$ . The dash indicates that this functor acts on objects by plugging them in to the slot. Foreshadowing: for this example, we worked in the category of sets. However, note that all we really needed was for $\mathsf{Hom}_\mathcal{C}(X,Y)$ to be an object of $\mathcal{C}$ whenever $X$ and $Y$ are; a category having this property is called closed. This is the case, for example, in the category of left $R$ -modules and of Haskell types.
In the previous example we saw that $\mathsf{Hom}(X,-)$ is a functor $\textsc{Set} \rightarrow \textsc{Set}$ . What about $\mathsf{Hom}(-,X)$ ? I’ll leave it as an exercise to show that $\mathsf{Hom}(-,X)$ is a contravariant functor $\textsc{Set} \rightarrow \textsc{Set}$ , or more generally, $\mathcal{C} \rightarrow \mathcal{C}$ for a closed category $\mathcal{C}$ .

There are many more examples of functors, but that’s enough for now. I’ll write more about functors later. Also note that similar to the case for ordinary morphisms, a functor $F : \mathcal{C} \rightarrow \mathcal{C}$ is called an endofunctor.

Every functor $F : \mathcal{C} \rightarrow \mathcal{D}$ induces, for every pair of objects $A,B \in \mathcal{C}$ , a class map $F_{A,B} : \mathsf{Hom}_\mathcal{C}(A,B) \rightarrow \mathsf{Hom}_\mathcal{D}(F A, F B)$ . We now introduce a few definitions:

$F$ is called full if $F_{A,B}$ is surjective for all $A$ and $B$ .
$F$ is called faithful if $F_{A,B}$ is injective for all $A$ and $B$ .

Since functors are a kind of class map, it makes sense to ask if they are injective or surjective. However, in a category we aren’t usually concerned about two objects being equal, only if they are isomorphic. And so we introduce alternate properties of functors that are close enough to surjectivity and injectivity for our needs.

A functor $F : \mathcal{C} \rightarrow \mathcal{D}$ is called essentially surjective if for every object $Y \in \mathcal{D}$ , there is an object $X \in \mathcal{C}$ such that $F X \cong Y$ .
A functor $F : \mathcal{C} \rightarrow \mathcal{D}$ is called essentially injective if for every pair of objects $X,Y \in \mathcal{C}$ , if $F X \cong F Y$ then $X \cong Y$ .

Finally, given two functors $F : \mathcal{C} \rightarrow \mathcal{D}$ and $G : \mathcal{D} \rightarrow \mathcal{E}$ , we can form a composite functor $G \circ F : \mathcal{C} \rightarrow \mathcal{E}$ in the way you expect: first apply $F$ and then $G$ . Again, showing this is a functor is not hard.

Functors are very important actors in category theory, so it’s important that you understand what they are and how they work.

Posted in Breadcrumbs | Leave a Comment »

unnatural projections

Research in Mathematics: A Postmortem

What is Frugality?

Pages

Recent Posts

Categories

Archive

Blog Stats

Chip Music

Math