Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 26, 2008

Groupoidification Made Easy

Posted by John Baez

Merry Christmas! It’s still Christmas here in California, despite what the time stamp on this blog may say. So, it’s not too late for one last present! Here’s one just for you, from Santa and his elves:

You’ve probably heard me mutter and rhapsodize about groupoidification. I’ve been doing it for years — in fact, I have an entire webpage devoted to such rhapsodic mutterings.

But now, finally, you can learn the basic idea in an actual math paper that contains actual proofs of the most basic results! This is just the beginning of a much bigger story — but at least it’s a start.

Here’s the abstract:

Groupoidification is a form of categorification in which vector spaces are replaced by groupoids, and linear operators are replaced by spans of groupoids. We introduce this idea with a detailed exposition of ‘degroupoidification’: a systematic process that turns groupoids and spans into vector spaces and linear operators. Then we present two applications of groupoidification. The first is to Feynman diagrams. The Hilbert space for the quantum harmonic oscillator arises naturally from degroupoidifying the groupoid of finite sets and bijections. This allows for a purely combinatorial interpretation of creation and annihilation operators, their commutation relations, field operators, their normal-ordered powers, and finally Feynman diagrams. The second application is to Hecke algebras. We explain how to groupoidify the Hecke algebra associated to a Dynkin diagram whenever the deformation parameter qq is a prime power. We illustrate this with the simplest nontrivial example, coming from the A 2A_2 Dynkin diagram. In this example we show that the solution of the Yang–Baxter equation built into the A 2A_2 Hecke algebra arises naturally from the axioms of projective geometry applied to the projective plane over the finite field 𝔽 q\mathbb{F}_q.

Be the first on your block to groupoidify something. Make a New Year’s resolution to do it! Ho-ho-ho!


Posted at December 26, 2008 4:01 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1881

94 Comments & 4 Trackbacks

Re: Groupoidification Made Easy

Fascinating!

What happens with more general tensors than just vectors and linear operators, I wonder? Many-legged spans?

There doesn’t seem to be much to asymmetrically distinguish the two legs of a span in the case of linear operators to tell me which came from which half of VV=VV *V \multimap V = V \otimes V^*, but certainly tensor contraction seems to come out nicely as weak pullback for both the degroupoidification of matrix multiplication and the inner product.

Posted by: Jason Reed on December 26, 2008 3:35 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Quick afterthought: maybe it’s that you actually want to take the opposite groupoid in one side of the span, but you can’t tell that you did so here, precisely because it’s a groupoid and not merely a category.

Posted by: Jason Reed on December 26, 2008 4:03 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Your guess is right: nn-legged spans of groupoids degroupoidify to give rank-nn tensors. We’ve talked about that before here at the Café.

A nice example is the multiplication operator in the groupoidified Hecke algebra. In our paper you’ll see it described as an ordinary 2-legged span from Z×ZZ \times Z to ZZ (where ZZ is a groupid that we call (X×X)//G(X \times X)//G in the paper). But, this really deserves to be thought of as a 3-legged span with ZZ’s on all three feet.

And you’re also right that inputs versus outputs don’t matter much when it comes to spans of groupoids. That’s why degroupoidifying them really gives, not just real vector spaces, but real Hilbert spaces: such a vector space is canonically isomorphic to its dual.

And yes, it’s possible that if we go to categories, we should think about spans from C opC^{op} to DD. I’ve thought about that a lot, with no great results so far.

For example, I would like a category to give a complex Hilbert space, and I’d like C opC^{op} to give the dual of the Hilbert space that CC gives. Then, maybe the contravariant isomorphism between CC and C opC^{op} would be related to the conjugate-linear isomorphism between a complex Hilbert space and its dual.

But, I haven’t gotten this to work. If anyone out there can, please let me know how!

Posted by: John Baez on December 27, 2008 3:47 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Gosh, doomed to repeat the history I didn’t know about. Good to know I was on the right track anyway. Hard to know where to find these old discussions some times; maybe nLab will help in the future somehow…

Another little generalization exercise that occurred to me reading the paper was changing “weak quotient of a set by a group action, yielding a groupoid” to “weak quotient of a groupoid by a group action, yielding a groupoid” so that division could be iterated.

Obviously a group G acting on a groupoid C ought to be a functor * : G → Aut(C). It looked like the weak quotient would have the same objects, and arrows reminiscent of a Kleisli category: an arrow A → B in C // G is a pair (f, g) such that g an element of G and f : A → g * B. Composition is defined by (f2,g2) o (f1,g1) = ((g1 * f2) o f1, g1 g2).

Then you get |C // G| = |C| / |G| like you’d expect, and when C is a discrete groupoid, it reduces to the group-acting-on-set case.

Posted by: Jason Reed on December 27, 2008 4:05 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

more to the point, f : A → g * B as an arrow in C.

Posted by: Jason Reed on December 27, 2008 4:15 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Jason wrote:

Gosh, doomed to repeat the history I didn’t know about.

You’re lucky: at least this history is something pleasant, rather than war, famine or the collapse of an empire!

Another little generalization exercise that occurred to me reading the paper was changing “weak quotient of a set by a group action, yielding a groupoid” to “weak quotient of a groupoid by a group action, yielding a groupoid” so that division could be iterated.

Yes, you can take the weak quotient of any groupoid XX by an action of a group GG and get a new groupoid X//GX // G, and the groupoid cardinality works out nicely:

|X//G|=|X|/|G||X // G| = |X| / |G|

Professional category theorists would probably call this weak quotient construction a ‘pseudo colimit’: whenever you have a group GG acting on an object XX in some 2-category CC, you can think of it this as a functor

F:GCF : G \to C

where GG is reinterpreted as a category with one object **, and F(*)=XF(*) = X. Then you can think of as a ‘diagram’ in CC. The pseudo colimit of this diagram may or may not exist, but if it does, it deserves to be thought of as X//GX//G.

You can read a tiny bit about this here.

I hope you join the nnLab crew!

Posted by: John Baez on December 27, 2008 5:01 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Right, it was exactly that nnLab page’s sticking to actions on sets that prompted me to think about actions on groupoids.

I’d love to actually get a good feel for pseudo (co)limits. Ordinary (co)limits make perfect sense, but it’s a struggle up there at the 2-categorical level to transmute the thicket of diagrams into intuition :) I guess it just takes practice…
Posted by: Jason Reed on December 27, 2008 4:10 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

*gulp*

Groupification Made Easy and the two examples are Feynman diagrams and Hecke algebras??? :)

A subtitle could be “If You Already Know Feynman Diagrams and Hecke Algebras”. Just kidding. It looks neat! :)

I really like to see papers like this. Thanks! I will consider it homework to go through it all. One of these days, I still want to finish working through

An Exercise in Groupoidification: The Path Integral

PS: Do you have any reservations about me going through the definitions and creating corresponding nLab pages?

Posted by: Eric on December 26, 2008 9:58 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Eric writes:

Groupification Made Easy and the two examples are Feynman diagrams and Hecke algebras???

Well, groupoidification is really pathetically easy. In fact Alan Weinstein asked me, after a talk I gave at Berkeley, whether I’d considered teaching this stuff to bright high school students. I think he meant it in a good way — and I think bright high-school students could learn it — but that sort of compliment is a bit of a double-edged sword. Math is supposed to be clear but also deep. If everything is too easy, mathematicians don’t find it exciting. Some people try to make a shallow pool look deep by throwing in mud, but that’s not my style. So, I felt the need to include some interesting applications in this paper, not just the basic stuff.

The first main section of the paper, called ‘Degroupoidification’, doesn’t require that you know about Feynman diagrams, Hecke algebras or any fancy stuff.

If you want to learn about Feynman diagrams and groupoidification in a slow and gentle way, you can read the notes of my year-long course on that subject. It starts from scratch and proceeds systematically.

This paper just touches on the highlights of that course.

PS: Do you have any reservations about me going through the definitions and creating corresponding nLab pages?

No, that would be great! I’d be honored!

Posted by: John Baez on December 27, 2008 3:53 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

In fact Alan Weinstein asked me, after a talk I gave at Berkeley, whether I’d considered teaching this stuff to bright high school students.

Actually, I have tried teaching it to some bright high school students. I think it went fairly well. It would have probably gone even better if I knew more about Feynman diagrams.

Posted by: Mike Shulman on January 12, 2009 8:16 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Did you try to teach them about Feynman diagrams? Did you show them cool tricks with generating functions? The latter would be very fun — there are tons of examples in Wilf’s free book, Generatingfunctionology. So, starting from ideas of groupoid cardinality you could segue seamlessly to concrete puzzles like: “how many permutations of an nn-element set have no fixed points?” (These are called derangements.)

Posted by: John Baez on January 12, 2009 8:56 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Yes, I did try to teach them something about Feynman diagrams (although it would have helped if I understood Feynman diagrams better.) We didn’t have a whole lot of time, but I had a co-teacher who knew something about generating functions and did some of it; I don’t remember what. Unfortunately I think we didn’t do a really great job of seamlessly connecting the groupoid cardinality to the generating functions; I could probably do it better if I tried again.

Posted by: Mike Shulman on January 12, 2009 9:40 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I take great exception to your assertion that the natural numbers were invented. Plato FTW!

Posted by: peter on December 27, 2008 11:47 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Just a thought concerning the term “groupoidification”:

one can think of the passage from any category CC to the category of spans in CC (i.e. the category with the same objects of CC and with equivalence classes of spans in CC as morphisms) as the localization of CC at all morphisms.

In other words, we can think of CC as a category with weak eqivalences (\to nnLab) by taking all morphisms of CC to be weak equivalences. Then the corresponding homotopy category (\to nnLab) Ho CHo_C is the “groupoidification” of CC in that it is the universal groupoid with the property that there is a functor CHo CC \to Ho_C.

If we assume that CC has enough pullbacks, then then morphisms in Ho CHo_C are represented by equivalence classes of spans in CC.

This sense of “groupoidification” therefore is pretty close to the sense in which it is used here. But it is not quite the same.

What about de-cardinalization?

Posted by: Urs Schreiber on December 27, 2008 12:35 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Some comments on the file:

- Def 1 and 2 on p. 7: a matter of didacticts, but what is easier to understand (for an audience which is assumed to appreciate the notion of a functor):

maps from isomorphism classes of XX to \mathbb{R}, or, equivalently, functors from XX to \mathbb{R}, regarded as a discrete category?

The latter perspective is the more conceptual one, which generalizes properly, as in Jeffrey Morton’s 2-Vector spaces and groupoids. I find that “easier” in the sense that thinking about it this way reduces my internal confusion about what’s going on.

- def 4 in light of example 6: if the groupoid is not finite, should one say what is meant by the sum in def 4? I mean, we could have infinite groupoids XX where |X||X| depends on in which order I sum up the contributions from each vertext. No?

- def 8: there seems to be a small typo in the last line: it should be objects of Ψ\Psi which become isomorphic to xx under pp.

Posted by: Urs Schreiber on December 27, 2008 2:50 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Urs wrote:

- def 1 and 2 on p. 7: a matter of didactics, but what is easier to understand (for an audience which is assumed to appreciate the notion of a functor):

maps from isomorphism classes of XX to \mathbb{R}, or, equivalently, functors from XX to \mathbb{R}, regarded as a discrete category?

I’m quite sure normal people — once you were one, think back — have had more practice thinking about functions from sets to \mathbb{R} than functors from categories to \mathbb{R} regarded as a discrete category. Indeed, normal people have no idea what a discrete category is — and they cringe at the word ‘functor’.

This paper is all about making things easy for amateurs, hence the title. So, there are many important things we’re not talking about. We plan to write an infinite number of papers that go into more detail later.

- def 4 in light of example 6: if the groupoid is not finite, should one say what is meant by the sum in def 4? I mean, we could have infinite groupoids XX where |X||X| depends on in which order I sum up the contributions from each vertex. No?

Nope, sums of nonnegative numbers don’t change when you rearrange them: you always get a well-defined answer, which could be finite or ++\infty. In a sense, it’s only negative numbers (or complex numbers) that make infinite sums tricky. And that’s an interesting point, because degroupoidification as described in this paper is all about the rig [0,+][0,+\infty]: the nonnegative real numbers, together with ++\infty.

(We act like we’re talking about \mathbb{R}, but that’s just a didactic trick: everybody knows about vector spaces over the field \mathbb{R}, while almost nobody knows about modules over the rig [0,+][0,+\infty].)

- def 8: there seems to be a small typo in the last line: it should be objects of Ψ which become isomorphic to xx under pp.

Whoops! Thanks. Fixed.

We just fixed a huge number of mistakes; you may want to reload before reporting any more typos.

Posted by: John Baez on December 27, 2008 7:28 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Nope

Er, thanks. Stupid me.

Let me try to compensate by saying something more sensible:

one nice thing about sums, series and integrals of non-negative real number is that:

in this case the “limit” of analysis is reproduced by the categorical limit.

If we consider [0,][0,\infty] as a poset with (xy)(xy)(x \to y) \Leftrightarrow (x \geq y) then the equation

lim k n=0 k1n!=e lim_{k \to \infty} \sum_{n=0}^k \frac{1}{n!} = e

makes sense and is correct in the ordinary sense of analysis as well as an equation about a categorical limit.

Posted by: Urs Schreiber on December 28, 2008 11:42 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Urs wrote:

in this case the “limit” of analysis is reproduced by the categorical limit.

Hmm! That’s a nice observation, and maybe it helps ‘explain’ why infinite sums in [0,+][0,+\infty] are so much better-behaved than infinite sums in \mathbb{R}.

lim k n=0 k1n!=e lim_{k \to \infty} \sum_{n=0}^k \frac{1}{n!} = e

We can also categorify this:

colim k n=0 k1//n!E colim_{k \to \infty} \sum_{n=0}^k 1//n! \simeq E

where n!n! means the group of permutations of nn things, 1//n!1//n! is the action groupoid, \sum means coproduct, colim\colim means limit in the category of groupoids, and EE is the groupoid of finite sets. Taking groupoid cardinality everywhere in this formula, we get the previous one.

Of course I’ve said this about a million times, because I think it’s so cool. But your observation says that that in both formulas above, the limit can be thought of as a (co)limit in the categorical sense!

Posted by: John Baez on December 28, 2008 4:46 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

That’s a nice observation, and maybe it helps ‘explain’ why […]

I had started thinking about this in a discussion with David Corfield long time ago, when I tried to understand how Lawvere’s categorical notion of metric space relates to notions by Grandis in directed homotopy theory and in particular how it induces a notion of length of paths.

In the old comment

Integration

I essentially observe that if we put the following simple facts together:

- a metric space is an enriched category hence a lax functor;

- the length of a path in a metric space is the supremum of the lengths of its piecewise linear approximations;

- every supremum is a categorical limit of a functor with values in a poset

you get a formula for length of a path in a metric space in terms of a categorical limit.

I also make some further observations there. Later I had tried to see if this can be used to understand the path integral in quantum mechanics from a categorical perspective.

Posted by: Urs Schreiber on December 28, 2008 9:39 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

This general discussion on limits in spaces and limits in categories reminds me of a few things which I’d like to jot down (and maybe expand on in the nLab at some point).

(1) In his metric spaces paper, Lawvere defines the general notion of “point of a Cauchy completion” in terms of an adjoint pair of bimodules. Such a point can be considered either as a topological limit (of a Cauchy sequence or something similar), or it can be considered as an (enriched) categorical limit of a special kind: what is called an “absolute” limit (i.e., a limit that is preserved by any functor). Let me say quickly in passing that the notion of absolute limit is self-dual: absolute limits coincide with absolute colimits, so this indecision whether to compare topological limits to categorical limits or to colimits should melt away in this context.

(How do you make an arrow with a vertical slash through the middle? I’d like to use that symbol category theorists like to use when discussing relations, spans, profunctors, that sort of thing. Instead, I’ll use an arrow with a bullet over it.)

Very quickly: if XX is a metric space in Lawvere’s sense, and 11 is the one-pointed space, then a point pp in the Cauchy completion X¯\bar{X} is an adjoint pair of VV-enriched bimodules (letting VV for now be the symmetric monoidal closed preorder ([0,],)([0, \infty], \geq) with addition as tensor)

(p:1X)(q:X1)(p: 1 \stackrel{\bullet}{\to} X) \dashv (q: X \stackrel{\bullet}{\to} 1)

which when you work it out is a pair of VV-enriched functors p:X opVp: X^{op} \to V, q:XVq: X \to V with unit and counit inequalities that look like this:

0 x:Xp(x)+q(x)p(x)+q(y)X(x,y)0 \geq \int^{x: X} p(x) + q(x) \qquad p(x) + q(y) \geq X(x, y)

The way to think of this is that p(x)p(x) measures the distance X¯(x,p)\bar{X}(x, p) in the Cauchy completion, and q(x)q(x) measures the distance X¯(p,x)\bar{X}(p, x), and so the second inequality expresses a triangle inequality condition in the Cauchy completion. As for the first inequality: the coend here is a sup in the preorder ([0,],)([0, \infty], \geq), hence an infimum wrt the usual ordering, and so it says that the two distances X¯(x,p)\bar{X}(x, p), X¯(p,x)\bar{X}(p, x) both become arbitrarily small as xx ranges over XX. In other words, that XX is dense in X¯\bar{X} (in the topological sense).

On the categorical side, we have embeddings

XX¯V X opX \hookrightarrow \bar{X} \hookrightarrow V^{X^{op}}

and so by Yoneda, points of the Cauchy completion can be thought of as special types of enriched colimits of representables. They are “absolute” colimits, i.e., they are preserved by any VV-functor f:XYf: X \to Y. This isn’t too hard to see: roughly speaking, any VV-functor f:XYf: X \to Y may be regarded as a bimodule XV Y opX \to V^{Y^{op}} [by composing with the Yoneda embedding], and as such is a left adjoint in the bicategory of enriched bimodules; its right adjoint takes yy in YY to Y(f,y):X opVY(f-, y): X^{op} \to V. Therefore, since left adjoints compose, composition with ff gives a map

X¯=Ladj Bim(1,X)fLadj Bim(1,Y)=Y¯\bar{X} = Ladj_{Bim}(1, X) \stackrel{f \circ -}{\to} Ladj_{Bim}(1, Y) = \bar{Y}

We can think of this as saying that any functor ff preserves these special types of colimits of representables. Finally, these absolute colimits are essentially the same as absolute limits because we could equally well think of points pp of X¯\bar{X} as given by their right adjoint bimodules qq, which sit inside (V X) op(V^X)^{op}, the free VV-enriched completion of XX (as opposed to V X opV^{X^{op}}, the free cocompletion), and play a game dual to what we said above.

If this seems very abstract, it may help to think of concrete examples for various VV. When V=SetV = Set, the Cauchy completion is the Karoubi envelope or idempotent-splitting completion of CC, which we can think of either as closing up a category CC with respect to equalizers of diagrams

π,1:cc\pi, 1: c \stackrel{\to}{\to} c

where π\pi is idempotent, or closing up with respect to taking coequalizers of the same diagrams – it comes out the same either way, and it is well known that such split (co)equalizers are preserved by any functor. Or, if we take V=AbV = Ab, then the absolute limit-closure is closing up under these types of equalizers and finite products; the absolute colimit-closure is closing up under coequalizers of these diagrams and finite coproducts; either way the result is the same, and all such limits/colimits are preserved by any AbAb-enriched functor.

(2) Hm, I was going to make some other points about general topology and general category theory, but this comment has already gotten longer than I’d originally planned. I was going to describe some interesting work by Walter Tholen and his colleagues (such as Maria Clementino and Dirk Hofmann – I may be omitting other key players) on general unifying categorical contexts in which to put metric spaces, topological spaces, multicategories and other things on a common footing. Instead, I’ll just supply one reference and maybe discuss it another time.

Posted by: Todd Trimble on December 29, 2008 4:54 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Urs writes:

every supremum is a categorical limit of a functor with values in a poset

I slightly prefer to say ‘colimit’.

This is just a matter of convention: it depends on our convention for turning posets into categories. If we use the convention where aba \le b means we have a morphism bab \to a in the corresponding category, then you’re right. If we use the convention where aba \le b means we have a morphism aba \to b in the corresponding category, then I’m right. But you can see above why I like my convention: in any category where we feel okay about writing coproducts as sums, we have

i=1 X i=colim n i=1 nX i \sum_{i = 1}^\infty X_i = colim_{n \to \infty} \sum_{i = 1}^n X_i

and with my conventions we also have

i=1 X i=colim n i=1 nX i \sum_{i = 1}^\infty X_i = colim_{n \to \infty} \sum_{i = 1}^n X_i

for X i[0,+]X_i \in [0,+\infty].

Interestingly however the sum in the second formula, namely the usual addition, is not the coproduct in the poset [0,+][0,+\infty] thought of as a category! Somehow product and coproduct of finite sets (or tame groupoids) makes their poset of cardinalities into a rig, where the rig operations (addition and multiplication) are not coproduct and product in that poset.

This is a tiny trivial remark, but maybe pondering this tiny issue will help us understand some big questions a bit better someday…

Posted by: John Baez on December 29, 2008 5:59 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

I slightly prefer to say ‘colimit’. This is just a matter of convention […]

Yes. I had only chosen conventions such that the the limit of analysis maps to the limit of category theory. Which is kind of fun.

maybe pondering this tiny issue will help us understand some big questions a bit better someday…

Yes, that’s why I am interested in this, too. It is the feeling that behind these terminological similarities there is a deeper meaning hidden which can help understand the true structure behind some phenomena.

This gets even better with ends and coends. As you know. Not only do these have the suggestive integral notation, but also satisfy a bunch of laws which remind us of integration. Such as the “Fubini theorem” for coends.

For instance for F:CF : \mathbb{N} \to C some functor (with \mathbb{N} regarded as a discrete category) we have that

nF(n) \int^{n \in \mathbb{N}} F(n)

is the coproduct of all F(n)F(n). (I am just saying this for completeness, in case anyone else is reading this who does not know coends.) If CC is a category with cardinality, i.e. a bimonoidal category equipped with a bimonoidal functor

||:(C,×,)(,×,+) |\cdot| : (C, \times, \sqcup) \to (\mathbb{R},\times, +)

then in this notation “cardinality commutes with the integral sign” in that

| nF(n)|= n|F(n)|. \left| \int^{n \in \mathbb{N}} F(n) \right| = \int^{n \in \mathbb{N}} |F(n)| \,.

So with ||:(Groupoids,×,+)(,×,+) |\cdot | : (Groupoids, \times,+) \to (\mathbb{R},\times, +)

being groupoid cardinality we can write your favorite example with F:GroupoidsF : \mathbb{N} \to Groupoids given by F:nBS n=I//S nF : n \mapsto \mathbf{B} S_n = I // S_n as

| nI//S n|= n|I//S n|= n1/n!=e \left| \int^{n \in \mathbb{N}} I//S_n \right| = \int^{n \in \mathbb{N}} |I//S_n| = \int^{n \in \mathbb{N}} 1/n! = e

and its nice that it is the same integral sign everywhere, even though it means different things inside and outside the cardinality operation.

Alternatively, the groupoid cardinality can be built into the integration process automatically.

If we generalize the discrete integration domain category \mathbb{N} to any groupoid XX and if we assume that the functor F:XCF : X \to C is “free”, then

| xXF(x)|= xX¯|F(x)|dμ X(x), \left| \int^{x \in X} F(x) \right| = \int^{x \in \bar X} |F(x)| d\mu_X(x) \,,

where X¯\bar X denotes the set of isomorphism classes of XX and dμ Xd\mu_X is the function

dμ X:x1|Aut(x)| d \mu_X : x \mapsto \frac{1}{|Aut(x)|}

which assigns the groupoid measure to xx.

So in this setup then we would get the above example as the integral over the functor 1:FinSetFinSet1 : FinSet \to FinSet constant on the singleton set

| nFinSet1| nFinSet¯=1dμ FinSet(n)= n1/n!=e \left| \int^{n \in FinSet} 1 \right| \mapsto \int^{n \in \bar FinSet = \mathbb{N}} 1 d\mu_{FinSet}(n) = \int^{n \in \mathbb{N}} 1/n! = e

only that the first step is not an equality, since the constant functor is not free.

Of course Tom Leinster then generalized this statement from groupoids to categories. I had spent a bit of time trying to see which categories are such that this kind of coend over them automatically reproduces measures dμ Xd\mu_X that should appear in certain discrete path integrals, since it feels that

maybe pondering this tiny issue will help us understand some big questions a bit better someday…

Posted by: Urs Schreiber on December 29, 2008 11:04 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

I’m sure I’ve asked this before, but has anyone thought about a ‘distance’ on FinGpd so that groupoids which only differ in a single component with many automorphisms are near each other?

Or so that as kk varies,

n=0 k1//n! \sum_{n = 0}^k 1//n!

forms a kind of Cauchy sequence. Then Cauchy completion would produce tame groupoids such as EE here.

If FinGpd is equivalent to the category of finite multisets of finite groups (although now I think of it, there was a question of whether multiset was the right term), could we not take the cardinality of the symmetric difference between two finite groupoids?

E.g., d(1//2!+1//2!,1//2!+1//3!)=1/2+1/6=2/3d(1//2! + 1//2!, 1//2! + 1//3!) = 1/2 + 1/6 = 2/3

Posted by: David Corfield on January 12, 2009 1:56 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

You might not like this, but I think the following satisfies all your criteria.

Write |C||C| for the cardinality (Euler characteristic) of a finite category CC. (Restrict to groupoids if you like, but everything I’m about to say works more generally for categories.) Then define the distance between finite categories CC and DD to be the absolute value of |C||D||C| - |D|.

There might be more to this than meets the eye. There’s a kind of subtraction operation on categories, as follows. Given a pair of categories C,DC, D and a pair of functors F,G:CD, F, G: C \stackrel{\to}{\to} D, there’s a ‘category of elements’ EE, formed by taking the disjoint union of CC and DD then adjoining a new arrow cF(c)c \to F(c), and similarly a new arrow cG(c)c \to G(c), for every cCc \in C. Composition is defined in the way that’s obvious once you think about it. Write E=D F,GCE = D -_{F, G} C: it’s

DD minus CC, relative to FF and GG’.

Little theorem: |D F,GC|=|D||C|. |D -_{F, G} C| = |D| - |C|. In particular, the left-hand side is independent of the choice of FF and GG. The distance between CC and DD is its absolute value.

Posted by: Tom Leinster on January 12, 2009 3:36 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

So why wouldn’t I like that?

I guess it’s because I was looking to have 11 and 1//2!+1//2!1//2! + 1//2! have a distance of 2 between them, where you have them at zero distance.

Hmm, if FF and GG are the functors from 11 to each copy of 1//2!1//2!, then your category of elements has an initial object, right, so is of cardinality 1?

What am I doing wrong?

Posted by: David Corfield on January 12, 2009 5:06 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

The category of elements doesn’t have an initial object. The root cause of the problem is that I didn’t describe the category of elements, EE, very precisely.

I said that to obtain EE, you had to adjoin an arrow ϕ c:cF(c)\phi_c: c \to F(c) for each cCc \in C, and similarly ψ c:cG(c)\psi_c: c \to G(c). What I omitted to say is that you then have to add in composites, so that EE is a category; and you’re meant to add in composites not freely, but subject to ‘obvious’ rules. These rules say that if f:abf: a \to b in CC then (afbϕ bF(b))=(aϕ aF(a)F(f)F(b)) \left(a \stackrel{f}{\to} b \stackrel{\phi_b}{\to} F(b) \right) = \left( a \stackrel{\phi_a}{\to} F(a) \stackrel{\F(f)}{\to} F(b) \right) and similarly for ψ\psi.

Abstractly, EE is the category of elements of the functor from the category (01)(0 \stackrel{\to}{\to} 1) to Cat\mathbf{Cat} that sends 00 to CC, 11 to DD, and the two arrows to FF and GG.

In your example, the object that you presumably thought was initial is, in fact, the source of two arrows to each of the other objects. I did a direct calculation to confirm that the category of elements does have cardinality 00, as the ‘little theorem’ says.

Posted by: Tom Leinster on January 12, 2009 5:26 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Ah, I see. Actually John’s hint did the trick.

So your way of providing distances fits well with the coarse decategorification of TameGpd to +\mathbb{R}^+.

Hmm, but is it not a little odd that the distance be zero between the groupoid 11 and the groupoid made of a copy of the monster group for each of its elements?

After all, it will be easy for me to give a sequence of groupoids with zero distance between successive terms, yet not converging to a groupoid. With my distance, convergence does follow.

Posted by: David Corfield on January 12, 2009 8:01 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

David asked ‘is it not a little odd…?’

Perhaps it is… and I did begin by saying that you might not like my suggestion. I’m not sure I do either.

We have to get used to the fact that in topology, the circle has the same cardinality (Euler characteristic) as the empty space. Whenever you have an invariant that isn’t a complete invariant, different objects sometimes get assigned the same number. But I think that’s a slightly different issue: for a good notion of distance, being distance zero apart should be some naturally-arising equivalence relation.

Here’s a question. Suppose we have a proper subgroup HH of a finite group GG. Regarding both as groupoids, what do you want the distance between GG and HH to be? Your symmetric difference distance would make it 1/o(G)+1/o(H)1/o(G) + 1/o(H), where oo means order.

Posted by: Tom Leinster on January 13, 2009 12:38 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Good points. So for group HH of order less than group GG, you always have distance 1/o(H)1/o(G)1/ o(H) - 1/ o(G) and I always have distance 1/o(H)+1/o(G)1/ o(H) + 1/ o(G), while we might want the distance to reflect whether HH is a subgroup, and perhaps whether there’s a common subgroup of low index.

So could there be a lattice-like distance between groups where you track back to the greatest common factor?

Then for groupoids you’d need a sort of \mathbb{N}-module thing over the lattice of finite groups.

Posted by: David Corfield on January 13, 2009 1:51 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I wonder if Diego Dominici’s distance between natural numbers could be adapted to provide a distance between finite groups or groupoids. There could be a ‘Hasse diagram’ for finite abelian groups, where a line goes from one group to another if the former is a subgroup with cyclic quotient of prime order. What to do in the nonabelian case? The number of cosets being prime?

Posted by: David Corfield on June 4, 2009 11:50 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Tom wrote:

Composition is defined in the way that’s obvious once you think about it.

How do you compose the unique arrow cF(c)c \to F(c) with an arrow f:F(c)df : F(c) \to d in DD? Do we ‘freely’ put in an arrow that’s the answer to this question?

Here are some other questions:

A species is a functor from the groupoid of finite sets, say EE, to SetSet. Similarly, a CatCat-valued species is a functor from the groupoid of finite sets to CatCat. The generating function of a CatCat-valued species

F:ECat F : E \to Cat

is defined by

|F|(z)= n0|F(n)|n!z n |F|(z) = \sum_{n \ge 0} \frac{|F(n)|}{n!} z^n

where |F(n)||F(n)| is defined using your cardinality of a category. Unlike ordinary species, the coefficients of this generating function can be negative.

Have you considered using your notion of subtraction to get interesting CatCat-valued species that are differences of the species we know and love?

Is there any really enlightening candidate for a CatCat-valued species whose generating function is

cosz= n0(1) n(2n)!z 2n cos z = \sum_{n \ge 0} \frac{(-1)^n}{(2n)!} z^{2n}

and similarly one for sinzsin z?

You might ask “What counts as enlightening?”

Well, for one thing, I’d like nice ‘bijective proofs’ — that is, proofs at the level of CatCat-valued species — that

ddzsinz=cosz \frac{d}{d z} sin z = cos z

and

ddzcosz=sinz \frac{d}{d z} cos z = -sin z

It would be nice to have proofs that resemble the known proofs for sinhsinh and coshcosh. The bijective proof that

ddzsinhz=coshz \frac{d}{d z} sinh z = cosh z

simply says ‘if you add one element to a set with an odd number of elements, you get a set with an even number of elements’. The bijective proof that

ddzcoshz=sinhz \frac{d}{d z} cosh z = sinh z

says ‘if you add one element to a set with an even number of elements, you get a set with an odd number of elements’. That’s very satisfying.

Posted by: John Baez on January 12, 2009 7:19 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

John wrote, apropos of my description of the category of elements of a diagram F,G:CDF, G: C \stackrel{\to}{\to} D of categories and functors:

How do you compose the [specified] arrow cF(c)c \to F(c) with an arrow f:F(c)df: F(c) \to d in DD?

My description wasn’t well-phrased: sorry. See my answer to David.

An alternative way to say it is that you take the disjoint union of CC and DD then adjoin, for each arrow h:abh: a \to b in CC, arrows ϕ h:aF(b)\phi_h: a \to F(b) and ψ h:aG(b)\psi_h: a \to G(b); that really does describe all the arrows in the category of elements, and the rule for composition is obvious.

Have you considered using your notion of subtraction to get interesting CatCat-valued species that are differences of the species we know and love?

Yes — you asked me that in Barcelona last year… maybe you remember that but you’re too polite to assume that I remember. We also considered the question of whether there’s a natural Cat\mathbf{Cat}-valued species whose generating function is the generating function for cos\cos (or sin\sin). I haven’t had any bright ideas about it since then, unfortunately.

Posted by: Tom Leinster on January 13, 2009 1:27 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

But don’t you, as John said, need to put in extra arrows for the compositions of arrows of the form aF(b)a \to F(b) and F(b)dF(b) \to d? Consider CC the groupoid 11 and DD the groupoid 1//2!1//2!, with only nontrivial arrow ff, and FF and GG both the only possible functor. There are two new arrows from the object of CC to the object of DD, but then these both need to compose with ff. So there are 4 new arrows from CC to DD.

The cardinality of that category, ‘DD minus CC, relative to FF and GG’, is 1/2-1/2 as it should be.

Posted by: David Corfield on January 13, 2009 2:05 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Yes, sorry; I wasn’t concentrating. It’s nothing more than a special case of the usual description of the category of elements of a Cat\mathbf{Cat}-valued functor. But even so, I said it wrong.

Here’s the general case. Let X:ACatX: A \to \mathbf{Cat} be a functor. (For our purposes it’s a genuine functor, but in general it only needs to be a colax 2-functor.) The category of elements of XX is defined as follows. An object is a pair (a,x)(a, x) where aAa \in A and xXax \in X a. A map (a,x)(a,x)(a', x') \to (a, x) is a pair (f,ξ)(f, \xi) where f:aaf: a' \to a in AA and ξ:(Xf)(x)x\xi: (X f)(x') \to x in XaX a. Composition and identities are defined in the ‘obvious’ way, I claim. (I used the same word last time and was wrong; but this time I believe I’ve checked it.)

Now for our special case, which is A=(01)A = (0 \stackrel{\to}{\to} 1). Unless I’m malfunctioning again, the category of elements is formed by taking the disjoint union of CC and DD together with one new arrow cdc \to d for each arrow F(c)dF(c) \to d in DD, and similarly another new arrow cdc \to d for each arrow G(c)dG(c) \to d in DD.

Posted by: Tom Leinster on January 13, 2009 3:28 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

You’d imagine that any good species-based approach to cos zz would explain the fact that

cosz=coshiz, cos z = cosh i z,

so relate to ii-coloured sets with an even number of elements.

How about just fishing for Cat-valued species, e.g., F(n)F(n) is the category with two objects, aa and bb, and the only nontrivial morphisms are such that |hom(a,b)|=n|hom(a, b)| = n.

Then |F(n)|=(2n)|F(n)| = (2 - n), so

|F|(z)=(2z)e z. |F| (z) = (2 - z)e^z.

Posted by: David Corfield on January 14, 2009 8:50 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

To find categorical species whose generating functions have all odd coefficients 00, we could try thinking about spheres. After all, χ(S n)\chi(S^n) alternates between 22 and 00 as nn increases.

There is, for each nn, a category that might deserve to be called S nS^n. It’s the poset

categorical n-sphere

and it satisfies |S n|=1+(1) n|S^n| = 1 + (-1)^n, as you’d hope.

(It deserves to be called S nS^n because its classifying space is S nS^n, and because if we take the usual construction of the topological sphere S nS^n as a CW-complex with two cells in each dimension n\leq n, then the set of cells ordered by inclusion is this poset S nS^n.)

The category S nS^n has an evident 22-fold symmetry, and you can quotient out by it so that the cardinalities became 1,0,1,0,1, 0, 1, 0, \ldots instead of 2,0,2,0,2, 0, 2, 0, \ldots. Precisely, there’s an action of C 2C_2 on S nS^n, and the cardinality of the lax quotient S n//C 2S^n//C_2 is (1+(1) n)/2(1 + (-1)^n)/2.

To turn the sequence of categories (S n//C 2)(S^n//C_2) into a categorical species, we have to write down an action of the symmetric group S nS_n on the category S n//C 2S^n//C_2. Is there anything more natural than the trivial action? (The other possibility, in which even permutations act trivially and odd permutations reflect in the horizontal axis, doesn’t seem natural if we’re trying to use the whole groupoid of finite sets rather than a skeleton.)

No matter what symmetry we choose, the generating function of this categorical species is n01+(1) n2n!z n= m01(2m)!z 2m=coshz. \sum_{n \geq 0} \frac{1 + (-1)^n}{2 \cdot n!} z^n = \sum_{m \geq 0} \frac{1}{(2m)!} z^{2m} = \cosh z. We already had cosh\cosh as the generating function of a species, though (see John’s comment). Now we’ve obtained it in another way. But we still haven’t got cos\cos.

Posted by: Tom Leinster on January 14, 2009 6:07 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Tom wrote:

To find categorical species whose generating functions have all odd coefficients 0, we could try thinking about spheres. After all, χ(S n)\chi(S^n) alternates between 2 and 0 as nn increases.

Great idea!

Now subtract one, to get numbers that alternate between 1 and 1-1.

If we take the nn-sphere and remove one point, we should get spaces whose Euler characteristic alternates between 11 and 1-1 as nn increases. This idea might lead us to a nice species whose generating function is

e ze^{-z}

Of course, if we really used spaces, we’d need to use the Euler–Schanuel characteristic. Why? A 1-sphere minus a point has Euler–Schanuel characteristic 01=10 - 1 = -1, which is what we want: (1) n(-1)^n with n=1n = 1. If we used the ordinary Euler characteristic, we’d get 1… no good.

But we’re really trying to build a categorical species, so we’re going to use not spaces but categories — and the Euler–Leinster characteristic of a category.

So: is there a nice category version of the ‘punctured nn-sphere’, which has Euler–Leinster characteristic (1) n(-1)^n?

Posted by: John Baez on January 14, 2009 10:03 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

You ask what might be the category analogous to the punctured nn-sphere. I don’t know how to go about answering this, because whenever I’ve thought about the correspondence between categories and topological spaces, I’ve put restrictions on so that we’re dealing with compact spaces. I guess I have to drop those restrictions now. This means working with infinite categories, or with finite categories containing one or more non-invertible endomorphisms.

On a different topic, I realized last night that there’s a second categorical species whose generating function is coshz\cosh z (or actually, 2coshz2\cosh z). This one seems more happy to be a species.

Given a set SS, let Q(S)Q(S) be the set of all subsets of SS except the two trivial ones, \emptyset and SS itself. Then Q(S)Q(S) is an ordered set, hence a category. Any bijection SSS \leftrightarrow S' induces an isomorphism Q(S)Q(S)Q(S) \leftrightarrow Q(S'). Hence QQ is a functor from (finite groupoids) to Cat\mathbf{Cat}.

If SS is a set with cardinality nn then Q(S)Q(S) is a category with cardinality 1+(1) n1 + (-1)^n. So QQ has generating function 2+2z 2/2!+2z 4/4!+=2coshz. 2 + 2z^2/2! + 2z^4/4! + \cdots = 2\cosh z.

Posted by: Tom Leinster on January 15, 2009 3:25 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

What’s to stop you doing your subtraction trick? I.e., choose a category T nT_n, such that |T n|=1|T_n| = 1, with two functors into S nS_n, then form the difference with respect to the functors. In fact, T nT_n could be 11, and you map it into c 0c_0 and d 0d_0.

Posted by: David Corfield on January 15, 2009 3:58 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Tom wrote:

Given a set SS, let Q(S)Q(S) be the set of all subsets of SS except the two trivial ones, \emptyset; and SS itself. Then Q(S)Q(S) is an ordered set, hence a category. Any bijection SSS \to S' induces an isomorphism Q(S)Q(S)Q(S) \to Q(S'). Hence QQ is a functor from (finite groupoids) to CatCat.

If SS is a set with cardinality nn then Q(S)Q(S) is a category with cardinality 1+(1) n1+(-1)^n. So QQ has generating function 2+2z 2/2!+2z 4/4!+=2coshz2+2z^2/2!+2z^4/4!+\cdots=2 \cosh z.

As you mentioned in your next post, the first 2 needs to be omitted. And maybe this is the reason: if SS is a set with nn elements, then Q(S)Q(S) is the poset of simplices in the boundary of the (n1)(n-1)-simplex; that is, Q(S)Q(S) is an n2n-2-sphere. So this example is in a sense a shifted version of your previous example.

Posted by: Dan Christensen on January 16, 2009 12:35 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Oops: I didn’t think about the case S=S = \emptyset, which needs handling separately. Since Q()Q(\emptyset) is empty, its cardinality is 00 (not 22). So QQ has generating function 2(coshz1)2(\cosh z - 1).

Posted by: Tom Leinster on January 15, 2009 3:28 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

You might imagine all kinds of variants on this: the poset of odd (resp. even) subsets excluding (resp. including) the empty set and/or the full set.

Posted by: David Corfield on January 15, 2009 4:05 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

David wrote:

You’d imagine that any good species-based approach to coszcos z would explain the fact that

cosz=coshiz, cos z=cosh i z,

so relate to ii-coloured sets with an even number of elements.

Ah! Complex numbers!

Tom also knows categories whose objects have complex cardinalities. So, we probably want species valued in one of those categories, not Cat, if we want a combinatorial proof that

cos(z)=cosh(iz) cos(z) = cosh(i z)

I agree that complex numbers are needed for a deep understanding of trig functions. But people did manage to limp along for quite a while doing trig without complex numbers, so it’s possible we’ll understand the cosine function using a Cat-valued species before we discover a really interesting object with cardinality ii.

I somehow don’t think the set of Motzkin trees is that object. But who knows?

Posted by: John Baez on January 15, 2009 12:04 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Later in that discussion I mention Motzkin n-paths, after which you state your preference for trees. But I see Tom has been busily thinking about paths, or at least walks.

Posted by: David Corfield on January 15, 2009 9:00 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Abstractly, EE is the category of elements of the functor from the category (0)(0 \stackrel{\to}{\to} ) to Cat\mathbf{Cat} that sends 0 to CC, 1 to DD, and the two arrows to FF and GG.

This construction ought to be something like the lax colimit over CIdCFDGCIdC. C \stackrel{Id}{\leftarrow} C \stackrel{F}{\to} D \stackrel{G}{\leftarrow} C \stackrel{Id}{\to} C \,.

Posted by: Urs Schreiber on January 12, 2009 10:46 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I’m not sure what you have in mind here, but I think it can be more simply described: the category of elements of the diagram F,G:CDF, G: C \stackrel{\to}{\to} D is the lax colimit of the corresponding functor from (01)(0 \stackrel{\to}{\to} 1) to Cat\mathbf{Cat}.

Generally, the category of elements of a Cat\mathbf{Cat}-valued functor XX is the same thing as the lax colimit of XX. I think.

Posted by: Tom Leinster on January 13, 2009 5:24 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I’m not sure what you have in mind here

The lax colimit over a diagram of categories CFDC \stackrel{F}{\to} D is that not the category generated from CC and DD and from new morphisms η a:aF(a)\eta_a : a \to F(a) subject to the relation a η a F(a) f F(f) b η b F(b) \array{ a &\stackrel{\eta_a}{\to}& F(a) \\ \downarrow^f && \downarrow^{F(f)} \\ b &\stackrel{\eta_b}{\to}& F(b) }

?

The laxity 2-cell η\eta in

C F D η C F laxD \array{ C &&\stackrel{F}{\to} && D \\ & \searrow &\stackrel{\eta}{\Rightarrow}& \swarrow \\ && C \sqcup_F^{lax} D }

is the natural transformation whose component at aa is precisely that new generator η a:aF(a)\eta_a : a \to F(a). No?

Posted by: Urs Schreiber on January 13, 2009 7:56 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Tom,

hm, I guess that’s what you said. Never mind.

But another question: how can I understand that one needs two functors to induce subtraction of cardinality this way?

Posted by: Urs Schreiber on January 13, 2009 8:29 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Tom,

re the above discussion of lax colimits:

what can we say about the construction of the lax limit over such a diagram of categories? In particular, I am interested in the case where one arrow is an identity:

F,Id:CC. F, Id : C \stackrel{\to}{\to} C \,.

I find this lax limit harder to see than the lax colimit. But it seems to be something interesting…

Posted by: Urs Schreiber on January 28, 2009 8:13 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Urs wrote:

But another question: how can I understand that one needs two functors to induce subtraction of cardinality this way?

A very heuristic answer, which may still be helpful.

Suppose CC and DD are one-point sets, thought of as categories. We want to form their ‘difference’, which should have Euler characteristic 11=01 - 1 = 0. There’s a unique functor from CC to DD. If we use this functor to build a category including CC and DD following Tom’s prescription, the resulting category is the ‘walking arrow’:

\bullet \to \bullet

which looks like an interval, and thus has Euler characteristic 1. No good!

If we use two copies of this functor to build a category including CC and DD, the resulting category is the ‘walking double arrow’:

\bullet \stackrel{\to}{\to} \bullet

which looks like a circle (especially if you draw the arrows nicely curved), and thus has Euler characteristic 00. Good!

(I can never tell if it’s a deep fact or divine coincidence that the closed unit interval looks like the number 1 and has Euler characterstic 1, while the circle looks like the number 0 and has Euler characteristic 0.)

In general, the disjoint union of categories CC and DD has Euler characteristic (or cardinality) equal to the sum of the Euler characteristics of CC and DD. Each time we use a functor from CC to DD to throw in more arrows, we subtract the Euler characteristic of CC. So, we need to do this twice to get the Euler characteristic of DD minus the Euler characteristic of CC.

Posted by: John Baez on January 13, 2009 9:45 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I can never tell if it’s a deep fact or divine coincidence that the closed unit interval looks like the number 1 and has Euler characterstic 1, while the circle looks like the number 0 and has Euler characteristic 0.

I don't know about 0, but it's a deep fact for 1. Numerals were originally tally marks, and our symbols for 1, 2, and 3 are still derived from these; ‘1’ is vertical (sometimes with added serifs), while ‘2’ and ‘3’ are horizontal (with added connecting curves). I believe that this claim is controversial, but only for lack of clear evidence; nobody with any imagination doubts it very much.

And of course, it's no coincidence that a group of nn tally marks has Euler characteristic nn.

Posted by: Toby Bartels on January 13, 2009 10:04 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Toby wrote:

I don’t know about 0, but it’s a deep fact for 1. Numerals were originally tally marks…

Right, so the numeral 1 is a picture of ‘one thing’, drawn to be a bit more visible than a mere dot — so it’s not surprising that the it’s homotopy equivalent to a point, and thus has Euler characteristic 1.

Similarly, the numeral 0 is presumably a picture of ‘nothing’, drawn to be a bit more visible than a blank spot on the page — sort of like a frame for an empty picture. So, it’s like a closed disc with a closed disc removed, which is a space whose Schanuel Euler characteristic is 1-1 = 0.

So maybe they’re both deep facts.

Posted by: John Baez on January 13, 2009 11:29 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Jim Dolan insists that the numeral zero looks like a closed disc with an open disc removed; luckily this again has Euler–Schanuel characteristic equal to 0: the open nn-disc has Euler–Schanuel characteristic equal to (1) n(-1)^n, so we get 1 2(1) 2=01^2 - (-1)^2 = 0.

Posted by: John Baez on January 17, 2009 4:21 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

The digits in Arabic script make an interesting comparison. I don’t know if they’ll show up properly on everyone’s browsers, but here goes:

۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹

For those who can’t see them, zero is just a speck like a decimal point; one is almost the same as the western 1, just a little tilted; two and three are obvious (?) systematic decorations of 1, and four is still almost part of the same system. After that things go irregular … though I like the fact that 7 “points down” and 8 “points up”.

Posted by: Greg Egan on January 14, 2009 3:24 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Since Tom has a notion of cardinality for categories, and a closely related notion of distance for categories, and notion of cardinality for topological spaces, it might be interesting to compare some known notions of distance for topological spaces.

Posted by: John Baez on January 12, 2009 4:36 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I was just looking at that paper last night. In that spirit, you might think of a kind of ‘distance’ between categories that’s completely unlike what David was after.

First let’s consider metric spaces. In Lawvere’s approach, they’re categories enriched in V=[0,]V = [0, \infty]. There’s a thing called ‘Gromov-Hausdorff distance’ measuring the distance between two abstract metric spaces. This makes VCatV-\mathbf{Cat} itself into a metric space, that is, a VV-category.

Question: for which VV can VCatV-\mathbf{Cat} be sensibly construed as a VV-category?

(Point of precision: VCatV-\mathbf{Cat} has as its objects the VV-categories with a set of objects.)

I don’t know the answer. However, the answer is also ‘yes’ when V=SetV = \mathbf{Set}. In that case, a VV-category is a locally small category, and VCat=CatV-\mathbf{Cat} = \mathbf{Cat}, which is itself a locally small category.

In the case V=[0,]V = [0, \infty], the VV-category structure on VCatV-\mathbf{Cat} was given, for VV-categories AA and BB, by VCat(A,B)=d GH(A,B) V-\mathbf{Cat}(A, B) = d_{GH}(A, B) where d GHd_{GH} is Gromov–Hausdorff distance. In the case V=SetV = \mathbf{Set}, it’s given by VCat(A,B)={functorsAB}. V-\mathbf{Cat}(A, B) = \{ functors A \to B \}. So the analogue of Gromov–Hausdorff distance is: the set of functors. ‘Distance’ is no longer a real number — it’s a set. It’s not really reasonable to think of it as any kind of distance, e.g. the ‘distance’ from AA to AA is the set of endofunctors of AA, which might be highly nontrivial.

(Of course, you might prefer to take the category of functors instead of the mere set. This still doesn’t deserve to be called ‘distance’.)

Posted by: Tom Leinster on January 12, 2009 5:01 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Are the Φ p\Phi^p in the second and third paragraphs supposed to be Φ n\Phi^n, or have I just not reloaded enough times? :)
Posted by: Jason Reed on December 28, 2008 6:28 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

You just didn’t reload enough times.

I’ve tried to make the notation consistent now, by changing all the pp’s to nn’s.

Posted by: John Baez on December 28, 2008 7:55 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I just reloaded, and some letters were fixed, but Definition 8 seems still wrong? I’ll go with Urs’s definition, but it caught me up the first time, because there are two possible definitions:

(1) Let v:ΨXv : \Psi \to X be a groupoid over XX. For each xXx\in X, there is a full subgroupoid of Ψ\Psi consisting of all ψΨ\psi \in \Psi so that v(ψ)v(\psi) is isomorphic to xx.

(2) Let v:ΨXv : \Psi \to X be a groupoid over XX. For each xXx\in X, there is a full subgroupoid of Ψ\Psi consisting of all ψΨ\psi \in \Psi so that ψ\psi is isomorphic to some ϕ\phi with v(ϕ)=xv(\phi) = x.

These two notions are different. For instance, XX might be the groupoid of two isomorphic objects (with unique isomorphisms, say), and Ψ\Psi the discrete groupoid with two objects, and vv the functor that is one-to-one on objects. Then notion (1) associates to each object all of Ψ\Psi, whereas notion (2) associates just the one-element discrete groupoid. Notion (2) will always return a full subcategory of notion (1), I believe.

So, which is it?

Posted by: Theo on December 29, 2008 6:58 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Theo asked, about the two possible ways to fix definition 8 in its version from December 28:

So, which is it?

It should be possible to figure this out from the way the proofs later on work. Only one version will makes these proofs come out right.

Browsing through the file, I see that the proofs, such as that of theorem 23, make use of lemmas 19 and 54 which say that we can assume all groupoids in the game to be replaced by their equivalent skeletons.

So we have to check which of the two interpretations of def 8 is well behaved under passage to skeleta.

The second version which Theo listed is not, the example he gives serves as a counterexample:

Let

v:(Ψ:={a,b})(X:={ab}) v : (\Psi := \{a , b\}) \to (X :=\{a \stackrel{\simeq}{\to} b\})

be the identity on objects. On skeleta this becomes the unique morphism

v:{a,b}{[a]}. v' : \{a , b\} \to \{[a]\} \,.

Clearly, the essential preimage under vv' of [a][a] is all of Ψ={a,b}\Psi = \{a, b\}.

To reproduce this result, up to taking skeleta, for the original vv, we have to define the essential preimage of xXx \in X to be the full subgroupoid of Ψ\Psi on all pΨp \in \Psi such that v(p)xv(p) \simeq x.

If we say this differently, it may become more intuitively accessible:

for xXx \in X let X xX_x be the full subgroupoid of XX on all objects isomorphic to xx. Then the essentially preimage of xx is nothing but the preimage of X xX_x.

Posted by: Urs Schreiber on December 29, 2008 11:40 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Theo writes:

So, which is it?

It’s your definition 1:

Let v:ΨXv : \Psi \to X be a groupoid over XX. For each xXx\in X, the essential inverse image v 1(x)v^{-1}(x) is the full subgroupoid of Ψ\Psi consisting of all ψΨ\psi \in \Psi so that v(ψ)v(\psi) is isomorphic to xx.

I thought this is what I said. I must have phrased it in an ambiguous or incorrect way. I’ll take a look and try to improve things. Thanks!

Here’s the idea: we’re trying to define the ‘inverse image’ of an object xx under the functor vv. In set theory this consists of elements ψ\psi such that v(ψ)=xv(\psi) = x. But in category theory it’s evil to demand an equation here. So, we instead assert the existence of an isomorphism. And then we take the full subcategory of such objects.

I could never possibly have wanted your definition 2. That definition is evil, because it involves an equation between objects:

Let v:ΨXv : \Psi \to X be a groupoid over XX. For each xXx\in X, there is a full subgroupoid of Ψ\Psi consisting of all ψΨ\psi \in \Psi so that ψ\psi is isomorphic to some ϕ\phi with v(ϕ)=xv(\phi) = x.

What do I mean by ‘evil’? The equation makes this definition ‘brittle’: if we replace vv by a naturally isomorphic ww, the full subcategory we get from ww may not be equivalent to the one we got from vv!

The original definition is robust: if v,w:ΨXv, w: \Psi \to X are naturally isomorphic functors, the essential inverse images v 1(x)v^{-1}(x) and w 1(x)w^{-1}(x) are equivalent groupoids. This is very beneficial.

Posted by: John Baez on December 29, 2008 7:51 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I thought this is what I said. I must have phrased it in an ambiguous or incorrect way.

Maybe you need to update the version on the web. The version of the file currently available, dated Dec 28, still contains the wrong definition 8, with no changes: there it still says:

all objects of Ψ\Psi isomorphic to xx

Posted by: Urs Schreiber on December 29, 2008 8:18 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Urs wrote:

Maybe you need to update the version on the web.

Or maybe I need to carefully read what I wrote, and see that it doesn’t even parse!

Okay: now I’ve read it, and fixed it.

Thanks, everyone!

Posted by: John Baez on December 30, 2008 3:24 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Sorry for jumping in without knowing the context for this discussion at all. But presumably, you’ve also made plenty of use of the 2-inverse image? This is the groupoid whose objects consist of pairs (ϕ,f)(\phi, f), where ff is an isomorphism

f:ν(ϕ)x,f: \nu(\phi) \simeq x,

and some obvious morphisms. More generally, one forms the 2-product

Ψ× XA,\Psi\times_X A,

given another map F:AXF:A \rightarrow X of groupoids, whose objects are triples, (ϕ,a,f)(\phi, a, f), where ff is an isomorphism from ν(ϕ)\nu(\phi) to F(a)F(a). This has the nice property that maps

h:BΨh:B \rightarrow \Psi

and

g:BAg:B\rightarrow A

together with an isomorphism

νhFg\nu\circ h \simeq F\circ g

determine a map

BΨ× XA.B \rightarrow \Psi\times_X A.

I’m sure these constructions are familiar to most people here, but I thought I’d take the opportunity to review them, because they are among the small things that add up to give category theory its real fizz.

Posted by: Minhyong Kim on December 29, 2008 11:27 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Minhyong wrote:

But presumably, you’ve also made plenty of use of the 2-inverse image? This is the groupoid whose objects consist of pairs (ϕ,f)(\phi, f), where ff is an isomorphism f:ν(ϕ)xf: \nu(\phi) \simeq x.

Yes! In fact I like that construction so much that it took me an embarrassingly long time to realize that it’s not what we need here. (We’re taking a groupoid over a groupoid XX and turning it into a vector in the vector space whose basis consists of isomorphism classes in XX.)

So you call this the ‘2-inverse image’? Influenced by topology, one might call it the ‘homotopy fiber’. I don’t know what most people call it. I just know what it is.

Here’s a nice way to summarize the difference between this construction and the ‘essential inverse image’ that I’m using in this paper. The essential inverse image consists of objects ϕ\phi with the property that ν(ϕ)\nu(\phi) is isomorphic to xx. The 2-inverse image consists of objects equipped with the structure of an isomorphism from ν(ϕ)\nu(\phi) to xx.

This is all part of the elaborate yoga of Postnikov towers and “properties, structure and stuff”, explained Lectures on cohomology and nn-categories.

Posted by: John Baez on December 30, 2008 3:36 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

The ‘2-inverse image’ terminology I just made up then. But it is a special case of the 2-product, and that seems reasonable usage, since it’s the natural product in the 2-category of categories. The 2-product of course is in its turn a special case of the 2-limit. The expressions ‘2-product’ and ‘2-limit’ occur at least in the SGA series, as well as Deligne’s famous papers on the Weil conjectures.

Of course my favorite example of the 2-product is the fixed-point groupoid of a map

F:XXF: X\rightarrow X

of groupoids, which is defined as the 2-product

X× X×XX,X\times_{X\times X} X,

where the maps from XX to X×XX\times X are F×IF\times I and the diagonal.

It’s when I realized that this is the only fixed-point construction compatible with a trace formula that I became convinced of the utility of the ‘2-‘framework.

It’s interesting that you had to tear yourself away from its seductive power.

Posted by: Minhyong Kim on December 30, 2008 11:56 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Inspired by John’s talk at the JMM, I just got around to reading this paper. I definitely did a double-take when I realized that what you call the “essential inverse image” is not the “2-inverse image”. I would call the latter the “fiber” of xx, or perhaps the “essential fiber” if I needed to distinguish it from the strict fiber of objects and morphisms whose image is equal to xx. I’m not that fond of “essential inverse image” for your notion since it makes me think of the other one; what about something like “full essential fiber?”

Additionally, it’s not clear to me why just using the fiber doesn’t work; it seems to me that it would be just like choosing a different basis. It seems to me that the cardinality of your “essential inverse image” would just be the cardinality of the fiber divided by |Aut(x)||Aut(x)|. And {z nn!}\{\frac{z^n}{n!}\} is just as good a basis of R[[z]]R[[z]] as {z n}\{z^n\}. Am I missing something?

Posted by: Mike Shulman on January 9, 2009 8:59 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Mike wrote:

I’m not that fond of “essential inverse image” for your notion since it makes me think of the other one; what about something like “full essential fiber?”

I thought “essential inverse image” was the terminology Alan Weinstein convinced me to use… but I just looked at his email again, and it turns out he wanted “full inverse image”. I think that’s pretty good — I’ll change it to that in the next draft.

So, thanks.

Additionally, it’s not clear to me why just using the fiber doesn’t work; it seems to me that it would be just like choosing a different basis. It seems to me that the cardinality of your “essential inverse image” would just be the cardinality of the fiber divided by |Aut(x)||Aut(x)|. And {z nn!}\{\frac{z^n}{n!}\} is just as good a basis of R[[z]]R[[z]] as {z n}\{z^n\}. Am I missing something?

I’ll have to think about this again. What I want is conventions that get the theory of generating functions to work out in the usual way.

If you have a tame groupoid over the groupoid of finite sets: p:ΨE p: \Psi \to E you get a power series called its ‘generating function’.

A classic example is the groupoid of 2-colored finite sets. The generating function in this case is

ψ(z)= n=0 2 nn!z n \psi(z) = \sum_{n = 0}^\infty \frac{2^n}{n!} z^n

There are 2 n2^n ways to 2-color an nn-element set; that explains the 2 n2^n here. The n!n! in the denominator seems like a weird fudge factor, but it’s really necessary to make things work beautifully: for example, multiplying generating functions should correspond to some nice operation on structure types. We ‘explain’ this fudge factor by noting that the groupoid of 22-colored finite sets has cardinality

2 nn!\frac{2^n}{n!}

This groupoid is the ‘full inverse image’ of nEn \in E.

In this classic example, pp is faithful, so p:XEp: X \to E is called a ‘structure type’ or ‘species’ — Joyal called them especes de structure. It’s also important to correctly handle ‘stuff types’, where pp is not faithful.

A nice example of a stuff type is the groupoid of ‘1/21/2-colored finite sets’. This has generating function

n=0 12 nn!z n \sum_{n = 0}^\infty \frac{1}{2^n n!} z^n

You may not know what a ‘1/21/2-colored finite set’ is, but don’t be scared! Here’s what matters. In this example, the ‘full inverse image’ of nEn \in E is equivalent to a certain one-object groupoid, which we can think of as a group: the wreath product of S nS_n and /2\mathbb{Z}/2. This group has 2 nn!2^n n! elements. So, the cardinality of the full inverse image of nn is 12 nn!\frac{1}{2^n n!}.

I will have to check again whether some reshuffling of the various interlocking conventions can make things work out… but this stuff works now, and it’s important. The way I think of it now, it’s the morphisms ‘upstairs’ that really matter in these examples: the morphisms up in Ψ\Psi, not down in EE.

Posted by: John Baez on January 11, 2009 11:38 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

I will have to check again whether some reshuffling of the various interlocking conventions can make things work out… but this stuff works now, and it’s important.

Well, there are two conventions already in the world of generating functions, and you are using the exponential generating functions, right?

I do notice that the essential fibre is more manifestly equivalence-invariant than the fibre; it warms my nn-categorial heart.

Posted by: Toby Bartels on January 12, 2009 2:17 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Toby wrote:

Well, there are two conventions already in the world of generating functions, and you are using the exponential generating functions, right?

Right — but we don’t get to choose; exponential generating functions are the only ones that work well for groupoids over the groupoid of finite sets. The so-called ‘ordinary’ generating functions, without the factorial in the denominator, are the ones that work for groupoids over the groupoid of linearly ordered finite sets.

Groupoidification, as described in this paper, automatically produces both sorts of generating functions, depending on which groupoid we use as the ‘base’.

I agree that the ‘essential fiber’ warms the cockles of my n-categorical heart more than (what I’ll henceforth call) the ‘full inverse image’. But, I believe I was forced into using the full inverse image by the pressure of mathematical reality. I’d be glad to be corrected — and you’ve got me wanting to recheck all the possible conventions, to see if I overlooked a way out. But, the formalism has got to reproduce the known results about generating functions to count as successful.

Posted by: John Baez on January 12, 2009 3:04 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

JB wrote

exponential generating functions are the only ones that work well for groupoids over the groupoid of finite sets. The so-called ‘ordinary’ generating functions, without the factorial in the denominator, are the ones that work for groupoids over the groupoid of linearly ordered finite sets.

There are also ‘logarithmic’ generating functions (denominator is nn, and you sum starting from n=1n=1) which correspond to cyclically ordered sets. I guess there ought to be a way to exponentiate cyclically ordered sets and get linearly ordered sets, but if there is, I’ve forgotten it or never knew it.

Posted by: Tim Silverman on January 12, 2009 5:00 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

The exponential of a cyclically ordered set is more appropriately thought of as a set equipped with a permutation (a finite \mathbb{Z}-set). Same cardinality as finite sets equipped with linear orders, but different.

Posted by: Todd Trimble on January 12, 2009 6:45 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Ah! Of course. I should have seen that. Thanks!

(Of course, you can put permutations into bijection with orderings, in an obvious way, but not canonically. Group vs. torsor!)

Posted by: Tim Silverman on January 13, 2009 12:43 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

the formalism has got to reproduce the known results about generating functions to count as successful.

Absolutely!

Let me explain a little more about the direction in which I was thinking. Consider a groupoid p:ΨEp:\Psi\to E. (By the way, let me mention that I am exceptionally amused by writing “EE” for the groupoid of finite sets.) We are supposed to associate a vector space to EE and a vector in this vector space to Ψ\Psi. The way you’ve written it, the vector space is R[[z]]R[[z]], with basis {z n}\{z^n\}, and the vector corresponding to Ψ\Psi is n|Ψ n|z n,\sum_n |\Psi_n| z^n, where Ψ n\Psi_n is the full inverse image of nEn\in E. The way I am instead thinking of writing it, the vector space is still R[[z]]R[[z]], but now with basis {z nn!}\{\frac{z^n}{n!}\}, and the vector corresponding to Ψ\Psi is n|F n|z nn!,\sum_n |F_n| \frac{z^n}{n!}, where F nF_n is the essential inverse image of nn. The 1n!\frac{1}{n!} is no more arbitrary in this case, though; now it’s the cardinality of Σ n\Sigma_n, the component of EE containing nn. So the equality of the two expressions for the generating function comes down to the equality |Ψ n|=|F n||Σ n||\Psi_n| = |F_n| \cdot |\Sigma_n|. This is true because we have a fiber sequence

F nΨ nΣ n F_n \to \Psi_n \to \Sigma_n

of groupoids in which Σ n\Sigma_n is connected, so for each connected component of Ψ n\Psi_n we get a short exact sequence of groups, and ordinary cardinality is multiplicative for extensions of finite groups.

This also makes me feel a little fuzzier inside because it feels more like the automorphisms in EE have something to do with the construction of the vector space. Of course in one sense they don’t, since it is the same (or isomorphic) in each case, but in some sense they are telling us what basis we should use.

I wonder if there is any way to think about R[[z]]R[[z]] as an “orbi-vector-space” whose points still “have automorphisms?”

Posted by: Mike Shulman on January 12, 2009 7:59 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Is it too late to complain that, while ‘categorification’ is being kept nicely broad, the term ‘groupoidification’ is being shunted into a very narrow path?

In particular, this paper is really about ‘linear groupoidification’ (or even ‘K-linear groupoidification’ if you fix the ground field K), as you can tell because it's the reverse of ‘linear degroupoidification’ (that is replacing a groupoid with a linear space).

But ‘degroupoidification’ is replacing a groupoid with a set, and ‘groupoidification’, the reverse of this, is extremely general, just like ‘categorification’.

Posted by: Toby Bartels on December 28, 2008 8:35 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Is it too late to complain that, while ‘categorification’ is being kept nicely broad, the term ‘groupoidification’ is being shunted into a very narrow path?

I had similar worries, when it occurred to me that maybe the motivation for the term “groupoidification” has really been that it involves passing from a category to its categeory of spans.

As I mention above, this step fully deserves to be called “groupoidification”, albeit not in the sense of a restriction of categorification.

I was alerted to this fact when talking with Igor Baković and Thomas Nikolaus about cocycles in nonabelian cohomology where the coefficient object is a category, not a groupoid. There is a definition by Ieke Moerdijk for what such a principal category bundle should be like, If one looks at this definition closely, it essentially says that a cocycle with a category coefficient object is a cocycle with values in spans in this category. So in this sense the definition says that a cocycle with values in a category is a cocycle with values in the groupoidification of that category.

Posted by: Urs Schreiber on December 28, 2008 11:52 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Toby wrote:

Is it too late to complain that, while ‘categorification’ is being kept nicely broad, the term ‘groupoidification’ is being shunted into a very narrow path?

No, it’s never too late to take a term and broaden its use so vastly that its original precise meaning is almost lost.

And, it may be a good thing to do!

But, Jim Dolan had a pretty specific idea about what groupoidification is about. This idea is somewhat visible in the Tale of Groupoidification, but it’s obscured in this version of ‘Groupoidification Made Easy’.

Namely: groupoidification is a continuation of Felix Klein’s Erlangen Programm, in which composition of spans of groupoids is used to formalize the ‘probabilistic composition of invariant binary relations’. Jim sometimes calls this the ‘quantization of logic’.

A great illustration of this is the A 2A_2 Hecke algebra, as groupoidified in this paper. The span PP means ‘randomly change the point on a line’, while LL means ‘randomly change the line through a point’, and the Hecke algebra relations describe the behavior of these operations in projective geometry over a finite field. In particular, the Yang–Baxter equation PLPLPLP L P \simeq L P L winds up meaning ‘two distinct points determine a line, and two distinct lines determine a point’.

But, I need to add more explanation of the role of Klein geometry before launching into this specific example. To people who don’t know and love the relation between Dynkin diagrams and kinds of geometry, what we’ve written so far will sound obscure and technical.

We also need to add a section on Hall algebras, and explain how these three applications of groupoidification — to Feynman diagrams, Hecke algebras and Hall algebras — are all part of a single idea, namely: the Klein geometry idea applied to the groupoid FinSetFinSet and its qq-deformation FinVect 𝔽 qFinVect_{\mathbb{F}_q}.

It’s this stuff, rather than the general idea of spans or the general idea of replacing sets by groupoids, that’s what really thrills me about groupoidification. Tons of ‘quantum mathematics’ arises naturally from thinking about Klein geometry! That’s a surprising development, whose potential hasn’t been tapped.

Posted by: John Baez on December 28, 2008 5:13 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

If you’re ‘randomly changing the line through a point’ and such like, do you make contact with Klain and Rota’s Geometric Probability?

Can you sympathise with this:

Geometric probability has suffered in this century the fate of other fields that would have enjoyed a healthy autonomous development, had it not been for the overpowering development of representation theory. One can reduce integral geometry to the study of actions of Lie groups, to symmetric spaces, to the Radon transform; in so doing, however, the authentic problematic of the subject is lost. Geometric probability is a customer of representation theory, in the same sense that mechanics is a customer of the calculus.

Posted by: David Corfield on December 30, 2008 11:52 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

David wrote:

If you’re ‘randomly changing the line through a point’ and such like, do you make contact with Klain and Rota’s Geometric Probability?

I think so — though sadly, I haven’t read this book! What I know is that we’re doing the finite field case of things like the Radon transform, Penrose transform and so on. I talked about this in the Tale of Groupoidification, but only very sketchily. Rota might like what we’re doing, though: the representation theorists take a span of GG-spaces and turn it into an intertwining operator between representations of GG on vector spaces — but that’s a form of degroupoidification, and we’re resisting that move, working with the things themselves instead of their shadows in the world of linear algebra.

Posted by: John Baez on December 30, 2008 10:28 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

We have the generalization of groupoid cardinality to strict nn-groupoids. What is known about the generalization of theorem 23 to this context. In particular its generalization to 2-groupoids?

Dopes the obvious generalization hold?

Posted by: Urs Schreiber on December 29, 2008 9:07 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Is there something wrong in def. 16 (adjoint span)? Both diagrams are the same.

Posted by: RodMcGuire on December 29, 2008 11:32 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Rod wrote:

Both diagrams are the same.

You got me scared for a second, but no: they’re not the same.

I admit they’re similar, but the first is a span from XX to YY, while the second is a span from YY to XX.

Similarly, a relaxed sort of person might say that a matrix is the ‘same’ as its transpose, because you can get one by flipping the other around. But they’re not really equal.

I will clarify this in the paper now.

Posted by: John Baez on December 30, 2008 3:15 AM | Permalink | Reply to this
Read the post Groupoidification from sigma-Models?
Weblog: The n-Category Café
Excerpt: On constructing sigma-models from differential nonabelian cocycles and how this gives rise to methods of groupoidification.
Tracked: December 30, 2008 4:25 PM

Re: Groupoidification Made Easy

Is there a way to extend the real numbers to a ri(n)g in such a way that the definition of groupoid cardinality could be extended to all groupoids?

Or, what is perhaps the same question, can the relation “has the same cardinality” be extended to all groupoids in a way preserving sums and products?

This seems closely related to the question of why, intuitively, a point with an automorphism should be counted as “a fraction of a point.”

Posted by: Mike Shulman on January 12, 2009 8:05 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Here’s a cheap answer to your question. Let RR be the collection of all equivalence classes of groupoids — where the equivalence relation is none other than equivalence. Then RR has a rig structure coming from the usual notions of ++ and ×\times for groupoids, that is, ‘disjoint union’ (or ‘coproduct’) and ‘cartesian product’ (or ‘product’). We can then define an RR-valued cardinality for groupoids in a completely tautologus way: given a groupoid XX, its cardinality |X|R|X| \in R is just its equivalence class.

Of course this rig RR is a proper class. So, it’s what truck drivers call a big rig.

What’s interesting is that this big rig has [0,+][0,+\infty] as a quotient rig. So, maybe [0,+][0,+\infty] is the answer to your question. Or maybe you’re asking for larger but still manageable quotients of RR. I don’t know a good answer to that. There are probably many good answers.

Posted by: John Baez on January 12, 2009 8:20 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

By the way, the rig RR described above might well be called the rig of 2-cardinals, since the collection of isomorphism of classes of sets is the usual rig of cardinals, and now we’re mimicking that idea using equivalence classes of groupoids.

We could also form rigs of equivalence classes of nn-groupoids, or nn-categories, to get even more sophisticated notions of ‘cardinal’. However, right now these all seem rather unmanageable to me.

Posted by: John Baez on January 12, 2009 9:08 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Yeah, I actually thought of that. But then I convinced myself that RR, itself, is not really all that interesting. It seems that an alternate construction of RR is as follows (assuming that by “groupoid” we mean “small groupoid”): consider the class GrpGrp of all (small) groups, made into a monoid with cartesian product. Let CardCard be the big rig of (small) 1-cardinals. Then RR is just the “big monoid algebra” Card[Grp]Card[Grp] (in which we allow arbitrary small sums, not just finite ones).

I think that, yes, I was hoping for a larger quotient of RR than [0,+][0,+\infty]. But I would also be interested if one could give an explicit description of the kernel of R[0,+]R\to [0,+\infty]. Could one use this as a construction of the real numbers?

Posted by: Mike Shulman on January 13, 2009 12:38 AM | Permalink | Reply to this
Read the post Dendroidal Sets and Infinity-Operads
Weblog: The n-Category Café
Excerpt: Notes from a talk by Ieke Moerdijk on dendroidal sets, with a few remarks on presheaves on the category of posets.
Tracked: February 6, 2009 1:04 AM
Read the post Journal Club -- Geometric Infinity-Function Theory -- Week 1
Weblog: The n-Category Café
Excerpt: Journal Club on Geometric oo-Function theory part I: Introduction to integral transforms.
Tracked: April 27, 2009 4:58 PM

Re: Groupoidification Made Easy

I thought I knew where it was written, but now I can’t find it:

where is the statement that the Karoubi-envelope of spans in groupoids is equivalent to finite dimensional vector spaces?

Split(Span(Grpd))FinVect Split(Span(Grpd)) \simeq FinVect

??

Posted by: Urs Schreiber on August 11, 2009 2:53 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

You’ll find a stronger (yet still, I hope, true) statement here. If you take that statement and set the group GG equal to the trivial group, you’ll get a statement that resembles the one you’re asking for here.

(But note: not exactly what you just said! Your version of the claim doesn’t explain how a particular field gets into the game!)

It sounds like you’re hinting we should include a result like this in Groupoidification Made Easy. That would be a good idea, especially since we’re in the process of adding some extra stuff to this paper and turning it into ‘HDA7: Groupoidification’.

There will be more on this sort of stuff in ‘HDA8: The Hecke Bicategory’.

Posted by: John Baez on August 12, 2009 2:56 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Thanks.

Have you thought about the following:

N(Span(Grpd))N(Span(Grpd)) looks like a first step in the Kan-fibrant replacement of N(Grpd op)N(Grpd^{op}) in terms of the ExEx-functor as described here.

I am wondering what happens if we take N(Grpd op)N(\infty Grpd^{op}) and then its full Kan fibrant replacement, then freely \mathbb{Q}-linearize somehow and split idempotents.

Is there any literature on Karoubi envelopes of dg-categories?

Posted by: Urs Schreiber on August 12, 2009 12:58 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Is there any literature on Karoubi envelopes of dg-categories?

I have now collected some pointers to references that have useful things to say on this at Karoubi envelope .

Posted by: Urs Schreiber on August 12, 2009 8:31 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

There is another thing I thought I knew where to look for but now can’t find:

your prescription for groupoidification for spans of groupoids over a given groupoid.

It’s not in Groupoidification made easy, is it?

I thought it was in HDA VII, but the old version of this which I remembered (it had lots of topos-theoretic statements in it) seems to be gone, under the above link I find a file whose content seems to be a copy of “Groupoidification made easy”.

I want the non-easy version! :-) Do you still have that somewhere?

Posted by: Urs Schreiber on August 18, 2009 10:07 AM | Permalink | Reply to this

Re: Groupoidification Made Easy

Sorry for the confusion!

  • ‘Groupoidification Made Easy’ has been renamed ‘HDA7: Groupoidification’, and we plan to expand it a little and publish it soon.

  • ‘HDA7: the Hecke Bicategory’ has been renamed ‘HDA8: the Hecke Bicategory’, and we plan to expand it a lot.

It’s the latter paper that contains material related to topos theory. For material on spans of groupoids over a given groupoid, you may be thinking of Episode 4 of the Tale of Groupoidification.

For quick and clearly explained access to all our papers, lecture notes and videos on groupoidification, go to:

http://math.ucr.edu/home/baez/groupoidification

Posted by: John Baez on August 18, 2009 4:33 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Okay, thanks, I see.

you may be thinking of Episode 4 of the Tale of Groupoidification.

I did look at that, but didn’t see what I was looking for. Now I am thinking that I was probably hallucinating: I seemed to remember that for spans over groupoids you had a twisted degroupoidification prescription that differed from the one obtained by forgetting that the spans are over something.

But probably you don’t. So, sorry for the confusion on my part, too.

and we plan to expand it a little and publish it soon.

I see. By the way: do you maybe still find time to add a discussion of groupoidified traces? That’s an important aspect of the whole story. It would be a pity if it weren’t in there.

Posted by: Urs Schreiber on August 18, 2009 4:57 PM | Permalink | Reply to this

Re: Groupoidification Made Easy

Urs wrote:

By the way: do you maybe still find time to add a discussion of groupoidified traces? That’s an important aspect of the whole story. It would be a pity if it weren’t in there.

I should really include a bit about multilegged spans as groupoidified versions of multi-index tensors T ijkT_{ijk \cdots}, and point out that all the usual index-juggling can be done at the groupoidified level, including index-raising and index-lowering. We talked about this earlier.

The trace T i iT_i^i is a nice example.

I’d actually been hoping — somewhat optimistically — to finish this paper off today! Guess that won’t happen. But yes, this stuff is important and easy.

Posted by: John Baez on August 18, 2009 5:09 PM | Permalink | Reply to this
Read the post Higher-Dimensional Algebra VII: Groupoidification
Weblog: The n-Category Café
Excerpt: Check out our new paper "Higher-dimensional algebra VII: groupoidification".
Tracked: August 23, 2009 2:56 AM

Post a New Comment