Lecture 72 - Chapter 4: Monoidal Categories

John Baez · August 2018

In the last few lectures, we have seen how to describe complex systems made out of many parts. Each part has abstract wires coming in from the left standing for 'requirements' - things you might want it to do - and from the right standing for 'resources' - things you might need to give it, so it can do what you want:

We've seen that these parts can be stuck together in series, by 'composition':

and in parallel, using 'tensoring':

One reason I wanted to show you this is for you to practice reasoning with diagrams in situations where you can both compose and tensor morphisms. Examples include:

functions between sets
linear maps between vector spaces
electrical circuits
PERT charts
the example we spent a lot of time on: feasibility relations
or more generally, $\mathcal{V}$-enriched profunctors.

The kind of structure where you can compose and tensor morphisms is called a 'monoidal category'. This is a category $\mathcal{C}$ together with:

a functor $\otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C} $ called tensoring,
an object $I \in \mathcal{C}$ called the unit for tensoring,
a natural isomorphism called the associator

$$ \alpha_{X,Y,Z} \colon (X \otimes Y) \otimes Z \stackrel{\sim}{\longrightarrow} X \otimes (Y \otimes Z) $$

a natural isomorphism called the left unitor

$$ \lambda_X \colon I \otimes X \stackrel{\sim}{\longrightarrow} X $$

and a natural isomorphism called the right unitor

$$ \rho_x \colon X \otimes I \stackrel{\sim}{\longrightarrow} X $$

such that the associator and unitors obey enough equations so that all diagrams built using tensoring and these isomorphisms commute.

We need the associator and unitors because in examples it's usually not true that $ (X \otimes Y) \otimes Z$ is equal to $X \otimes (Y \otimes Z)$, etc. They're just isomorphic! But we want the associator and unitors to obey equations because they're just doing boring stuff like moving parentheses around, and if we use them in two different ways to go from, say,

$$ ((W \otimes X) \otimes Y) \otimes Z) $$ to

$$ W \otimes (X \otimes (Y \otimes Z)) $$ we want those two ways to agree! Otherwise life would be too confusing.

If you want to see exactly what equations the associator and unitors should obey, read this:

John Baez, Some definitions everyone should know.

But beware: these equations, discovered by Mac Lane in 1963, are a bit scary at first! They say that certain diagrams built using tensoring, the associator and unitors commute, and the point is that Mac Lane proved a theorem saying these are enough to imply that all diagrams of this sort commute.

This result called 'Mac Lane's coherence theorem'. It's rather subtle; if you're curious about the details try this:

Peter Hines, Reconsidering MacLane:the foundations of categorical coherence, October 2013.

Note: monoidal categories may not necessarily have a natural isomorphism

$$ \beta_{X,Y} \colon X \otimes Y \stackrel{\sim}{\longrightarrow} Y \otimes X .$$ When we have that, obeying some more equations, we have a 'braided monoidal category'. You can see the details in my notes. And when our braided monoidal category has the feature that braiding twice:

$$ X\otimes Y \stackrel{\beta_{X,Y}}{\longrightarrow } Y \otimes X \stackrel{\beta_{Y,X}}{\longrightarrow } X \otimes Y $$ is the identity, we have a 'symmetric monoidal category'. In this case we call the braiding a symmetry and often write it as

$$ \sigma_{X,Y} \colon X \otimes Y \stackrel{\sim}{\longrightarrow} Y \otimes X $$ since the letter $\sigma$ should make you think 'symmetry'.

All the examples of monoidal categories I listed are actually symmetric monoidal - unless you think of circuit diagrams as having wires in 3d space that can actually get tangled up with each other, in which case they are morphisms in a braided monoidal category.

Puzzle 278. Use the definition of monoidal category to prove the interchange law

$$ (f \otimes g) (f' \otimes g') = ff' \otimes gg' $$ whenever $f,g,f',g'$ are morphsms making either side of the equation well-defined. (Hint: you only need the part of the definition I explained in my lecture, not the scary diagrams I didn't show you.)

Puzzle 279. Draw a picture illustrating this equation.

Puzzle 280. Suppose $f : I \to I$ and $g : I \to I$ are morphisms in a monoidal category going from the unit object to itself. Show that

$$ fg = gf .$$ To read other lectures go here.

Igor Kulieshov · August 2018

Puzzle 279 Here's my attempt: tensoring

To show that $h = f' \circ f$ and $e = g' \circ g$ (Exercise 278), we need the triangles in the picture (bottom) commute. Here I stuck - while $f' \circ f$ and $g' \circ g $ are natural candidates for $h$ and $e$ respectively, they are not the only ones.

One possible explanation is that we need the morphisms $f \otimes g $ and $f' \otimes g'$ of the $C \times C$ category to be composable, such that $(f' \otimes g') \circ (f \otimes g) = (h \otimes e)$, and this in turn implies that $h = f'\circ f$ and $e = g'\circ g$, but I'm waiting for a more formal explanation.

Anindya Bhattacharyya · August 2018

@Igor note that $\otimes$ is a functor – which tells us it preserves composition...

Reuben Cohn-Gordon · August 2018

280: my thought process: consider a monoid where morphisms I->I are elements and multiplication is composition. Then the exercise is asking to show that this monoid is commutative. This sounds like the Eckmann-Hilton argument.

Concretely (but with mistakes I need help with) note that $(f \otimes g) \circ (a \otimes b) = (f \circ a) \otimes (g \circ b) $ which is to say that $ \otimes $ is a functor as Anindya noted (but I suppose this also needs to be shown). I've described this as an equality, but is that too strong?

Then $id $ = $id \circ id$ = $ (I \otimes id) \circ (id \otimes I) $ = $ (I \circ id) \otimes (id \circ I) $ = $ I \otimes I $ = $I $ . Again, lots of these equalities are clearly wrong. Not least because there's no morphism from X to $ I \otimes X $. Moreover, id is a morphism and I is an object. They're definitely not equal, although for id restricted to I, they might be isomorphic.

One continues as on https://en.wikipedia.org/wiki/Eckmann–Hilton_argument to show that a.b = b.a: I'm not bothering with that yet, because I want to debug my conceptual confusion this far / check if I'm doing something reasonable.

Edit 1: hmm okay, $ (id \circ I) $ isn't even well-typed.

Edit 2: aha! maybe what I should show is, instead: for any morphism f : $I \to I $, f is isomorphic to $ id $. Then commutativity of fg and gf follows trivially. This is easier: $ f \approx (f \otimes f) = ((f \circ id) \otimes (id \circ f) ) = ((f \otimes id) \circ (id \otimes f) ) = (id \otimes id ) \approx id $ . This is still clearly wrong somehow, but maybe less wrong?

John Baez · August 2018

Anindya's clue for Puzzle 278 is worth exploring. Someone please take the definition of functor, apply it to the functor

$$ \otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C} , $$ and see what each clause actually says.

I'll add that Puzzle 278 is the key to solving Puzzle 280.

John Baez · August 2018

Reuben wrote approximately:

Concretely (but with mistakes I need help with) note that $(f \otimes g) \circ (f' \otimes g') = (f \circ f') \otimes (g \circ g') $ which is to say that $ \otimes $ is a functor as Anindya noted (but I suppose this also needs to be shown).

What's "this"?

You don't need to show $\otimes$ is a functor; we're assuming we have a monoidal category $\mathcal{C}$ so we're assuming among other things that $\otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C}$ is a functor?

You do need to show that $(f \otimes g) \circ (f' \otimes g') = (f \circ f') \otimes (g \circ g') $; that's Puzzle 278.

More precisely, you don't need to show it, but someone needs to show it.

I've described this as an equality, but is that too strong?

I suggest taking the definition of functor, applying it to $\otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C}$, and seeing what each clause gives, concretely. There is nothing so enlightening, nor soothing to the soul, as taking a definition and seeing what it says in a specific case.

John Baez · August 2018

Reuben wrote:

Then $id $ = $id \circ id$ = $ (I \otimes id) \circ (id \otimes I) $ = $ (I \circ id) \otimes (id \circ I) $ = $ I \otimes I $ = $I $ . Again, lots of these equalities are clearly wrong.

I'm glad you say that they're clearly wrong.

The most scary thing is that you're tensoring a morphism $id$ with an object $I$ - or at least, that's what it looks like, since I said in the lecture that $I \in \mathbf{Ob}(\mathcal{C}) $ is the unit object for the tensor product, while $ id $ is a standard name for an identity morphism from some object to itself - you're not saying which one. Overall, you seem to be saying the morphism $id$ is equal to the object $I$, which can't possibly be true.

There are people who tensor morphisms with objects, but nothing I said in the lecture enouraged doing that, or said what it would mean... so let's only tensor objects with objects, and morphisms with morphisms, okay? That's what the functor

$$ \otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C} $$ lets us do, and this should be enough for our puzzles here.

Ken Scambler · August 2018

I have some questions about the definitions PDF you linked to above, hopefully not too off topic.

Def 12 on monoidal equivalence rubs me strangely, because FG->1 and GF->1 feel like they "want" to be a unit & counit, as from an adjunction, or like a compact category. Except it's a counit & pseudo-counit! What am I to make of this?

Theorem 1, MacLane's theorem - is this similar to how we got a "skeletal" poset out of a preorder by collapsing all the isomorphisms?

Michael Hong · August 2018

Puzzle 278

Assuming $\otimes$ is functor, it will map objects and morphisms as below:

monoidal category

It will also conserve composition of morphisms:

$\otimes((f \circ f'),(g \circ g')) = \otimes(f,g) \circ \otimes(f',g')$

It also needs to conserve identities:

$id_x \otimes id_y = id_{x \otimes y}$

Igor Kulieshov · August 2018

Michael Hong, as always an excellent drawing, thank you! Concerning $\otimes((f \circ f'),(g \circ g')) = \otimes(f,g) \circ \otimes(f',g')$

We have a product $C \times C$, which has as objects ordered pairs $(x, y)$, and morpisms between such pairs, also ordered pairs like $(f, g)$, so $C \times C((x, y), (x', y')) = C(x, x') \times C(y, y'))$. This is all we know from definition.
Let's say the functor $\otimes$ maps an ordered pair $(f, g) $ to some morphism $a: C \to C$, and $(f', g')$ to $b: C \to C$, like this: $\otimes(f, g) = a$ and $\otimes(f', g') = b$, and of course preserves composition $\otimes((f' g') \circ (f, g)) = \otimes((f',g')) \circ \otimes((f,g))$.

What I need to figure out what is $(f' ,g') \circ (f, g)$. We have a lot of morphisms to choose from - $C \times C((x, y), (x'', y'')) = C(x, x'') \times C(y, y''))$, and among them, by definition of category, we have a morphism $(f' \circ f, g' \circ g)$. So we picked it up as the only candidate for $(f', g') \circ (f, g)$, which makes perfect sense, but still I'm not sure how to show this.

John Baez · August 2018

Great answer to Puzzle 278, Michael!

Igor wrote:

What I need to figure out what is $(f' ,g') \circ (f, g)$.

Okay, you're trying to figure out how to compose two morphisms in $\mathcal{C} \times \mathcal{C}$. For this you can look at Lecture 52, where I explained how to compose morphisms in a product of categories:

Theorem. For any categories $\mathcal{X}$ and $\mathcal{Y}$, there is a category $\mathcal{X} \times \mathcal{Y}$ for which:

An object is a pair $ (x,y) \in \mathrm{Ob}(\mathcal{X}) \times \mathrm{Ob}(\mathcal{Y}) $.

A morphism from $ (x,y) $ to $ (x',y') $ is a pair of morphisms $ f: x \to y'$ and $g: y \to y'$. We write this as $ (f,g) : (x,y) \to (x',y') $.

We compose morphisms as follows:

$$ (f',g') \circ (f,g) = (f' \circ f, g' \circ g) .$$

Identity morphisms are defined as follows:

$$ 1_{(x,y)} = (1_x, 1_y) .$$
Proof. Just check associativity and the right/left unit laws. $ \qquad \blacksquare $

John Baez · August 2018

Ken wrote:

Def 12 on monoidal equivalence rubs me strangely, because FG->1 and GF->1 feel like they "want" to be a unit & counit, as from an adjunction, or like a compact category. Except it's a counit & pseudo-counit! What am I to make of this?

Your instincts are good, but there's nothing wrong here.

Just so everyone knows what we're talking about, it's this definition:

Definition 12. If $C$ and $D$ are monoidal categories, a monoidal functor $F \colon C \to D$ is a monoidal equivalence if there is a monoidal functor $G \colon D \to C$ such that there exist monoidal natural isomorphisms $\alpha \colon FG \Rightarrow 1_C$, $\beta \colon GF \Rightarrow 1_D$.

Note that $\alpha$ and $\beta$ are required to be invertible in this definition: they are isomorphisms. So, I could equally well have written the definition with either of them turned around, like this:

Definition 12${}^\prime$. If $C$ and $D$ are monoidal categories, a monoidal functor $F \colon C \to D$ is a monoidal equivalence if there is a monoidal functor $G \colon D \to C$ such that there exist monoidal natural isomorphisms $\alpha \colon 1_C \Rightarrow FG $, $\beta \colon GF \Rightarrow 1_D$.

This makes them look more like the 'unit' and 'counit' in a compact closed category, which we have been calling the 'cup' and 'cap'. And that's actually good! Maybe I should have written the definition this way - but I wasn't writing it for people who knew about compact closed categories, so I figured they'd be more puzzled by

$$ \alpha \colon 1_C \Rightarrow FG , \qquad \beta \colon GF \Rightarrow 1_D $$ than by the superficially more symmetrical

$$ \alpha \colon FG \Rightarrow 1_C, \qquad \beta \colon GF \Rightarrow 1_D. $$ Note also, Ken, that:

1) We could delete the word 'monoidal' everywhere and get a simpler and incredibly important concept, which alas we have not yet discussed in this course:

Definition. If $C$ and $D$ are categories, a functor $F \colon C \to D$ is an equivalence if there is a functor $G \colon D \to C$ such that there exist natural isomorphisms $\alpha \colon 1_C \Rightarrow FG $, $\beta \colon GF \Rightarrow 1_D$.

2) In these definitions we are not imposing the snake equations (aka zig-zag equations) for $\alpha$ and $\beta$, unlike what we've done for cups and caps.

3) However, there's a wonderful theorem that if we have $\alpha$ and $\beta$ as above, we can always improve them in a systematic way to get new ones that do satisfy the snake equations! Then we say we have an adjoint equivalence, because then $F$ and $G$ are also adjoint functors.

4) This works equally well in the monoidal situation: every monoidal equivalence can be improved to give a monoidal adjoint equivalence, meaning one where $\alpha$ and $\beta$ obey the snake equations.

John Baez · August 2018

Ken wrote:

Theorem 1, MacLane's theorem - is this similar to how we got a "skeletal" poset out of a preorder by collapsing all the isomorphisms?

NO!!!

That's a mistake every newcomer makes. It's a natural guess, but fact Mac Lane's theorem is proved by making the monoidal category very 'fat', the opposite of skeletal.

Unlike a preorder, a skeletal category still has lots of isomorphisms: it's just that they go from an object to itself. So, to make the associator and unitor isomorphisms between identity morphisms, it doesn't help to make the category skeletal. In fact it makes it harder!

It would take quite a while to explain this, and I don't have the energy, but it's fairly rare for a monoidal category to be both strict and skeletal. To get a vague sense of how tricky things are: the category of finite sets with $\times$ as its monoidal structure is monoidally equivalent to one that's both strict and skeletal, but not the category of all sets.

Igor Kulieshov · August 2018

Ken wrote:

Def 12 on monoidal equivalence rubs me strangely, because FG->1 and GF->1 feel like they "want" to be a unit & counit

Yes, I was also waiting for an opportunity to ask about existence of identities similar to that of adjoints and what do they mean. Here are a few pictures: equiv coequiv

So as I understand, equivalence means that we are trying to find a similar piece of structure between $C$ and $D$, and once we found it, we want some property being preserved. Still I need to catch up, so what I'm saying further is not precise at all, but it seems that with equivalence we are preserving products (or more generally limits). Also it seems that monoidal products can be constructed using products in a category. For example we can have a functor $\otimes: (b, c) \mapsto a, (b, a) \mapsto a, (c, a) \mapsto a$, and using it we make $C$ into monoidal category. Similarly for co-equivalence (I totally made up this, need to find out what it name is), when you have natural transformation arrows reversed - this time we preserve coproducts.

From these one can easily pick up unit and counit. Using unit $1_C \Rightarrow G \circ F$ we contract $C$ to $G \circ F$ along morphisms, and using counit $F \circ G \Rightarrow 1_D $ we ensure that $G \circ F \circ G \circ F$ is naturally isomorphic to $G \circ F$.

Hopefully at least something from above makes any sense.

EDIT 1 While I was writing this, John already answered this question in 11.

Igor Kulieshov · August 2018

John, thanks for the answer in 10!

This was a missing piece of the puzzle - I forgot that this is a part of definition of a product of categories. Still, what is the shortest and the most correct answer to the puzzle 278, how to formulate it?

Igor Kulieshov · August 2018

Here come a few more questions, I apologize if they were already asked during the course. Again, trying to make things more or less precise, but may fail in that :)

Let's say we have a category $C$, which has all products. Is it true that we can define a functor $\otimes: C \times C \to C$ by pointing each pair $(x, y)$ to the product of $x$ and $y$, $x \leftarrow p \rightarrow y$, and in this way make $C$ somewhat monoidal?
Working with the same category $C$, which happens to have all coproducts, we define a functor $\oplus: C \times C \to C$ by sending each pair $(x, y)$ to their coproduct $x \rightarrow p \leftarrow y$. How this structure ($C, \oplus)$ is called then?
For any other structure $(C, \odot, \boxdot)$ with $\odot: C \times C \to C$ and $\boxdot: C \times C \to C$, where we are using spans and cospans of pairs of elements $(x, y)$ to define $\odot, \boxdot$, is it true that we can always establish a pair of adjoints between $(C, \otimes, \oplus)$ and $(C, \odot, \boxdot)$, using the property of products and coproducts being limits and colimits (so we always can move from a span to a limit, and from a colimit to a cospan in a natural way). So these structures $(C, \odot, \boxdot)$ may be viewed as more relaxed versions of $(C, \otimes, \oplus)$?
Are there any other functor $OP: C \times C \to C$, which is interesting in a certain way, so we can define a structure $(C, \otimes, \oplus, OP)$? The way $\otimes, \oplus$ are defined in 1 and 2 makes them interesting, are there any other universal objects, except for products and coproducts, which can be utilized to construct $OP$ as well?

Michael Hong · August 2018

Igor

Maybe this will help? There is really not much to Puzzle 278. It's pretty much the conservation of composition.

monoidal category composition

Anindya Bhattacharyya · August 2018

@Igor – here's a one-line answer to Puzzle 278:

$(f\otimes g)\circ(f'\otimes g') = \otimes(f, g)\circ\otimes(f', g') = \otimes((f, g)\circ(f', g')) = \otimes(ff', gg') = ff'\otimes gg'$

Anindya Bhattacharyya · August 2018

there's a more revealing diagram for 278 if you use the boxes-and-wires notation @John sketches out at the start of the lecture

Michael Hong · August 2018

Anindya

LOL I wanted to draw that but too late and tired. Will try tmrw.

Igor Kulieshov · August 2018

@Michael, @Anindya, thanks for the help! The second picture is even better than the previous one.

The problem is that in such "obvious" proofs everything is so obvious, that I don't even know how to formulate it and where it is better to start and how to end.

I immediately drew what one may see in 1, it a coarser version of @Michael drawings. It took me less than a minute to see how it works, the remaining question was why we prefer it to work in this way. @Anindya hinted to look into composition, and @John reminded that composition of morphisms works in this way in the product of categories by definition. And then in 17 @Anindya provided a perfect one-liner, thanks! It reads like this to me: since $\otimes$ is a functor, it preseves composition, we use this fact to get to the 3rd equiality in 17, and then realize that composition in the source, product category, is a well defined process.

Anindya Bhattacharyya · August 2018

re Puzzle 280 I think @Reuben is right that we can solve this using the Eckmann-Hilton argument mentioned earlier in this course. Here's as far as I've got.

First note that Puzzle 278 is basically an "exchange law":

$$(f\otimes g)\circ(h\otimes k) = (f\circ h)\otimes(g\circ k)$$ In the special case where $f, k : I \to I$ and $g = h = 1_I$ we get

$$(f\otimes 1)\circ(1\otimes k) = (f\circ 1)\otimes(1\circ k) = f\otimes k$$ But we also have

$$f\otimes k = (1\circ f)\otimes(k\circ 1) = (1\otimes k)\circ(f\otimes 1)$$ This tells us

$$(f\otimes 1)\circ(1\otimes k) = (1\otimes k)\circ(f\otimes 1)$$ ... which is almost $f\circ k = k\circ f$ but not quite.

I think we need to mess about with with left/right unitors and coherence equations to iron out this final step.

Michael Hong · August 2018

Here is a string diagram showing the conservation of composition by the tensor functor. It seems a bit more "categorical" in that it kind of reminds me of a commutative diagram but maybe just coincidence.

monoidal category string diagram

Michael Hong · August 2018

I have a question that has been plaguing me for awhile and this lecture has brought it back to my attention. It seems like once we start talking about categories, all laws or equations are presented as natural transformations like the associator and unitors.

I don't get why we present it as natural transformations.

It seems like this is something important when learning category but I haven't fully understood while building up from definitions.

John Baez · August 2018

Michael wrote:

It seems like once we start talking about categories, all laws or equations are presented as natural transformations like the associator and unitors. I don't get why we present them as natural transformations.

Is there something else you would prefer?

That's usually the best way to think about questions like this. If you're wondering why mathematicians do something in some way, try to do it some other way and see what happens.

For example, consider the tensor product $ \otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C}$. In fact, let's think about a specific example, the cartesian product

$$ \times \colon \mathbf{Set} \times \mathbf{Set} \to \mathbf{Set} .$$ Are you happy with thinking about this as a functor? Maybe you haven't thought about it much. Treating cartesian product as a functor automatically lets us take cartesian products of morphisms (functions) as well as objects (sets). Do you see how given functions

$$ f \colon X \to Y $$ and

$$ f' \colon X' \to Y' $$ we get a function

$$ f \times f' \colon X \times X' \to Y \times Y' \; ? $$ That's nice. Also, the fact that cartesian product is a functor summarizes useful facts like

$$ (g \times g') \circ (f \times f') = (gf \times g'f') .$$ Now consider the associative law. You might hope to express it as an equation:

$$ (X \times Y) \times Z = X \times (Y \times Z) $$ but in fact this equation isn't true! Do you see why not? If you don't see why, maybe someone else can explain why

$$ (X \times Y) \times Z \ne X \times (Y \times Z) $$ What we really have is an isomorphism

$$ (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z). $$ However, while there are usually lots of isomorphisms

$$ (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z) $$ for any particular choice of sets $X,Y,Z$, there's a particular 'best' one which we call

$$ \alpha_{X,Y,Z} \colon (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z) .$$ Do you see which one I'm talking about? Can you write down a formula for it?

But even once we have the 'best' isomorphism, how can we make precise the idea that it's the 'best', or at least 'good'? Here's how: the best isomorphism

$$ \alpha_{X,Y,Z} \colon (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z) .$$ is a natural isomorphism. Do you see why it's natural? To show it's natural, you need to check that certain 'naturality squares' commute - remember Lecture 43.

It turns out that requiring naturality picks out the one 'best' isomorphism. Showing this is a bit harder than the other things I've asked you to show, so I'll let you off the hook here. But as you can see, I've asked you to do a lot of little calculations. I think these are required to see what's really going on here. I could do them for you, but it's much better to do these things oneself and build ones mathematical muscles!

John Baez · August 2018

Igor wrote:

Let's say we have a category $\mathcal{C}$, which has all products. Is it true that we can define a functor $\otimes: \mathcal{C} \times \mathcal{C} \to \mathcal{C}$ by pointing each pair $(x, y)$ to the product of $x$ and $y$, $x \leftarrow p \rightarrow y$, and in this way make $\mathcal{C}$ somewhat monoidal?

Yes!

More precisely: given two objects $x$ and $y$ we can define the concept of a product of these objects. Not the product. Anyone who hasn't seen this important definition, and wants to see it now, should go here:

Wikipedia, Product (category theory)

There can be more than one product of $x$ and $y$, but any two choices will be canonically isomorphic: that is, isomorphic in a unique way making a certain diagram commute.

If we choose a product of $x $ and $y$ for every pair of objects in $\mathcal{C}$, we can use this choices to make $\mathcal{C}$ into a monoidal category.

This takes a bit of work: for example, we have to get our hands on the associators and unitors, and show that they obey the necessary laws. Everyone who learns category theory needs to do this work at some point.

But it works. So, there is no need for the word "somewhat" in your question: we do indeed get a monoidal category from any category with products.

Working with the same category $\mathcal{C}$, which happens to have all coproducts, we define a functor $\oplus: \mathcal{C} \times \mathcal{C} \to \mathcal{C}$ by sending each pair $(x, y)$ to their coproduct $x \rightarrow p \leftarrow y$. How this structure ($\mathcal{C}, \oplus)$ is called then?

We also get a monoidal category form any category with coproducts! Again, we need to pick a specific coproduct for each pair of objects. And again, people who don't know about coproducts should turn to Wikipedia:

Wikipedia, Coproduct.

Products and coproducts are the two most important ways of getting monoidal categories, so your questions here are very good. The first kind of monoidal category is called a cartesian monoidal category, while the second kind is called a cocartesian monoidal category.

They're connected: $\mathcal{C}$ is cartesian monoidal iff $\mathcal{C}^{\text{op}}$ is cocartesian monoidal.

There is more to say, but I hope this is good for starters.

John Baez · August 2018

Igor wrote:

Still, what is the shortest and the most correct answer to the puzzle 278, how to formulate it?

'Shortest' and 'most correct' are complementary quantities. Anindya wins the prize for brevity in comment #17:

$(f\otimes g)\circ(f'\otimes g') = \otimes(f, g)\circ\otimes(f', g') = \otimes((f, g)\circ(f', g')) = \otimes(ff', gg') = ff'\otimes gg'$

and every step here is perfectly correct... but the best possible answer will explain why each step is valid. So, something like this would make me very happy;

Solution to Puzzle 278.

Suppose $\mathcal{C}$ is a monoidal category. It is equipped with a functor

$$ \otimes \colon \mathcal{C} \times \mathcal{C} \to \mathcal{C}. $$ Since a functor preserves composition, if we take any composable morphisms $ (f,g) $ and $ (f',g') $ in $ \mathcal{C} \times \mathcal{C} $ we must have

$$ \otimes ( (f,g) \circ (f',g')) = \otimes (f,g) \; \circ \; \otimes (f',g') .$$ However, we compose morphisms in $ \mathcal{C} \times \mathcal{C} $ componentwise, so

$$ (f,g) \circ (f',g') = (f\circ f', g \circ g'). $$ Thus, the previous equation gives

$$ \otimes ( f \circ f', g \circ g' ) = \otimes (f,g) \; \circ \; \otimes (f',g'). $$ Moreover, we usually write the effect of applying the functor $ \otimes $ to a pair $ (f,g) $ not as $ \otimes (f,g) $ but as $ f \otimes g$. If we do this three times above, we get the interchange law

$$ (f \circ f') \otimes (g \circ g') = (f \otimes g) \circ (f' \otimes g'). $$

John Baez · August 2018

Michael wrote:

Yes! This is an almost perfect pictorial explanation of the interchange law

$$ (f \circ f') \otimes (g \circ g') = (f \otimes g) \circ (f' \otimes g'). $$ As you note, it's a commutative square: tensoring and then composing equals composing and then tensoring.

A couple of nitpicky criticisms:

1) it's best to use arrows like this

$$ f \colon X \longrightarrow Y $$ or this

$$ X \stackrel{f}{\longrightarrow} Y $$ to stand for a function $f $ from the set $X$ to the set $Y$ (or a morphism between objects), while using \mapsto arrows

$$ f \colon x \mapsto y $$ to indicate that the function $f$ maps the element $x \in X$ to the element $y \in Y$. They are completely different kinds of arrows!

So I'd use $\mapsto$ for the big arrows in your diagram.

2) A bit more importantly, two of your big arrows have complicated labels that do not describe those processes but rather the result of applying those processes. I would probably write $\otimes$ above the bottom horizontal arrow and $ \circ $ next to the right vertical arrow.

Jonathan Castello · August 2018

Michael wrote:

I have a question that has been plaguing me for awhile and this lecture has brought it back to my attention. It seems like once we start talking about categories, all laws or equations are presented as natural transformations like the associator and unitors.

I don't get why we present it as natural transformations.

It seems like this is something important when learning category but I haven't fully understood while building up from definitions.

I've seen similar things crop up in topology; for instance, a topological space $T$ is Hausdorff iff the diagonal $\Delta = \{(x, x) \mid x \in T\}$ is a closed set in $T \times T$. There's something very pleasant about being able to embed a property, a kind of external observation about an object, as an internal feature of that object's structure. Giving laws in terms of natural transformations has the same feel: we're specifying that the category under consideration possesses some extra internal features that reify desirable properties.

Maybe a slightly more accurate comparison is with the idea of a "metric space" vs. a "metrizable space". A metric space is a space coupled with a metric; a metrizable space is merely one that can be generated by some undetermined metric. The latter has the feel of a property; the former has the feel of structure.

(In other news, I'm getting forum notifications again. Huzzah!)

Anindya Bhattacharyya · August 2018

ok I think I've got a solution to Puzzle 280

Suppose $f : I \to I$ and $g : I \to I$ are morphisms in a monoidal category going from the unit object to itself. Show that $fg = gf$.

We've seen earlier how to prove

$$(1\otimes f)\circ(k\otimes 1) = (k\otimes 1)\circ(1\otimes f)$$

I've switched $f$ and $k$ around to match the diagram below, sorry!

The other ingredient we need is the fact that $\lambda_I = \rho_I : I \otimes I \to I$

This is listed in Mac Lane as one of the coherence equations, although more recent treatments seem to omit it. I'm assuming this because it can be derived from the other two equations ("pentagon" and "triangle"). I'm at a loss as to how to go about this, however.

Putting these together we get the following commutative diagram:

The central diamond commutes because of the result proved earlier, and the wonky squares are all naturality diagrams.

The outer square, together with $\lambda_I = \rho_I$, gives us what we're looking for: $f\circ k = k\circ f$

Marius Furter · August 2018

Nice answer for Puzzle 280 Anindya! I had just worked out something similar based on your earlier equation, but you beat me to it. I'll post my diagrams anyway for an additional perspective. (Note that I reverted back to $f$ and $g$)

You showed that the top square of this cube commutes:

The sides commute because of the naturality conditions and because in our case $\lambda_I = \rho_I$

Where $UR(x,-) = x $ and $UL(-,x) = x $

Since the top and sides of the square commute, so does the bottom.

Anindya Bhattacharyya · August 2018

oh of course, it's a cube! I missed that simplification.

Igor Kulieshov · August 2018

@Marius, it's a super-cube in 30!

EDIT: btw, $fg = gf$ implies that composition of morphisms in $C(I, I)$ is commutative, it is interesting whether there are other implications for $I$.

John Baez · August 2018

Excellent solutions to Puzzle 280, folks! I guess it was a bit sadistic to assign this without mentioning that $\rho_I = \lambda_I$.

Anindya wrote:

This is listed in Mac Lane as one of the coherence equations, although more recent treatments seem to omit it. I'm assuming this because it can be derived from the other two equations ("pentagon" and "triangle").

Yes, right now I'm forgetting who first noticed that this can be derived from the other ones.

A more reasonable definition of monoidal category might say that all diagrams built using tensor products, composition, $I$, $\alpha$, $\rho$ and $\lambda$ commute. While trimming down this infinite set of equations to the bare minimum is nice, using this bare minimum as the definition of monoidal category makes this concept look rather mysterious at first.

However, correctly stating that "all diagrams built using tensor products, composition, $I$, $\alpha$, $\rho$ and $\lambda$ commute" is actually a bit tricky: if you say this the wrong way it will be false.

So, people state the bare minimum set of equations - Mac Lane had three but nowadays we use just two: the "pentagon" and "triangle". Then, Mac Lane's coherence theorem says these imply all the rest. Here's a precise statement, and sketch of the proof:

nLab, Mac Lane's proof of the coherence theorem for monoidal categories.

It's a pretty technical inductive argument. But this page does give a nice explanation of why a naive formulation of "all diagrams built using tensor products, composition, $I$, $\alpha$, $\rho$ and $\lambda$ commute" doesn't actually work.

John Baez · August 2018

Igor wrote:

Btw, $fg = gf$ implies that composition of morphisms in $\mathcal{C}(I, I)$ is commutative, it is interesting whether there are other implications for $I$.

Not much:

Theorem. For any commutative monoid $A$, there is a monoidal category $\mathcal{C}$ with just one object $ I $ (the unit for the tensor product) such that $ \mathcal{C}(I,I) = A$, with both tensor product and composition equal to the multiplication in $A$.

In simpler, rougher terms: a one-object monoidal category is the same as a commutative monoid.

Michael Hong · August 2018

John wrote:

So I'd use $\mapsto$ for the big arrows in your diagram.

2) A bit more importantly, two of your big arrows have complicated labels that do not describe those processes but rather the result of applying those processes. I would probably write $\otimes$ above the bottom horizontal arrow and $ \circ $ next to the right vertical arrow.

Here is a version with the corrections:

monoidal category string diagram

Anindya Bhattacharyya · August 2018

Thanks for those pointers @John – fyi the nLab page says the fact we can derive $\lambda_I = \rho_I$ from the pentagon and triangle was first proved by Kelly in this 1964 paper:

On MacLane's conditions for coherence of natural associativities, commutativities, etc

I've tried working through the proof of the coherence theorem several times but without success. I'll have another go using that nLab page which might offer some clues about the bits I got stuck on.

Michael Hong · August 2018

John, thanks for the guideline to better understanding!

Is there something else you would prefer? $$ \times \colon \mathbf{Set} \times \mathbf{Set} \to \mathbf{Set} .$$ Are you happy with thinking about this as a functor?

Actually, I was thinking why not a functor LOL. But associativity is built off of the product functor so it has to be a natural transformation! So if we set the cartesian product as a functor and all equations using the cartesian product will be a natural transformation.

$$ (X \times Y) \times Z = X \times (Y \times Z) $$ but in fact this equation isn't true! Do you see why not? If you don't see why, maybe someone else can explain why

Yes, they are not equal because the tuple is structured differently ie wearing different clothes. More specifically, if they are equal then $(X \times Y) = X \text{ and } Z = (Y \times Z)$ which not true generally (this can be true for monoidal products when $ Y=I$). But they are isomorphic since the cardinalities are the same.

However, while there are usually lots of isomorphisms $$ (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z) $$ for any particular choice of sets $X,Y,Z$, there's a particular 'best' one which we call $$ \alpha_{X,Y,Z} \colon (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z) .$$ Do you see which one I'm talking about? Can you write down a formula for it?

If I am not mistaken, the "lots of isomorphisms" is referring to the fact that there are many instances of tuples that are isomorphic? The best one is the one that can describe all of those isomorphisms. As you pointed out, it is $\alpha_{X,Y,Z}$ which needs to satisfy $\alpha_{XYZ}^{-1} \alpha_{XYZ} = 1_{(XY)Z} \text{ and } \alpha_{XYZ} \alpha_{XYZ}^{-1} = 1_{X(YZ)}$ and $\alpha_{X',Y',Z'} \circ F(f,f',f'') = G(f,f',f'') \circ \alpha_{X,Y,Z}$?

But even once we have the 'best' isomorphism, how can we make precise the idea that it's the 'best', or at least 'good'? >Here's how: the best isomorphism $$ \alpha_{X,Y,Z} \colon (X \times Y) \times Z \stackrel{\sim}{\rightarrow} X \times (Y \times Z) .$$ is a natural isomorphism. Do you see why it's natural? To show it's natural, you need to check that certain 'naturality squares' commute - remember [Lecture 43]

This is probably wrong but the best I could do... We need the diagram above to commute giving us the following equations: $$f_x=\rho_x f_{x(yz)}=\pi_x \rho_{xy} f_{(xy)z}$$ $$f_y=\pi_y \rho_{yz} f_{x(yz)}=\pi_y \rho_{xy} f_{(xy)z}$$ $$f_z=\rho_z f_{(xy)z}=\pi_z \rho_{yz} f_{x(yz)}$$ $$\alpha_{xyz} f_{(xy)z} = f_{x(yz)}$$ $$\alpha_{xyz}^{-1} f_{x(yz)} = f_{(xy)z}$$ The last two equations when factored out will extract each component x,y,z from both sides. For example: $$\rho_x = \pi_x \rho_{xy} \alpha_{xyz}^{-1}$$ Ultimately, it seems that the associativity isomorphism stems from the fact that these are just tuples in disguise and the cardinality is the same no matter where you put the parentheses since it always factors down the triangle? The last two questions are still unclear to me...

Anindya Bhattacharyya · August 2018

OK with a few pointers from that paper I've got a proof that $\lambda_I = \rho_I : I\otimes I\to I$.

First we note that $\rho$ is natural, so for any $\phi : I\otimes I\to I$ we have $\phi\circ\rho_{I\otimes I} = \rho_I\circ(\phi\otimes 1_I)$.

Setting $\phi = \rho_I$ gives us $\rho_I\circ\rho_{I\otimes I} = \rho_I\circ(\rho_I\otimes 1_I)$.

But $\rho_I$ is an isomorphism, so we can conclude that $\rho_{I\otimes I} = \rho_I\otimes 1_I$.

Setting $\phi = \lambda_I$ gives us $\lambda_I\circ\rho_{I\otimes I} = \rho_I\circ(\lambda_I\otimes 1_I)$.

Combining these two gives us $\lambda_I\circ(\rho_I\otimes 1_I) = \rho_I\circ(\lambda_I\otimes 1_I)$.

Here's a couple of diagrams for this stage:

For the second bit we need two "triangle" equations:

$\qquad\rho_A\otimes 1_C = (1_A\otimes\lambda_C)\circ\alpha_{A, I, C} : (A\otimes I)\otimes C\to A\otimes C$

$\qquad\lambda_B\otimes 1_C = \lambda_{B\otimes C}\circ\alpha_{I, B, C} : (I\otimes B)\otimes C\to B\otimes C$

The first of these is one of the standard coherence equations from the definition of a monoidal category. The second one can be derived from the first one together with the "pentagon" diagram – although this is a little fiddly, so let's just assume it for now.

Setting $A = B = C = I$ in the triangle equations, and using the naturality of $\lambda$, we get the following diagram:

The outer square tells us $\lambda_I\circ(\lambda_I\otimes 1_I) = \lambda_I\circ(\rho_I\otimes 1_I)$.

But $\lambda_I$ is an isomorphism, hence $\lambda_I\otimes 1_I = \rho_I\otimes 1_I$.

Combining this with $\lambda_I\circ(\rho_I\otimes 1_I) = \rho_I\circ(\lambda_I\otimes 1_I)$ proved above gives us $\lambda_I = \rho_I$. QED

Anindya Bhattacharyya · August 2018

The final bit of the puzzle is proving the second triangle equation from the first one and the pentagon. I'll just sketch a proof here.

The trick here is to tensor the second triangle equation by $A$ on the left. This looks like it's making it more complicated, but the fact we now have a four-fold product allows us to use the pentagon diagram to go from $A\otimes ((I\otimes B)\otimes C)$ to $A\otimes (I\otimes (B\otimes C))$ the "long way round".

At each stage we knock out the $I$ with a suitable unitor. This gives us the following diagram:

The quads (2) and (4) are both naturality diagrams for associators. The triangles (3) and (5) are both instances of the first triangle equation (in the case of (3) we've tensored everything by $I$ on the right). Note also that $1_{B\otimes C} = 1_B \otimes 1_C$, which is what allows us to "glue" the sides of (4) and (5) together.

Now since the outer pentagon commutes, and (2), (3), (4), (5) commute, we must have (1) commutes. To remove the $A$, we simply set it equal to $I$ then apply the natural isomorphism $\lambda$ to get our second triangle equation $\lambda_B\otimes 1_C = \lambda_{B\otimes C}\circ\alpha$.

Marius Furter · August 2018

Michael wrote in 37:

The last two questions are still unclear to me...

Remember that in the case of a natural transformation $\alpha: F \rightarrow G $ you have two functors $F, G : \mathcal{C} \rightarrow \mathcal {D}$ and that for objects $A$ and $B$ in $\mathcal{C}$ and morphism $f : A \rightarrow B$ we need to have $\alpha_B \circ F(f) = G(f) \circ \alpha_A$

In this case we have functors $LP, RP: \mathcal{C} \times \mathcal{C} \times \mathcal{C} \rightarrow \mathcal{C} $ and we need to show that the following sqaures commute:

or with the functors applied:

Also, remember how the product functor acts on morphisms:

With these hints and your projection diagram, you should be able to solve the problem.

John Baez · August 2018

I just found some nice slides on Mac Lane's coherence theorem, which says roughly that all diagrams built using tensor products, the unit object, associators and unitors in a monoidal category commute:

Peter Hines, Reconsidering MacLane:the foundations of categorical coherence, October 2013.

It goes into a lot of the subtleties... which is good if the subtleties matter to you.

I'll add this reference to the lecture.

Michael Hong · August 2018

Marius

It took a while but I think I finally got what you are saying. The "best" one is the natural transformation $\alpha: LP \rightarrow RP$ without applying it to individual objects and morphisms since if we apply it, they would be instances and therefore are themselves objects and morphisms not natural transformations. The naturality squares it needs to satisfy are the two squares you have shown : $RP(f_x,f_y,fz) \alpha_{XYZ} = \alpha_{XYZ}LP(f_x,f_y,f_z)$ and $LP(f_x,f_y,fz) \alpha_{XYZ}^{-1} = \alpha_{XYZ}^{-1}RP(f_x,f_y,f_z)$.

Thanks!

John Baez · August 2018

Michael wrote:

John wrote:

$$ (X \times Y) \times Z = X \times (Y \times Z) $$ but in fact this equation isn't true! Do you see why not? If you don't see why, maybe someone else can explain why.

Yes, they are not equal because the tuple is structured differently i.e. wearing different clothes. More specifically, if they are equal then $(X \times Y) = X \text{ and } Z = (Y \times Z)$ which not true generally (this can be true for monoidal products when $ Y=I$).

Hmm. I would have said this. The cartesian product of sets is usually defined to be a set of ordered pairs:

$$ X \times Y = \lbrace (x,y) : x \in X, y \in Y \rbrace .$$ Given this definition, we can work out $ (X \times Y) \times Z $ and $ X \times (Y \times Z) $ and see that they are different sets. (Can you or someone else do it?)

However, we can also see an obvious one-to-one correspondence between these sets! We can write down a formula for this bijection and call it the associator

$$ \alpha_{X,Y,Z} \colon (X \times Y) \times Z \to X \times (Y \times Z). $$ (Can you or someone else do it?)

Of course, there will usually be other bijections. For example, suppose $X,Y$ and $Z$ each have 10 elements. Then $ (X \times Y) \times Z $ and $ X \times (Y \times Z) $ will each have 1000 elements, so there will be many bijections between them. To be precise, there will be

402,387,260,077,093,773,543,702,433,923,003,985,719,374,864, 210,714,632,543,799,910,429,938,512,398,629,020,592,044,208, 486,969,404,800,479,988,610,197,196,058,631,666,872,994,808, 558,901,323,829,669,944,590,997,424,504,087,073,759,918,823, 627,727,188,732,519,779,505,950,995,276,120,874,975,462,497, 043,601,418,278,094,646,496,291,056,393,887,437,886,487,337, 119,181,045,825,783,647,849,977,012,476,632,889,835,955,735, 432,513,185,323,958,463,075,557,409,114,262,417,474,349,347, 553,428,646,576,611,667,797,396,668,820,291,207,379,143,853, 719,588,249,808,126,867,838,374,559,731,746,136,085,379,534, 524,221,586,593,201,928,090,878,297,308,431,392,844,403,281, 231,558,611,036,976,801,357,304,216,168,747,609,675,871,348, 312,025,478,589,320,767,169,132,448,426,236,131,412,508,780, 208,000,261,683,151,027,341,827,977,704,784,635,868,170,164, 365,024,153,691,398,281,264,810,213,092,761,244,896,359,928, 705,114,964,975,419,909,342,221,566,832,572,080,821,333,186, 116,811,553,615,836,546,984,046,708,975,602,900,950,537,616, 475,847,728,421,889,679,646,244,945,160,765,353,408,198,901, 385,442,487,984,959,953,319,101,723,355,556,602,139,450,399, 736,280,750,137,837,615,307,127,761,926,849,034,352,625,200, 015,888,535,147,331,611,702,103,968,175,921,510,907,788,019, 393,178,114,194,545,257,223,865,541,461,062,892,187,960,223, 838,971,476,088,506,276,862,967,146,674,697,562,911,234,082, 439,208,160,153,780,889,893,964,518,263,243,671,616,762,179, 168,909,779,911,903,754,031,274,622,289,988,005,195,444,414, 282,012,187,361,745,992,642,956,581,746,628,302,955,570,299, 024,324,153,181,617,210,465,832,036,786,906,117,260,158,783, 520,751,516,284,225,540,265,170,483,304,226,143,974,286,933, 061,690,897,968,482,590,125,458,327,168,226,458,066,526,769, 958,652,682,272,807,075,781,391,858,178,889,652,208,164,348, 344,825,993,266,043,367,660,176,999,612,831,860,788,386,150, 279,465,955,131,156,552,036,093,988,180,612,138,558,600,301, 435,694,527,224,206,344,631,797,460,594,682,573,103,790,084, 024,432,438,465,657,245,014,402,821,885,252,470,935,190,620, 929,023,136,493,273,497,565,513,958,720,559,654,228,749,774, 011,413,346,962,715,422,845,862,377,387,538,230,483,865,688, 976,461,927,383,814,900,140,767,310,446,640,259,899,490,222, 221,765,904,339,901,886,018,566,526,485,061,799,702,356,193, 897,017,860,040,811,889,729,918,311,021,171,229,845,901,641, 921,068,884,387,121,855,646,124,960,798,722,908,519,296,819, 372,388,642,614,839,657,382,291,123,125,024,186,649,353,143, 970,137,428,531,926,649,875,337,218,940,694,281,434,118,520, 158,014,123,344,828,015,051,399,694,290,153,483,077,644,569, 099,073,152,433,278,288,269,864,602,789,864,321,139,083,506, 217,095,002,597,389,863,554,277,196,742,822,248,757,586,765, 752,344,220,207,573,630,569,498,825,087,968,928,162,753,848, 863,396,909,959,826,280,956,121,450,994,871,701,244,516,461, 260,379,029,309,120,889,086,942,028,510,640,182,154,399,457, 156,805,941,872,748,998,094,254,742,173,582,401,063,677,404, 595,741,785,160,829,230,135,358,081,840,096,996,372,524,230, 560,855,903,700,624,271,243,416,909,004,153,690,105,933,983, 835,777,939,410,970,027,753,472,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

bijections between them. But there will be one "best" bijection.

Michael Hong · August 2018

$$ X \times Y = \lbrace (x,y) : x \in X, y \in Y \rbrace .$$ Given this definition, we can work out $ (X \times Y) \times Z $ and $ X \times (Y \times Z) $ and see that they are different sets. (Can you or someone else do it?)

$$( X \times Y) \times Z = \lbrace (a,b) : a \in X \times Y, b \in Z \rbrace .$$ $$ X \times (Y \times Z )= \lbrace (c,d) : c \in X , d \in Y \times Z \rbrace .$$

However, we can also see an obvious one-to-one correspondence between these sets! We can write down a formula for this bijection and call it the associator $$ \alpha_{X,Y,Z} \colon (X \times Y) \times Z \to X \times (Y \times Z). $$ (Can you or someone else do it?)

Let $\pi_1 \text{ and } \pi_2$ be functions that extract out the first and second components respectively. Then a formula for the bijection would be :

$$ \pi_1 a \mapsto c$$ $$ \pi_2 a \mapsto \pi_1 d $$ $$ b \mapsto \pi_2 d $$

To be precise, there will be 402,387,260 ... 000 bijections between them. But there will be one "best" bijection.

This sounded like Dr. Strange from Infinity Wars LOL. I get utterly confused whenever I hear the words "best" or "canonical" in category theory. I think it means the one that can best represent them all in which in this case it would be the associator. If I have to choose from actual bijections, I honestly don't know.

Scott Oswald · August 2018

To be precise, there will be 1000! bijections between them. But there will be one "best" bijection.

Just for clarity, John got that monstruous number by computing 1000! (that's 1000 factorial). Why is the number of bijections 1000! ? For any finite set, the number of bijections is the same as the number of permutations. In fact, permutations are bijections of a set with itself (AKA automorphisms in the category of sets). To see that the number of permutations is $n!$ for a set with cardinality $n$, consider a set $X$. Pick an element $x$, there's permutation that sends $x$ to each of the $n$ elements of $X$. Once you've determined where $x$ is mapped, pick another element $y$. There's a permutation that sends $y$ to each of the $n-1$ remaining elements (you can't send it to the same element as $x$ since permutations are bijections).

By induction, the set of permutations on $X$ is $n(n-1)\ldots 1= n!$.

Anindya Bhattacharyya · August 2018

@Michael – I think we can simplify your answer slightly:

$$ (X \times Y) \times Z = \lbrace \langle\langle x, y\rangle, z\rangle : x \in X, y \in Y, z\in Z \rbrace $$ $$ X \times (Y \times Z) = \lbrace \langle x, \langle y, z\rangle\rangle : x \in X, y \in Y, z\in Z \rbrace $$ $$ \alpha_{X, Y, Z} : \langle\langle x, y\rangle, z\rangle \mapsto \langle x, \langle y, z\rangle\rangle $$ On a related note, is there a rigorous definition of "canonical"? I'd always assumed the term to be (mildly) informal.

Azimuth Forum

Howdy, Stranger!

Categories

Lecture 72 - Chapter 4: Monoidal Categories

Comments