The Unapologetic Mathematician

I should have mentioned this before, but usually dual notions are marked by the prefix “co-”. As an example, we have “well-powered” and “co-well-powered” categories.

Another example: We know through Erdős that “a mathematician is a device for turning coffee into theorems”. It thus follows by duality that a comathematician is a device for turning cotheorems into ffee.

One of the most interesting general facts about categories is how ubiquitous the notion of duality is. Pretty much everything has a “mirror image”, and the mirror is the opposite category.

Given a category , with objects and morphisms , we can construct the “opposite category” simply enough. In fact, it has the exact same objects and morphisms as does. The difference comes in how they relate to each other.

Remember that we had two functions, and assigning the “source” and “target” objects to any arrow. To get the opposite category we just swap them. Given a morphism, its source in is its target in , and vice versa. Of course, now we have to swap the order of composition. If we have and in , then we get and in . In the composition is defined, but in the composition is defined.

Most definitions we give will automatically come with a “dual” definition, which we get by reversing all the arrows like this. For example, monos and epis are dual notions, as are subobjects and quotient objects. Just write down one definition in terms of morphisms, reverse all the morphisms (and the order of composition), and you get the other.

Theorems work this way too. If you dualize the hypotheses and the conclusions, then you can dualize each step of the proof to prove the dual theorem. I can prove that any injection is monic, so it follows immediately by duality that any surjection is epic. Many texts actually completely omit even the statements of dual notions and theorems once they define the opposite category, but I’ll try to be explicit about the duals (though of course I won’t need to give the proofs).

Another place duality comes up is in defining “contravariant” functors. This is just a functor . It sends each object of to an object of , and sends a morphism in to a morphism in . See how the direction of the image morphism flipped? Early on, contravariant and regular (”covariant”) functors were treated somewhat separately, but really they’re just the same thing once you take the opposite category into account. Sometimes, though, it’s easier to think in terms of contravariant functors rather than mentally flipping all the arrows.

I’ll close with an example of a contravariant functor we’ve seen before. Consider a ring with unit and a left module over . That is, is an object in the category . We can construct the dual module , which is now an object in the category of right -modules. I say that this is a contravariant functor. We’ve specified how the dual module construction behaves on objects, but we need to see how it behaves on morphisms. This is what makes it functorial.

So let’s say we have two left -modules and , and an -module homomorphism . Since we want this to be a contravariant functor we need to find a morphism . But notice that , and similarly for . Then we have the composition of -module homomorphisms . If is a linear functional on , then we get as a linear functional on . We can define .

Now, is this construction functorial? We have to check that it preserves identities and compositions. For identities it’s simple: , so every linear functional on gets sent back to itself. For compositions we have to be careful. The order has to switch around because this is a contravariant functor. We take and and check , as it should.

Today I’ll give my own solution to the power question I posted last week. I’m going to present it as I always wished I could have: as a whole with answers to the specific questions spun off as they naturally arise, rather than separated part by part.

First I’ll restate the setup into a more natural language. This is really a question about certain endomorphisms on vector spaces over the field . This is the quotient of the ring of integers by the maximal ideal generated by . If you haven’t seen it before, you should be able to construct it by all I’ve said so far.

Anyhow, the “arrangements” are just vectors in the vector space . Such a space comes with a basis , where has a in place and elsewhere. Each of these spaces of course has the identity endomorphism , and it also has a “left rotation” endomorphism sending to and to , and its inverse — right rotation. The transformation we are concerned with is .

Since we are given bases we are justified in writing out matrices for transformations, and even for vectors (because ). The transformation has the matrix where is if or and otherwise. A vector of length will be an matrix.

Numbers 1 and 2 are just calculations, so I’ll omit them.

We can write as the matrix , so has matrix , which sends every vector to the zero vector. This is part 4.

Now one interesting property we can see straight off. We can tell whether there are an even or an odd number of ones in a given arrangement by adding up all the entries. That is, we can take the product with the matrix consisting of all ones. If we first transform an arrangement , then measure the number of ones, this is like taking the product . But each column of the matrix for has exactly two ones in it, so the product consists of all zeroes, and thus is always zero. That is, the image of any arrangement after a transformation always has an even number of ones. That’s number 10.

What arrangements are fixed by the transformation? This amounts to solving the equation

so we must have or . The zero vector is the only fixed point.

What vectors get sent to this fixed point? This is the kernel of the transformation — the vectors such that . Equivalently, these satisfy (why?). Thus all the entries must be the same, and the vector must consist of all zeroes or all ones. That’s number 9.

Now we see that if then is in the kernel of , and is thus either all zeroes or all ones. But if is odd, the vector consisting of all ones is not in the image of . Thus if we don’t start with a vector in the kernel we’ll never land in the kernel, and we’ll never get to the vector of all zeroes. That’s number 11. As a special case we have number 3.

Let’s consider . We expand this as , since we’re working over . Similarly, if we square this we get . In fact, we have that . Indeed, this is true by definition for , and if it’s true for then

so the claim is true by induction.

This means that after transformations a vector is sent to the sum (in ) of itself with its left-rotation by places. Thus if we can divide the entries in into vectors of length each — just pick the entries spaced out by separations of . Then acts on the same way acts on each of the subvectors, since the shift by places fixes the subvectors. That’s number 7. Parts 5 and 6 are now special cases.

Also, if then , so , so transformations send every vector of length to zero. That’s number 8.

Finally, let be any even number that is not a power of . Now the result of is the same as applying to each of the subvectors as described above. But now each subvector has odd length. If has a single in it, then one of these subvectors must contain it. By number 11 this subvector can never be sent to zero, so is never zero. If were ever zero then would be for a large enough , which will never happen. That’s part 12.

It should be pretty clear from all the examples in groups, rings, and modules that two categories and are isomorphic if there are functors and so that is the identity functor on and is the identity functor on .

Unfortunately, that’s not really as useful as it is in more mundane structures. The problem is that isomorphism is really strict, and categories are more naturally sort of loose and free-flowing. We have to weaken the notion of isomorphism to get something really useful. I’ll try to motivate this with one example. It’s sort of simple, but it gets to the heart of the problem pretty quickly.

Remember the category with one object and its identity morphism. We draw it as , taking the identity as given. Let’s also consider a category with two objects and two non-identity morphisms, one going in either direction: . Call the objects and , and the four arrows , , , , where goes from to . Then we have and . That is, the two non-identity arrows are inverses to each other, and the two objects are thus isomorphic.

Now since the two objects in our toy category are isomorphic, they are “essentially the same”. The category should (and does) behave pretty much the same as the category , but they’re clearly not isomorphic as categories.

Here’s another way they’re “the same” category. Since each hom-set in our toy category has at most one object, we can consider it as a preorder. We have the set with and in the order. If we (as usual) move to a partial order, we identify these two points and just get the unique partial order on one point — the category !

Okay, so if they’re not isomorphic, what are they? The key here is that the two objects in our toy category are isomorphic, but not identical. The definition of isomorphism of categories requires that (for example) is exactly again. But really should it matter if we don’t get back itself, but just an object isomorphic to it? Not really. And we also shouldn’t care if we get different results for every object in as long as they’re all isomorphic to the object we stick into , and as long as these isomorphisms all fit together nicely with morphisms between the objects.

The upshot of all this is that we do know how to weaken the concept of isomorphism of categories: we just change the functor equalities in the definition to natural isomorphisms of functors! That is, we have natural isomorphisms and . Let’s unpack this all for our toy category.

The functor from to is the only one possible: send both objects to the single object in and all the arrows to its identity. For a functor the other way we have two choices. Let’s send the singlt object of to the object . The identity arrow must then go to . Now we need natural isomorphisms.

To find these, let’s write down the compositions explicitly: sends the single object of to the object in our toy category, which then gets sent back to the single object in . Its identity arrow just comes along for the ride. Thus is exactly the identity functor on , so we can just use its identity natural transformation as our .

On the other hand, sends both objects of our toy category to the object , and all four arrows to the identity arrow . This is clearly not the identity functor on our category, so we need to find a natural isomorphism. That is, we need to find isomorphisms and so that the two nontrivial naturality squares commute. Clearly we can only pick and . Now if we write out the naturality squares for and (do it!) we see that they do commute, so is a natural isomorphism.

When we have two functors running back and forth between two categories so that their composites are naturally isomorphic to the respective identities like this, we say that they furnish an “equivalence”, and that the categories are “equivalent”. Every isomorphism of categories is clearly an equivalence, but there are many examples of categories which are equivalent but not isomorphic. This is a much more natural notion than isomorphism for saying categories are “essentially the same”.

Last week I was using the word “invertible” as if it was perfectly clear. Well, it should be, more or less, since categories are pretty similar to monoids, but I should be a bit more explicit. First, though, there’s a few other kinds of morphisms we should know.

We want to motivate these definitions from what we know of sets, but the catch is that sets are actually pretty special. Some properties turn out to be the same when applied to sets, though they can be different in other categories.

First of all, let’s look at injective functions. Remember that these are functions where implies . That is, distinct inputs produce distinct outputs. Now we can build a function as follows: if for some we define . This is well-defined because at most one can work, by injectivity. Then for all the other elements of we just assign them to random elements of . Now the composition is the identity function on because for all . We say that the function has a (non-unique) “left inverse”.

Now since has a left inverse there’s something else that happens: if we have two functions and both from to , and if then . That is, is “left cancellable”.

Now in any category we say a morphism is a “monomorphism” (or “a mono”, or “ is monic”) if it is left cancellable, whether or not the cancellation comes from a left inverse as above. If has a left inverse we say is “injective” or that it is “an injection”. By the same argument as above, every injection is monic, but in general not all monos are injective. In the two concepts are the same.

Similarly, a surjective function has a right inverse , and is thus right cancellable. We say in general that a right cancellable morphism is an “epimorphism” (or “an epi”, or “ is epic”). If the right cancellation comes from a right inverse, we say that is “surjective”, or that it is “a surjection”. Again, every surjection is epic, but not all epis are surjective. In the two concepts are again the same.

If a morphism is both monic and epic then we call it a “bimorphism”, and it can be cancelled from either side. If it is both injective and surjective we call it an “isomorphism”. All isomorphisms are bimorphisms, but not all bimorphisms are isomorphisms. If is an isomorphism, then we can show (try it) that the left and right inverses are not only unique, but are the same, and we call the (left and right) inverse . When I said “invertible” last week I meant that such an inverse exists.

We’ve already seen these terms in other categories. In groups and rings we have monomorphisms and epimorphisms, which are monos and epis in the categories and .

Now recall that any subset of a set comes with an injective function “including” into . Similarly, subgroups and subrings come with “inclusion” monomorphisms. We generalize this concept and define a “subobject” of an object in a category to be a monomorphism . In the same way we generalize quotient groups and quotient rings by defining a “quotient objects” of to be epimorphisms .

Notice that we define a subobject to be an arrow, and we allow any monomorphism. Consider the function defined by and . It seems odd at first, but we say that this is a subobject of . The important thing here is that we don’t define these concepts in terms of elements of sets, but in terms of arrows and their relations to each other. We “can’t tell the difference” between and since they are isomorphic as sets. If we just look at the arrow and the usual inclusion arrow of , they pick out the same subset of so we may as well consider them to be the same subset.

Let’s be a little more general here. Let and be two subobjects of . We say that “factors through” if there is an arrow so that . If we take the class of all subobjects of (all monomorphisms into ) we can give it the structure of a preorder by saying if factors through . It should be straightforward to verify that this is a preorder.

Now we can turn this preorder into a partial order as usual by identifying any two subobjects which factor through each other. If and then . Since is monic we can cancel it from the left and find that . similarly we find that . That is, and are inverses of each other, and so and are isomorphic as subobjects of . Conversely, if and are isomorphic subobjects then and factor through each other by an isomorphism . This gives us a partial order on (equivalence classes of) subobjects of . If the class of equivalence classes of subobjects is in fact a proper set for every object we say that our category is “well-powered”.

The preceding two paragraphs can be restated in terms of quotient objects. Just switch the directions of all the arrows and the orders of all the compositions. We get a partial order on (equivalence classes of) quotient objects of . If the class of equivalence classes is a proper set for each object then we say that the category is “co-well-powered”.

It should be noted that even though isomorphic subobjects come with an isomorphism between their objects, just having an isomorphism between the objects is not enough. One toy example is given in the comments below. Another is to consider two distinct one-element subsets of a given set. Clearly the object for each is a singleton, and all singletons are isomorphic, but the two subsets are not isomorphic as subobjects.

As an exercise, consider the category of commutative rings with unit and determine the partial order on the set of quotient objects of .

Now, back to the math. John Baez has posted a new This Week’s Finds. He continues his “Tale of Groupoidification”. It features a great comparison of group actions on sets and those on vector spaces (which we’ll get to soon enough). Even better, he gives a translation “for students trying to learn a little basic category theory” into the language of categories.

This afternoon (after I’d returned to consciousness) a friend of mine said that he didn’t know why anyone would go to a ceremony like commencement if they didn’t have a friend involved. Why did I force myself up much earlier than I’m used to just so I could tromp around under the sun in a suit plus a good five pounds of robes if it wasn’t for those four people involved who I’ve spent the last six or seven years with?

I can’t give a universal answer to this question. For me, at least, I’m there because of the Ph.D.s. The doctorate is the gold standard of the academy. You can’t get it by spitting back answers on a sequence of course finals. You can’t get it by retaining the material until a collection of comprehensive exams, or by writing up a survey of relevant literature. You attain a doctorate by extending the boundaries human knowledge.

This society generally speaks well of originality, but it tends to mean a rather pale sort. To really, truly think of something nobody else has before — and to be able to justify it — is really far more difficult than most people give credit to. It’s not something you do on weekends, in your spare time while doing other more important things. The Great Work is hard. It means steeping yourself in a subject until you understand in a way only a handful of other people do. It means sacrificing years of your life to the pursuit of something truly new and different. The path is littered with those who started and did not make it through to the end.

And it has no justification but itself. Nobody goes into academics for the money. Nobody does it for the praise of the masses. Compared to most other things any of these new doctors could have done it will be temporally thankless. You live the academic life because you look outside at the amazing world around yourself and you realize that, for you, the highest achievement of the human spirit is to understand it more deeply — to internalize some aspect of it, digest it, and help share that with the rest of humanity. You do it because it is fundamentally worth doing. The life of the mind has a value in and of itself. And so these men and women have chosen this value over all the others they might have.

While the new doctors wander the streets of New Haven in their velvet tams and bright blue robes they will be showered with a series of offhand congratulations, but there’s little comfort in them. They’re easy enough to toss off, and they’ll fade as soon as the regalia is in the closet for another year. It’s only human to wonder about the other paths you could have followed, and whether your choice was worth it.

I go to commencement exercises as someone who has made the same choice to join in a resounding “yes!” I may not understand what you have studied, but I know what you have done, and I know the value in it. I know what you have put in, and I know what you hope to gain in return. And so I drag myself out of bed and into my regalia to stand in testament to that value. Yes, like all ceremonies it is just a recognition of a state that already exists, but it is a state uniquely worth recognizing. You who attain the doctorate have been to the mountain, and I stand to welcome you back.

I would like to quote here the words of Robert Frost from “The Road Not Taken”

Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

Then took the other, as just as fair,
And having perhaps the better claim,
Because it was grassy and wanted wear;
Though as for that the passing there
Had worn them really about the same,

And both that morning equally lay
In leaves no step had trodden black.
Oh, I kept the first for another day!
Yet knowing how way leads on to way,
I doubted if I should ever come back.

I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I—
I took the one less traveled by,
And that has made all the difference.

To Sam Kim, Anthony Licata, Joan Licata, and Helen Wong — who walked for the doctorate from our mathematics department today — to Jim Bremer and Josh Sussan — who also completed their studies this year — to the three hundred fifty-some other new doctors today at Yale, and to all the others graduating this year: you chose the academic life like those who came before you and those who will come after. And that makes all the difference. Congratulations, and good luck.

If it gets this hot wearing regalia in New Haven, New Orleans will be hell at next year’s commencement. I’ll post somthing real when I’ve recovered.

Notes for now: Dean Butler’s comment to the graduate school was inspiring, but not quite so much as last year when he gave it to my graduating class. Also, though the econ Ph.D.s will tell you there’s no such thing as a free lunch, there is such a thing as a lunch that someone else pays for — two if you’re faculty.

Tomorrow is Yale’s commencement, and a good number of the sixth-year graduate students are getting out. Since I only took three years through college, I — like them — was in the high school graduating class of 1997. And that was the year Chicago Tribune columnist Mary Schmich published a collection of advice for those in our situation. Or was it the year Kurt Vonnegut gave a commencement address at MIT? No, it wasn’t, no matter how many people believe it. It was the newspaper column.

Why does anyone care? Because in 1998 Baz Luhrmann released in America an album of covered, reproduced, remixed, and adapted music inspired by his cinema, television, and live performance productions. On this album was a mostly-instrumental track with Schmich’s column read over it, and the date tweaked to “1999″, though there are mixes around with “1997″ (like the copy I have). The voice that dominated the airwaves was, in fact, Richard Dreyfuss Baz Luhrmann some Australian voice-actor you’ve probably never heard of named Lee Perry.

No, I have no idea why this track is such a magnet for urban legends.

Anyhow, it rightly became amazingly popular, spawning parodies (including this particularly apropriate one), inspiring many fan-vids, and being used in all sorts of productions.

So, originally released as a single in late 1997, Baz Luhrmann presents: “Everybody’s Free (to Wear Sunscreen)“.
Read more »

I came across this problem and I’ll be working on it myself, but I thought I’d toss it out for the group. Actually, the problem stated was a bit more specific, but that formulation lends itself to all sorts of pathologies, so I’m reformulating it to make it harder and more elegant at the same time.

We want to find the shape of a glass that minimizes the glass-liquid contact for any volume of liquid. Assume the glass is rotationally symmetric and closed at the bottom (”duh”, you might say, but it’s a pathology I’ve seen in the more specific version), and infinitely tall.

Given any glass , when we pour a volume of liquid into it the liquid settles at the bottom (ignore surface tension) and we get some surface area . We want a glass so that is less than or equal to for all other glasses for all volumes .

Go.

[UPDATE:] As Rishi points out below (after some trouble with WordPress’ formatting) there isn’t really a good solution to the problem as stated. Still, when we run into this sort of thing we naturally ask how good we can do. I’ll give a hint (that you should justify) that the problem really comes down to finding a function from the positive reals to themselves that “minimizes” (in some sense) the function . The questions now are, “what do we mean by ‘minimize’?” and “what function does that?” And with that, the problem becomes much more (ahem) open-ended.