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: monoids and coproducts

David Egolf (Feb 12 2023 at 21:34):

The natural numbers (including zero) together with addition form a monoid. We can associate to each natural number a set having the corresponding number of elements (e.g. associate to "3" a set have three elements). Then, we can use the coproduct in the category of sets to "carry out addition". For example, we can map "3" to a set with three elements, map "5" to a set with five elements, and then take the disjoint union of the resulting sets to get a set with eight elements. By counting the number of elements in the resulting set, we can produce a natural number - so that the addition of the two numbers was computed in the category of sets using the coproduct.

So, at least in some cases, it is possible to compute a monoid operation in a different category using coproducts. When is this possible? And what do these other categories - used for computation in terms of coproducts - look like? Are they anything like the category of sets in general?

For example, consider the monoid having elements 0,1,2,3 together with addition modulo 4 (e.g. 2+3=1 now). Is there some other category where we can compute this operation using coproducts, in a way analogous to how we could carry out regular addition on the natural numbers in the category of sets using coproducts?

Symbolically, if the elements of the monoid in question form the set $M$, when is there a category with objects $C$ so that there are functions $F: M \to C$ and $G: C \to M$ satisfying the following: $m_1 \circ m_2 = G(F(m_1) \sqcup F(m_2))$?

(I'm also interested in thinking about what kind of monoids we can generate in this way by using different universal constructions besides the coproduct...)

John Baez (Feb 13 2023 at 02:15):

So, you're asking for necessary and/or sufficient conditions for a monoid to arise from decategorifying a category with coproducts. (This is how an expert would say your question. It's an interesting question.)

John Baez (Feb 13 2023 at 02:17):

I don't know the answer to your question, but here are some necessary conditions for a monoid to arise from decategorifying a category with coproducts:

• The monoid must be commutative.
• If $x + y = 0$ then we must have both $x = 0$ and $y = 0$.

The latter condition rules out all groups except the trivial group! So, the answer to this question:

For example, consider the monoid having elements 0,1,2,3 together with addition modulo 4 (e.g. 2+3=1 now). Is there some other category where we can compute this operation using coproducts, in a way analogous to how we could carry out regular addition on the natural numbers in the category of sets using coproducts?

is no!

John Baez (Feb 13 2023 at 02:18):

And here's a little puzzle:

• There is a category with coproducts that when decategorified gives the natural numbers with multiplication as the monoid operation. What is it?

John Baez (Feb 13 2023 at 02:27):

And another little puzzle:

• Find a category with coproducts that when decategorified gives a monoid that lacks the cancellation property. That is, find a category with objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$.

Matteo Capucci (he/him) (Feb 13 2023 at 17:03):

It seems relevant that natural numbers are an ordered monoid, the order being a shadow of some of the maps from FinSet (namely the monomorphisms aka injections)

David Egolf (Feb 13 2023 at 19:01):

Thanks to both of you for your responses!
John Baez said:

And here's a little puzzle:

• There is a category with coproducts that when decategorified gives the natural numbers with multiplication as the monoid operation. What is it?

My initial guess is that the category we are looking for here is the opposite category of the category of sets. My idea is that when we move from a category to its opposite, what were products (should intuitively) become coproducts. In the category of sets, we can carry out multiplication (in terms of numbers of elements) by using the product. So, maybe in $\mathsf{Set}^{op}$ the coproduct corresponds to multiplication of natural numbers.
Thinking about it a little more, in $\mathsf{Set}^{op}$ a morphism from a set $A$ to a set $B$ is a function from $B$ to $A$. So, if any diagram exists in $\mathsf{Set}$, we can draw a corresponding diagram in $\mathsf{Set}^{op}$ by reversing all the arrows. I believe the diagrams describing a product and a coproduct are the same, except with arrows reversed. It seems like a product in $\mathsf{Set}$ should be a coproduct in $\mathsf{Set}^{op}$ then.

David Egolf (Feb 13 2023 at 19:06):

John Baez said:

And another little puzzle:

• Find a category with coproducts that when decategorified gives a monoid that lacks the cancellation property. That is, find a category with objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$.

I know that multiplying by zero can result in a situation like this: $x \cdot 0 = y \cdot 0$ even when $x \neq y$. The natural numbers (including zero) together with multiplication form a monoid where this situation can occur. If I figured out the previous puzzle, then I would expect $\mathsf{Set}^{op}$ to be a setting where there exist objects $x,y,a$ such that $x + a \cong y + a$ with $x \ncong y$ (where "+" denotes the coproduct).
For example, let $x$ be a set with three elements and $y$ be a set with two elements. Let $a$ be the empty set. Then $x + a$ in $\mathsf{Set}^{op}$ I think should be the product of $x$ and $a$ in $\mathsf{Set}$, which is the empty set $a$. Similarly, $y+a$ should be the product of $y$ and $a$ in $\mathsf{Set}$, which is also the empty set. So, $x+a \cong y+a$ but $x \ncong y$.

David Egolf (Feb 13 2023 at 19:27):

Matteo Capucci (he/him) said:

It seems relevant that natural numbers are an ordered monoid, the order being a shadow of some of the maps from FinSet (namely the monomorphisms aka injections)

That sounds interesting. I'd be interested to learn what other monoids exist that have a natural ordering inherited like this. I guess the natural numbers together with multiplication have the opposite ordering, if we produce the order from the monomorphisms in $\mathsf{Set}^{op}$ (which I think should be epimorphisms in $\mathsf{Set}$, which are the surjections)? Although this ordering is a little bit weird compared to what I would have expected, because there is no function from a non-empty set to an empty set.
(Hmm. I may have gotten confused with all the "op" stuff. I'll leave this up with this disclaimer, though.)

John Baez (Feb 13 2023 at 23:29):

David Egolf said:

John Baez said:

And here's a little puzzle:

• There is a category with coproducts that when decategorified gives the natural numbers with multiplication as the monoid operation. What is it?

My initial guess is that the category we are looking for here is the opposite category of the category of sets. My idea is that when we move from a category to its opposite, what were products (should intuitively) become coproducts. In the category of sets, we can carry out multiplication (in terms of numbers of elements) by using the product.

That's almost right! You've definitely got the key idea. So why is your answer actually wrong?

John Baez (Feb 13 2023 at 23:30):

You can easily fix it.

John Baez (Feb 13 2023 at 23:32):

David Egolf said:

John Baez said:

And another little puzzle:

• Find a category with coproducts that when decategorified gives a monoid that lacks the cancellation property. That is, find a category with objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$.

I know that multiplying by zero can result in a situation like this: $x \cdot 0 = y \cdot 0$ even when $x \neq y$. The natural numbers (including zero) together with multiplication form a monoid where this situation can occur. If I figured out the previous puzzle, then I would expect $\mathsf{Set}^{op}$ to be a setting where there exist objects $x,y,a$ such that $x + a \cong y + a$ with $x \ncong y$ (where "+" denotes the coproduct).

Excellent! Even though your answer to the first problem was not quite correct, you are right in saying that $\mathsf{Set}^{\text{op}}$ has objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$. As you said, we can take $a$ to be the empty set.

John Baez (Feb 13 2023 at 23:34):

So now I can't resist giving you this clue to why your answer to the first problem was wrong. In fact $\mathsf{Set}$ is also a category with objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$. This was the example I had in mind.

John Baez (Feb 13 2023 at 23:41):

There are also other nice examples.

David Egolf (Feb 14 2023 at 15:52):

John Baez said:

So now I can't resist giving you this clue to why your answer to the first problem was wrong. In fact $\mathsf{Set}$ is also a category with objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$. This was the example I had in mind.

This was fun to think about! I think the answer has to do with the presence of infinite sets. For example, let $x$ be a set with three elements, and let $y$ be a set with five elements. Then let $a$ be a countably infinite set. Then I think that $x+a$ and $y+a$ both have a countably infinite number of elements, so $x+a \cong y+a$ but $x \ncong y$.
So, if we create a monoid from $\mathsf{Set}$ by creating an element of the monoid for each isomorphism class of $\mathsf{Set}$, we don't just get the natural numbers. We get the natural numbers augmented with some fancy extra elements that I think model different infinite cardinalities. I don't know what that resulting structure is called!

David Egolf (Feb 14 2023 at 15:54):

Working from this hint, if we want to decategorify some category with coproducts to get the natural numbers together with multiplication - we probably want to make sure we don't end up with extra elements (from infinite sets) like this. So, maybe instead of $\mathsf{Set}^{op}$, we want $\mathsf{FinSet}^{op}$, the opposite category of the category of finite sets.

John Baez (Feb 14 2023 at 16:44):

Why "maybe"? Please tell me what you're worrying about.

John Baez (Feb 14 2023 at 22:33):

David Egolf said:

John Baez said:

So now I can't resist giving you this clue to why your answer to the first problem was wrong. In fact $\mathsf{Set}$ is also a category with objects $x,y,a$ such that $x + a \cong y + a$ but $x \ncong y$. This was the example I had in mind.

This was fun to think about! I think the answer has to do with the presence of infinite sets. For example, let $x$ be a set with three elements, and let $y$ be a set with five elements. Then let $a$ be a countably infinite set. Then I think that $x+a$ and $y+a$ both have a countably infinite number of elements, so $x+a \cong y+a$ but $x \ncong y$.

Right!

John Baez (Feb 14 2023 at 22:35):

So, if we create a monoid from $\mathsf{Set}$ by creating an element of the monoid for each isomorphism class of $\mathsf{Set}$, we don't just get the natural numbers. We get the natural numbers augmented with some fancy extra elements that I think model different infinite cardinalities.

Right!

I don't know what that resulting structure is called!

It's called Card, the class of all cardinals. You can add cardinals, but if $a \le x$ and $x$ is infinite then $x + a = x$.

The class of all cardinals is too big to be a set, so Card is not a monoid in the usual sense. It's a 'large' monoid.

John Baez (Feb 14 2023 at 22:37):

Here are some more puzzles:

What monoids do you get from these two categories with coproducts?

• $\mathsf{FinSet}$

• $\mathsf{FinSet}^{\textrm{op}}$

Also, here's a nice little category with coproducts:

$0 \to 1$

It has two objects, 0 and 1, and a morphism from 0 to 1 (along with the two identity morphisms).

What commutative monoid does this give? Does this monoid obey the cancellation law

$x + a \cong y + a \implies x \cong y ?$

John Baez (Feb 14 2023 at 22:44):

By the way, this category $0 \to 1$ is also called the poset of truth values or Booleans - it's very important in classical logic.

David Egolf (Feb 15 2023 at 15:49):

John Baez said:

Why "maybe"? Please tell me what you're worrying about.

Well, I missed a detail before, and I wouldn't put it past me to miss another one. :upside_down: I suppose I'm just generally not super familiar with this stuff... Plus, I'm not carefully writing these arguments out anywhere, and that tends to lead to me making more mistakes. However, I didn't have a specific mathematical worry.

David Egolf (Feb 15 2023 at 15:52):

John Baez said:

What monoids do you get from these two categories with coproducts?

• $\mathsf{FinSet}$

• $\mathsf{FinSet}^{\textrm{op}}$

Based on the discussion above, from $\mathsf{FinSet}$ we get the natural numbers together with addition. And from $\mathsf{FinSet}^{\textrm{op}}$ we get the natural numbers together with multiplication.

David Egolf (Feb 15 2023 at 16:01):

John Baez said:

Also, here's a nice little category with coproducts:

$0 \to 1$

It has two objects, 0 and 1, and a morphism from 0 to 1 (along with the two identity morphisms).

What commutative monoid does this give? Does this monoid obey the cancellation law

$x + a \cong y + a \implies x \cong y ?$

Before thinking about $0 \to 1$, I want to quickly think about the category $0$. This has one object, and a single identity morphism. I believe it has coproducts, and $0+0=0$. So this category with coproducts produces the trivial monoid by decategorification.

Ok, back to $0 \to 1$. The coproduct of 0 and 0 needs to have a morphism to it from 0, and a unique morphism to every other object that satisfies this condition. That means 0+0=0. The coproduct of 1 and 1 needs to have a morphism to it from 1, and a unique morphism to every other object that satisfies this condition. That means 1+1=1. The coproduct of 0 and 1 needs to have a morphism to it from 0 and a morphism to it from 1, and a unique morphism from it to every other object that satisfies this condition. That means 0+1=1, and 1+0=1.

This monoid does not obey the cancellation law! $1+0 \cong 1+1$ but $0 \ncong 1$. (And 0 is indeed not isomorphic to 1, as there is no inverse for the morphism from 0 to 1 in our category).

David Egolf (Feb 15 2023 at 16:02):

John Baez said:

By the way, this category $0 \to 1$ is also called the poset of truth values or Booleans - it's very important in classical logic.

Ah, right! I can see that this monoid is one I'm familiar with, if we think of 0 as "false" and 1 as "true" and our monoid operation as "OR".

David Egolf (Feb 15 2023 at 16:07):

A few thoughts about this:

• I suppose that $A + B \cong B + A$ in any category. Without checking carefully, it seems like if we get a coproduct with one order of the objects $A$ and $B$, then the resulting object will still satisfying the appropriate diagram after we rearrange the order of the objects. Since coproducts, if they exist, are unique up to isomorphism, and $A+B$ and $B+A$ (I think) satisfy both of the coproduct diagrams (with one corresponding to each order), then I think that means we have $A+B \cong B+A$.
  That would explain why the monoids we get from decategorification have to be commutative.

David Egolf (Feb 15 2023 at 16:10):

• While working out coproducts in $0 \to 1$, I noticed that for $A+B = C$, we need there to be morphisms from $A$ and $B$ to $C$. If we put a partial order on the objects by saying that $X \leq Y$ exactly when there is at least one morphism from $X$ to $Y$, then that means that if $A+B = C$, then $A \leq C$ and $B \leq C$.

David Egolf (Feb 15 2023 at 16:14):

• The result that 0+1=1 and 1+1=1 reminds me of something that happens when working with instruments that take readings. Generally there is a maximum reading that a sensor can produce, and if the input is larger than that maximum, the sensor may just output that maximum reading. I remember wondering years ago what kind of algebraic structure would model what I was thinking of as "saturated addition". I wonder if categories in this style would model this sort of thing.

David Egolf (Feb 15 2023 at 16:24):

• Matteo Capucci's comment above also has me wondering if the morphisms to the coproduct $A+B$ from $A$ and $B$ in the coproduct diagram are always monomorphisms.

John Baez (Feb 15 2023 at 16:34):

David Egolf said:

John Baez said:

Why "maybe"? Please tell me what you're worrying about.

Well, I missed a detail before, and I wouldn't put it past me to miss another one. :upside_down: I suppose I'm just generally not super familiar with this stuff... Plus, I'm not carefully writing these arguments out anywhere, and that tends to lead to me making more mistakes. However, I didn't have a specific mathematical worry.

Okay, I guess that makes sense. A really important thing about math is that one can work things out to the point of being completely sure about things... and being right, too. I had thought you were at that point. It wouldn't be good to be so scared that one sticks a "maybe" in a sentence when there's no real doubt. But yes, if you're not familiar with these things and you're not writing things up there may be a "cloud of doubt" even absent any specific worry.

Usually I deal with the opposite problem: I've had a lot of bright grad students of an intuitive bent who leap to a conclusion because the conclusion feels like it makes sense and it's very attractive. It's important to be able to make these leaps - intuition is an important tool. But I need to teach them to be careful, because the "flash of insight" often comes with a purely subjective sense that something "must be true", which is actually quite different from being sure because you've worked out the details.

John Baez (Feb 15 2023 at 16:36):

David Egolf said:

John Baez said:

What monoids do you get from these two categories with coproducts?

• $\mathsf{FinSet}$

• $\mathsf{FinSet}^{\textrm{op}}$

Based on the discussion above, from $\mathsf{FinSet}$ we get the natural numbers together with addition. And from $\mathsf{FinSet}^{\textrm{op}}$ we get the natural numbers together with multiplication.

Yes, that's right! This is where addition and multiplication of natural numbers come from... though usually we say multiplication comes from the product in $\mathsf{FinSet}$ (which is the same as the coproduct in $\mathsf{FinSet}^{\textrm{op}}$).

John Baez (Feb 15 2023 at 16:38):

David Egolf said:

Before thinking about $0 \to 1$, I want to quickly think about the category $0$. This has one object, and a single identity morphism. I believe it has coproducts, and $0+0=0$. So this category with coproducts produces the trivial monoid by decategorification.

Right! It's good to go back like that. I also urge you to go forward and look at $0 \to 1 \to 2$. Categories of this ilk are called "ordinals".

John Baez (Feb 15 2023 at 16:39):

Your analysis of $0 \to 1$ was spot on.

David Egolf said:

Ah, right! I can see that this monoid is one I'm familiar with, if we think of 0 as "false" and 1 as "true" and our monoid operation as "OR".

Right!

John Baez (Feb 15 2023 at 16:40):

And if we looked at products in $0 \to 1$ we'd get "AND".

John Baez (Feb 15 2023 at 16:40):

The arrow in $0 \to 1$ is "false implies true".

John Baez (Feb 15 2023 at 16:41):

So this is an extremely important category.

John Baez (Feb 15 2023 at 16:41):

David Egolf said:

A few thoughts about this:

• I suppose that $A + B \cong B + A$ in any category. Without checking carefully, it seems like if we get a coproduct with one order of the objects $A$ and $B$, then the resulting object will still satisfying the appropriate diagram after we rearrange the order of the objects. Since coproducts, if they exist, are unique up to isomorphism, and $A+B$ and $B+A$ (I think) satisfy both of the coproduct diagrams (with one corresponding to each order), then I think that means we have $A+B \cong B+A$.
  That would explain why the monoids we get from decategorification have to be commutative.

Yes, all this is correct.

John Baez (Feb 15 2023 at 16:47):

David Egolf said:

• While working out coproducts in $0 \to 1$, I noticed that for $A+B = C$, we need there to be morphisms from $A$ and $B$ to $C$. If we put a partial order on the objects by saying that $X \leq Y$ exactly when there is at least one morphism from $X$ to $Y$, then that means that if $A+B = C$, then $A \leq C$ and $B \leq C$.

Yes, that's right. It's nice how you can make up a concept of $\le$ that's compatible with addition to this extent. Now I'm wondering if this $\le$ obeys the usual axiom

$A \le A', B \le B' \implies A + B \le A' + B'$

Yes, it does.

John Baez (Feb 15 2023 at 16:48):

David Egolf said:

• The result that 0+1=1 and 1+1=1 reminds me of something that happens when working with instruments that take readings. Generally there is a maximum reading that a sensor can produce, and if the input is larger than that maximum, the sensor may just output that maximum reading. I remember wondering years ago what kind of algebraic structure would model what I was thinking of as "saturated addition". I wonder if categories in this style would model this sort of thing.

You might take a look and see whether this category with coproducts:

$0 \le 1 \le 2$

gives the commutative monoid $\{0, 1, 2\}$ where the monoid operation is 'saturated addition', $x + y \min 2$.

Jason Erbele (Feb 15 2023 at 19:24):

John Baez said:

And if we looked at products in $0 \to 1$ we'd get "AND".

If you want to get "AND" without switching to products, you can change the assignments of "false" and "true" instead (i.e. by thinking of 0 as "true" and 1 as "false"). :octopus:
Of course, using the product is "better" in the sense that "AND" and "OR" are compatible – they have matching notions of what 0 and 1 mean.

John Baez (Feb 15 2023 at 20:56):

A: You misunderstood me because when I say "true" it means what you mean by "false"; when I say "false" it means what you mean by "true"; when I say "implies" it means what you mean by "implied by"; when I say "and" it means what you mean by "or", and when I say "or" it means what you mean by "and".

B: What about "not"?

A: Oh - on that we agree.

David Egolf (Feb 16 2023 at 16:09):

John Baez said:

I also urge you to go forward and look at $0 \to 1 \to 2$. Categories of this ilk are called "ordinals".

The coproduct of 0 and 0 needs to have morphisms to it from zero, and have a unique morphism to every other object that satisfies this condition. In terms of the induced preorder mentioned above, I think this corresponds to asking for the smallest object at least as large as zero. So, $0+0=0$.

I think this line of argument indicates that $a+b = \max(a,b)$. So, $0+1=1$, $0+2=2$, $1+1=1$, $1+2=2$, $2+2=2$. This is a bit different than the "saturated addition" mentioned above, which would have $1+1=2$.

David Egolf (Feb 16 2023 at 16:12):

Looking here, I read that the "join" operation corresponds to the coproduct in posets, which makes sense.

David Egolf (Feb 16 2023 at 16:21):

The categories we've looked at so far induce an identity element: they have an object $0$ so that $0+a \cong a$ for all $a$. That ensures that in each of these categories there exists an object $0$ so that $0 \leq a$ for all $a$. (This is under the preoder induced by saying $x \leq y$ when there is at least one morphism from $x$ to $y$).

So, our categories with coproducts must have a "smallest element" if they are to induce a monoid via decategorification. In the case of these ordinal categories, the smallest element is the one we've called "0". But in $\mathsf{FinSet}$, every set is a "smallest element" in this sense, so this isn't enough to specify which object will act as the identity element in the induced monoid.

David Egolf (Feb 16 2023 at 16:31):

I notice that "0" is the initial object in the ordinal categories, and we saw it became the identity element in the monoid induced by decategorification. The empty set is the initial object in $\mathsf{FinSet}$, and it also became the identity element after decategorification. In $\mathsf{FinSet}^{\mathrm{op}}$, an initial object is a terminal object of $\mathsf{FinSet}$, so any singleton set is an initial object in $\mathsf{FinSet}^{\textrm{op}}$. Each singleton set $S$ satisfies $S+X \cong X$ for each $X$ in $\mathsf{FinSet}^{\textrm{op}}$, and so each singleton becomes the identity element in the monoid induced by decategorification.

In each of these three cases, the initial object becomes the identity morphism in the induced monoid. That seems like an interesting pattern! I wonder if this is always the case.

Morgan Rogers (he/him) (Feb 16 2023 at 17:32):

If $0+X \cong X$ for every $X$, then there must be exactly one morphism from $0$ to each $X$, so yes, that must be the case! From this perspective, uniqueness up to isomorphism of initial objects decategorifies to uniqueness of the unit element of a monoid.

Jason Erbele (Feb 16 2023 at 20:32):

Would $\mathsf{FinSet}$ restricted to sets with two or fewer elements have a coproduct that, when decategorified, gives the "saturated addition" commutative monoid on $\{0,1,2\}$? Note that there are two morphisms $1 \to 2$ and two morphisms $2 \to 2$ in this category, so it's not the same as the poset $0 \to 1 \to 2$. I have no problems finding $\forall X, X \sqcup 0 \cong X$, but I'm confusing myself on whether the other coproducts exist (mostly because I forgot the second $2 \to 2$ morphism exists until I ran out of spare time to think about this).

John Baez (Feb 17 2023 at 01:08):

I don't think the category of sets with at most 2 elements has coproducts. Remember

$\mathrm{hom}(x, y + z) \cong \mathrm{hom}(x,y) \times \mathrm{hom}(x,z)$

I think you can use this to show that the category of finite sets with at most 2 elements, and functions between those, does not have the coproduct 2 + 2.

David Egolf (Feb 17 2023 at 16:16):

Morgan Rogers (he/him) said:

If $0+X \cong X$ for every $X$, then there must be exactly one morphism from $0$ to each $X$, so yes, that must be the case!

I've been staring at this for a while, and I wish I knew how to prove this. I can see that there is at least one morphism from $0$ to each $X$. If $f: 0+X \to X$ is an isomorphism, and $i:0 \to 0+X$ is the coprojection morphism of the coproduct from $0$, then $f \circ i: 0 \to X$. However, I'm not sure where to begin to show that this morphism is unique.

Graham Manuell (Feb 17 2023 at 16:48):

I don't know exactly what Morgan meant, but I don't think this is actually true as stated. Consider the full subcategory of the category of sets containing the set of natural numbers as its only object. This category has binary coproducts and satisfies that condition, but has no initial object.

Graham Manuell (Feb 17 2023 at 16:49):

(Of course, if a category does have an initial object, then this will be the unit with respect to the operation of binary coproduct.)

Morgan Rogers (he/him) (Feb 18 2023 at 10:08):

It's true, I'm missing a hypothesis, thanks for spotting that @Graham Manuell . I think "naturally in X" would do it, or the less powerful assumption that for each $X$ there exists $Y$ such that $\mathrm{Hom}(X,Y)$ is (non-empty and) finite; the latter one seems to be what I was assuming when I wrote that above.

Morgan Rogers (he/him) (Feb 18 2023 at 10:20):

(Fortunately, a terminal object fulfils this requirement, and having a terminal object isn't a terribly constrictive thing to require.)

David Egolf (Feb 18 2023 at 16:00):

I'm not quite sure where I'd like to take this topic as this point. The discussion so far has been interesting, and I've learned a number of cool things from it.

I'll take this moment to summarize some of the things I've learned:

• The coproduct is commutative up to isomorphism, so the decategorified monoids we get are always commutative.
• To get a monoid by decategorification, we need coproducts to exist and for there to be a neutral element with respect to the coproduct operation. This neutral element is often an initial object.
• The resulting monoids produced by decategorification can be non-cancellative.
• Different categories with coproducts can decategorify to the same monoid (e.g. the category "0" with a single object and only the identity morphism; and the full subcategory of $\mathsf{Set}$ with the only object being the natural numbers)
• Monoids we've been able to get by decategorification so far include: the trivial monoid, the monoid with n+1 elements 0,1,..., n and the monoid operation being "max", and the natural numbers with addition or multiplication.

David Egolf (Feb 18 2023 at 16:08):

Does anyone have some specific direction/question they think would be interesting to discuss in this thread? I sometimes get a little overwhelmed by how much there is to learn, and I struggle to pick a constructive direction.

John Baez (Feb 18 2023 at 17:59):

I guess this is a good thing to notice now. A category is called a preorder if there's at most one morphism from any object to any other; then we write $x \le y$ if there's a morphism from $x$ to $y$. A preorder is called a poset if whenever $x \le y$ and $y \le x$ then $x = y$.

It's very interesting to think about posets that have finite coproducts (that is, binary coproducts $+$ and an initial object $0$). This sort of poset is called a [[join-semilattice]].

Examples include our friends $0 \to 1 \cdots \to n-1 \to n$ but also many other interesting things.

John Baez (Feb 18 2023 at 18:06):

Do you see why any join-semilattice is a commutative monoid?

John Baez (Feb 18 2023 at 18:09):

Do you see how to make the collection of all subsets of a set $X$ into a join-semilattice?

John Baez (Feb 18 2023 at 18:09):

Join-semilattices are a very interesting kind of commutative monoid.

Graham Manuell (Feb 18 2023 at 20:03):

It's worth noting that every finitely-cocomplete finite category is a preorder, so the monoids we get from finite categories are always semilattices.

David Egolf (Feb 19 2023 at 17:20):

Thinking about join-semilattices sounds interesting!
John Baez said:

Do you see why any join-semilattice is a commutative monoid?

Well, we can decategorify a join-semilattice to get a commutative monoid. Join-semilattices have binary coproducts to provide the composition of elements, and an initial object to provide a neutral element in the monoid. The decategorified monoid will be commutative because the binary coproduct operation is commutative up to isomorphism.

However, I think the objects of a join-semilattice together with the binary coproduct operation directly form a monoid. If $x \cong y$ for objects $x$ and $y$, then in a preorder $x \leq y$ and $y \leq x$, and in a poset that means that $x=y$. Since $a+b \cong b+a$ where "+" denotes the binary coproduct operation, that means that in a join semi-lattice $a+b=b+a$ for all objects $a$ and $b$. And similarly $0+a=a$ for all objects $a$, where $0$ is the unique initial object.

David Egolf (Feb 19 2023 at 17:25):

Interestingly, the nlab article points out that the monoid induced by a join semi-lattice is idempotent. That is, we have $a+a=a$ for all monoid elements $a$.

David Egolf (Feb 19 2023 at 17:32):

John Baez said:

Do you see how to make the collection of all subsets of a set $X$ into a join-semilattice?

We can set the objects of our category to be the subsets of $X$, and put a morphism $A \leq B$ when $A \subseteq B$, I would guess. This forms a preorder, and actually a poset since if $A \subseteq B$ and $B \subseteq A$ then $A = B$. The join of two sets corresponds to the union, which always exists, and provides a binary commutative operation with the empty set as its neutral element. The empty set is the initial object, and I think that means we've met all the conditions to have a join-semilattice.

David Egolf (Feb 19 2023 at 17:40):

This reminds me a little bit of the definition of a topological space. Starting with a set $X$, we can form a category $C$ where the objects are all the subsets of $X$ and there is a morphism from $A$ to $B$ exactly when $A \subseteq B$, as we did above. However, we can then consider full subcategories of $C$. At first I thought that requiring a full subcategory of $C$ to have all coproducts and finite products would result in a topological space, but I believe that isn't quite right - for example, coproducts can end up being different than the union.

David Egolf (Feb 19 2023 at 17:59):

Graham Manuell said:

It's worth noting that every finitely-cocomplete finite category is a preorder, so the monoids we get from finite categories are always semilattices.

Huh, so somehow having (1) all colimits under finite diagrams and (2) a finite number of objects and morphisms then forces a category to have at most one morphism between any pair of objects?

Graham Manuell (Feb 19 2023 at 23:02):

Yes. The proof is just like the usual proof that a small complete category is a preorder.

David Egolf (Feb 20 2023 at 00:14):

Graham Manuell said:

Yes. The proof is just like the usual proof that a small complete category is a preorder.

Thanks for the link! This is quite interesting. I may ask some questions about this proof in a separate thread, to keep this one organized.

John Baez (Feb 20 2023 at 07:54):

David Egolf said:

Thinking about join-semilattices sounds interesting!
John Baez said:

Do you see why any join-semilattice is a commutative monoid?

Well, we can decategorify a join-semilattice to get a commutative monoid. Join-semilattices have binary coproducts to provide the composition of elements, and an initial object to provide a neutral element in the monoid. The decategorified monoid will be commutative because the binary coproduct operation is commutative up to isomorphism.

This is all correct!  Decategorifying a poset is a rather mild operation, since when we decategorify we take isomorphism classes of objects, but in a poset isomorphic objects are already equal!   (As you said.)

Sam Speight (Feb 20 2023 at 08:08):

David Egolf said:

Graham Manuell said:

Yes. The proof is just like the usual proof that a small complete category is a preorder.

Thanks for the link! This is quite interesting. I may ask some questions about this proof in a separate thread, to keep this one organized.

Note that while this holds classically, it does not hold constructively in general.

Graham Manuell (Feb 20 2023 at 13:55):

Yes, though I think the finite version does hold constructively, depending on what you mean by finite.

Sam Speight (Feb 20 2023 at 15:59):

(deleted)

Sam Speight (Feb 20 2023 at 16:02):

Graham Manuell said:

Yes, though I think the finite version does hold constructively, depending on what you mean by finite.

Ah interesting! Even as I wrote I wondered whether small=finite is okay! :)

John Baez (Feb 20 2023 at 17:58):

I wonder that too!

Graham Manuell (Feb 20 2023 at 23:24):

The point is that if $X$ and $B$ are Bishop-finite and $|B| > 1$ then $B^X$ can't inject into $X$ even constructively since we have $b^n > n$ for $b \ge 2$.