# Do rational numbers admit a categorification which respects the following “duality”?

I need to give a lot of quite basic background to this question because I think (at least from conversing with fellow graduate students) that most mathematicians have not really thought about fractions for a long time. I think that there is an interesting germ of an idea in here somewhere, but I cannot exactly pinpoint it. Essentially there seems to be two canonical ways to solve division problems and there does not seem to be a "natural isomorphism" relating the two ways. I am interested in framing this duality formally: is there a "categorification" of the rational numbers where this duality can be precisely framed?

I TA a class for future elementary school teachers. The idea is to go back and really understand elementary school mathematics at a deep level. Hopefully this understanding gets passed on to the next generation.

We were discussing division of fractions. Rather than say "Yours is not to wonder why, just invert and multiply", we try to make sense of this question physically, and then use reasoning to solve the problem. Take (3/4) / (2/3). When doing this there seems to be two reasonable interpretations:

1) 3/4 of a cup of milk fills 2/3 of a container. How much milk (in cups) does it take to fill the entire container?

This is a "How many in each group" division problem, analogous to converting 6/3 into the question "If I have six objects divided into three equal groups, how many objects will be in each group?"

The solution that stares you in the face if you draw a picture of this situation is the following: 3/4 of a cup fills 2 thirds of a container. That means there must be 3/8 cups of milk in each third of the container. One container must have 9/8 cups of milk then, because this is 3 of these thirds. Note that the solution involved first dividing and then multiplying.

2) I have 3/4 cups of milk, and I have bottles which each hold 2/3 of a cup. How many bottles can I fill?

This is a "How many groups" division problem, analogous to converting 6/3 into the question "If I have six objects divided into groups of two, how many groups do I have?"

The solution suggested by this situation is the following: 3/4 of a cup of milk is actually 9 twelfths of a cup . Each twelfth is an eighth of a bottle. So I have 9/8 of a bottle. This solution involved first multiplying and then dividing.

Now I come to my question. This pattern persists! Every real world example of a "how many in each group" division problem suggests a solution by first dividing and then multiplying, whereas each "How many groups" division problem involves first multiplying and then dividing. It seems that solving the problem in the other order does not admit a conceptual realization in terms of the original problem. This is interesting to me! It suggests that the two solution methods are fundamentally different somehow. The standard approach to rational numbers (natural numbers get grothendieck grouped into integers, which get ring of fractioned into rational numbers) ignores this kind of distinction. Is there a "categorification" of the rational numbers which preserves the duality between these two types of question?

UPDATE 1: In the category of sets, if you wanted to express $(\frac{6}{2})(3) = \frac{(6)(3)}{2}$ you would have to do something like this:

Let $A$ be a set with 6 elements, $B$ a set with 3 elements, $\sim$ an equivalence relation on A where each equivalence class has 2 elements, and $\cong$ an equivalence relation on $A \times B$ where each equivalence class has 2 elements. Then there is no canonical morphism from $(A/ \sim) \times B \to (A \times B)/ \cong$. This seems to explain things somewhat on the level of integers, but we are talking fractions here.

UPDATE 2: Qiaochu points out in a comment to his answer that the order of operations is not the most essential thing here. You can solve the first problem by observing that 9/4 cups of milk fill 2 containers, so 9/8 must fill one. Torsors give a formal distinction between the two situations, but it still feels like UPDATE 1 should go through in a suitable category of "fractional sets".

UPDATE 3: For a very nice discussion of the ideas related to Theo's answer see http://golem.ph.utexas.edu/category/2008/12/groupoidification_made_easy.html

-
Incidentally, there is a classical fact that given a set-theoretic isomorphism $A\times2 \overset\sim\to B\times2$, you can construct an isomorphism $A \overset\sim\to B$ without any axiom of choice. One of my favorite papers is "Division by three" by PG Doyle and JH Conway, arXiv:0605779. They present a similar combinatorial construction of an isomorphism $A \overset\sim\to B$ given an isomorphism $A\times3 \overset\sim\to B\times3$. To my knowledge, constructions with higher values of "2,3" are unknown. –  Theo Johnson-Freyd Apr 28 '10 at 17:01
I posted excerpts from this paper on the "colorful language" thread. One of my favorites as well! Even though you can construct an isomorphism, it is very far from "canonical" in any sense. –  Steven Gubkin Apr 28 '10 at 17:10
@Theo: What I remember from reading Doyle and Conway is that they state that their construction generalizes to all positive integers. –  Qiaochu Yuan Apr 28 '10 at 19:56
@QY: Oh, that's possible. It's been a while since I've looked at the paper, and may have misremembered it. –  Theo Johnson-Freyd Apr 29 '10 at 19:34
Just to link back: This question also connects, to some extent, with the answer I put up to MESE 7837. –  Benjamin Dickman Apr 11 at 4:28

I don't claim to have a full answer, but I wanted to put it here so that others might help elaborate it.

I think that the "classical" (aside: at a recent seminar on Heegaard Floer homology, the word "classical" was defined as "posted on the arXiv") categorification of the positive rationals is to the world of finite groupoids. This is, in any case, the approach pushed by John Baez and collaborators in their HDA and Groupoidification series. You may know this already, but I'll review the basic structure for other readers. So recall that a finite groupoid is precisely: a finite set of objects, and for each pair of objects a finite set of ways that they are isomorphic, and some composition rules so that isomorphism is transitive. The simplest examples of groupoids are: discrete groupoids, aka "sets", in which each object is isomorphic to itself in exactly one way, and not isomorphic to any other object; and "point mod G", in which there is a single object, and a finite group G worth of ways that it is isomorphic to itself (G should be a group so that isomorphism is correctly transitive). There is a good notion of "equivalence" of groupoids, in which, for example, the groupoid with only one object, which is isomorphic to itself in only one way, is equivalent to the groupoid with two objects which are each isomorphic to themselves in precisely one way and which are isomorphic to each other in precisely one way. Groupoids have a good notion of "disjoint union", and in fact every finite groupoid is equivalent to a groupoid that is a disjoint union of various "point mod G"s for various groups G, just as every finite set is a disjoint union of points.

What Baez and Dolan described was the correct notion of "cardinality" of a groupoid. Namely, cardinality is additive under disjoint union, preserved under equivalence of groupoids, and the cardinality of "point mod G" is 1/|G|. (They prove that this uniquely defines a cardinality.) There is also a notion of cartesian product of groupoids, and this notion of cardinality is multiplicative under products. Moreover, if a group G acts on another groupoid X, then there is a "quotient groupoid" X//G, which has the same objects as X and extra isomorphisms for the G action. If the action is free, then X//G is equivalent to the usual "coarse" quotient X/G. Moreover, the cardinality of X//G is the cardinality of X divided by the number of group elements of G.

Since there are groups of arbitrary positive-integer cardinality, there are groupoids of arbitrary nonnegative-rational cardinality. In this sense, {Groupoids} categorifies {Rationals}.

But there are at least two reasons to be suspicious of this proposed categorification. First of all, although addition and multiplication categorify as we expect them to --- to disjoint union and cartesian product --- division is a bit strange. It is not inverse to multiplication except on one side: if you take a groupoid A, multiply it by a set B, and then divide by a group that acts freely and transitively on B, you get a groupoid equivalent to A; but if you divide first, you cannot multiply back. Similarly, it is not generally true that X//G is equivalent to X times pt//G. Maybe there is some sort of "semidirect product" or "crossed product" of groupoids that really does unify it all --- I don't know. In any case, when Baez explains his division, he treats numerator and denominator very differently: the numerator is something like a set, whereas the denominator is something like a group.

Second, it is not true that {Rationals} are the "grothendieck group" of {Groupoids}, at least not without some heavy duty groupifying. At the very least, there are many inequivalent groupoids with the same cardinality. Maybe this is a plus from the point of view of your question: {Groupoids} may be able to tell apart the two kinds of division that you sketch.

-
Excellent! This seems more in line with what I was looking for. Looks very promising. –  Steven Gubkin Apr 28 '10 at 17:03
I am accepting this answer because the failure of "multiplication to commute with division" for groupoid cardinality is exactly the analogue of my UPDATE 1. Finite groupoids are a beautiful categorization of the rationals! It seems with a little effort, it actually corresponds to my intuitive view of what division is really all about. –  Steven Gubkin Apr 28 '10 at 19:27

Let me expand on the answer I gave in meta. In my mind the appropriate "categorification" begins with the observation that "cups" is a unit, and in the first approach you endow only the numerator with units while in the second approach you endow both the numerator and denominator with units. This is formalized as follows. Quantities with units which take values in $\mathbb{Q}$ are torsors for the nonzero rationals $G$ under multiplication, e.g. $G$-sets $X$ which are free and transitive. The choice of unit corresponds to a choice of element of $X$ against which all other elements are measured.

In the first approach, you give a group element $g = \frac{2}{3}$ and a set element $x = \frac{3}{4} \text{ cup}$ (where $\text{cup}$ is the distinguished element of $X$) and are asked to find the unique $y \in X$ such that $gy = x$. In the second approach, you give two set elements $x = \frac{3}{4} \text{ cup}, y = \frac{2}{3} \text{ cup}$ and are asked to find the unique $g \in G$ such that $gy = x$. So I think the key here is that the group action, as a function $G \times X \to X$, treats $G$ and $X$ nearly the same, but not canonically so. (I haven't thought this through, but it's also significant that in the first problem one can just write $y = g^{-1} x$, whereas in the second problem it is actually necessary, or at least natural, to express $x$ and $y$ in terms of $\text{cup}$ to determine $g$.)

-
Very cool! I have heard the word "torsor" thrown around, but had never looked it up before. Seems like a relevant concept, but I am not sure it completely answers my question (It might! I just haven't thought enough!). If we are just dealing with sets, it does not seem that there is a canonical way to relate first multiplying and then dividing, v.s. first dividing and then multiplying. This is because division does not specify a particular quotient map. I think I want to extend this reasoning to fractions, but we do not have "fractional sets". I am adding this as an update. –  Steven Gubkin Apr 28 '10 at 15:59
I'm not convinced that the order of the operations is the most significant difference between the two scenarios. In my mind, a key difference is that the second formulation is independent of a choice of unit, so one can conveniently choose the new unit to be 1/12 cup (essentially your solution) and this immediately tells you what g is. In the first formulation one must instead compute with g and, reading over that solution, I think it makes just as much sense to say "that means there must be 9/4 cups of milk in every two containers." –  Qiaochu Yuan Apr 28 '10 at 16:07
Haha. Yes you are right. I can first multiply and then divide to solve 1 - I must have had a mental block against seeing this for some reason. I will still have to confirm that considering Q-torsors does everything I want them too. I would still be happier with a solution that more closely parallels the story for sets. Note actually that, in my edit, ~ gives you a canonical choice of a $\cong$, but $\cong$ does not give you a canonical choice of ~. –  Steven Gubkin Apr 28 '10 at 16:51
Fair enough. Also, maybe a less eclectic way to say what I wanted is that a quantity with unit is a one-dimensional Q-vector space; that way I can admit a value of zero, and changing the unit corresponds to a change of basis. –  Qiaochu Yuan Apr 29 '10 at 15:39

Another way of categorifying $\mathbb{Q}_+$ is as follows:

Let $\mathcal{F}$ be the category of finite non-empty sets and bijections. This is a symmetric monoidal category with respect to $\times$. Let $\mathbb{N}$ be viewed as a symmetric monoidal category, such that the objects are $\mathbb{N}$ and we only have identity morphism. The product is given by the usual product $\cdot$ in $\mathbb{N}$.

Then there is an obvious symmetric monoidal functor $G \colon \mathcal{F} \to \mathbb{N}$, which simply counts the elements in the set. Taking Grayson Quillen construction on both sides, we get a symmetric monoidal functor:

$G' \colon \mathcal{F}^{-1}\mathcal{F} \to \mathbb{Q}_+$,

whic may be viewed as a categorification (note that this is also the $\pi_0$ functor). The Grayson Quillen construction may be thought of as a categorified version of the Grothendeick construction. Objects in $\mathcal{F}^{-1}\mathcal{F}$ are pairs of objects in $\mathcal{F}$ which I suggestively write as $A/B$

If we only use the skeletal category of $\mathcal{F}$ given by objects $s_n=\{1,\dots,n\}$ for each $n\in \mathbb{N}$ we get that $G$ is an isomorphism on the set of objects. This is not true for $G'$, because we have implicitly divided out by isomorphisms in the image (i.e. $p/q=np/(nq)$ in $\mathbb{Q}_+$ not just isomorphic objects as they are in the Grayson Quillen construction on $\mathbb{N}$). We cannot do this on the domain of $G'$ because $s_p/s_q$ is NOT isomorphic to $s_{np}/s_{nq}$. However, there are many maps from $s_p/s_q$ to $s_{np}/s_{nq}$, which identifies them when taking $\pi_0$.

I should note that I believe (but am not sure) that this can be made bi-monoidal by taking the category of finite sets and bijections as a bimonoidal category and localizing with respect to $\times$ over the full subcategory of finite and non-empty sets.

-
Can you give me a link where the Garyson-Quillen construction is detailed? I wasn't able to google it easily. This approach seems like it is "cheating" a lot more than Theo's answer though - fractions arise naturally in his set up because nontrivial automorphisms of an object display the fact that they are divided up into "pieces". This seems more like formally inverting elements. –  Steven Gubkin Apr 30 '10 at 16:31
I find it more natural because it is this formal, note also that the category of finite set is one of the most important bimonoidal categories around: it basically is to bimonoidal categories what $\mathbb{Z}$ is to rings, and the spectrum realization in the sense of Ellmendorf and Mandell gives the sphere spectrum which to spectra is as $\mathbb{Z}$ is to abelian groups, and in the case of S-algebras in spectra, to rings. The reference for the Grayson Quillen construction is <a href="math.uiuc.edu/~dan/Papers/HigherAlgKThyII.pdf">; HIgher algebraic K-theory II<\a>. –  Thomas Kragh Apr 30 '10 at 17:41
Ups the link is not working right here it is again: math.uiuc.edu/~dan/Papers/HigherAlgKThyII.pdf –  Thomas Kragh Apr 30 '10 at 18:06
Thanks for the link –  Steven Gubkin Apr 30 '10 at 20:04
It is very important to not that the comment about making this bi-monoidal should be taken quite carefully, as explained by Thomason in "Beware the phony multiplication on Quillen's ...". –  Jacques Carette May 22 at 22:25