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: Which came first, the monad or the monoid?

Shea Levy (Oct 20 2020 at 15:42):

As a Haskell programmer, I've long "known" that monads are monoids in an endofunctor category. Studying (unbiased) monoidal categories now, though, there's a clear monadic structure being relied on, specifically $\gamma$ turns a $map$ into a $join$ and $\iota$ is just $unit$, given the monad of finite lists. But of course finie lists are just the free monoid!

Two questions come out of this:

1. Perhaps a matter of taste, but which notion is the more fundamental one?
2. Is there a notion of "monoidal category" where instead of a finite list of objects we have a functor over some other monad of objects? The realization that got me on this path in the first place is that unbiased operators in general can be defined over other monads, e.g. multicategorical composition operates over trees, and the monadic definition makes expressing associativity simple

Nathanael Arkor (Oct 20 2020 at 15:48):

Regarding the second question: monoidal categories are representable T-multicategories for T = free monoid monad / free list monad on Set. By picking another cartesian monad, you can get analogous notions. By T-multicategory, I mean the concept defined in Section II.4 of Higher Operads, Higher Categories.

Dan Doel (Oct 20 2020 at 15:50):

I'm pretty sure monoids came first historically, at least. In fact, I think the "mon" in monad comes from "monoid".

Dan Doel (Oct 20 2020 at 15:50):

Before that they were called even worse names, like "triple" and "standard construction".

Dan Doel (Oct 20 2020 at 15:52):

My vague understanding is that they (monoids) aren't really recognized as part of traditional abstract algebra because they're considered too boring.

John Baez (Oct 20 2020 at 15:56):

In a typical modern algebra course they breeze through monoids in about 1 minute before getting to the real star of the show: groups.

John Baez (Oct 20 2020 at 15:56):

When I become king of the world I will correct this.

Jules Hedges (Oct 20 2020 at 15:57):

Shea Levy said:

1. Perhaps a matter of taste, but which notion is the more fundamental one?

I think it's part of the appeal of category theory that everything can be defined in terms of everything else, with no need to arbitrarily pick one to be more fundamental. You also see it with the universal constructions, which are all mutual special cases of each other. It's postmodern, or something

Jacques Carette (Oct 20 2020 at 15:58):

If you're looking for deep structure theorems, groups are what you want. If you're looking for a fundamental structuring mechanism that is pervasive in the organizational structure of mathematics (and computer science and ...), then monoids are your stars. It depends on what you value.

John Baez (Oct 20 2020 at 16:01):

Mac Lane came up with the name "monad" because he thought "triple" was stupidly vague, "monad" sounds like "monoid", and because Leibniz had a theory of monads:

5.1 Monads and the World of Phenomena

Thus far we have seen that Leibniz rejected the Cartesian account of matter, according to which matter, the essence of which is extension, could be considered a substance. Leibniz held instead that only beings endowed with true unity and capable of action can count as substances. The ultimate expression of Leibniz's view comes in his celebrated theory of monads, in which the only beings that will count as genuine substances and hence be considered real are mind-like simple substances endowed with perception and appetite.

Mac Lane's monads have nothing to do with Leibniz's, but he liked stealing philosophical jargon (Aristotle's "categories", Carnaps "functors").

John Baez (Oct 20 2020 at 16:06):

I personally think the fundamental concept is "monoid in a monoidal category", where monoidal category is a special case of "pseudomonoid in a monoidal bicategory", and monoidal bicategory is a special case of "pseudomonoid in a monoidal tricategory", ad infinitum. One can deal with this "ad infinitum" efficiently using a good theory of $(\infty,1)$-categories.

John Baez (Oct 20 2020 at 16:09):

I forget how well homotopy type theory does at crushing all these layers of complexity into a simple thing. Traditional homotopy theorists would call it an $A_\infty$ space.

Reid Barton (Oct 22 2020 at 14:29):

One could also argue that groups are more fundamental than monoids, for example:

• Groups arise as the automorphisms of an object in a groupoid, while monoids arise as the endomorphisms of an object in a category. Presumably groupoids are more fundamental than categories (and spaces are more fundamental than $(\infty,1)$-categories).
• Likewise, isomorphisms are more fundamental than more general maps because every "reasonable" mathematical notion respects isomorphism, while lots of notions (e.g. the endomorphisms of an object, or the finiteness of a set) have no particular relationship to general maps. Furthermore, a type of mathematical object built out of sets with added structure has an intrinsic notion of isomorphism, but it might admit several notions of "map" without a clear reason to prefer one over the others (e.g. arbitrary map between sets vs injective map between sets, continuous map between top. spaces vs open map vs map which induces the topology on the domain vs ...). The constructions of Galois representations in number theory is an example where a "fixed" object (the algebraic closure of a field) actually has automorphisms and these automorphisms automatically induce an action on everything built from this algebraic closure. If we considered a "Galois monoid" instead of a Galois group, then this wouldn't work.
• In HoTT we have a convenient description of $\infty$-groups (= grouplike $A_\infty$ spaces) via their classifying spaces, but no known description of general $A_\infty$ spaces.

Morgan Rogers (he/him) (Oct 22 2020 at 14:45):

I find the entire premise that isomorphisms are "more fundamental" somewhat shaky. If it is based on the fact that there can be different kinds of morphism between objects of a particular kind, then I should point out that the notion of isomorphism depends on the choice of morphisms; just because you picked some class of examples where different notions of morphisms give the same isomorphisms doesn't mean this is always the case, at which point the argument falls apart. Also...
Reid Barton said:

The constructions of Galois representations in number theory is an example where a "fixed" object (the algebraic closure of a field) actually has automorphisms and these automorphisms automatically induce an action on everything built from this algebraic closure. If we considered a "Galois monoid" instead of a Galois group, then this wouldn't work.

As someone who is in the process of building an analogue of Galois theory which replaces (topological) groups with (topological) monoids, I find this contention personally offensive :joy:

Reid Barton (Oct 22 2020 at 14:47):

I think you misunderstand what I'm saying about isomorphisms.

Morgan Rogers (he/him) (Oct 22 2020 at 14:48):

Quite possibly! What do you mean when you say "more fundamental"?

Reid Barton (Oct 22 2020 at 14:49):

I'm saying there is an a priori notion of isomorphism which is not "a map of class X together with a map in the other direction of class X whose compositions are identities", and if you manage to come up with some class of maps X for which that definition in terms of X isn't equivalent to the intrinsic one, then it means that either your class of maps X is wrong or the structure you claim to be working with isn't in fact structure at all.

Reid Barton (Oct 22 2020 at 14:52):

And again this a priori notion of isomorphism relies on the fact that everything respects isomorphism.

Morgan Rogers (he/him) (Oct 22 2020 at 14:52):

What notion is that?

Reid Barton (Oct 22 2020 at 14:52):

For example, an isomorphism of topological spaces $(X, \tau_X)$ and $(Y, \tau_Y)$ is an isomorphism between the sets $X$ and $Y$ such that, when we identify $X$ and $Y$ via this isomorphism, the topologies become equal.

Morgan Rogers (he/him) (Oct 22 2020 at 14:52):

How do you express isomorphism without reference to, well, morphism?

Reid Barton (Oct 22 2020 at 14:54):

An isomorphism of groups is an isomorphism of their underlying sets such that, when we identify the sets by this isomorphism, the group laws become equal (and also the identity and inverse, but this follows automatically).

James Wood (Oct 22 2020 at 14:54):

[Mod] Morgan Rogers said:

just because you picked some class of examples where different notions of morphisms give the same isomorphisms doesn't mean this is always the case

The only natural counterexample I can think of is the category of contexts (in some fixed type theory) under, respectively, renaming and substitution, which have different isomorphisms. I don't know what that suggests in terms of the original argument.

Morgan Rogers (he/him) (Oct 22 2020 at 14:58):

I feel like these examples just push the argument down to $\mathbf{Set}$, though; you still have to say what an isomorphism is there, and you can't do that without functions.

James Wood (Oct 22 2020 at 15:01):

In a univalent setting, the isomorphisms in Set are just the paths, which are not defined in terms of morphisms. Though, now the argument is pushed down to univalence...

Reid Barton (Oct 22 2020 at 15:01):

I think this gets to questions about foundations (and obviously I'm not trying to argue that you can do math without talking about functions, or without talking about monoids).

Reid Barton (Oct 22 2020 at 15:02):

In ZF the definition of a function in turn involves the definition of an ordered pair, but this is just some encoding detail, and doesn't mean that the concept of an ordered pair is more fundamental than the concept of a function

Nathanael Arkor (Oct 22 2020 at 15:03):

The fact that you can describe isomorphisms with morphisms, but not vice versa, suggests to me that the latter are more fundamental.

Reid Barton (Oct 22 2020 at 15:03):

The point is that this isomorphism structure is the thing that gets preserved by everything that we consider a mathematical definition.

Reid Barton (Oct 22 2020 at 15:05):

I think this kind of argument is missing the point, but maybe we just have incompatible understandings of what a fundamental concept is.

Morgan Rogers (he/him) (Oct 22 2020 at 15:05):

That is why I asked what you meant by "more fundamental" :wink:

Reid Barton (Oct 22 2020 at 15:05):

A 1-category is a 2-category whose Hom-categories are all discrete categories. Does it mean a 2-category is more fundamental than a 1-category?
This is the same argument as with groups and monoids.

Reid Barton (Oct 22 2020 at 15:06):

For a homotopy theorist, a monoid is more like a group plus extra noninvertible stuff.

Reid Barton (Oct 22 2020 at 15:07):

And this viewpoint "explains" why in HoTT we can define an $\infty$-group, but we don't know how to talk about the extra stuff in an $\infty$-monoid.

Reid Barton (Oct 22 2020 at 15:10):

Maybe a better word than "fundamental" would be something like "central" or "important"--I don't mean "foundational".

Morgan Rogers (he/him) (Oct 22 2020 at 15:16):

The notion of importance is entirely cultural/context-dependent, though. Take monads, since the OP was asking about those too: I would argue that non-invertible monads (ie monoids in the category of endofunctors which are not groups) are a lot more 'central' than their invertible counterparts.

Morgan Rogers (he/him) (Oct 22 2020 at 15:18):

(I am kind of curious what an invertible monad looks like now, though, admittedly, even if it is just an auto-equivalence as I suspect)

James Wood (Oct 22 2020 at 15:19):

Hopf algebras in the category of endofunctors?

Nathanael Arkor (Oct 22 2020 at 15:22):

It's not generally appropriate to study groups in categories of endofunctors, because they're naturally monoidal categories, but not rigid, so it doesn't make sense to talk about a group object internal to the category of endofunctors.

James Wood (Oct 22 2020 at 15:22):

Anyway, I guess if you're the kind of person who uses monoids with no inverses other than for the identity (e.g, ℕ, any free monoids over sets), that they happen to be the 0 group with some extra structure is a little incidental.

James Wood (Oct 22 2020 at 15:22):

“Now draw the rest of the owl”, &c

Reid Barton (Oct 22 2020 at 15:24):

More than anything else, I would say math is about the question: when are two things the same? Out of this falls the notion of isomorphism, and hence automorphism, and hence group, but not monoid.
Meanwhile, CS is to a larger extent concerned with processes, and usually non-reversible ones.
So I think the common idea that groups are more fundamental/central/important/whatever than monoids in math, while the reverse is the case in CS, seems to have some basis.

Reid Barton (Oct 22 2020 at 15:25):

And obviously monoids have many uses in math and vice versa.

Reid Barton (Oct 22 2020 at 15:26):

But to say "a group is a monoid in which every object is invertible" and conclude that monoids are the true objects underlying the phenomena in math where we see groups is, I think, too reductionist and committed to specific presentations of the concepts of monoids and groups.

Reid Barton (Oct 22 2020 at 15:45):

I guess maybe another way to look at this is that the theory of $(n, k)$-categories depends very much on $k$ but not so much on $n$, and it's hard to explain how this could be unless adding a new kind of invertible morphisms is actually quite different from adding a new kind of non-invertible morphisms.

Reid Barton (Oct 22 2020 at 15:52):

For example it's hopeless to try to understand a (5, 1)-category as a (5, 5)-category in which every 2-, 3-, 4- and 5-morphism is invertible, but fortunately we have a working theory of (n, 1)-categories for any n (which we can get by truncating the theory of $(\infty, 1)$-categories) in which we can set n = 5.

Reid Barton (Oct 22 2020 at 15:53):

So, while by comparison it's not at all difficult to understand a (1, 0)-category (i.e. groupoid) as a special case of a (1, 1)-category (i.e. category), at least it should be plausible that this might not be the only or always the best way to view a (1, 0)-category.

Shea Levy (Oct 22 2020 at 15:53):

Reid Barton said:

The point is that this isomorphism structure is the thing that gets preserved by everything that we consider a mathematical definition.

This sold it for me. It reminded me of a fun post about why the category of sets is "wrong", at least when you compare to our pre-mathematical notion of a set, and it ultimately solves the problem by starting with the isomorphisms: https://bowtochris.tumblr.com/post/162010650907/mark-gently-jerry-seinfeld-voice-whats-the

Dan Doel (Oct 22 2020 at 16:04):

Wouldn't a bunch of people say that it's wrong because it's identifying sets up to isomorphism?

Dan Doel (Oct 22 2020 at 16:04):

Instead of up to extension, like 'normal'. :smile:

Reid Barton (Oct 22 2020 at 16:09):

By the way, if you expand out the ZF definition of a function down to ordered pairs, it's a set $S$ such that

$$\forall (a_1, b_1), (a_2, b_2) \in S. \, (a_1 = a_2) \to (b_1 = b_2)$$

while it's a bijection when

$$\forall (a_1, b_1), (a_2, b_2) \in S. \, (a_1 = a_2) \iff (b_1 = b_2)$$

so you can push this discussion all the way down to the level of propositional logic and the relationship between -> and <->.

Reid Barton (Oct 22 2020 at 16:12):

If you accept propositional extensionality, which seems appropriate in this context, then <-> is "being the same".

Reid Barton (Oct 22 2020 at 16:19):

So the core of the discussion amounts to whether you think of P <-> Q as an abbreviation for P -> Q /\ Q -> P, or as expressing that P and Q are "the same". Then that translates into the relationship between function and bijection, and in turn the relationship between monoid and group.

Reid Barton (Oct 22 2020 at 16:21):

Treating P <-> Q as denoting P -> Q /\ Q -> P means that foundationally you only need the single concept -> (which you obviously need anyways), but it fails to "explain" why this condition is the one we need to substitute Q for P freely.

Reid Barton (Oct 22 2020 at 16:23):

And defining a homeomorphism of topological spaces as a continuous map with continuous inverse is foundationally convenient because we needed continuous maps anyways, but it doesn't explain the phenomenon that all properties of topological spaces that mathematicians consider are preserved under homeomorphisms, but not under general continuous maps.

Reid Barton (Oct 22 2020 at 16:32):

HoTT is nice for this purpose because it gives a specific name to this "substitutability" facet of the concept of homeomorphism, namely the identity/path types of the type of all topological spaces. But I think the concept exists even prior to its encoding in some particular formal system (although the encoding can certainly help!)

Morgan Rogers (he/him) (Oct 22 2020 at 17:47):

Reid Barton said:

So the core of the discussion amounts to whether you think of P <-> Q as an abbreviation for P -> Q /\ Q -> P, or as expressing that P and Q are "the same". Then that translates into the relationship between function and bijection, and in turn the relationship between monoid and group.

The former way is exactly how I think of <->. I guess that's just another instance of the difference in perspective that has already been established, but on the other hand I don't see how you can escape the fact that an isomorphism is not just the statement that two things are the same, but a way in which two things are the same. In order to show "not P <->Q" I show one of "not P -> Q" or "not Q -> P". If I'm not gifted with a guarantee that P <-> Q then to prove it I would necessarily start with a proof of one implication or the other; I would have to construct an isomorphism, and that starts with constructing a morphism of some kind or other, even if it's just a function.
Reid Barton said:

Treating P <-> Q as denoting P -> Q /\ Q -> P means that foundationally you only need the single concept -> (which you obviously need anyways), but it fails to "explain" why this condition is the one we need to substitute Q for P freely.

I don't think it fails. P -> Q means I can substitute any P for a Q; the other implication gives substitution the other way around.

Reid Barton (Oct 22 2020 at 17:48):

By substitution I mean in an arbitrary context. If you only have P -> Q then you can't substitute Q for P in not P.

Dan Doel (Oct 22 2020 at 17:49):

HoTT can also be seen as a general framework for saying how things are the same in an inherently symmetric way.

Dan Doel (Oct 22 2020 at 17:51):

Because the type theory it was built from already accidentally left that possibility, but didn't have any non-trivial ways of saying how two things are the same.

Reid Barton (Oct 22 2020 at 17:59):

(And in the case of isomorphism, by "arbitrary" I don't mean literally a completely arbitrary formula of ZF, just the ones which encode "reasonable" mathematical notions.)

Morgan Rogers (he/him) (Oct 22 2020 at 18:06):

It is true that as soon as you think of these things as directed arrows, you have to worry about which way they're pointing..! Thanks for the perspective, in any case. Maybe my inner homotopy theorist will one day break out of his cage.

David Michael Roberts (Oct 23 2020 at 05:50):

Reid Barton said:

By the way, if you expand out the ZF definition of a function down to ordered pairs, it's a set $S$ such that

$$\forall (a_1, b_1), (a_2, b_2) \in S. \, (a_1 = a_2) \to (b_1 = b_2)$$

while it's a bijection when

$$\forall (a_1, b_1), (a_2, b_2) \in S. \, (a_1 = a_2) \iff (b_1 = b_2)$$

so you can push this discussion all the way down to the level of propositional logic and the relationship between -> and <->.

One problem with this is that in ZF functions don't remember their codomain. So all this says is that the function is injective.

Reid Barton (Oct 23 2020 at 08:57):

Yes, in addition to the condition $\forall a \in A. \, \exists b \in B. \, (a, b) \in S$, you need the add the symmetric condition $\forall b \in B. \, \exists a \in A. \, (a, b) \in S$.