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: community: general

Topic: commutative semigroups

John Baez (Apr 04 2020 at 19:32):

I know category theorists prefer commutative monoids, and I do too, but people who study them intensively seem to prefer commutative semigroups, so that's what I talked about today on Twitter:

• Commutative semigroups.

I outlined what could be called the "fundamental structure theorem of commutative semigroups".

You can always stick a unit in a commutative semigroup without damaging it too much: if it already had a unit it'll be dethroned by the new one, but the commutative monoid you had will sit inside the new one. So maybe let's think about commutative monoids.

Various questions that I'll pose as puzzles, regardless of whether I know the answers or not:

Puzzle 1. You can take the nerve of a category, so you can take the nerve of a commutative monoid $C$. What sort of space $NC$ do you get? (Here I'm calling a simplicial set a "space": if you don't like that, do geometric realization and get a topological space.)

Puzzle 2. Any commutative monoid $C$ maps to a semilattice $C'$ formed by imposing the relations $x + x = x$ for all $x \in C$. What sort of space do you get by taking the nerve of a semilattice? What can you say about the map $NC \to NC'$?

Puzzle 3. The fundamental theorem says the fibers of the map $C \to C'$ are 'archimedean monoids' (defined in my tweet more generally for semigroups). What sort of space do you get by taking the nerve of an archimedean monoid?

Puzzle 4. What topological picture of $NC$ do you get from the fundamental theorem?

I stand up for all downtrodden, oppressed mathematical objects. Consider the humble "commutative semigroup". This is a set with a binary operation + obeying a+b = b+a (a+b)+c = a+(b+c) Too simple for any interesting theorems? No! (1/n) https://twitter.com/johncarlosbaez/status/1246470112321953792/photo/1

- John Carlos Baez (@johncarlosbaez)

Sam Tenka (Apr 04 2020 at 23:57):

Ooh! I wonder how this compares to Krohn Rhodes Decomposition? (Noncommutative structure theorem I've long tried to grok without yet success)

John Baez (Apr 05 2020 at 00:02):

Thanks for reminding me of Krohn-Rhodes theory. I ran into it in a strange book by Rhodes, sometimes called The Wild Book:

This book was originally written in 1969 by Berkeley mathematician John Rhodes. It is the founding work in what is now called algebraic engineering, an emerging field created by using the unifying scheme of finite state machine models and their complexity to tie together many fields: finite group theory, semigroup theory, automata and sequential machine theory, finite phase space physics, metabolic and evolutionary biology, epistemology, mathematical theory of psychoanalysis, philosophy, and game theory. The author thus introduced a completely original algebraic approach to complexity and the understanding of finite systems. The unpublished manuscript, often referred to as "The Wild Book," became an underground classic, continually requested in manuscript form, and read by many leading researchers in mathematics, complex systems, artificial intelligence, and systems biology. Yet it has never been available in print until now.

But I don't really understand the Krohn-Rhodes decomposition, though I understand most of the words by now.

Sam Tenka (Apr 05 2020 at 00:05):

It's a very entertainingly written book! For example, the first few pages motivate the structure problem for semigroups as philosophical quest to understand time. When I tried to read it in undergrad, I got lost. Maybe I'm more mature now.

vikraman (Apr 05 2020 at 00:10):

For this, am I supposed to think of a commutative monoid as a one object monoidal category? Making it a semilattice seems to make it compact closed? I don't know much about nerves besides the definitions, what are some ways those are usually described?

Sam Tenka (Apr 05 2020 at 00:13):

I'm in similar boat as you, @vikraman. I'm not sure how nerves are usually described. Here, though, I think that the nerves we get are especially nice as (geometrically realized) spaces. [For example, commutativity of the semigroup means that every square fills: ab = ba, meaning that the fundamental group is a bit simpler than otherwise (not trivial, like I said before)

(Unlike in normal math, each of my statements is false with some probability, so the overall correctness decays with length of comment. I might be totally wrong)

John Baez (Apr 05 2020 at 00:18):

It decayed: the nerve of the abelian group A is a space whose fundamental group is A.

Sam Tenka (Apr 05 2020 at 00:19):

Ah! Thanks! Yeah we don't have the 2 cell relations for general a and b, just for ab=ba and likewise.

John Baez (Apr 05 2020 at 00:21):

The nerve of any group G, thought of as a category, is called the Eilenberg-Mac Lane space K(G,1). It's good to think about these.

John Baez (Apr 05 2020 at 00:25):

To form the nerve of G you start with a point, add an edge from it to itself for each element of G, add a triangle with edges g,h,gh for each pair of group elements... and so on, with an n-simplex for each n-tuple of group elements.

John Baez (Apr 05 2020 at 00:26):

You get a space with fundamental group G and all higher homotopy groups being trivial.

Sam Tenka (Apr 05 2020 at 00:34):

Hmm okay so if monoid C maps to monoid G then we should have NC mapping to NG, since hopefully N is functorial. I'd like to say that when G is the abelian group generated by C, NC and NG are homotopic. I can see that I'm not equipped to think well about this, though. Off to learn about nerves and basic alg top!

John Baez (Apr 05 2020 at 00:39):

For monoids that aren't groups, the nerve is less famous... hmm, this looks good:

• O. U. Lenz, The Classifying Space of a Monoid.

John Baez (Apr 05 2020 at 00:40):

The geometric realization of the nerve is often called the "classifying space".

John Baez (Apr 05 2020 at 00:41):

Yes, N is a functor. The thesis above shows the nerve of a free monoid is homotopy equivalent to the corresponding free group.

vikraman (Apr 05 2020 at 00:45):

So for example, $N\mathbb{N} \simeq N\mathbb{Z} \simeq \mathbb{S}^1$

John Baez (Apr 05 2020 at 00:46):

Yeah, and that's about all there is to it, morally speaking....

David Michael Roberts (Apr 05 2020 at 00:58):

John Baez said:

Yes, N is a functor. The thesis above shows the nerve of a free monoid is homotopy equivalent to the corresponding free group.

There's something to be said here about group completion, I imagine, but I can't think of it off the top of my head. I do know that the classifying space of a category has as fundamental group the localisation of the category that inverts all morphisms (this is due to Quillen).

John Baez (Apr 05 2020 at 01:35):

So the fundamental group of the classifying space of a monoid is the group completion of that monoid. That's nice! But maybe you were talking about group completions of topological monoids.

John Baez (Apr 05 2020 at 01:37):

The group completion of a semilattice (thought of as a monoid) is trivial, since $x + x = x$ in the semilattice forces $x = 0$ in the corresponding group. So, the fundamental group of the classifying space of a semilattice is trivial - that's a partial answer to Puzzle 2.

I have a vague feeling that the classifying space of a semilattice is contractible, but I don't know if that's true.

John Baez (Apr 05 2020 at 01:42):

And I just got some insight into Puzzle 1 from MathOverflow:

If $G$ is the group completion of a commutative monoid $M$, the
canonical map $BM \to BG$ is a homotopy equivalence; even if $M \to G$
is not injective. (This is easy to prove: think of $M \to G$ as a
functor between one object categories and apply Quillen's Theorem A to
it. There is only one slice category to check and using commutativity
it is easy to see this category is filtered and thus contractible.)

John Baez (Apr 05 2020 at 01:43):

Here $BM$ is the geometric realization of the nerve of $M$.

David Michael Roberts (Apr 05 2020 at 02:23):

@John Baez yes, topological monoids. So in this case it's even easier!

John Baez (Apr 05 2020 at 05:08):

So the remarks above let us solve this puzzle:

Puzzle 2. Any commutative monoid $C$ maps to a semilattice $C'$ formed by imposing the relations $x + x = x$ for all $x \in C$. What sort of space do you get by taking the nerve of a semilattice? What can you say about the map $NC \to NC'$?

I'll talk in terms of the geometric realizations of these nerves. The classifying space of a commutative monoid is homotopy equivalent to its group completion, and the group completion of a semilattice is the trivial group, so the classifying space of a semilattice is contractible! My guess was right! :+1:

Thus, $BC'$ is contractible, while $BC$ is homotopy equivalent to $BG$ where $G$ is the group completion of $C$. So the natural map $BC \to BC'$ is homotopy equivalent to the map from $BG$ to a point.

John Baez (Apr 05 2020 at 05:10):

I never really got the point of Quillen's Theorem A before, but now that I've used it to solve this puzzle I like it!

David Michael Roberts (Apr 05 2020 at 09:44):

Yes, Quillen's Theorem A is really nice. As a student I once worked out a version for categories internal to Top (and used it to prove the geometric realisation of a weak equivalence is a homotopy equivalence), but it was probably already known or quickly surpassed by infinity-category techniques.

Morgan Rogers (he/him) (Apr 05 2020 at 10:57):

fyi I made a monoid stream not too long ago. If this topic ends up expanding, please feel free to carry it over there!

Matteo Capucci (he/him) (Apr 05 2020 at 11:00):

Morgan Rogers said:

fyi I made a monoid stream not too long ago. If this topic ends up expanding, please feel free to carry it over there!

But semigroups do not have an identity! :grinning_face_with_smiling_eyes:

Morgan Rogers (he/him) (Apr 05 2020 at 11:06):

Fun fact: The category of semigroups is a full reflective subcategory of the category of monoids. This sounds the wrong way around, so it makes you think.

Paolo Capriotti (Apr 05 2020 at 13:09):

Morgan Rogers said:

Fun fact: The category of semigroups is a full reflective subcategory of the category of monoids. This sounds the wrong way around, so it makes you think.

How does this work? The forgetful functor does not have a right adjoint.

Morgan Rogers (he/him) (Apr 05 2020 at 13:19):

No, it has a left adjoint :stuck_out_tongue:

Morgan Rogers (he/him) (Apr 05 2020 at 13:23):

I'm having second thoughts about it being a full subcategory, though, you should definitely check whether my claim was right or not :wink:

Paolo Capriotti (Apr 05 2020 at 13:30):

The best I can see is that the category of monoids is comonadic over the category of semigroups (classically).

Morgan Rogers (he/him) (Apr 05 2020 at 14:04):

And the category of semigroups is monadic over the category of monoids, since the functor adding an identity element preserves coequalizers.

Morgan Rogers (he/him) (Apr 05 2020 at 14:04):

PS: why "classically"?

Paolo Capriotti (Apr 05 2020 at 14:07):

I meant you need excluded middle to prove that the adjunction is comonadic: given a monoid $M$, you want to construct a coalgebra map $M \to M + 1$ that maps the unit to the second component, and you need decidable equality on $M$ (at least for the unit) to do that.

Morgan Rogers (he/him) (Apr 05 2020 at 14:13):

Would you mind giving more detail? I can't see where one needs to decide equality here, given that the units of internal monoids in a category are specified by morphisms :thinking:

Paolo Capriotti (Apr 05 2020 at 14:14):

sorry, that was backwards, let me try again

Paolo Capriotti (Apr 05 2020 at 14:17):

To show that the functor from semigroups to coalgebras is essentially surjective, given a monoid with a coalgebra structure, you need to construct the corresponding semigroup. Classically, you do that by removing the unit from the monoid, but that does not work constructively.

Paolo Capriotti (Apr 05 2020 at 14:18):

You need that $M \cong M \backslash \{e\} + 1$ as sets.

Paolo Capriotti (Apr 05 2020 at 14:25):

Paolo Capriotti said:

The best I can see is that the category of monoids is comonadic over the category of semigroups (classically).

Oops, I meant it the other way, sorry for the confusion. :blush:

And the category of semigroups is monadic over the category of monoids, since the functor adding an identity element preserves coequalizers.

This I don't see, because the functor adding an identity does not have a left adjoint. It has a right adjoint, so of course it preserves coqualisers.

Morgan Rogers (he/him) (Apr 05 2020 at 14:30):

mild embarrassment I... may have drawn my adjunction upside down at the start of this discussion, and you making the same mistake re which is comonadic over which meant I didn't notice until now :scream:

Paolo Capriotti (Apr 05 2020 at 14:34):

This has been way more confusing than I expected it would be. :smile:
Have we reached an agreement, though? The adjunction between monoids and semigroups is both monadic and comonadic. Is that right?

Morgan Rogers (he/him) (Apr 05 2020 at 14:35):

So the counit at a monoid $M$ is the map $M+1 \to M$ which identifies the added unit with the original one, while the unit at a semigroup $S$ is the inclusion into $S+1$. Both functors are conservative, adding a unit preserves equalisers, and the forgetful functor preserves coequalizers (as far as I can tell), so yes, the adjunction is both monadic and comonadic. :tada:

Gershom (Apr 06 2020 at 09:03):

Sam Tenka (naive student) said:

It's a very entertainingly written book! For example, the first few pages motivate the structure problem for semigroups as philosophical quest to understand time. When I tried to read it in undergrad, I got lost. Maybe I'm more mature now.

Sorry for the off-topic, but holy moly. I just realized that I must have taken a very strange seminar for undergraduates from Rhodes at Berkeley, and not known much about him at the time. I remember being given runoffs from a manuscript of his to read (must have been the Wild Book!), and thinking they were the oddest things I'd ever seen a professor write and hand out to students. I did learn a fair amount about automata in that class, along with some very confusing discussions about how they could explain consciousness...

Thibaut Benjamin (Apr 06 2020 at 10:25):

Out of curiosity - Has anyone ever studied "colored" semigroups, (or categories without unities)? I wonder what category theory results break when removing unity. I can envision the concept of adjunction, but there wouldn't be unit and counit, so probably no monad and comonad associated to an adjunction. Sorry if this is too off-topic, the "commutative" part doesn't fit well with colors

James Wood (Apr 06 2020 at 10:28):

All I know is that it's called a “semicategory”. https://ncatlab.org/nlab/show/semicategory

Amar Hadzihasanovic (Apr 06 2020 at 14:33):

What do the unit and counit of an adjunction have to do with the presence of identity morphisms?

Morgan Rogers (he/him) (Apr 06 2020 at 14:45):

^structures without identity elements still have an identity automorphism!

Thibaut Benjamin (Apr 06 2020 at 14:53):

@Amar Hadzihasanovic isn't the unit of the adjunction obtained as being the image of the identity morphism through the isomorphism $\mathrm{Hom}(FA,FA) \simeq \mathrm{Hom}(A,GFA)$? if there is no identity morphism I can't see where the unit comes from. To be fair, maybe I should have said that there are two notions of adjunction - one stating the equivalence of Homs and the other one being a pair of functor with unit and counit satisfying the correct coherence. Without identity morphism, I don't see a reason why with two notions would coincide

Thibaut Benjamin (Apr 06 2020 at 14:54):

Oh I see what you meant there, my bad!

Thibaut Benjamin (Apr 06 2020 at 14:55):

I mixed up between the internal and eternal part

Morgan Rogers (he/him) (Apr 06 2020 at 15:51):

Thibaut Benjamin said:

Amar Hadzihasanovic isn't the unit of the adjunction obtained as being the image of the identity morphism through the isomorphism $\mathrm{Hom}(FA,FA) \simeq \mathrm{Hom}(A,GFA)$? if there is no identity morphism I can't see where the unit comes from. To be fair, maybe I should have said that there are two notions of adjunction - one stating the equivalence of Homs and the other one being a pair of functor with unit and counit satisfying the correct coherence. Without identity morphism, I don't see a reason why with two notions would coincide

This is a good point, perhaps I spoke too quickly. :hushed:

Lê Thành Dũng (Tito) Nguyễn (Apr 06 2020 at 16:04):

John Baez said:

But I don't really understand the Krohn-Rhodes decomposition, though I understand most of the words by now.

One intuitive way to see it is in automata-theoretic terms. A Mealy machine is like a deterministic finite automaton, but each transition also outputs a letter; it computes the function obtained by concatenating the ouputted letters for a run over some input word. Then the Krohn-Rhodes theorem says that a string-to-string function computable by a Mealy machine (called a synchronous function) can be obtained by composing (by ordinary function composition) simpler Mealy machines:

• machines whose transition monoid is a group,
• machines with only 2 states and whose transitions cannot swap the two states (you are only allowed "stay in the same state", "go to state 1 independently of where you were", "go to state 2").
  The "wreath product" involved in the semigroup version is just a way to give an algebraic account of the function composition of Mealy machines.

Lê Thành Dũng (Tito) Nguyễn (Apr 06 2020 at 16:08):

This version can also be extended to more general automata models (e.g. sequential transducers) and is now a common workhorse of algebraic language theory (as someone who is not really an automata theorist I get the feeling that there are two intensively used results on semigroups, one is Krohn-Rhodes and the other is Simon's factorization forest theorem). I recommend looking at https://www.mimuw.edu.pl/~bojan/2019-2020/transducers-and-their-krohn-rhodes-decompositions

Lê Thành Dũng (Tito) Nguyễn (Apr 06 2020 at 16:13):

Let me take this opportunity to do some self promotion :p Pierre Pradic and I used Krohn-Rhodes to relate star-free languages to a non-commutative lambda-calculus in a recent preprint: https://hal.archives-ouvertes.fr/hal-02476219/document
About star-free languages, there have been some blog posts recently on Gödel's Last Letter, https://rjlipton.wordpress.com/2020/03/21/star-free-regular-languages-and-logic/ and https://rjlipton.wordpress.com/2020/03/29/logic-and-star-free-part-deux/

Martti Karvonen (Apr 06 2020 at 16:27):

Thibaut Benjamin said:

Out of curiosity - Has anyone ever studied "colored" semigroups, (or categories without unities)? I wonder what category theory results break when removing unity. I can envision the concept of adjunction, but there wouldn't be unit and counit, so probably no monad and comonad associated to an adjunction. Sorry if this is too off-topic, the "commutative" part doesn't fit well with colors

Not quite the same, but in "A remark on the theory of semi-functors" Hoofman and Moerdijk study categories and semifunctors (i.e. "functors" that preserve composition but not necessarily identity morphisms), and show that the resulting 2-category is equivalent to the 2-category of Karoubi-complete categories and ordinary functors. Perhaps this equivalence extends to an adjunction between semicategories and categories? Edit: indeed, this is more or less said in the nlab article linked above.

Joe Moeller (Apr 06 2020 at 17:46):

I think I've heard these categories without identity maps called semi-categories...

Dan Doel (Apr 06 2020 at 17:48):

They're also called semigroupoids.

John Baez (Apr 06 2020 at 17:49):

Nguyễn Lê Thành Dũng said:

This version can also be extended to more general automata models (e.g. sequential transducers) and is now a common workhorse of algebraic language theory (as someone who is not really an automata theorist I get the feeling that there are two intensively used results on semigroups, one is Krohn-Rhodes and the other is Simon's factorization forest theorem). I recommend looking at https://www.mimuw.edu.pl/~bojan/2019-2020/transducers-and-their-krohn-rhodes-decompositions

Thanks! I should learn these theorems well, then. I'll never be an expert on semigroups, but as a category theorist I should not be ignorant of them!

Dan Doel (Apr 06 2020 at 17:49):

Since that follows the algebra-oid naming scheme.

Reid Barton (Apr 06 2020 at 17:50):

Unfortunately this name is quite difficult for category theorists I think because "groupoid" is about 100x as common as "semigroup", so it looks like a unit.

Reid Barton (Apr 06 2020 at 17:50):

While the intended parsing is "(semigroup)oid".

Dan Doel (Apr 06 2020 at 17:50):

Yeah.

Dan Doel (Apr 06 2020 at 17:52):

What would a semi(groupoid) be, though? Groupoid is the categorification of group, right? So wouldn't it be expected to work out given what a semigroup is (although that might not be well known)?

Reid Barton (Apr 06 2020 at 17:52):

right, it can't be anything so my brain just goes :boom: and doesn't backtrack to the other parsing.

Reid Barton (Apr 06 2020 at 17:53):

or well that's not quite what you said, hmm

Dan Doel (Apr 06 2020 at 17:53):

Semigroup might be a bad name already.

Reid Barton (Apr 06 2020 at 17:53):

I think "semi-" has been co-opted to mean "nonunital" (really, "nonunital category" is the safest name) and so... yeah. You can't have a semigroup in that sense because it's no longer a group.

Dan Doel (Apr 06 2020 at 17:59):

Anyhow, a lot of hits for 'semigroupoid' will probably be functional programmers, because they're good at coming up with structures where composition makes sense, but where there's no unit unless you formally add one (which just causes you more bookkeeping work). But I did see at least one paper that sounded more like examining the theory of 'semigroupoids.'

Dan Doel (Apr 06 2020 at 18:00):

The only thing I remember theory-wise from the programming context is that the Yoneda lemma probably doesn't work anymore.

John Baez (Apr 06 2020 at 19:25):

Dan Doel said:

What would a semi(groupoid) be, though?

For better or worse, here Dusa McDuff defined semigroupoids to be non-empty, small, discrete categories in which all objects are isomorphic.

Dan Doel (Apr 06 2020 at 19:35):

If it's discrete and all objects are isomorphic, can it only have one object?

Dan Doel (Apr 06 2020 at 19:36):

I guess not.

Nathanael Arkor (Apr 06 2020 at 19:38):

why not?

Dan Doel (Apr 06 2020 at 19:39):

Because 'discrete' doesn't necessarily mean 'all maps are identities' like I thought.

Oscar Cunningham (Apr 06 2020 at 19:39):

What does 'discrete' mean here?

John Baez (Apr 06 2020 at 19:39):

Sorry: she means discrete in the topological sense. She's a topologist.

John Baez (Apr 06 2020 at 19:39):

So category theorists can leave out the word "discrete" here.

Dan Doel (Apr 06 2020 at 19:40):

So, is this a contractible groupoid with a small set of objects or something?

Oscar Cunningham (Apr 06 2020 at 19:40):

So up to equivalence we're talking about the deloopings of (EDIT: small) monoids

Dan Doel (Apr 06 2020 at 19:44):

Or is it groupoids that are equivalent to groups?

John Baez (Apr 06 2020 at 19:54):

So, is this a contractible groupoid with a small set of objects or something?

No, McDuff is not demanding that all morphisms be invertible: she said "non-empty, small category in which all objects are isomorphic." So it's a small category that's equivalent to a monoid.

John Baez (Apr 06 2020 at 19:54):

I don't think this is a good thing to call a "semigroupoid" - I'm just warning y'all that she did it.

Dan Doel (Apr 06 2020 at 19:56):

Oh, I see. It needn't be a groupoid.

Dan Doel (Apr 06 2020 at 19:56):

Great. :)

Dan Doel (Apr 06 2020 at 19:58):

This seems like it's using the algebra-oid version though: https://arxiv.org/pdf/1902.09375.pdf

Dan Doel (Apr 06 2020 at 19:58):

So I guess they're both in use in actual category theory papers.

Dan Doel (Apr 06 2020 at 20:00):

Oh wait, I guess it isn't? Because it says categories are semigroupoids. This may even be a third definition of 'semigroupoid'.

Sam Tenka (Apr 07 2020 at 01:28):

@Nguyễn Lê Thành Dũng Thanks! This is clarifying. It seems that KR morally reveals that those 2 state machines are the "source of all non-invertibility" --- neat!