The n-Category Café

Can they do anything useful with them?

These “semigroupads”, or a dual notion, come up a bit in topos theory. They come up for example in some notes on a theorem that I wrote up, which combines three fundamental theorems of topos theory into one.

The three theorems are quite well known.

1. A slice $\mathbf{E}/X$ of a topos $\mathbf{E}$ is again a topos.
2. The category of coalgebras of a left exact comonad on a topos is again a topos.
3. The category of algebras of a left exact idempotent monad on a topos is again a topos.

One uses 1. and 2. to prove that the category of (internal) presheaves on an (internal) category in a topos is again a topos. One uses 3. to show that the category of sheaves for a Lawvere-Tierney topology in a topos is again a topos (Lawvere-Tierney topologies are more or less the same thing as left exact idempotent monads). So it’s this succession of theorems which gives you Grothendieck toposes relative to a base topos $\mathbf{E}$.

Less advertised than 1. and 2. is a theorem that generalizes both:

1.’ The category of coalgebras for a pullback-preserving comonad on a topos is again a topos.

One gets 1. as a special case, because $\mathbf{E}/X$ is the category of coalgebras for an evident comonad $X \times -$, and this comonad preserves pullbacks. This theorem is certainly known and appears in the Elephant (Remark A.4.2.3), but seems not to get mentioned so much in the introductory textbooks. However, it’s possible to use this theorem to prove the presheaf result in a single shot (rather than in two stages, the slice result coming first and the presheaf topos second).

Even less advertised are generalizations which manage to get 3. in the game, and that’s what my notes are about. Another is due to Toby Kenney, in his notion of diad, which is another kind of semigroupad notion.

My version of cosemigroupad is something I had begun calling a “modal operator” (although I’m not sure I like the name anymore). If $\mathbf{E}$ is a category with pullbacks, then a modal operator is defined to be a pullback-preserving functor $G: \mathbf{E} \to \mathbf{E}$ equipped with a natural transformation $\delta: G \to G G$ such that the evident coassociativity square is a pullback (hence in particular commutes). If $\mathbf{E}$ also has a terminal object, then a modal operator $(G, \delta)$ is strict if

$$1_{G 1} = \left(G 1 \stackrel{\delta 1}{\to} G G 1 \stackrel{G!}{\to} G 1\right).$$

To state the theorem, we need an appropriate notion of action of a modal operator: a $G$-structure is an object $X$ together with a coaction map $\eta: X \to G X$ such that the coaction square

$$\array{ X & \stackrel{\eta}{\to} & G X \\ \mathllap{\eta}\; \downarrow & & \downarrow \mathrlap{G\eta} \\ G X & \stackrel{\delta X}{\to} & G G X }$$

is a pullback. A map of $G$-structures is just a map $f: X \to Y$ that respects the coactions.

Theorem: If $\mathbf{E}$ is a topos and $(G, \delta)$ is a strict modal operator on $\mathbf{E}$, then the category of $G$-structures is again a topos.

The notes explain how for the pullback-preserving comonad result 1.’, the counit actually plays a fairly limited role, one which can be accounted for in the pullback coassociativity squares in the definitions above, so that 1.’ becomes a special case of the theorem. Meanwhile, this theorem also yields the result 3. for lex idempotent monads $M$, by taking $\delta: M \to M M$ to be the inverse of the monad multiplication.

Unfortunately I cannot recall the details of Toby Kenney’s diads and their three-in-one (maybe even four-in-one) applications to topos theory (his article is behind a paywall). My memory is that his development is rather pretty, and that his results might be slightly more general than mine.

Do you have an example?

Hmm! That triggered a thought. If we take a semigroupad on a category (like a monad on a category, but missing the unit), we can try to form its Kleisli category… but since the unit of a monad is involved in defining the identity morphisms in its Kleisli category, it seems we only get a Kleisli semicategory for a semigroupad.

Wow! Let me think about that… after some sleep.

If you fix an $n$ so that the endofunctor in question is $T=P^n$, then $T(f)$ is the function that applies $f$ to elements $n$ levels deep in its argument. For example, if $n=2$, we have:

$T(f)(\{\{a\},\{b\}\}) = \{\{f(a)\},\{f(b)\}\}$

We define $m$ so that the component of $m$ at any object is a function that maps its argument to the union of all the elements of its argument at level $n$. For example, if $n=2$, we have:

$m(\{\{A, B\},\{C\}\}) = A \cup B \cup C$

That $m:T^2\to T$ is a natural transformation requires:

$T(f)(m(S)) = m(T^2(f)(S))$

Here the LHS says take the union of the elements of $S$ at level $n$ and then apply $f$ to the result, $n$ levels deep, while the RHS says apply $f$ to the elements of $S$ that are $2n$ levels deep, and then take the union of the elements at level $n$. In either case, $f$ ends up being applied to the same elements.

That $m$ is a monad multiplication requires:

$m(T(m)(S)) = m(m(S))$

Here the LHS first applies $m$ to the elements of $S$ that are $n$ levels deep, so it gives us a set (of sets … to depth $n$) of unions of elements originally $2n$ levels deep, and then it takes the union of everything of depth $n$. So the result is just the union of all the elements that were of depth $2n$ in $S$.

And the RHS gives the same thing.

In fact, under the hypotheses of the theorem we get a second multiplication

$$M': X \otimes X \to X$$

just by reflecting the pictures:

$$M' = (1_x \otimes m) (1_x \otimes 1_x \otimes m)$$

and the proof that this is associative is just the mirror image of the one I showed for $M$.

In theory we could have $M = M'$, but in the case we were originally looking at, where $x$ is the power set monad on $\mathrm{Set}$, I’m pretty sure $M \ne M'$. If so, we get not just one but two affirmative solutions to my original question! But the answer is definitely “yes”.

Furthermore, as Greg noted, all this generalizes: given an object $x$ with an associative multiplication in a strict monoidal category, we can give all its tensor powers associative multiplications.

And of course there’s nothing important about strictness here: I was using it just to avoid mentioning associators. In any monoidal category we can define a semigroup object to be an object $x$ with an associative multiplication $m: x \otimes x \to x$. We’ve seen that if $x$ is a semigroup object, so is $x^{\otimes n}$ for any $n \ge 1$, in multiple ways.

Of course what makes this interesting is that if $x$ and $y$ are semigroup objects, $x \otimes y$ is not necessarily a semigroup object, unless we have a distributive law $d: y \otimes x \to x \otimes y$ to help us out.

I’m quite amazed that you translated the approach I gave into something so general … especially as your version, when translated back into the original context, expresses the multiplication differently.

If $P:C \to C$ is an endofunctor, $m$ is a natural transformation that serves as the multiplication that makes $P$ a monad, and $X$ is an object in the category $C$, your construction translates as:

$M_X = m_{P(X)} m_{P^2(X)}$

$M'_X = P(m_X) P^2(m_X)$

So in the context where $C$ is Set and $P$ is the power set functor, rather than taking the union of all the elements of depth 2 in its argument, as I did, your $M$ applies $m$ (which takes the union of all the elements of its argument) twice. Which of course has the same net effect, but it has a different flavour.

$M'$ certainly is different from $M$ in this case. For example, suppose we have:

$X=\{a,b,c\}$

$S = \{\{\{\{\},\{a\},\{b,c\}\},\{\{b\},\{c\},\{a,b\},\{a,c\}\}\}\} \in P^4(X)$

$m_{P^2(X)}(S) = \{\{\{\},\{a\},\{b,c\}\},\{\{b\},\{c\},\{a,b\},\{a,c\}\}\}$

$M_X(S) = \{\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}$

$P^2(m_X)(S) = \{\{\{a,b,c\}\}\}$

$M'_X(S) = \{\{a,b,c\}\}$

The contravariant powerset functor $P : Set^{op} \to Set$ is actually monadic (this is a general fact about any elementary topos), and its left adjoint is itself. Thus, the double contravariant powerset $P P$ is a monad whose category of algebras is $Set^{op}$.

$Set^op$ is equivalent to the category of complete atomic Boolean algebras, right? I hadn’t known it was the category of algebras of the double contravariant powerset monad $P P$. Is there some intuitive way to see how an algebra structure $a: P P X \to X$ provides $X$ with the operations of a complete atomic Boolean algebra?

$Set^op$ is equivalent to the category of complete atomic Boolean algebras, right?

Right.

Is there some intuitive way to see how an algebra structure $a: P P X \to X$ provides $X$ with the operations of a complete atomic Boolean algebra?

There ought to be, but I don’t think I’ve ever seen this written down explicitly, nor have I managed to work it out myself. The only proof of the monadicity of $P$ that I’ve seen is an abstract application of the monadicity theorem. (A cool application of the monadicity theorem, certainly, but it doesn’t give much intuition for the relationship to CABAs.)

I’m wondering if given a complete atomic Boolean algebra $X$, the algebra structure $a: P P X \to X$ maps a set of subsets of $X$ to the meet of their joins.

This would be a bit like how the covariant powerset monad is the monad for complete join-semilattices. In that case, an algebra structure $a : P X \to X$ maps a subset of $X$ to its join.

Isar Stubbe points out that his paper The double power monad is the composite power monad may be relevant to this question; it “categorifies without increasing dimension”, considering enriched categories over monoidal posets (and even locally ordered bicategories) other than $\mathbf{2}$. I haven’t really read it, but the abstract says that the algebras of the double-presheaf monad are the “completely codistributive complete categories”, which sounds like a potential categorification of CABAs.