January 4, 2010

Generalized Multicategories

Posted by Mike Shulman

Geoff Cruttwell and I have just finished an improved version of our paper “A unified framework for generalized multicategories,” which can be found here. Although the main purpose of the paper is, as the title says, to describe a framework which unifies the many existing approaches to generalized multicategories, we deliberately started out from basics so that it would also be suitable as an introduction to the subject. So whether or not you’ve ever encountered generalized multicategories before, if you have a chance to look over the paper, we’d appreciate any feedback. It’s a little long, but not as long as it looks, since a lot of space is taken up by diagrams.

(Coincidentally, the timing of this post is quite good; this paper is another example of the importance of double categories, proarrow equipments, and lax functors. The notion of “representability” for generalized multicategories is also closely related to the “algebraic/non-algebraic” dichotomy under discussion here.)

I won’t say much more here, because I want you to go read the paper, but let me try to whet your appetite a bit. In particular, if you’ve never seen generalized multicategories before, I’d like to try to convince you that they’re interesting. (I gave a very different sort of introduction back here. To start with, an ordinary multicategory is like a category, except that the source of an arrow can be a finite list of objects instead of a single object. A nice example is the multicategory of vector spaces, in which a “multiarrow” $(V_1, \dots, V_n) \to W$ is just a multilinear map. The composition of multiarrows can be visualized by drawing them as trees with $n$ inputs and one output, and then “plugging” outputs into inputs. There are some nice ASCII pictures at week 191.

Now, a generalized multicategory is what we get when we replace the “finite lists” by “something else.” It turns out that a lot of interesting and well-known things pop up when we make clever choices of the “something else.” For example:

• If we replace “finite lists” by “finite lists whose elements can be permuted,” we get symmetric multicategories. These are actually what John was talking about in week 191, or rather their one-object version called operads.

• Of course, if we replace finite lists by “single objects,” then we just get out categories again.

• If we replace them by “finite lists whose elements can be discarded or duplicated,” we get (multi-sorted) Lawvere theories, along with some variants that I was talking about back here.

• If we replace them by “objects labeled by an integer,” we get $\mathbb{Z}$-graded categories, i.e. categories in which every morphism has an degree $\in\mathbb{Z}$ and composition is additive on degrees.

• If we internalize in globular sets and replace finite lists by “pasting diagrams,” we get (multi-sorted) Batanin/Leinster globular operads.

• And if we enrich over truth values and replace finite lists of objects by ultrafilters of objects, we get… topological spaces! The idea here is that if $U$ is an ultrafilter of objects, then there’s an arrow $U\to x$ (necessarily unique, since we’re enriched over truth values) if and only if $U$ converges to $x$. This is the Australian definition of a topological space.

In general, the basic data for a “type of generalized multicategory” consists of a monad $T$. The idea is that if $X$ is the set of objects, then $T X$ is the set of “possible sources” for a multiarrow. (For ordinary multicategories, $T$ is the “free monoid” monad.) The problem is that $T$ is often a lax functor—but as we’ve recently seen there is no good 2- or 3-category of lax functors, so it’s unclear what a “lax monad” should mean. Different authors have come up with different ideas of what the relevant monads should look like, but usually only relative to a particular bicategory or class of bicategories. What one would really like, however, is a framework that captures all the above examples at once.

Geoff and I realized that this problem can be solved by using double categories, or more precisely proarrow equipments, since for those we do have a 2- or 3-category of lax functors. Double categories also solve another problem: if we just consider $T$ as a monad (lax or not) on a bicategory, then it’s not immediately clear how to define functors and transformations between generalized multicategories, but if we use double categories, both fall out automatically.

The final nifty thing I want to mention is the idea of representability. In the multicategory of vector spaces, we have universal multiarrows $(V_1,\dots, V_n) \to V_1\otimes \dots \otimes V_n$. This, in turn, implies that $Vect$ is not just a multicategory but a monoidal category. In general, any pseudo $T$-algebra has an underlying generalized multicategory relative to $T$, and a generalized multicategory comes from a $T$-algebra if and only if its multiarrows have this “representability” property. I believe this was first written down in some generality by Claudio Hermida. It also makes sense in the general double-categorical context as long as our double categories are actually proarrow equipments.

Because of this close connection between algebras and multicategories for a monad, Geoff and I proposed to call generalized multicategories defined relative to the monad $T$ virtual $T$-algebras. This is most advantageous when working with a monad $T$ whose algebras are called (say) “widgets,” but for which $T$ itself has no name other than “the free widget monad,” since it is more convenient and descriptive to say “virtual widget” than “free-widget-multicategory.” In fact, for the theory of generalized multicategories it turned out to be necessary to use, not ordinary double categories, but virtual double categories, a.k.a. fc-multicategories.

(Edit: There’s a confusing subtlety here in that some notions of multicategory can be defined starting from two different monads $T$, using slightly different definitions of “generalized multicategory.” For instance, ordinary multicategories are related both to the “free monoid” monad and to the “free monoidal category” monad, while virtual double categories are related both to the “free category” monad and to the “free double category” monad. Tom Leinster’s terminology “$T$-multicategory” uses the former kind of definition, hence the name “fc-multicategory” with “fc” standing for the “free category” monad. Geoff and I use the latter kind of definition, since it turns out to include more examples; hence “virtual double category” rather than “virtual category.” There also seems to be some dispute about the appropriateness of “virtual;” see the comments below.)

You can have some fun working out what representability means in all the above examples, but here’s one I didn’t mention before. Suppose we fix a category $A$ and work internal to $Cat^{ob(A)}$, with $T$ the monad whose algebras are functors $A^{op}\to Cat$. Then a virtual $T$-algebra turns out to be just a category $C$ equipped with a functor $C\to A$, and the “representability” property turns out to say precisely that this functor is a fibration. Thus, the equivalence between fibrations and pseudofunctors is a special case of representability for generalized multicategories.

Posted at January 4, 2010 2:10 AM UTC

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

Re: Generalized Multicategories

Nice stuff, Mike!

Somebody should start internalizing this nice general theory into the $(\infty,1)$-context:

as you know (but I’ll repeat it for the record), there are currently two different definitions of $(\infty,1)$-operad in the literature: one of them $\infty$-categorifies the definition of ordinary operads in terms of its category of operators, the other defines the expected notion of nerve of an $(\infty,1)$-operad in terms of dendroidal sets.

It would be nice to have in addition a definition in terms of $(\infty,1)$-monads. I suppose if we’d had a notion of proarrow equipment of an $(\infty,1)$-category (which sounds easier) or framed $(\infty,2)$-category (which sounds harder), we’d be in business, by directly applying your theory.

We had a discussion about this already last time. But I am not sure: have you seriously thought about the notion of $(\infty,1)$-proarrow structures?

Posted by: Urs Schreiber on January 4, 2010 11:42 AM | Permalink | Reply to this

Re: Generalized Multicategories

I’ve thought about it a bit. One approach to defining a “quasi–double-category” is to look for horn-filling conditions on a bisimiplicial set. One could also pick a notion of $(\infty,2)$-category and generalize Wood’s definition of proarrow equipment. However, I think my inclination would be to fill in the analogy

operad : dendroidal set :: virtual double category : ??

and then write down horn-filling conditions on the ??s to obtain a notion of quasi-vdc. The universal properties of units, composites, and cartesian fillers should then also be expressible in this language, analogously to the notion of Cartesian fibration between quasicategories. A quasi-vdc with units and cartesian fillers one might then call an “$(\infty,2)$-category with a (virtual) proarrow equipment.”

As for what ?? is, probably the general stuff about nerves and familial representability would be helpful. However, I think one could also give a direct definition in terms of the equipment of $T$-spans, where $T$ is the “free category” monad on directed graphs.

Posted by: Mike Shulman on January 4, 2010 8:41 PM | Permalink | Reply to this

Re: Generalized Multicategories

look for horn-filling conditions on a bisimiplicial set.

Or maybe on a dendroidal simplicial set?

(Non-planar dendroidal, that is.)

Modelling how the virtual double category pairs the aspects of a multicategory with that of a category “running parallely”.

There is a known model structure on dendroidal simplicial sets that localizes the simplicial direction such as to be Quillen equivalent to the standard Moerdijk-Cisinki model structure. This is useful for many computations in the ordinary model structure.

I am not sure if it is known what this models without the localization in the simplicial direction.

In other words, my remark here probably amounts to asking/suggesting if a dendroidal refinement of $\Theta$-spaces might be a way to model double $(\infty,r)$-categories, i.e. in terms of localizations of dendroidal presheaves on $\Theta_r$.

Even if not, that would be something interesting to look at. The model structure should be the evident one.

(NB:as usual, the links provided are just for the record and for other readers. )

Posted by: Urs Schreiber on January 5, 2010 10:34 AM | Permalink | Reply to this

Re: Generalized Multicategories

Dendroidal simplicial sets just don’t seem to me to have the right shapes to model virtual double categories. I can see why you might guess that, and there might be some sort of relationship, but I wouldn’t expect it to be anything simple.

Posted by: Mike Shulman on January 5, 2010 7:02 PM | Permalink | Reply to this

Re: Generalized Multicategories

First of all, are the “finite lists whose elements can be permuted” here the same as multisets (free commutative monoids)? Conversely, are the “objects labeled by an integer” of graded categories related to free abelian groups?

How do multicategories relate (if at all) to the way monads are used in functional programming? Here’s an introduction to FP monads from the free object perspective.

Posted by: guest on January 5, 2010 8:34 PM | Permalink | Reply to this

Re: Generalized Multicategories

First of all, are the “finite lists whose elements can be permuted” here the same as multisets (free commutative monoids)?

If you read the paper (hint, hint), you’ll find that the answer is no. The relevant monad is the “free symmetric monoidal category” monad. So “can be permuted” was a rough way of talking, not about unordered lists, but about lists equipped with an isomorphism to each of their permutations.

Conversely, are the “objects labeled by an integer” of graded categories related to free abelian groups?

Not exactly, but they are related to free Z-sets.

(That’s a use of “conversely” that I haven’t seen before… are free abelian groups the converse of free commutative monoids? (-: )

Posted by: Mike Shulman on January 5, 2010 9:49 PM | Permalink | Reply to this

Re: Generalized Multicategories

virtual double categories, a.k.a. fc-multicategories

For many years I’ve regretted the name ‘fc-multicategory’ and hoped for a better alternative. Virtual double category seems reasonable to me. By the same token, a multicategory might be called a virtual monoidal category.

While I quite like it, I have one reservation, which is that it makes a multicategory sound a bit like a defective or wannabe monoidal category. It’s got a slight ring of ‘pseudo-X’ about it — the insinuation is that X’s are the real thing, and pseudo-X’s are some kind of not-quite-as-good alternative. As you argue, the multicategory structure on vector spaces is in a way more basic than the monoidal category structure. This is a common situation.

I believe this is why the term rig was coined, even though the synonymous term semiring already existed. The point was that rigs are a very natural concept in their own right: they shouldn’t be seen as rings manquants.

All of the above is what I was going to say until I reread that paragraph in your post. But now I’m confused, because you also write:

Geoff and I proposed to call $T$-multicategories virtual $T$-algebras […] it is more convenient and descriptive to say “virtual widget” than “free-widget-multicategory”.

As you know (but lots of people don’t), fc-multicategories are $T$-multicategories in the case where $T$ is the free category monad fc on the category of directed graphs. In that case, a $T$-algebra is a category. So doesn’t your proposal make an fc-multicategory a ‘virtual category’?

Posted by: Tom Leinster on January 7, 2010 2:45 PM | Permalink | Reply to this

Re: Generalized Multicategories

For many years I’ve regretted the name ‘fc-multicategory’ and hoped for a better alternative.

I’m glad that we aren’t stepping on your toes by trying to rename them! (-:

I have one reservation, which is that it makes a multicategory sound a bit like a defective or wannabe monoidal category.

This is true. One could argue that a multicategory is, in fact, a not-quite-as-good alternative to a monoidal category. Certainly, there are things that one can do with monoidal categories that one can’t do with multicategories. I also think that “virtual” is not as bad as “pseudo” in this respect, because in ordinary language, “virtually X” means “almost X” or “might as well be X” (TheFreeDictionary says “virtual” means “existing or resulting in essence or effect though not in actual fact, form, or name”), whereas “pseudo” has the connotation of a fake imitation.

That said, if you’ve got a better suggestion, I’m all ears. I do like the idea of attaching an adjective to “monoidal category” (resp. “double category”) to obtain a name for “multicategory” (resp. “fc-multicategory”). But I’m not especially attached to “virtual,” if anyone has a better suggestion.

As you know (but lots of people don’t), fc-multicategories are T-multicategories in the case where T is the free category monad fc on the category of directed graphs.

That’s true, if “T-multicategory” is meant in your sense (which Geoff and I call a T-monoid in a virtual equipment of spans). But fc-multicategories are also T-multicategories where T is the free double category monad on the virtual equipment of Cat-graphs and Cat-graph-profunctors, where now “T-multicategory” is meant in the slightly different sense of Hermida (which Geoff and I call a normalized T-monoid). Likewise, ordinary multicategories are T-monoids where T is the free-monoid monad on (spans of) sets, but are also normalized T-monoids where T is the free-monoidal-category monad on categories and profunctors. And quite generally, T-monoids can be identified with normalized Mod(T)-monoids for any monad T on a virtual equipment.

However, some other notions of multicategory can only be defined as normalized T-monoids for some T which is not of the form Mod(S). For instance, symmetric multicategories are normalized T-monoids, where T is the free-symmetric-monoidal-category monad on categories and profunctors, and this T is not of the form Mod(S). For that reason, Geoff and I decided that “normalized T-monoid” is a better definition of “generalized multicategory,” since it is actually more general. So when I said that we call T-multicategories “virtual T-algebras,” I meant that we call normalized T-monoids “virtual T-algebras.” Thus, since fc-multicategories are normalized T-monoids for the free-double-category monad T, they are “virtual double categories.” A “virtual category” would be a normalized T-monoid for the free-category monad, which is actually a pretty weird sort of structure. (I hope you agree that fc-multicategories should be called “virtual double categories” and not “virtual categories”? Since they are manifestly double-category-like.)

All of this is explained in the paper (hint, hint). It’s possible that it’s not explained very well, though; we had a lot of trouble trying to get this across clearly. So if you have any suggestions about how to improve the exposition, we’d love to hear them.

Posted by: Mike Shulman on January 7, 2010 7:14 PM | Permalink | PGP Sig | Reply to this

Re: Generalized Multicategories

Re “virtual double category”, if you’re going to go with the strategy of finding some phrase along the lines of “not quite a double category”, then I think “virtual” is a good choice. It’s certainly a whole lot better than pseudo, quasi, weak, etc, and I agree that it has less of a connotation of fakeness. It makes me think of virtual reality.

That’s true, if “$T$-multicategory” is meant in your sense (which Geoff and I call a $T$-monoid in a virtual equipment of spans). But fc-multicategories are also $T$-multicategories where $T$ is the free double category monad on the virtual equipment of Cat-graphs and Cat-graph-profunctors, where now “$T$-multicategory” is meant in the slightly different sense of Hermida

Ah, I see. Thanks.

All of this is explained in the paper (hint, hint)

:-)

Posted by: Tom Leinster on January 7, 2010 11:19 PM | Permalink | Reply to this

Re: Generalized Multicategories

Tom wrote:

For many years I’ve regretted the name ‘fc-multicategory’…

Good! I haven’t paid much attention to them, precisely because their name leaves me unable to tell what they’re like, and therefore unable to guess when they might be the thing I need.

(I also get them mixed up with $T$-multicategories, which are somewhat easier to fathom, as long as one is the elite club of people who know that ‘$T$’ means ‘monad’, and that multicategories involve the ‘free monoid’ monad.)

Tom wrote:

I believe this is why the term rig was coined, even though the synonymous term semiring already existed.

I don’t know why it was coined, but there are three additional reasons I like the term ‘rig’. First, the term ‘semiring’ suggests an analogy

$semiring:ring::semigroup:group$

but this is sadly misleading, since a semiring lacks only negatives, while a semigroup lacks not only negatives but also the identity element.

(A semigroup is slightly less than half a group: it should be called a ‘$(\frac{1}{2}-\epsilon)$-group’, while a monoid could be called a ‘$(\frac{1}{2} + \epsilon)$-group’.)

Second, the term ‘rig’ always gets a laugh when you explain how it means ‘ring without negatives’. And this laugh makes the definition impossible to forget.

Third — but this one is a lot less important — I think it’s fun to point out that $Card$, the class of all cardinals, is a big rig.

Posted by: John Baez on January 8, 2010 3:45 PM | Permalink | Reply to this

Re: Generalized Multicategories

I haven’t paid much attention to [fc-multicategories], precisely because their name leaves me unable to tell what they’re like, and therefore unable to guess when they might be the thing I need.

Is “virtual double category” better in this regard?

At least, once you’ve been told that “virtual X : X :: multicategory : monoidal category”?

Posted by: Mike Shulman on January 8, 2010 6:39 PM | Permalink | Reply to this

Re: Generalized Multicategories

I think it’s somewhat better. At least it doesn’t look like an acronym for ‘f***ing-crazy multicategory’.

It was Jim Dolan who brought the word ‘virtual’ into my mathematical vocabulary. For him a ‘virtual object’ is a universal property of an object: that is, a representable presheaf. So, he calls anafunctors ‘virtual functors’, since they are like functors, except they send objects to virtual objects.

So, that’s the sense in which I most like to use the term ‘virtual’. I don’t think that’s quite what’s going on here.

Posted by: John Baez on January 8, 2010 8:16 PM | Permalink | Reply to this

Re: Generalized Multicategories

I don’t think that’s quite what’s going on here.

No… but it’s related, as you probably know. If a multicategory is “representable,” then any pair of objects $x,y$ has a tensor product $x\otimes y$ which is a “virtual object” in Jim’s sense. And similarly for generalized multicategories, such as fc-multicategories.

I’d be inclined to just use “ana-” for Jim’s notion. We have “anafunctor” already, which I think is a perfectly good name. Makkai already uses “ana-object” for an anafunctor with source $1$, which is more or less what you describe as a “virtual object,” and likewise “anabicategory” or “ana-monoidal category.”

Although actually, unless pedantry is necessary for some reason, I prefer not to distinguish at all between things and ana-things. Since an ana-object is determined uniquely up to unique specified isomorphism, who cares about any remaining ambiguity? I would just call that “an object.”

Posted by: Mike Shulman on January 8, 2010 8:34 PM | Permalink | PGP Sig | Reply to this

Re: Generalized Multicategories

I don’t love the term ‘ana’, because I don’t actually have much of a feeling for what that prefix actually means! I know there’s metabolism, catabolism and anabolism — and anabolic steroids — but what do thoese have to do with anafunctors?

Most of the times, I don’t distinguish between things and virtual things. But there are times when some pedantry is called for.

I suppose if you don’t want to use it much, ‘ana-’ is a good prefix.

Posted by: John Baez on January 8, 2010 10:58 PM | Permalink | Reply to this

Re: Generalized Multicategories

I don’t love the term ‘ana’, because I don’t actually have much of a feeling for what that prefix actually means! I know there’s metabolism, catabolism and anabolism — and anabolic steroids — but what do thoese have to do with anafunctors?

Makkai explains it in the introduction of his article: he was thinking of something that relates to profunctors as anaphase relates to prophase in cell mitosis.

While I can live with the prefix “ana”, I never understood this analogy.

What I dislike about the term anafunctor is that the term hides that this is a specical case of a well known concept (well know already when the term was invented): that of morphisms out of acyclic fibrations over the domain.

Posted by: Urs Schreiber on January 9, 2010 11:18 AM | Permalink | Reply to this

Re: Generalized Multicategories

oh, no relation to anabaptist! ;-)

let’s hear it for virtual

Posted by: jim stasheff on January 9, 2010 2:36 PM | Permalink | Reply to this

Re: Generalized Multicategories

jim stasheff:

oh, no relation to anabaptist! ;-)

let’s hear it for virtual

If you want more distinction than present in just the word “virtual” then you can borrow terminology for specific virtual types, such as Prudence, Justice, Restraint, Temperance, Courage, Fortitude, Faith, Hope, Love, Charity, Chastity, Diligence, Patience, Kindness, or Humility. Or from the co-virtual types such as Wrath, Avarice, Greed, Sloth, Vanity, Lust, Envy, Gluttony, Pride, Extravagance, or Despair.

Some of these concepts are already enshrined in mathematical and related terminology. But others are still begging for adoption.

Posted by: RodMcGuire on January 10, 2010 12:08 AM | Permalink | Reply to this

Re: Generalized Multicategories

Here’s what Makkai wrote in the introduction to “Avoiding the axiom of choice…”:

The use of the prefix “ana” has been suggested by Dusko Pavlovic. He noted the use of “pro-” in category theory (profunctor, proobject), and noted than in biology, the terms “anaphase” and “prophase” are used in the same context.

That sounds to me like anafunctors aren’t supposed to be necessarily related to profunctors, only that “ana-” was a heretofor unused prefix in mathematics, and that biologists happen to apply it to at least one of the same things that they apply “pro-” to. Note that he mentions pro-objects as well as profunctors, which are two totally unrelated uses of the prefix “pro-” in mathematics.

So I never thought the prefix “ana-” was supposed to mean anything a priori; it’s just something previously meaningless that Makkai chose to give this particular meaning to.

the term hides that this is a special case of a well known concept… morphisms out of acyclic fibrations over the domain.

Unfortunately, “morphism out of an acyclic fibration over the domain” isn’t a really snappy name, or very easy to say if you want to talk about them a lot.

Posted by: Mike Shulman on January 9, 2010 9:43 PM | Permalink | Reply to this

Re: Generalized Multicategories

Here’s what Makkai wrote in the introduction […]

True, he doesn’t exactly claim an analogy, only notices that “anaphase” and “prophase” are two words used in the same context.

Unfortunately, “morphism out of an acyclic fibration over the domain” isn’t a really snappy name, or very easy to say if you want to talk about them a lot.

Right, while a well-studied concept, it’s not snappy term, unfortunately. A snappy version of it is: cocycle.

Maybe it’s not so much that the term “anafunctor” doesn’t make clear that it’s a morphism out of an acyclic fibration that bothers me, but that the literature discussing them doesn’t make it clear.

It might be good to define anamorphism to mean:

in a category $C$ equipped with a calculus of fractions $W \subset Mor(C)$, an anamorphism from $X$ to $Y$ is a span

$\array{ \tilde X &\to& Y \\ {}^{\mathllap{\in W}}\downarrow \\ X } \,.$

These spans are studied a lot. It seems that nobody bothered to give them a dedicated name. We could call them anamorphisms. Then Makkai’s anafunctors are anamorphisms for the caluclus of fractions on $Cat$ given by surjective equivalences.

Posted by: Urs Schreiber on January 10, 2010 3:18 PM | Permalink | Reply to this

Re: Generalized Multicategories

A snappy version of it is: cocycle.

Unfortunately, “cocycle” doesn’t sound to me like any sort of morphism. If someone talks about “a cocycle from $A$ to $B$” I’m likely to say “huh?” whereas if they talk about “an anafunctor from $A$ to $B$” I can at least guess that an anafunctor is something like a functor.

It might be good to define anamorphism…

I had a similar thought, but then I dismissed it as too ridiculous. But if it occurred to you too, then maybe there’s something to it.

Making the connection explicit between anafunctors and calculi of fractions is also nice. For instance it connects this fact about local-smallness of the localization w.r.t. a calculus of fractions with some of these facts about when categories of anafunctors are essentially small.

Unfortunately, “anamorphism” already means something. But we could follow Jim’s suggestion and use “virtual” instead, so that a span of that sort is called a “virtual morphism.” I observe that Makkai himself later adopted the term “virtual functor” in place of “anafunctor” (and also used “virtual monoidal category” in a corresponding sense). And Makkai’s notion of “very surjective morphism” for any FOLDS-definable concept is a nice generalization of acyclic fibrations, which presumably will admit a calculus of fractions and result in a good notion of “virtual morphism” this way.

But if we do that, then Geoff and I need a new adjective for generalized multicategories! Help!

Posted by: Mike Shulman on January 11, 2010 4:28 AM | Permalink | PGP Sig | Reply to this

Ana-terminology (Was: Generalized Multicategories)

But if we do that, then Geoff and I need a new adjective for generalized multicategories!

Your terminology is very nice, and I don't think that you should let it get pushed aside by this other meaning of ‘virtual’, which is (here I make my bold claim) not important.

Of course, it is important to understand the concept of anafunctor, etc. But an anafunctor simply is a functor, described in a set-theoretical context. Consider these theorems:

• A fully faithful functor between categories is an equivalence, in the sense that it has a weak inverse in the form of another functor, if it is essentially surjective on objects.

• A fully faithful anafunctor between categories is an equivalence, in the sense that it has a weak inverse in the form of another anafunctor, if it is essentially surjective on objects.

• A fully faithful functor between categories is an equivalence, in the sense that it has an inverse in the form of another functor, if it is surjective on objects.

The first theorem holds in the language of set theory assuming the axiom of choice, while the middle theorem holds in the language of set theory regardless of the axiom of choice; they are really about strict categories. But the last theorem holds in the non-evil language of category theory itself, again regardless of the axiom of choice. Just as we learn to say ‘functor’ instead of ‘2-functor’ or ‘psuedofunctor’ for something that goes between 2-categories, so we will also someday learn to say ‘functor’ instead of ‘anafunctor’ or ‘virtual functor’ for something that goes between categories and is applicable regardless of the axiom of choice. Most mathematicians simply don't work in a language in which this is natural (although most also accept the axiom of choice and so don't notice the discrepancy here).

Things are a little more complicated when discussing internal categories. By thinking of categories as internal to a category of (possibly large) sets, we are forcing them into the mould of set theory, and it is this situation (the study of strict categories) that we immediately generalise when discussing categories internal to some other category. So there is a real difference between smooth functors and smooth anafunctors between Lie groupoids, for instance. So we need terminology for this situation, as well as for any discussion of the foundations of category theory. But fundamentally, the concept of anafunctor is simply the concept of functor, only better described.

Posted by: Toby Bartels on January 13, 2010 12:04 AM | Permalink | Reply to this

Re: Ana-terminology

Incidentally, the oldest term for an ana-concept appears to be ‘clique’ for ana-object. There's a reference to this in Makkai's paper (Joyal & Street, 1991, The geometry of tensor calculus).

Posted by: Toby Bartels on January 13, 2010 1:12 PM | Permalink | Reply to this

Re: Generalized Multicategories

So we need terminology for this situation, as well as for any discussion of the foundations of category theory. But fundamentally, the concept of anafunctor is simply the concept of functor, only better described.

I agree with that completely, as you probably know – it’s what I was trying to get at up here. But I’m getting the impression that people would prefer to use “virtual” in preference to “ana-” as the terminology for that situation, I guess because its meaning is more evident. I think Geoff said that some people at CT09 expressed similar feelings to him.

Posted by: Mike Shulman on January 13, 2010 1:17 AM | Permalink | Reply to this

Re: Generalized Multicategories

A snappy version of it is: cocycle.

Unfortunately, “cocycle” doesn’t sound to me like any sort of morphism.

It doesn’t sound like it. But it turns out that these morphisms typically encode what people call cocycles.

If someone talks about “a cocycle from $A$ to $B$” I’m likely to say “huh?”

But that somebody will say insstead: “a cocycle on $A$ with coefficients in $B$”.

For pretty much every notion of cohomology out there, there is an $(\infty,1)$-category $\mathbf{H}$ such that the “the cohomology of $X$ with coefficients in $A$ is $\pi_0 \mathbf{H}(X,A)$.

And this hom-set may often be modeled by anamorphisms from $X$ to $A$, in that $\pi_0 \mathbf{H}(X,A) = colim_{\tilde X \stackrel{\in W}{\to} X} Hom(\tilde X, A)$, as you know. This is for instance true for all flavors of sheaf cohomology.

It might be good to define anamorphism…

I had a similar thought, but then I dismissed it as too ridiculous. But if it occurred to you too, then maybe there’s something to it.

Why is that more ridiculous than the special case of anafunctor? Well, I am maybe not promoting the use of “anamorphism”-terminology, because I think if one says, for instance, “representative of a morphism in the homotopy category”, while not as snappy, more people will understand it. But if one uses “anafunctor” in order to have a snappy name, then one should embed this in its full context, and speaking of “anamorphisms” could be a way to do that.

Posted by: Urs Schreiber on January 11, 2010 7:32 AM | Permalink | Reply to this

Re: Generalized Multicategories

If someone talks about “a cocycle from $A$ to $B$” I’m likely to say “huh?”

But that somebody will say instead: “a cocycle on $A$ with coefficients in $B$”.

But that sounds even less like some kind of morphism from $A$ to $B$!

Yes, it’s certainly true that the kinds of “morphism” we’re thinking about are often the same as cocycles in some cohomology theory, and yes, certainly cohomology is usually a set of homotopy classes of morphisms in some $(\infty,1)$-category. But I think it is less confusing to use a different terminology when we’re thinking about them as morphisms, rather than as representatives of cohomology classes.

Consider anafunctors in particular. Part of the point is that they are what one should use instead of functors in the absence of the axiom of choice (and when founding category theory on set-theory). So, for instance, if a category has binary products but not specified binary products, then it has a product anafunctor $C\times C\to C$, instead of a product functor. Such an anafunctor is just as good as a functor for almost any purpose. But I think it would be harder to convince people of that if instead of “anafunctor $C\times C\to C$” we had to say “cocycle on $C\times C$ with coefficients in $C$”.

“Anafunctor” sounds like something related to a functor. So does “virtual functor.” But “cocycle” sounds like some combinatorial object and will make some people (like me) think “wait, what sort of cohomology of a category are we talking about here?” And, in fact, I think there are several notions of “cohomology of a category” in fairly common use, none of which is computed as a set of morphisms in Ho(Cat). So calling an anafunctor a cocycle is ambiguous and misleading as well as confusing.

I do like the idea of having a unified word for spans of this sort, when considered as generalized morphisms rather than as representatives of cohomology classes. “Anamorphism” would be good except that it’s been used for something else already. Perhaps “virtual morphism” is a good choice.

Posted by: Mike Shulman on January 11, 2010 3:37 PM | Permalink | PGP Sig | Reply to this

Re: Generalized Multicategories

Mike,

it seems you are trying to convince me not to try to convince people to say “cocycle” for “anafunctor”.

But I am not trying to do that! I can see how our conversation made you think I am proposing this, but it was really a bit of back and forth:

I said – and I still think so – that it would be good to make clear, terminologically or otherwise, that “anafunctor” is not a new concept but a special case of what is well-known and well-studied as, for instance, “morphisms out of replacements in a calculus of fractions”.

Then you remarked that this general phrase is not snappy. Then I remarked that the general phrase does happen to be known under a snappy name: “cocycle”. I also gave a reference demonstrating this usage.

The very special case of this given by Makkai’s anafunctors in $1Cat$ is a very degenerate or at least exotic case of the general situation, as with the usual practice about sets, we don’t see that there is anything cocyclic at all going on, and so it doesn*t look to us like what we usually think of as “cocycle” when we remove choice.

For typical internal anafunctors it’s already an entirely different issue. These do look like what is readily recognized as cocycles. As Cech cocycles, to be specific. The first chapter of David Roberts’ thesis exposes this nicely, as you know.

Still, I think that when talking even about plain anafunctors, it is good to make clear what they are really a special case of. And they are a special case of what in all other contexts (see the reference I gave) may be called cocycles.

So even though they may look different, I think it is worthwhile to point out, terminologically or otherwise, that anafunctors are a special case of what in other contexts is called a cocycle, or, less snappily, a morphism out of a resolution of its domain.

I started a entry on this: cocycle with discussion along these lines, as you will have seen.

Thanks for pointing out that “anamorphism” is already taken. That’s not an option then. Persinally I tend to stick with “morphisms out of a resolution”, non-snappy as it may be.

Posted by: Urs Schreiber on January 11, 2010 5:12 PM | Permalink | Reply to this

Re: Generalized Multicategories

And, in fact, I think there are several notions of “cohomology of a category” in fairly common use, none of which is computed as a set of morphisms in $Ho(Cat)$.

The common use of “cohomology of a groupoid” – and that of cohomology of a group – is precisesely a Hom-set in $Ho(\infty Grpd)$. (If it’s group cohomology with coefficients in a module, then its in the overcategory $Ho(\infty Grpd_{/\mathbf{B}G})$).

Which notion of cohomology of a category are you thinking of? Not by any chance one where the category is a homotopical category and it’s cohomology in that category?

Posted by: Urs Schreiber on January 11, 2010 5:18 PM | Permalink | Reply to this

Re: Generalized Multicategories

Okay, sorry I misunderstood. I did think you were proposing “cocycle” as a replacement word for “anafunctor.” I certainly agree that there is a general notion of cocycle which specializes to anafunctors when applied to the acyclic fibrations in Cat, and that pointing this out is a good thing to do. My remark down here was also informed by my misunderstanding; I intended that as a reason why having the word “anafunctor” be distinct from “cocycle” is important.

Which notion of cohomology of a category are you thinking of?

One can take the nerve of a category and consider the cohomology of that space. Or one can consider cohomology in the classifying topos of the category. The two are not unrelated, although I think they’re not always the same. Neither one is a homset in Ho(Cat).

Posted by: Mike Shulman on January 11, 2010 7:14 PM | Permalink | Reply to this

Re: Generalized Multicategories

One can take the nerve of a category and consider the cohomology of that space.

Isn’t that cohomology in $Ho_{Thomason}(Cat)$?

Posted by: Urs Schreiber on January 11, 2010 7:32 PM | Permalink | Reply to this

Re: Generalized Multicategories

Isn’t that cohomology in $Ho_{Thomason}(Cat)$?

Yes. Which is, of course, different from what I meant by Ho(Cat).

Posted by: Mike Shulman on January 11, 2010 8:02 PM | Permalink | Reply to this

Re: Generalized Multicategories

Since it looks like we agree on all technical points, and we seem to pretty much agree even on the terminological bits, I am not sure if this deserves to be expanded, but one comment I do have now:

A morphism in $Ho_{Thomason}(Cat)$ you point out some people are happy with thinking of as (a class of) a cocycle in the “cohomology on a category”.

A morphism in $Ho_{folk}(Cat)$ you point out many people will not be so happy with thinking of as (a class of) a cocycle.

I agree that this is the state of the sociological situation. But don’t you agree that taken at face value, it’s a somewhat odd state of affairs?

After all (not that you need to be reminded), $Ho_{Thomason}(Cat)$ is equivalent to $Ho_{Quillen}(sSet)$ and thus has intrinsically really nothing to do with cocycles on categories. What people, we think, are used to calling a cocycle on a category is really a cocycle on an $\infty$-groupoid that happens to be the groupoidification of some category. If one speaks of “cocycles on a category” at all, morphisms in $Ho_{folk}(Cat)$ would be a much more natural candidate.

(Well, except that if we are looking at cohomology in degree higher than 1, then we should be talking $Ho_{folk}(\infty Cat)$).

Posted by: Urs Schreiber on January 11, 2010 8:54 PM | Permalink | Reply to this

Re: Generalized Multicategories

Yes, I agree that it’s odd. I think the reason is that a lot of people think of “homotopy theory” as being only about $\infty$-groupoids (which they, of course, call “spaces” or “homotopy types”), and so when they talk about “the homotopy theory of categories,” or apply homotopical terminology like “cocycle” or “cohomology” to categories, they mean a Thomason-type model.

It is true, of course, that many naturally occurring $\infty$-groupoids can be presented as nerves of categories, and the cohomology of those $\infty$-groupoids may be conveniently represented and computed in terms of those presentations. So I imagine that people who are mainly interested in $\infty$-groupoids would regard it as annoyingly pedantic to be told they have to talk about “cohomology of the nerve of a category” rather than just “cohomology of a category.”

Posted by: Mike Shulman on January 11, 2010 10:19 PM | Permalink | Reply to this

Re: Generalized Multicategories

By the way, could you remind me concerning that statement about posets which I mention at Thomason model structure? You once said that somebody said there might be some problem with Thomason’s claim about posets being the cofibrants in his structure or something. I forget where that was.

Posted by: Urs Schreiber on January 11, 2010 10:31 PM | Permalink | Reply to this

Re: Generalized Multicategories

Remark 42 in the paper

On the subdivision of small categories
Matias L. del Hoyo
arXiv:0707.1718

may be what you are looking for, to quote in part:

“By the work of Thomason [15] we know that C at admits a closed model structure, weak equivalences being the ones we work with. By the corrections made by Cisinski [2] over the paper of Thomason, we know that every coﬁbrant category under this structure is a poset.”

See the paper for the reference.

Posted by: David Roberts on January 12, 2010 12:53 PM | Permalink | Reply to this

Re: Generalized Multicategories

By the corrections made by Cisinski [2] over the paper of Thomason, we know that every cofibrant category under this structure is a poset.

That’s it, thanks!!

Added it to the entry: Thomason model structure.

Posted by: Urs Schreiber on January 12, 2010 4:51 PM | Permalink | Reply to this

Re: Generalized Multicategories

Above Mike and I had some discussion about the usage, or not, of the word “cocycle” for an “anamorphism” or “derived morphism” or the like.

One more comment on that:

while

“cocycle” doesn’t sound […] like any sort of morphism

as Mike complained #, the implicit implication that this makes the term ill-suited for wide use finds counterexamples:

as we all know, in a fully abelian context, it is entriely custom and familiar to call these morphisms $Ext$s – short for extensions .

Which extension? Those classified by the corresponding cocycle!

Speaking of a weak morphism from $A$ to $B$ as an “extension of A” – hence characterizing it by its homotopy fiber!! – is an even more indirect description than calling it a cocycle on $A$. Still, people are entirely happy with this practice.

(That $Ext$s are traditionally computed as morphisms into a fibrant resolution instead of out of a cofibrant resolution as anafunctors are is just a question of choice of model of course, not one of principle.)

This just as a side remark on the general issue. I don’t want this to be understood as propaganda for changing people’s terminological habits in any way, just as a remark to put things in perspective.

As usual, we are left with a historically evolved terminological mess. If we could rewind history a bit, we would all just speak of “$(\infty,1)$-morphisms”. If we could rewind even further, we would all be speaking of just “morphism”s – but meaning the right thing by that word! :-)

Posted by: Urs Schreiber on January 22, 2010 4:52 PM | Permalink | Reply to this

Re: Generalized Multicategories

I don’t see a contradiction between (1) something being “ill-suited for wide use” and (2) the observation that it is, in fact, used widely. (-: Many things are, in fact, used in ways to which they are ill-suited.

Posted by: Mike Shulman on January 22, 2010 7:42 PM | Permalink | Reply to this

Re: Generalized Multicategories

I don’t see a contradiction […]

hey, i am not arguing any genuine point here, i am just making a side remark (which, even though not meant as an argument, seems to be relevant – if that makes sense)

anyway, probably if makkai had chosen the term nonabelian ext instead of anafunctor, he would be considerably more famous now – or, since he is working with no linearity aassumed anywhere, today we could call the very same concept a nonabelian ext over $F_1$. ;-)

Posted by: Urs Schreiber on January 22, 2010 8:06 PM | Permalink | Reply to this

Re: Generalized Multicategories

Urs wrote: we would all be speaking of just morphisms

***I thought that was one of the great gifts of cat theory. Name the cat and then you can talk about morphisms without decorating them with the name of the cat.

As for terminology, since it’s hard to correct historical accidents, let’s try to be thoughtful when developing new terms. It’s helpful for the name to signify something.

Posted by: jim stasheff on January 23, 2010 2:24 PM | Permalink | Reply to this

Re: Generalized Multicategories

we would all be speaking of just morphisms

I thought that was one of the great gifts of cat theory. Name the cat and then you can talk about morphisms without decorating them with the name of the cat.

Yes, and this gift can be accepted also from higher category theory. Then we don’t need to speak of “Exts” and “anafunctors” and “Hilsum-Skandalis morphisms” and “cocycles” and “exactors” and “butterflies” and “derived global sections” and whatnot – but can just say: morphisms for all of this. And more.

Posted by: Urs Schreiber on January 23, 2010 3:59 PM | Permalink | Reply to this

Re: Generalized Multicategories

Then we don’t need to speak of “Exts” and “anafunctors” and “Hilsum-Skandalis morphisms” and “cocycles” and “exactors” and “butterflies” and “derived global sections” and whatnot – but can just say: morphisms for all of this. And more.

Within a given (higher) category, yes of course you can do this. But how do you tell somebody what category you are using? Just as you need a name for the objects, you need a name for the morphisms. This is why analysis has terms like ‘continuous map’, ‘uniformly continuous map’, etc; and it is why category theory and higher category theory have terms like ‘functor’, ‘anafunctor’, etc.

Posted by: Toby Bartels on January 25, 2010 7:00 PM | Permalink | Reply to this

Re: Generalized Multicategories

Unfortunately, “cocycle” doesn’t sound to me like any sort of morphism.

It doesn’t sound like it. But it turns out that these morphisms typically encode what people call cocycles.

Here is an article that explicitly uses terminology this way: Cocycle Categories.

This could have been titled “Anafunctor Categories”, as far as the content is concerned.

Posted by: Urs Schreiber on January 11, 2010 8:46 AM | Permalink | Reply to this

Re: Generalized Multicategories

Cocycle Categories… could have been titled “Anafunctor Categories”

Cocycles may be identifiable with anafunctors, but the category of cocycles is not the same as the category of anafunctors. A morphism of cocycles (according to Jardine) is a diagram $\array{ && Z && \\ & \swarrow && \searrow \\ X && \downarrow && Y \\ & \nwarrow && \nearrow \\ && Z'}$ whereas a morphism of anafunctors is a natural transformation: $\array{ && Z && \\ & \swarrow & \uparrow & \searrow \\ X && Z\times_X Z' & \Downarrow & Y \\ & \nwarrow & \downarrow & \nearrow \\ && Z'}$

Posted by: Mike Shulman on January 11, 2010 3:45 PM | Permalink | PGP Sig | Reply to this

Re: Generalized Multicategories

Cocycles may be identifiable with anafunctors, but the category of cocycles is not the same as the category of anafunctors.

I am not sure if you mean this as a side remark or regard it as a serious issue.

As cocycles are representatives of something more intrinsically defined, the technical definition of morphisms between them is bound to be subject to some flexibility.

We know that the complete answer to what the cocycle category is is the Dwyer-Kan construction. The point of Jardine’s paper is that he shows that there is a useful simplified version of this in certain cases which gives a useful algorithm for computing the homotopy category, i.e. the cohomology.

So he is only interested in $\pi_0$ of is cocycle category. For instance

$\array{ && Z \\ & \swarrow &\downarrow& \searrow \\ X &\leftarrow& K& \rightarrow& Y \\ & \nwarrow &\uparrow& \nearrow \\ && Z' }$

is a morphism in the groupoidification of his category, which appears if we also wish to look at $\pi_1$ of it (for instance if we want to loop cohomology to one lower degree and look at auto-coboundaries of the trivial cocycle).

Take here $K$ a suitable cylinder object to reproduce Makkai’s transformations.

Posted by: Urs Schreiber on January 11, 2010 5:34 PM | Permalink | Reply to this

Re: Generalized Multicategories

John wrote:

At least it doesn’t look like an acronym for ‘f***ing-crazy multicategory’.

One of the first conference talks I gave was about fc-multicategories, in Cambridge. I was extremely nervous. During it, Andy Pitts was heard to remark to his neighbour: ‘Does fc stand for fucking complicated?’ Fortunately I didn’t hear.

John also wrote:

I also get them mixed up with $T$-multicategories

That’s kind of impossible, because they are $T$-multicategories, in the case when $T =$fc. Here fc is the free category monad on directed graphs.

So ‘fc-multicategory’ was never a name in itself — it’s just an instance of another name. In the same way, ‘2-adic number’ isn’t a name in itself, it’s just the instance of ‘$p$-adic number’ when $p = 2$.

But it’s an important enough instance that it deserves a snappy special name of its own. I could never think of one.

I’m less happy that Mike and Geoff are using the term ‘$T$-multicategory’ to mean something different from its meaning in my work. Mike says that this usage goes back to work of Claudio Hermida, which I didn’t know. I was in touch with Claudio from the time that I wrote my first paper on generalized multicategories, in 1997, but he never mentioned it. It’s potentially really confusing to have two closely related but different usages of ‘$T$-multicategory’ out there.

Mike and Geoff have now done this nice work of generalization, and it’s the perfect opportunity for them to find some new terminology that doesn’t contradict anyone else’s. I’d urge them to do so before it’s too late!

Posted by: Tom Leinster on January 9, 2010 4:14 AM | Permalink | Reply to this

Re: Generalized Multicategories

Claudio didn’t actually use the name “$T$-multicategory” for his notion; he called them “lax $Bimod(T)$-algebras”. (As you probably know, but others may not, to make things ever more confusing, Burroni called your $T$-multicategories just “$T$-categories” and called fc-multicategories just “multicategories”.) Likewise, Geoff and I don’t actually use the name “$T$-multicategory” for a normalized $T$-monoid; we always call them either “normalized $T$-monoids” or “virtual $T$-algebras.” So what I wrote up above was poorly phrased. “Virtual $T$-algebra” is supposed to be a new terminology that doesn’t contradict anyone else’s. Does that make you any happier?

Posted by: Mike Shulman on January 9, 2010 2:17 PM | Permalink | Reply to this

Re: Generalized Multicategories

Claudio didn’t actually use the name “$T$-multicategory” […] Likewise, Geoff and I don’t actually use the name “$T$-multicategory” for [something other than what Tom calls a $T$-multicategory]

Oh! Then I totally misunderstood what you wrote before. That also explains why Claudio never told me, and why I couldn’t find this definition in your paper.

So yes, that totally makes me happier.

(Regarding Burroni’s terminology, the story is this. I came up with the idea of generalized multicategory — in the sense of $T$-multicategory for a cartesian $T$ — independently, in 1997. As soon as I wrote it up and circulated it on the categories list, Claudio wrote to me saying that he’d been giving talks involving similar ideas. A while later he wrote again saying that he’d discovered that Burroni had done it decades earlier. That’s one reason why my terminology and Burroni’s aren’t aligned. Another is that ‘$T$-category’ doesn’t sit so well with ‘$V$-category’, and obviously Burroni’s usage of ‘multicategory’ clashes with Lambek’s earlier usage.)

Posted by: Tom Leinster on January 9, 2010 2:54 PM | Permalink | Reply to this

Re: Generalized Multicategories

So wait — let me make sure I’ve got this straight. When you said ‘$T$-multicategory’ in this part of your post:

Geoff and I proposed to call $T$-multicategories virtual $T$-algebras

…you weren’t using ‘$T$-multicategory’ in any sense defined by you and Geoff, or Claudio, or me?

Posted by: Tom Leinster on January 9, 2010 3:05 PM | Permalink | Reply to this

Re: Generalized Multicategories

you weren’t using ‘$T$-multicategory’ in any sense defined by you and Geoff, or Claudio, or me?

Yah, that’s pretty poorly written, isn’t it? I was using it to mean “generalized multicategory defined relative to $T$” in an informal sense. However, that’s clearly a confusing and bad idea; I’ll see if I can edit the post to clarify. The problem is that I didn’t want to get into the “normalization” issue in the post, since it’s confusing and a bit complicated, but clearly that led me to oversimplify. We had something of the same problem writing the introduction to the paper.

Another is that ‘$T$-category’ doesn’t sit so well with ‘$V$-category’, and obviously Burroni’s usage of ‘multicategory’ clashes with Lambek’s earlier usage.

Oh yes, I’m with you there—I think your terminology was much better than Burroni’s. And better than Hermida’s, too—I find “$T$-multicategory” more descriptive than “lax $Bimod(T)$-algebra.”

Posted by: Mike Shulman on January 9, 2010 9:06 PM | Permalink | PGP Sig | Reply to this

Re: Generalized Multicategories

Thanks for the clarification, Mike. I hope it was apparent that I was just trying to firm up my understanding; looking back at what I wrote, I see that it could be interpreted as criticism. It wasn’t intended that way.

Posted by: Tom Leinster on January 10, 2010 5:09 PM | Permalink | Reply to this

Re: Generalized Multicategories

a semiring lacks only negatives, while a semigroup lacks not only negatives but also the identity element

I'm pretty sure that the way ring theorists originally used the term, a ‘semiring’ is allowed to lack an identity element as well. (Remember, these are the same people who originally defined a ‘ring’ to be allowed to lack a multiplicative identity.) So one can draw a technical difference between a semiring and a rig, as we did (well, I did it) on the nLab article.

Posted by: Toby Bartels on January 9, 2010 12:49 PM | Permalink | Reply to this

Re: Generalized Multicategories

.

virtual X : X :: multicategory : monoidal category

For what it’s worth, it’s a flavor of oidification.

Maybe saying $X$-oid is too unspecific. And there would be resistance against monoid-oidal category. But with none of this discussion and not the paper known to me, if you had asked me to guess meanings for “virtual $X$” and for “$X$-oid” in the second case I would have come much closer to what you have in mind.

Posted by: Urs Schreiber on January 10, 2010 3:31 PM | Permalink | Reply to this

Re: Generalized Multicategories

If you have a chance to plausibly name something monoidoidal, you must take it. That would instantly become the worst term in the history of mathematics, worse even than algebraic group. You could make history, man. You cannot throw an opportunity like that away.

Posted by: Walt on January 10, 2010 7:08 PM | Permalink | Reply to this

Re: Generalized Multicategories

Actually, I’ll take that back. It’s a bit of a stretch to think of passing from categories to operadic concepts as a horizontal categorification alike to adding more objects. Even though it is a bit like adding morphism horizontally.

Maybe we should add to horizontal and vertical categorification also a thrid direction. Hm transversal categorification? :-)

Posted by: Urs Schreiber on January 10, 2010 8:08 PM | Permalink | Reply to this

Re: Generalized Multicategories

I actually don’t see why passing from monoidal categories to multicategories is like any sort of categorification.

Posted by: Mike Shulman on January 11, 2010 4:10 AM | Permalink | Reply to this

Re: Generalized Multicategories

I actually don’t see why passing from monoidal categories to multicategories is like any sort of categorification.

If we do accept the perspectve that besides “vertical categorification” there is also “horizontal categorfication”, then this means we take “categorification” to mean: extend to a less specific notion of categorical structure.

Starting with monoids, we first realize that this is the special case of a category with a single object. So we horizontally categorify to categories with arbitrary objects. Then we realize that this is just the special case of $\infty$-categories with no nontrivial higher cells. So we vertically categorify to arbitrary $\infty$-categories. Then we realize that this is just the special case of $\infty$-multicategories with no higher arity operations. So we finally categorify, in this sense, in yet another direction, to get also to these.

Or in different order, to get the step you are looking at here: start with monoids, first verically categorify to monoidal $\infty$-categories, then, in one step, “transversally” to $\infty$-operads and horizontally to $\infty$-multicategories.

Posted by: Urs Schreiber on January 11, 2010 7:46 AM | Permalink | Reply to this

Re: Generalized Multicategories

If we do accept the perspectve that besides “vertical categorification” there is also “horizontal categorfication”, then this means we take “categorification” to mean: extend to a less specific notion of categorical structure.

Well, that’s one thing it might mean, but I don’t think it means that. “Extending to a less specific notion of categorical structure” is an extremely broad umbrella. I think in order to deserve the term “categorification,” a process ought to involve introducing categories where they weren’t before (at least not evidently)—since that’s what the word “categorification” means. Vertical categorification involves replacing hom-sets by hom-categories. Horizontal categorification involves replacing one-object structures, which are usually defined and described without explicit reference to that one object and thus may not seem like any kind of category at all, by versions that can have multiple objects and are evidently categories of some sort. But passing from monoidal categories to multicategories does not introduce any new categories that weren’t there before.

Posted by: Mike Shulman on January 11, 2010 4:01 PM | Permalink | Reply to this

Re: Generalized Multicategories

Sorry, I first missed your reply here, among the other discussion we were having.

Concerning the forms of categorifications: my original comment was a bit thoughtless and what I said then doesn’t actually apply to your step from $X$s to virtual $X$s, but I do think there are three kinds of categorification in a sense that you seem you would subscribe to

1. horizontal – many objects

2. vertical – higher morphisms

3. transversal – higher arity

The third one goes from categories to multicategories. Its decategorification process picks the category of unary operations inside a multicategory.

Posted by: Urs Schreiber on January 12, 2010 8:16 PM | Permalink | Reply to this

Re: Generalized Multicategories

What I’m saying is that I don’t think the third deserves the name “categorification,” because it doesn’t introduce any new categories where there weren’t any categories before. Passing from unary operations to n-ary operations is an interesting and important thing to do, but it’s not “categorification.”

Posted by: Mike Shulman on January 12, 2010 10:25 PM | Permalink | Reply to this

Re: Generalized Multicategories

What I’m saying is that I don’t think the third deserves the name “categorification,” because it doesn’t introduce any new categories where there weren’t any categories before.

Start with the singleton set. Transversally categorify and get the multicategory $Assoc$:

because transversally decategorifying this gives the category of unary operations of $Assoc$ which is the terminal category which is the terminal 0-category which is the singleton set.

Posted by: Urs Schreiber on January 12, 2010 11:13 PM | Permalink | Reply to this

Re: Generalized Multicategories

Urs, can you fill in this table?

• The concept of categories is a (vertical) categorification of the concept of sets.
• The concept of categories is a groupoidal categorification of the concept of posets.
• The concept of categories is a laxification of the concept of groupoids.
• The concept of categories is an oidification (or horizontal categorification) of the concept of monoids.
• The concept of categories is a virtualisation (or transversal categorification) of the concept of …?

If I understand correctly, Mike wants something there, but he doesn't know what to put there (and neither do I).

Posted by: Toby Bartels on January 13, 2010 12:03 AM | Permalink | Reply to this

Re: Generalized Multicategories

Toby’s question is a good one. Regarding your particular example, I would say that $Assoc$ is not obtained by “multi-fication” from the singleton set. Rather, it is obtained by starting with the singleton monoid, horizontally categorifying to regard this as a one-object category, and then “multi-fying” that to obtain a one-object multicategory. The “multi-fication” didn’t add any new categories where there weren’t before; that was done by the first step of horizontal categorification. In order to “multi-fy,” you already have to have a category.

Posted by: Mike Shulman on January 13, 2010 1:13 AM | Permalink | Reply to this

Re: Generalized Multicategories

In order to “multi-fy,” you already have to have a category.

But in order to oid-ify, you also already have to have a category:

you go from one-object categories to many-object categories.

or, depending on your viewpoint, you start with a monoid = monoidal 0-category, first deloop to get a one-object category, and only then pass to many object 1-caegories.

Categorification and decategorification is something taking place inside category theory. Not between category theory and something else. That’s where the concept of a 0-category, of a $(-1)$-category etc comes from.

Posted by: Urs Schreiber on January 13, 2010 5:33 AM | Permalink | Reply to this

Re: Generalized Multicategories

But in order to oid-ify, you also already have to have a category

But you didn’t know that you had a category. You were thinking of it as a monoid. Likewise, when you vertically categorify, you had a set that was “actually” a discrete category, but you didn’t know that—you were thinking of it as a set. That’s why I added the qualifier “(at least not evidently)” in my first comment.

But the category underlying a multicategory is already present and visible to everyone.

if you don’t allow yourself to say that the general notion of ∞-category is ∞-multicategory, you can’t say “monoidal ∞-category”, strictly speaking.

I don’t see what that has to do with whether passing from $\infty$-categories to $\infty$-multicategories should be called “categorification.” I don’t think that passing from $\infty$-categories to monoidal $\infty$-categories should be called “categorification” either.

Posted by: Mike Shulman on January 13, 2010 3:38 PM | Permalink | Reply to this

Re: Generalized Multicategories

Toby asks me to fill in the sentence: The concept of categories is a virtualization (or transversal categorification) of the concept of …?

Well: the concept of multicategories is a “transversal” categorification of that of categories.

In the same way that I don’t want to distinguish between higher category theory and category theory, I don’t want to distinguish between multicategory theory and higher multicategory theory and category theory. This is all “category theory”.

The general concept (not even the most general one) is that of an $\infty$-multicategory.

For instance, take the definition of monoidal $(\infty,1)$-category by a certain prominent category theorist. This is defined to be a certain $\infty$-multicategory. In this perspective, if you don’t allow yourself to say that the general notion of $\infty$-category is $\infty$-multicategory, you can’t say “monoidal $\infty$-category”, strictly speaking.

Posted by: Urs Schreiber on January 13, 2010 5:44 AM | Permalink | Reply to this

Re: Generalized Multicategories

Yeah, I just realised that; replace ‘virtualisation’ with ‘multification’ in my challenge above.

Would you use ‘categorification’ for every movement within the framework of higher categories? That seems uselessly general to me. (Of course, I'm someone who was never much pleased about ‘horizontal categorification’ either.)

Posted by: Toby Bartels on January 13, 2010 1:05 PM | Permalink | Reply to this

Re: Generalized Multicategories

Would you use “categorification” for every movement within the framework of higher categories?

Hm, no, I don’t think so.

I’d think de/categorification is about admitting or not more equivalence classes of the objects in question.

So for instance horizontal categorificartion is about allowing nontivial $\pi_0$ of $\infty$-categories (not groupoidal $\pi_0$, but categorical $\pi_0$). Similarly vertical categorificatoin is about $\pi_n$s for higher $n$.

When we generalize from $\infty$-categories to $\infty$-multicategories, there appears one more kind of such invariants, related to arity.

And just like we have horizontal decategorification maps that make $\pi_i$s disappear, and for which we may look for right inverses (horizontal and vertical categorification), so now there is the map that sends a multicategory to its underlying category of unary operations and thus makes these new types of invariants related to arity disappear.

Posted by: Urs Schreiber on January 13, 2010 4:54 PM | Permalink | Reply to this

Re: Generalized Multicategories

I’d think de/categorification is about admitting or not more equivalence classes of the objects in question.

I can see that. But I still don’t think that “multification” falls under that heading. Adding n-ary morphisms doesn’t admit new equivalence classes of a type of object you had already; rather it introduces a new type of object.

Posted by: Mike Shulman on January 16, 2010 5:27 PM | Permalink | Reply to this

Re: Generalized Multicategories

I can see that. But I still don’t think that “multification” falls under that heading.

If you regard multicategory theory as outside of category theory then it won’t. But to me this looks as unnatural as regarding higher category theory as outside of category theory.

The general notion is that of an $\infty$-multicategory. Or something even a bit more general than that. That’s the topic of category theory. Processes of categorification should therefore describe paths that explore general objects in this theory from very restricted objects.

But of course we might say “multi-categorification” for emphasis that this particular path is meant. Just as one says vertical categorification or higher categorification for emphasizing that this is meant as opposed to horizontal categorification that some people do mean when they say just categorification . These people regard higher categorification as being in another theory.

Here we wouldn’t agree with such usage. Then similarly we should admit that there is even more to category theory than higher categories. And that hence categorification should reach that, too.

Posted by: Urs Schreiber on January 16, 2010 9:35 PM | Permalink | Reply to this

Re: Generalized Multicategories

If you regard multicategory theory as outside of category theory then it won’t.

What made you think that I regard multicategory theory as outside of category theory? I’m just saying that not all kinds of categorical structures are “categorification.”

The general notion is that of an ∞-multicategory.

I would be very wary of saying that there is any “the” general notion. Category theory, and higher category theory, are about lots of things. I don’t think there is any one notion of which everything else is a special case. Consider double categories, or n-fold categories. Or Z-categories. Or equipments or virtual double categories, for that matter. Or “$Gray_{lax}$-categories.” All of those are interesting and important, but none of them is a special case of $\infty$-multicategories, nor is there (as far as I can see) any general notion of which they are all a special case (except maybe “object of some $\infty$-category”, but everything in mathematics is a special case of that).

Given that there is no “most general notion,” it doesn’t make sense to use “categorification” to mean “any generalization within category theory.” To be a meaningful and useful word, it should have a more specific meaning.

But perhaps everyone else here is getting bored with this argument and we should wrap it up.

Posted by: Mike Shulman on January 17, 2010 5:02 AM | Permalink | Reply to this

Re: Generalized Multicategories

It might be worth pointing out the relationship between multicategories and another generalization of monoidal categories called promonoidal categories. This confused me for a while.

A promonoidal category is a pseudomonoid in the bicategory of profunctors. My preferred definition is that a profunctor $C ⇸ D$ is a functor $D^{op}\times C\to Set$, or equivalently a functor $C \to \mathcal{P}D$, where $\mathcal{P}D$ is the presheaf category of $D$, and hence also the same as a cocontinuous functor $\mathcal{P}C \to \mathcal{P}D$. It follows that with this definition, a (small) promonoidal category is the same as a small category $C$ together with a monoidal structure on $\mathcal{P}C$ which is cocontinuous in each variable, or equivalently (by the adjoint functor theorem) a closed monoidal structure on $\mathcal{P}C$. This equivalence is a generalized version of Day convolution.

On the other hand, if we consider not pseudomonoids but pseudo-comonoids in $Prof$ (or, equivalently, we define profunctors to go the other way, as some people do), then what we get is a subclass of multicategories. Specifically, in this case the (co)monoidal product is a functor $C\times C \to [C,Set]^{op}$; that is, to every pair of objects $x$ and $y$ we associate a functor $x\otimes y\colon C\to Set$. More generally, we have an $n$-fold product functor $C^n \to [C,Set]^{op}$, which we can use to make $C$ into a multicategory with multiarrows defined by $C(x_1,x_2,\dots,x_n ; y) = (x_1\otimes \dots\otimes x_n)(y).$ (Of course, promonoidal categories in the first sense similarly give rise to “co-multicategories,” in which arrows can have finite lists of objects as their target, rather than their source.)

We don’t get all multicategories arising in this way, but we do get all of them if we consider normal lax comonoids instead of just pseudo ones. Actually, there’s a pullback square: $\array{monoidal categories & \overset{}{\to} & weakly representable multicategories\\ \downarrow && \downarrow\\ pseudo-comonoids in Prof & \underset{}{\to} & multicategories}$ where a multicategory is “weakly representable” if for every finite list $(x_1,\dots,x_n)$ of objects, the functor $C(x_1,\dots, x_n ; -) \colon C\to Set$ is representable. These can also be identified with “normal colax monoidal categories.” Thus, if we could think of a less cumbersome version of the prefix “normal lax co-pro-“, Geoff and I could potentially use that instead of “virtual.”

Posted by: Mike Shulman on January 9, 2010 10:29 PM | Permalink | PGP Sig | Reply to this

Re: Generalized Multicategories

Since generalized multicategories relative to a monad $T$ are like $T$-algebras but without representation, perhaps they should be called T-parties.

Posted by: Mike Shulman on January 11, 2010 5:39 AM | Permalink | Reply to this

Re: Generalized Multicategories

If only we could get away with that ;)

Posted by: Geoff Cruttwell on January 11, 2010 7:01 PM | Permalink | Reply to this

Post a New Comment