Arrow Categories

One very useful example of a category is the category of arrows of a given category .

We start with any category with objects and morphisms . From this we build a new category called , for reasons that I’ll explain later. The objects of are just the morphisms of . The morphisms of this new category are where things start getting interesting.

Let’s take two objects of — that is, two morphisms of — and lay them side-by-side:

Now we want something that transforms one into the other. What we’ll do is connect each of the objects on the left to the corresponding object on the right by an arrow:

and require that the resulting square commute: as morphisms in . This is a morphism from to . Sometimes we’ll write , and sometimes we’ll name the square and write .

If we have three morphisms , , and in , and commuting squares and then we can get a commuting square . We check that this square commutes: . This gives a composition of commuting squares. It’s easily checked that this is associative.

Given any morphism in we can just apply the identity arrows to each of and to get a commuting square between and itself. It is clear that this square serves as the identity arrow on the object in , completing our proof that arrows and commuting squares in do form a category.

ARML Scrimmage Power Question

As expected, the only really interesting part of the scrimmage was the “power question”. This is basically a proof-based problem the whole team of 15 (or so) works on for an hour. This was always what I was best at, and tonight’s was no exception. I’ll post the question here for you to chew on. I’m restating it somewhat for this forum. You can ask for clarifications in the comments, but I’d rather you not post solutions since I intend to come back to it in a week to give my own (cleaned-up) solutions.

I didn’t write them all the answers out myself, but I could have done within the hour if I didn’t have to write them out longhand. I also give credit to more fastidious members of the team reviewing some of my answers and writing them out in the actual competition.

This problem is concerned with “arrangements” of “bits”. A bit is just a symbol in one of two states: or . A configuration is a string of bits, considered to loop around from one end to the other. Actually the problem is written in terms of bits arranged around a circle, but I’ll just write them as strings to avoid having to draw circular configurations here.

We’re interested in the following transformation on arrangements: a string becomes the string , where if and if . Since we’re considering the strings to loop around, we have if and if . As an example, the string becomes the string .

Part I
1. What arrangements are created by starting with and transforming it one, two, three, and four times?
2. Show the first 4 transformations of .
3. Justify why will never become all zeroes no matter how many transformations are applied.

Part II
4. Show that any arrangement of two bits becomes all zeroes within two transformations.
5. Let be any three consecutive bits in an arrangement, which may have any number of other bits (these three may also wrap from the end of a string to the beginning). Show that transforming the arrangements twice gives a or at position depending on whether and are the same or different.
6. Use problem 5 to prove the following statement: if an arrangement with an even number of bits is transformed twice, then the result is the same if every other bit was treated as an arrangement and transformed once. That is: going to in two transformations is equivalent to and going to and in one transformation each, and similarly for other even-length arrangements.
7. Extend the idea of problems 5 and 6 by proving the following. Let be an arrangement of length . Prove that after transformations, the value in position depends only on whether and were the same or different in the original arrangement for all .
8. Prove that, for any positive integer , any arrangement of bits becomes all zeros after transformations.
Part III
9. Justify why arrangements that are either all zeros or all ones are the only arrangements that give all zeros after one transformation.
10. Prove that one transformation on any arrangement of bits results in arrangement with an even number of ones.
11. Combine Problems 9 and 10 and prove that if an arrangement has an odd number of bits and is not all zeros and not all ones, then no number of transformations will result in all zeros.
12. Prove that if an arrangement has an even number of bits that is not a power of two, and exactly one bit is , then no number of transformations will result in an arrangement of all zeros.

[UPDATE] Somehow the post got clipped.. I’ve replaced the old material as close to my original wording as I remember

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.

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 from a category to a category consists of two functions, both also called . One sends objects of to objects of , and the other sends morphisms of to morphisms of . Of course, these are subject to a number of restrictions:

• If is a morphism from to in , then is a morphism from to in .
• For every object of , we have in — identities are sent to identities.
• Given morphisms and in , we have in — 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 of small categories (with only a set of objects and a set of morphisms) and functors between them.

Every category comes with an identity functor . This is an example of an “endofunctor” (in analogy with “endomorphism”).

Every category of algebraic structures we’ve considered — , , , , 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 that sends a group to its underlying set . It sends a homomorphism to itself, now considered as a function on the underlying sets. It should be apparent that this sends the identity homomorphism on the group to the identity function on the set , and that it preserves compositions. The same arguments go through for rings, monoids, -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 to — 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 to .

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 and 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 to the identity of 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 and as categories. If there is an arrow from to in then there must be an arrow from to . That is, if then . 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).

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 consists of two classes: the “objects” and the “morphisms”, or sometimes “points” and “arrows”. These are denoted and , respectively.

Every morphism has a “source” and a “target” object: and . If a morphism has source and target we often write . The class of all morphisms in with source and target is written , or just 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 , , and , we have an operation of “composition”: . We think of this as taking an arrow from to and one from to and joining them tip-to-tail to make an arrow from to . This composition must be associative — the following diagram commutes:

Also, every object has an “identity” morphism so that for all and for all .

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 : the category of sets. This has as objects the class of all sets (which can’t itself be a set). The morphisms are all functions .

Similarly, we have the categories — groups — — rings with identity — — left -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 with unit. We construct a small category as follows: take as objects the set of natural numbers. The morphisms are all matrices with entries in . The composition is regular matrix multiplication, and the identity on the object is the identity matrix.

Another great example of a category is a preorder. Given a preorder we take the set of elements as the objects of our category. Then we say that there is a single morphism in if and no morphisms in the hom-set otherwise. Reflexivity tells us that there is a morphism in for every object which can serve as an identity, and transitivity tells us that if there’s a morphism in and one in , then there’s one in 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.

Shameless Self-Promotion

If anything has become clearer after a year in the application trenches it is this: the better-known you and your ideas are, the better chance you have in the job market. To that end, I’d like to advertise myself.

Eventually the fall semester will start up, and with it the search for seminar speakers. Obviously I think I’d make a great choice. Here are a number of lectures I have basically ready to go.

• Functors extending the Kauffman Bracket
  The Kauffman Bracket is a family of invariants of knots and links up to regular isotopy taking their values in commutative rings, and defined by a “skein theory”. We want to find monoidal functors defined on the category of framed tangles so that if we restrict the functors to knots and links we recover (essentially) the old invariants. This approach highlights the fact that “skein theories” are actually just generating sets for monoidal categorical ideals, and that the skein-theoretic approach to knot invariants is another branch of representation theory.
  We thus study the representation theory of -linearizations of the category of framed tangles, and of the Temperley-Lieb categories . We show that the representation theory of these categories is equivalent to the theory of (non-symmetric) nondegenerate bilinear forms over .
• The Tangle Group
  The group of a knot or link is a well-known invariant of ambient isotopy. We would like to extend this invariant to a monoidal functor on the category of tangles in such a way that when we restrict to knots and links we recover (essentially) the old knot group.
  Here, we define a monoidal bifunctor from the bicategory of (tangles, isotopies) to the bicategory of cospans of groups, and show how the restriction of the decategorification of this bifunctor to knots and links reproduces the knot group. We also indicate how the use of cospans immediately applies to generalize the fundamental quandle of a link, the fundamental biquandle of a virtual link, and other such invariants.
• A Categorification of Quandle Coloring Numbers by Anafunctors
  The number of colorings of a link by a given quandle is a classical invariant of links up to ambient isotopy. We would like to categorify and extend this invariant to the category of tangles.
  Here, we show how to associate, functorially, to each tangle an anafunctor between two comma categories of quandles. When we restrict this assignment to knots and links and specify a quandle of colors we recover -coloring invariant. If we first decategorify and specify a quandle of colors we recover the -coloring matrix of a given tangle.
  This approach can be significantly generalized. We indicate the existence of a similar “-coloring” invariant for any co- object in the category of pointed topological pairs up to homotopy.

And now some comments. Generally, these abstracts apply to the highest-level version of each talk. I can tweak any of them down a bit, mostly to adjust for familiarity of the audience with categories and with knot theory.

The Kauffman Bracket talk is probably the most straightforward. It clearly highlights the relationship between skein theory and representation theory. Its primary interest is in this connection, and in the fact that it lays the groundwork for parallel categorifications of the Kauffman Bracket to Khovanov homology.

The knot group talk should be clear to an algebraic topology audience. It’s really the genesis of the use of cospans in the study of tangles For audiences more familiar with knot theory in particular, I can do the whole thing from the get-go in quandles.

The quandle talk really isn’t that abstract when it comes down to it, but it uses a number of tools possibly unfamiliar to the general mathematical audience. In fact, a good part of it is devoted to getting the definitions down straight. Once they’re in place, the whole structure just sort of builds itself, which is how I really like my mathematics to go. The caveat, then, is that the audience really does need to either be interested in knot theory already, or somewhat familiar with and friendly towards categories. Otherwise it’s really tough to motivate the material and to cover it within the usual microcentury.

I could possibly put the latter two together in a pair of lectures, since the quandle coloring invariant is a direct outgrowth of the fundamental quandle of a tangle. That would also make it a bit easier to motivate the second half, so it may well go more smoothly as a pair to a more general audience.

So, if your department is looking to fill a slot in an algebraic topology (or “quantum topology”, as they’re calling this stuff now) seminar, let’s talk. Clearly the easier it is for me to get there from New Orleans the easier it will be to make arrangements. Also, though I’ve gotten used to paying out of pocket for these things, assistance in travel would also be helpful.

I am particularly looking for an engagement in the Baltimore/Washington D.C. area around the weekend of October 6, so that gets high priority.

Future directions

I’m wrapping up my coverage of ring theory (for now). There’s a lot I’ve left unsaid about rings, and also about groups. I’m hoping, though, that I’ve given a certain amount of a feel for how algebraic structures work in preparation for the next topic: categories.

There are a number of readers, I know, who have been waiting for this point almost as much as I have been. There are also some who are dreading it. Everything up until this point has been stuff that everyone has to know, but categories are still a bit controversial in some circles. Many people find them even more abstract, or technical, or even content-free than other parts of algebra.

Category theory is at turns praised and derided with the same phrase, “abstract nonsense”. Indeed the earliest uses were to make general statements about algebra, just like ring theory makes general statements about polynomials, and polynomials make general statements about numbers. For some reason there are still mathematicians who draw a line in the sand and say, “Here! No further!”, just as others saw it as the next natural step.

Personally, I have been drawn to categories since I knew they existed. I still remember being shown the natural transformation from the identity functor on the category of vector spaces over a given field to the double-dual functor, and going back to Jeff Adams’ office (yes, the same Jeff Adams) again and again for more back in the spring of 1999. I hope now to say what it is that I saw then (and still see) in category theory, and to make the case for them. I really, honestly believe that within the next quarter-century nobody will be able to get a bachelor’s degree in mathematics without a passing familiarity with categories any more than one could avoid groups now, and it’s not just due to politicking on the part of its proponents as I’ve heard asserted.

First of all, categories are tremendously useful as a metamathematical language. I’ll show in the future how it unifies the First Isomorphism theorems, for example. I’ll also show how, in the language of categories, direct products of groups are like greatest lower bounds.

“So what,” the naysayer cries, “if this language says that those two concepts are related?” So, mathematics is about analogies. I can begin to understand this because I definitely understand that and this and that are similar in a certain way. Maybe knowing something about greatest lower bounds will tell me something new to look for in direct products of groups. Even if not, the relationships can help illuminate to newcomers — be they students or just lay readers — the essential points of the structures we consider, and more importantly why we consider them.

But there’s also another side of categories that the opposition completely ignores: a category can be just as useful a concrete mathematical structure as a group can, and the framework of categories can harmoniously sew together other objects into a coherent whole. The various rings and modules of matrices over a given field meld into the category of all matrices over that field. The braid groups weave together into the category of tangles.

And what do we gain from this categorical viewpoint? If unifying language isn’t enough for you, try this: category theory is, at its core, the language of the analytic/synthetic approach to mathematics in particular and all sciences in general. The scientific epistemology is to break complicated systems down into simpler parts, to understand those simple parts, and to understand how to reassemble them into the whole. This is exactly what category theory brings to the table: a systematic study of the nature of composition and how compositions transform when moving from one domain of discourse to another.

Category theory is the language of analogies, and analogies are the lifeblood of mathematics. Algebra gives us analogies between equations. Categories give us analogies between theories. Our future is concerned with analogies between analogies.

Do I smell cotton candy?

While I slept, The carnival came to town! (at The Geomblog)

Fractions

One thing we haven’t given good examples of is fields. We can get some from factoring out a maximal ideal from a commutative ring with unit, but the most familiar example — rational numbers — comes from a different construction.

First we define a multiplicatively closed set. This is a subset of a commutative ring with unit which is, predictably enough, closed under the ring multiplication. We also require for technicality’s sake that contains the unit . A good place to get such multiplicatively closed sets is as complements of prime ideals — given two elements and in but not in the prime ideal , their product must also be outside . Another good way is to start with some collection of elements and take the submonoid they generate under multiplication.

In general not all the elements of will be invertible in . What we want to do is make a bigger ring that properly contains (a homomorphic image of) in which all elements of do have inverses. We’ll do this sort of like how we built the integers by adding negatives to the natural numbers.

Consider the set of all elements with and . We’ll think of this as the “fraction” . Now of course we have too many elements. For example, should be “the same” as for all . We introduce the following equivalence relation: if and only if there is a with . Notice that if contained no zero-divisors we could do away with the “there is a ” clause, but we might need it in general.

So as usual we pass to the set of equivalence classes and assert that the result is a ring. The definitions of addition and multiplication are exactly what we expect if we remember fractions from elementary school. Choose representatives and , and define and . From here it’s a straightforward-but-tedious verification that these operations are independent of the choices of representatives and that they satisfy the ring axioms.

We call the resulting ring by a number of names. Two of the most common are and . If is generated by some collection of elements we sometimes write . There are a few more, but I’ll leave them alone for now.

It comes with a homomorphism , sending to . If contains no zero-divisors then this is an isomorphism onto its image, since then would imply that . That is, a copy of sits inside . This homomorphism has a nice universal property: if is any homomorphism of commutative rings with units sending each element of to a unit, then factors uniquely as . That is, is the “most general” such homomorphism.

Now let’s say we start with an integral domain . This means that the ideal consisting of only the zero element is prime. Then its complement — all nonzero elements of — is a multiplicatively closed set . We construct the field of fractions by adding inverses to all the nonzero elements. Now every nonzero element has an inverse, so this really is a field. In fact, it’s the “most general” field containing .

And, finally, let’s apply this construction to the integers. They are an integral domain, so it applies. Now the field of fractions consists of all fractions with , with the above-defined sum and product. That is, it consists of the fractions we all know from elementary school. We call this field : the field of rational numbers.

Prime Ideals

Now we know that we can talk about divisibility in terms of ideals, we remember a definition from back in elementary school: a number is “prime” if the only numbers that divide it are and itself. So, we might make the guess that a prime ideal is one so that the only ideals containing it are itself and the whole ring. Unfortunately, that’s not quite right.

There’s actually a different definition of a prime number, and it just so happens for numbers that the two definitions describe (almost) the same numbers. In more general rings, however, they’re different. What we’ve just described we’ll call a “maximal” ideal, since you can’t make it any bigger without getting the whole ring.

Here’s the other definition of a prime number: a number is prime if and only if whenever then either or . Let’s turn this into ideals. We’re defining a property of an ideal in terms of two other ideals and . In the case of integers, these are the principal ideals and since all ideals in are principal. The product of two integers generates the ideal — the product of the two ideals, so we’ll also consider the product ideal . Now we can state our property: an ideal is prime if whenever then either or . We also insist that is not the whole ring, just as we insist that is not a prime number.

Prime ideals have a number of nice properties, especially when we’re just looking at commutative rings with units. For instance, let’s consider the quotient of a commutative ring by a prime ideal , and elements and in this quotient ring. If their product then so . Now we can show that , so either or since is prime. In particular or , so or . That is, if the product of two elements in is zero, then one or the other must be — is an integral domain!

What happens if we use a maximal ideal in this construction? Given any element in , we have an element . If we try to make an ideal containing all of and also , then we get the whole ring . In particular we get for some . Then in , so is an inverse of — is a field!

Now we can be sure that there are rings with prime ideals that are not maximal, as indicated above. Take any integral domain that’s not a field. Then the ideal is prime, since is an integral domain, but it’s not maximal since isn’t a field. Of course I hear you cry out, “but maybe the only difference is ever the zero ideal!” Well, just take the direct sum of two copies of the ring: . Then the second copy is an ideal in the direct sum, and is an integral domain but not a field. Thus is a prime ideal, but not a maximal one.