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: Bimodules vs Spans: Puzzle 1

Eric Forgy (Jan 14 2021 at 01:36):

John Baez said:

I explained it here:

• John Baez, Spans versus bimodules, August 4, 2008.

I don't know if that counts as an explanation. It is a super interesting topic. You posed a puzzle, a bunch of smart people gave answers, but I don't really see any explanations there :thinking:
John Baez said:

When you understand this you'll be happy. I tried to explain it here on Zulip a while back, but you probably weren't desperate enough back then.

For sure I will be happy :blush: I'll try to find your explanation again :pray:

John Baez (Jan 14 2021 at 01:38):

The answers to the puzzles are the explanation. The answer to this puzzle:

Puzzle 3: What’s a bimodule of a pair of monoid objects in $\mathsf{Set}^{\mathrm op}$?

is a span of sets!

John Baez (Jan 14 2021 at 01:40):

The bimodules you like to think about are bimodules in $(\mathsf{Vect}, \otimes)$. But those are just a special case of a more general concept, and you need to go up a notch in generality to see that spans are also bimodules. It goes like this, briefly:

A set is a monoid object in the monoidal category $(\mathsf{Set}^{\mathrm{op}}, +)$.

We can define bimodules for monoid objects in any monoidal category.

A span of sets is a bimodule in $(\mathsf{Set}^{\mathrm{op}},+)$.

John Baez (Jan 14 2021 at 01:43):

I don't expect this to be extremely easy to understand, but it's also not extremely hard.

Eric Forgy (Jan 14 2021 at 02:12):

Thank you. I will try to understand this and come back when I get stuck :pray:

John Baez (Jan 14 2021 at 02:32):

Good luck! You have to do the puzzles in order, because each one depends on understanding the previous ones.

Eric Forgy (Jan 14 2021 at 11:37):

Puzzle 1: What’s a monoid object in $\mathsf{Set^{op}}$?

The "object" is a set $X$, but for this to be a monoid object, we need a multiplication

$\mu: X\times X\to X.$

and a unit

$\eta: *\to X$

satisfying the conditions. I don't think the answer is complete without specifying those :thinking:

Attempt #1: Before looking at Puzzle #2

I think a multiplication $X\times X\to X$ in $\mathsf{Set^{op}}$ is a function $X\to X\times X$ in $\mathsf{Set}$ and the only function that would make sense to me is
${}$
$x\mapsto (x,x)\in X\times X.$
${}$
A unit $*\to X$ in $\mathsf{Set^{op}}$ is a function $X\to *$ in $\mathsf{Set}$ and that is unique since $*$ is terminal.

A quick doodle confirms these satisfy associativity and unit laws.

Attempt #2: After looking at Puzzle #2, but before looking at Puzzle #3

I now see that I really wanted my monoid object to be a set of functions $[X,X]$ (or $\mathsf{End}(X)$).

Then multiplication $[X,X]\times [X,X]\to [X,X]$ is just composition of functions
${}$
$\sout{f\times g \mapsto f\circ g}$
${}$
and the unit $*\to [X,X]$ is the identity function
${}$
$\sout{\bullet\mapsto 1_X.}$
${}$
I don't actually see anything wrong with Attempt #1 though, so I think both might be correct. In that case, it means composition of endofunctions in $\mathsf{Set^{op}}$ is the opposite of the diagonal map of endofunctions in $\mathsf{Set}.$

Attempt #3: After looking at Puzzle #3

After attempting Puzzle #3, I think I need to come back here again.

There are actually two types of monoid objects in $\mathsf{Set^{op}}.$ The first is the one in Attempt #2 above, i.e. the set of functions $[X,X]$ (or $\mathsf{End}(X)$).

The second type of monoid object, maybe denote it $[X,X]^\mathsf{op}$ (or $\mathsf{End^{op}}(X)$). This monoid object is the same set of functions, but multiplication / composition
${}$
$\sout{[X,X]^\mathsf{op}\times[X,X]^\mathsf{op}\to[X,X]^\mathsf{op}}$
${}$
is reversed, i.e.
${}$
$\sout{f\times g\mapsto g\circ f.}$

Eric Forgy (Jan 14 2021 at 21:37):

Note: I split the stream into one stream for each Puzzle

1. Puzzle 1 (here)
2. Puzzle 2
3. Puzzle 3

so I am quoting John's reply for Puzzle 1 here.

John Baez said:

Eric Forgy said:

Puzzle 1: What’s a monoid object in $\mathsf{Set^{op}}$?

The "object" is a set $X$, but for this to be a monoid object, we need a multiplication

$\mu: X\times X\to X.$

and a unit

$\eta: *\to X$

satisfying the conditions. I don't think the answer is complete without specifying those :thinking:

---

Attempt #1: Before looking at Puzzle #2

I think a multiplication $X\times X\to X$ in $\mathsf{Set^{op}}$ is a function $X\to X\times X$ in $\mathsf{Set}$ and the only function that would make sense to me is
${}$
$x\mapsto (x,x)\in X\times X.$
${}$
A unit $*\to X$ in $\mathsf{Set^{op}}$ is a function $X\to *$ in $\mathsf{Set}$ and that is unique since $*$ is terminal.

A quick doodle confirms these satisfy associativity and unit laws.

Right! And the really cool part is that this is the only possible choice of maps $\mu: X \to X \times X$ and $\eta: X \to 1$ obeying (co)associativity and the (co)unit laws. (We usually put the word "co" in here since the maps are going backwards.) So while in $\mathsf{Set}$ you need to specify $\mu$ and $\eta$ to say how we are treating our set $X$ as a monoid, in $\mathsf{Set}^{\mathrm{op}}$ you don't: there's only one choice!

David Egolf (Jan 16 2021 at 19:48):

I've been trying to show that the choices for multiplication $\mu$ and unit $\eta$ on a monoid object in $\mathsf{Set^{op}}$ are forced. We are working in the monoidal category $\mathsf{Set^{op}}$ where objects are sets, a morphism $f:A \to B$ is a function from $B$ to $A$, the monoidal product $\otimes$ is the Cartesian product of sets $\times$, and the unit object the singleton set $\{*\}$.

A monoid object in this category is a set $M$ together with a morphism $\mu: M \times M \to M$ and a morphism $\eta: \{*\} \to M$, satisfying associativity and unit laws. Let $\mu^{op}: M \to M \times M$ be the function corresponding to $\mu$, and let $\eta^{op}: M \to \{*\}$ be the function corresponding to $\eta$. Notice that $\eta^{op}$ is forced to be the unique function sending every element of $M$ to the single element $*$. We want to show that the definition of $\mu$ is also forced, by making using of the associativity and unit laws.

Let us start by considering the unit laws. The unit laws required are: $\lambda = \mu \circ (\eta \otimes 1)$ and $\rho = \mu \circ (1 \otimes \eta)$. Here $\lambda$ is the left identity morphism corresponding to a function $\lambda^{op}:M \to I \otimes M$, acting by $\lambda^{op}(m) = (*, m)$. Similarly, $\rho$ is the right identity morphism corresponding to a function $\rho^{op}:M \to M \otimes I$, acting by $\rho^{op}(m) = (m,*)$. (I am guessing as to the definitions of the identity morphisms. I haven't checked that these really are what required for $\mathsf{Set^{op}}$ to be a monoidal category. I am also guessing that "1" here corresponds to the morphism that has corresponding function $1^{op}$ that is the identity function on $M$).

To expand these laws, we introduce the notation $\mu^{op}(m) = (\mu_1^{op}(m), \mu_2^{op}(m))$. Letting $m$ be some element of $M$, the first unit law corresponds to: $\lambda^{op}(m) = (\eta^{op} \otimes 1^{op}) \circ \mu^{op}(m)$, or equivalently $(*, m) = (\eta^{op}(\mu^{op}_1(m)), \mu^{op}_2(m)) = (*, \mu^{op}_2(m))$. This implies that we must have $\mu^{op}_2(m) = m$ for any $m$ in $M$.

The second unit law corresponds to $\rho^{op}(m) = (1^{op} \otimes \eta^{op}) \circ \mu^{op}$, or equivalently $(m,*) = (\mu^{op}_1(m), \eta^{op}(\mu^{op}_2(m)) = (\mu^{op}_1(m), *)$. This implies that we must have $\mu^{op}_1(m) = m$ for any $m$ in $M$.

So, it seems like we only need the unit law to force the definition of $\mu$. $\mu$ is the morphism corresponding to the function $\mu^{op}(m) = (m,m)$.

However, I made some guesses as to the definition of $\mathsf{Set^{op}}$ and the notation used in the unit laws. I am also a bit suspicious that I didn't have to use the associativity laws to force the definition of $\mu$. Is there a error in the argument above?

(Another assumption I made was regarding the notational use of $\otimes$: I assumed it corresponded to the corresponding functions "in parallel", so $1 \otimes \eta$ corresponds to the function $(1^{op} \otimes \eta^{op})(m) = (1^{op}(m), \eta^{op}(m))$.)

Eric Forgy (Jan 16 2021 at 19:52):

Nice! If you are like me, you must be feeling the neurons expanding :blush: