Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Categorifying algebraic structures

Asad Saeeduddin (Apr 19 2020 at 12:52):

Can someone teach me a systematic recipe for starting from an arbitrary algebraic structure and categorifying it so that a single object category with the categorified equipment recovers the original algebraic structure, and a newly specified family of functor with some additional equipment corresponds to homomorphisms of the original algebraic structure?

Nathanael Arkor (Apr 19 2020 at 12:58):

I don't believe a systematic procedure for horizontal categorification has been worked out. However, many kinds of horizontal categorification correspond to some kind of enrichment in a vertical categorification of the corresponding structure.

Asad Saeeduddin (Apr 19 2020 at 12:59):

Do you think such a procedure can exist, or are there theoretical problems with that?

Nathanael Arkor (Apr 19 2020 at 12:59):

That is, if you're horizontally categorifying a structure $\Sigma$, then $\mathrm{Hom}(A, A)$ should have $\Sigma$-structure, which is what you would expect in a $\Sigma$-enriched category.

Nathanael Arkor (Apr 19 2020 at 13:00):

I think it is possible; I just don't think it's been done. If you want to consider things like multicategories as the horizontal categorification of operads, simple enrichment isn't quite enough, for instance.

Nathanael Arkor (Apr 19 2020 at 13:01):

My conclusion when thinking about this was that it was not going to be possible to get unique/best notions of horizontal categorification for all structures: there might be multiple suitable candidate structures.

Nathanael Arkor (Apr 19 2020 at 13:02):

But perhaps the reason this hasn't been rigorously explored is that no-one has a use for such constructions at the moment. Do you have any ideas, or are you simply curious?

Asad Saeeduddin (Apr 19 2020 at 13:02):

Is there some special case of "simple" algebraic structures for which a recipe does exist? The kinds of things I'm interested in are fairly simple, like monoids, rings, vector spaces. I've read about the relevant categorical analogs piecemeal, but i really want to find a common thread that shows the pattern by which the categorical equipment was derived

Reid Barton (Apr 19 2020 at 13:05):

What's the horizontal categorification of a ring supposed to be? A category enriched in abelian groups?

Nathanael Arkor (Apr 19 2020 at 13:05):

I'm not aware of one, though my gut feeling is that you could use the results of Gould's Coherence for Categorified Operadic Theories (https://arxiv.org/abs/1002.0879) to perform vertical categorification for certain algebraic structures (that have at least monoidal structure), and enrich in these categories. I think this would coincide with horizontal categorification for the structures you mention.

Nathanael Arkor (Apr 19 2020 at 13:05):

Reid Barton said:

What's the horizontal categorification of a ring supposed to be? A category enriched in abelian groups?

Yes.

Asad Saeeduddin (Apr 19 2020 at 13:06):

@Nathanael Arkor Sorry, I'm not super familiar with vertical categorification either. Is that the one where you "partialize" the operations?

Reid Barton (Apr 19 2020 at 13:07):

If you can express your original structure as monoid objects in a monoidal category C, then you can take categories enriched in C for the horizontal categorification.

Reid Barton (Apr 19 2020 at 13:07):

I'm not sure what you expect to get for vector spaces though.

Nathanael Arkor (Apr 19 2020 at 13:07):

Asad Saeeduddin said:

Nathanael Arkor Sorry, I'm not super familiar with vertical categorification either. Is that the one where you "partialize" the operations?

Going from monoids to monoidal categories, for instance.

Asad Saeeduddin (Apr 19 2020 at 13:08):

@Reid Barton That's the main problem, you need to do some creative work to figure out the right structure. E.g. I have no idea by what process the data for rig categories or duoidal categories was derived, in which I believe objects that are compatibly bimonoids and monoids correspond to near-rings

Reid Barton (Apr 19 2020 at 13:08):

Yes, of course.

Asad Saeeduddin (Apr 19 2020 at 13:09):

Is there no way to not be creative when deriving the relevant equipment for the category?

Asad Saeeduddin (Apr 19 2020 at 13:10):

@Nathanael Arkor

Going from monoids to monoidal categories, for instance.

Is there a version of vertical categorification where the word "monoid" doesn't occur in this definition?

Nathanael Arkor (Apr 19 2020 at 13:10):

Asad Saeeduddin said:

Reid Barton That's the main problem, you need to do some creative work to figure out the right structure. E.g. I have no idea by what process the data for rig categories or duoidal categories was derived, in which I believe objects that are compatibly bimonoids and monoids correspond to near-rings

I believe these are examples of vertical categorification, not horizontal categorificaitons.

Nathanael Arkor (Apr 19 2020 at 13:11):

Asad Saeeduddin said:

Nathanael Arkor

Going from monoids to monoidal categories, for instance.

Is there a version of vertical categorification where the word "monoid" doesn't occur in this definition?

Rigs to rig categories is another example.

Asad Saeeduddin (Apr 19 2020 at 13:11):

@Nathanael Arkor I see. What I mean is the first step @Reid Barton mentioned:

If you can express your original structure as monoid objects in a monoidal category C

Is what I don't know how to do in most cases

Nathanael Arkor (Apr 19 2020 at 13:13):

If your algebraic structure isn't "monoid + extra stuff", it can be hard to see how to horizontally categorify it. If you want to vertically categorify it instead, the process is conceptually simpler, but you need to figure out the suitable coherence conditions.

Asad Saeeduddin (Apr 19 2020 at 13:13):

e.g. what is the series of steps that were followed to start from the definition of a rig and end up with the definition of a rig category? the distributivity and annihilation isomorphisms for a rig category definitely look similar to the rig laws, but what (if anything) is the systematic machine that you can run on the definition of a rig as an algebraic structure to get those isomorphisms?

Asad Saeeduddin (Apr 19 2020 at 13:15):

@Nathanael Arkor Right. How do you figure out what the suitable coherence conditions are? Like, what objective should we work towards when trying to come up with coherence conditions?

Nathanael Arkor (Apr 19 2020 at 13:15):

There's a general conceptual procedure, but it's not entirely precise except for very specific examples like those in Coherence for Categorified Operadic Theories. You replace operators with functors, equations with either natural isomorphisms or natural transformations, and you figure out the appropriate coherence rules to make sure that the natural transformations form a convergent rewriting system.

Nathanael Arkor (Apr 19 2020 at 13:16):

Asad Saeeduddin said:

Nathanael Arkor Right. How do you figure out what the suitable coherence conditions are? Like, what objective should we work towards when trying to come up with coherence conditions?

Beke's Categorification, term rewriting and the Knuth–Bendix procedure is a nice introduction to this topic.

Asad Saeeduddin (Apr 19 2020 at 13:17):

Thanks, I'll take a look at that

Reid Barton (Apr 19 2020 at 13:26):

Heuristically, though, you are trying to invert an operation (horizontal or vertical decategorification) that loses information, so you should expect some additional input to be required in general.

Reid Barton (Apr 19 2020 at 13:29):

In practice you would already have something that is supposed to be an example of the new concept, and that can also guide you.

Asad Saeeduddin (Apr 19 2020 at 13:41):

hmmm. so you're saying the categorified concept necessarily has more information than the original algebraic structure? i.e. merely requiring a one object category to be equivalent to the original algebraic structure doesn't uniquely determine the relevant functors and isomorphisms

Nathanael Arkor (Apr 19 2020 at 13:50):

Yes, because you're essentially reducing a multisorted structure to a single-sorted structure, and trying to ask how we might reconstruct the multisorted one.

Joe Moeller (Apr 19 2020 at 16:38):

I think the easier way to describe vertical categorification is "replace sets with categories".

Joe Moeller (Apr 19 2020 at 16:39):

What you're calling "horizontal categorification", I've also seen called "oidification", eg group |-> groupoid.

Joe Moeller (Apr 19 2020 at 16:41):

I think the horizontal categorification is actually where you "partialize" an operation, specifically the monoid one that turns into composition.

Joe Moeller (Apr 19 2020 at 16:48):

For coherence conditions in vertical categorification, what happens is that you turn your sets into categories, functions into functors, and equations into natural isomorphisms, then you can ask what you want the components of these natural transformations to satisfy. Of course, this doesn't really solve the problem :sweat:

Pastel Raschke (Apr 19 2020 at 17:26):

nlab: vertical categorification can often be decomposed into

• homotopification (allowing objects to come with automorphisms), replacing sets with ∞-groupoids in the limit
• laxification (relaxing invertibility of previously-invertible morphisms)

only uses horizontal categorification as meaning oidification. what do you mean by partialization?

Todd Schmid (he/they) (Apr 19 2020 at 17:40):

If what you care about are algebras in the sense of universal algebra, then packaging the signature data into a polynomial endofunctor on a category with the relevant structure is a nicely behaved "categorification" method, isn't it? This is precisely what's going on with group/ring/monoid-objects in a category.

Nathanael Arkor (Apr 19 2020 at 17:50):

@Todd Schmid: this gives you notions like "monoid in a cartesian category", rather than "monoids in a monoidal category" or "monoidal categories" (the latter being what one would expect from vertical categorification).

Nathanael Arkor (Apr 19 2020 at 17:51):

The problem with approaches that attempt to ignore issues of coherence is that you usually end up with overly strict notions (e.g. strict monoidal categories).

Joe Moeller (Apr 19 2020 at 19:18):

Pastel Raschke said:

nlab: vertical categorification can often be decomposed into

• homotopification (allowing objects to come with automorphisms), replacing sets with ∞-groupoids in the limit
• laxification (relaxing invertibility of previously-invertible morphisms)

only uses horizontal categorification as meaning oidification. what do you mean by partialization?

I was replying to someone else using that word, but basically monoids have a totally defined operation, whereas categories have a partially defined operation: composition.

Todd Schmid (he/they) (Apr 19 2020 at 19:46):

@Nathanael Arkor True, true. I suppose motivation is important here.

John Baez (Apr 19 2020 at 19:55):

Asad Saeeduddin said:

Is there no way to not be creative when deriving the relevant equipment for the category?

I'll just mention that this is the key conceptual problem in the subject of categorification: trying to figure out the patterns involved so one doesn't need to be creative anymore. There are many different kinds of structures to categorify, and many different ways to categorify them, so this key conceptual problem needs to be made specific, and then it becomes lots of different problems, and there's a whole lot to say about these problems. There are lots of papers on this stuff!

Morgan Rogers (he/him) (Apr 22 2020 at 10:41):

I find discussions like this about categorification somewhat reductive. It's like asking what the equivalent of a line in the plane would be in a 3D space. Both a line (dimension 1 subspace) and a plane (codimension 1 subspace) are completely valid answers, and we aren't surprised that there is more than one possible answer: throughout maths, we should expect that when we move to "higher dimensions" there will be multiple ways to lift concepts. For there to be a "right" categorification of a concept, you have to know in advance what you want the categorified thing to describe, either by having a putative example that you want to formalise, or at least by having strong preferences about how you want the thing to behave. You can't have clear answers without clear questions.

Nathanael Arkor (Apr 22 2020 at 10:58):

In the case of "categorifying algebraic structures", which is the subject of this topic, there often is a canonical categorification, though.

Nathanael Arkor (Apr 22 2020 at 10:59):

So it's entirely reasonable to ask if there is a procedure to categorify such structures, because both the question and the answer can be made precise.

Morgan Rogers (he/him) (Apr 22 2020 at 11:01):

Nathanael Arkor said:

In the case of "categorifying algebraic structures", which is the subject of this topic, there often is a canonical categorification, though.

Oh? For example?

Nathanael Arkor (Apr 22 2020 at 11:04):

Nathanael Arkor said:

I'm not aware of one, though my gut feeling is that you could use the results of Gould's Coherence for Categorified Operadic Theories (https://arxiv.org/abs/1002.0879) to perform vertical categorification for certain algebraic structures (that have at least monoidal structure), and enrich in these categories. I think this would coincide with horizontal categorification for the structures you mention.

Gould's results are the strongest I know of on this subject.

Nathanael Arkor (Apr 22 2020 at 11:05):

You can categorify any algebraic theory with linear equations canonically.

Nathanael Arkor (Apr 22 2020 at 11:06):

This gives you monoidal categories, but not rig categories, for instance.

Morgan Rogers (he/him) (Apr 22 2020 at 11:08):

But what's canonical about this choice? Monoidal categories are not the "canonical" categorification of monoids, they're a particular case chosen to have particular desirable properties. Just being the most well-studied or popular does not make something canonical.

Nathanael Arkor (Apr 22 2020 at 11:11):

Can you give a different categorification of monoids that satisfies: a monoid considered as a discrete category is an example, and every equation that holds for monoids holds up to isomorphism in the categorification?

Morgan Rogers (he/him) (Apr 22 2020 at 11:13):

If your specification contains a "that satisfies..." then you're in the "having strong preferences about how you want the thing to behave" camp, aren't you?

Nathanael Arkor (Apr 22 2020 at 11:14):

…if you don't have specifications, then calling something a categorification is entirely meaningless.

Nathanael Arkor (Apr 22 2020 at 11:14):

These requirements are not very strong.

Nathanael Arkor (Apr 22 2020 at 11:15):

Feel free to suggest a different notion of categorification of algebraic structure and a justification for calling it a "categorification".

Morgan Rogers (he/him) (Apr 22 2020 at 11:28):

A monoid is a category with one object; so another direction to categorify is to consider any of the kinds of 2-category with one object.
I can consider categories naively enriched over monoids.
I could weaken your demands that things hold up to isomorphism to the existence of a natural transformation; there is no a priori reason, without your explicit requirement, to assume otherwise.

Nathanael Arkor (Apr 22 2020 at 11:31):

A monoid is a category with one object; so another direction to categorify is to consider any of the kinds of 2-category with one object.

Right, this is horizontal categorification, which was discussed earlier. This is separate to the notion of vertical categorification. One obviously can't ask something to be a canonical categorification if one person means vertical and the other means horizontal.

Nathanael Arkor (Apr 22 2020 at 11:32):

I could weaken your demands that things hold up to isomorphism to the existence of a natural transformation; there is no a priori reason, without your explicit requirement, to assume otherwise.

Yes there is: the right notion of "equality" in a category is an isomorphism. Considering lax coherences gives you something that is more similar to relational structure than algebraic.

Morgan Rogers (he/him) (Apr 22 2020 at 11:41):

Nathanael Arkor said:

A monoid is a category with one object; so another direction to categorify is to consider any of the kinds of 2-category with one object.

Right, this is horizontal categorification, which was discussed earlier. This is separate to the notion of vertical categorification. One obviously can't ask something to be a canonical categorification if one person means vertical and the other means horizontal.

But even these aren't well-defined processes. If I take an algebraic theory with more than one type, there are more options for horizontal categorification, for example.

Nathanael Arkor (Apr 22 2020 at 11:43):

I'm talking about the process of vertical categorification. I already said earlier in this thread that horizontal categorification is less well-defined.

Morgan Rogers (he/him) (Apr 22 2020 at 11:44):

But so is vertical categorification!

What precisely that means may depend on circumstances and authors, to some extent. The following lists some common procedures that are known as categorification. They are in general different but may in cases lead to the same categorified notions, as discussed in the examples.

Nathanael Arkor (Apr 22 2020 at 11:46):

Yes, in the general setting of "what is the vertical categorification of an arbitrary mathematical concept X". I'm saying that for the special case X = linear algebraic theories, the concept of vertical categorification is not only well-defined, it's also solved.

Morgan Rogers (he/him) (Apr 22 2020 at 11:49):

I really don't think there's any need for us to be arguing here: you have a clear picture of what you want categorification to do for algebraic theories, and the answer is the one contained in Gould's paper. My original comment was targeted at the tangential discussion about the general process of categorification and the need for creativity in it, my argument being that clarity about what you want is needed for there to be any clear choice of categorification of a concept (and therefore that creativity can take a back seat once you've attained that clarity).

John Baez (Apr 22 2020 at 16:47):

Morgan Rogers said:

But what's canonical about this choice? Monoidal categories are not the "canonical" categorification of monoids.

I think they are. Take a monoid in Cat, say $M$. This is a strict monoidal category. Then take an equivalence $F \colon M \to M'$, and ask what structure $M'$ gets. It's not a strict monoidal category, usually. But it's a monoidal category.

So, "monoidal category" is precisely the generalization of "monoid" that's invariant under equivalence. This is what makes it canonical and this is also why it's important.

More generally, given a monoid object $M$ in some monoidal bicategory, and an equivalence $F \colon M \to M'$, you can ask what structure $M'$ gets. The answer is that it becomes a pseudomonoid.

Just being the most well-studied or popular does not make something canonical.

Right, but invariance under equivalence can.

Morgan Rogers (he/him) (Apr 23 2020 at 10:25):

John Baez said:

So, "monoidal category" is precisely the generalization of "monoid" that's invariant under equivalence. This is what makes it canonical and this is also why it's important.

This gives me the opportunity to refine what I originally said. To have a "canonical" categorification, the following ingredients are sufficient:
1) A categorical setting, which determines the "direction" of categorification and how far along in that direction one is going. In this example, we're in a 2-category of categories.
1) An example of the thing to be categorified in a more restricted setting, in this case the subcategory of categories with one object.
1) A choice of the type of equivalence (or weaker transformation!) under which the categorified notions will be invariant.

For the third point, equivalence is a nice choice, and we have agreed as a community that we prefer it to isomorphism in this setting, but (even if there are lots of justifications for this) it doesn't make it an inherently canonical choice. There are other, weaker notions of equivalence too, such as the homotopy equivalence that you and I have been discussing elsewhere, the equivalence-up-to-idempotent-completion that arises from constructing presheaves on a small category, and so forth. Maybe the reason someone else wants to categorify monoids is because they have an example of an object which looks like a monoid but where the hold only up to not-necessarily-invertible morphisms; their generalisation to a larger categorical setting still deserves to be called categorification, even if it's a (co/op)lax version, because it contains monoids as a motivating special case.

Anyway, the reason any of this is important is that when doing any mathematics it's vital to acknowledge and keep track of the choices that we're making, and not to take them for granted. When going from 1 to 2 dimensions there aren't a huge number of choices that make sense, especially if we have also made a choice about the notion of equivalence in the original setting; if we want to categorify "monoids up to isomorphism" then it's hard to come up with anything other than isomorphism or equivalence (constructively, weak equivalences provide a third option). But these are still choices, which multiply if one is inclined to go higher.

Reid Barton (Apr 23 2020 at 11:33):

Can someone explain how I know whether the "canonical vertical categorification" of a commutative monoid is a symmetric monoidal category or a braided monoidal category?

Eric M Downes (May 06 2020 at 20:34):

I am trying to categorify a certain algebra. It appears necessary to have an additive identity for each object, such that
$x + y = z \Rightarrow x + 0_y = z - y \Rightarrow x + 20_y = z - y + 0_y$
This teeters on the edge of madness, but when it is time to finish a calculation many (but not all) of these disappear under an equivalence class, and you are left with what appears to be a useful lower bound on error propagation in calculations performed with the resulting formula.

I feel like this must have been done before. If not in abstract algebra, then the design of floating point arithmetic, etc. Unfortunately I failed my Literature Search roll twice now, and can't attempt again until I've had a long rest. Any pointers on where I should look to educate myself would be very much appreciated! Thanks!