June 9, 2018

Sets of Sets of Sets of Sets of Sets of Sets

Posted by John Baez

The covariant power set functor $P : Set \to Set$ can be made into a monad whose multiplication $m_X: P(P(X)) \to P(X)$ turns a subset of the set of subsets of $X$ into a subset of $X$ by taking their union. Algebras of this monad are complete semilattices.

But what about powers of the power set functor? Yesterday Jules Hedges pointed out this paper:

The authors prove that $P^n$ cannot be made into a monad for $n \ge 2$.

I’ve mainly looked at their proof for the case $n = 2$. I haven’t completely worked through it, but it focuses on the unit of any purported monad structure for $P^2$, rather than its multiplication. Using a cute Yoneda trick they show there are only four possible units, corresponding to the four elements of $P(P(1))$. Then they show these can’t work. The argument involves sets like this:

As far as I’ve seen, they don’t address the following question:

Question. Does there exist an associative multiplication $m: P^2 P^2 \Rightarrow P^2$? In other words, is there a natural transformation $m: P^2 P^2 \Rightarrow P^2$ such that

$P^2 P^2 P^2 \stackrel{m P^2 }{\Rightarrow} P^2 P^2 \stackrel{m}{\Rightarrow} P^2$

equals

$P^2 P^2 P^2 \stackrel{P^2 m}{\Rightarrow} P^2 P^2 \stackrel{m}{\Rightarrow} P^2 .$

I’m not very good at these things, so this question might be very easy to answer. But if the answer were “obviously no” then you’d think Klin and Salamanca might have mentioned that. They do prove there is no distributive law $P P \Rightarrow P P$. But they also give examples of monads $T$ for which there’s no distributive law $T T \Rightarrow T T$, yet there’s still a way to make $T^2$ into a monad.

As far as I can tell, my question is fairly useless: does anyone consider “semigroupads”, namely monads without unit? Nonetheless I’m curious.

If there were a positive answer, we’d have a natural way to take a set of sets of sets of sets and turn it into a set of sets in such a way that the two most obvious resulting ways to turn a set of sets of sets of sets of sets of sets into a set of sets agree!

Posted at June 9, 2018 7:05 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3045

Re: Sets of Sets of Sets of Sets of Sets of Sets

It comes up occasionally in Haskell.

Posted by: Alex on June 9, 2018 8:50 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Can they do anything useful with them?

Posted by: John Baez on June 10, 2018 12:40 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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.

Posted by: Todd Trimble on June 10, 2018 2:44 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Here are the slides from Kenney’s talk about diads etc from CT2008.

Posted by: David Roberts on June 11, 2018 6:53 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Do you have an example?

Posted by: Christopher Upshaw on June 12, 2018 4:42 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

I have considered “product-preserving semicogroupads,” i.e. product preserving endofunctors with a comultiplication. They turn out to be sound and complete semantics for the (box fragment of) the modal logic K4.

This appears in a paper, and there’s more on it in the technical report.

I am currently working on constructing actual cases of these.

Posted by: Alex Kavvos on June 10, 2018 2:27 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Also, I suppose that semicategories are basically the same as semigroupads in a bicategory of spans, parallel to how categories are the same as monads in a bicategory of spans.

Posted by: Todd Trimble on June 10, 2018 2:49 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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.

Posted by: John Baez on June 10, 2018 7:42 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

I’m pretty sure the obvious generalisation of the multiplication you use for a single power of $P$ works for arbitrary powers of $P$. That is to say, you “flatten” a set of sets of … sets down to the necessary depth then take the union of all the elements of that flattened set.

For example, for $P^2$ you would have, for $X=\{a,b,c\}$ and some element $\{\{\{\{\}, \{a\}, \{b, c\}\}, \{\{b\}, \{c\}, \{a, b\}, \{a, c\}\}\}\} \in P^2(P^2(X))$:

$m_X(\{\{\{\{\}, \{a\}, \{b, c\}\}, \{\{b\}, \{c\}, \{a, b\}, \{a, c\}\}\}\}) = \{\{\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}\}$

I’ve check a lot of examples in Mathematica, and this $m$ seems to satisfy both the condition for being a natural transformation, and the condition for being a monad multiplication.

Posted by: Greg Egan on June 10, 2018 6:03 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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

Posted by: John Baez on June 10, 2018 7:43 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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.

Posted by: Greg Egan on June 11, 2018 12:11 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Thanks! I’ll think about this. But my original question was whether we could find an $m: T^2 \Rightarrow T$ obeying the associativity condition required in a monad. I’m not not sure you’ve checked this.

(By the way, I’m using the funky double arrow $\Rightarrow$ because $m$ is a natural transformation between functors between categories.)

I’m not worried about naturality; it’s just the associativity condition that’s worrying me. When you write

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

this makes me nervous, because it doesn’t look like the associativity I know. In fact I don’t even know what it means. I don’t know what $m(S)$ is; fundamentally what we’re supposed to have is a map

$m_S: T(T(S)) \to T(S)$

for each set $S$.

The associativity I know involves checking that two maps

$T^3(S) \to T(S)$

are equal: one where we first apply $m$ to the two leftmost $T$’s in $T^3 = T \circ T \circ T$ and then apply $m$ to the resulting $T^2$, and the other where we first apply $m$ to the two rightmost $T$’s.

I’m happy to consider only the case $T = P^2$. In this case the multiplication $m: T^2 \Rightarrow T$ is a map

$m_S : P^4(S) \to P^2(S)$

So, it’s a map sending sets of sets of sets of sets (of elements of $S$) to sets of sets (of elements of $S$.)

This gives rise to two maps sending sets of sets of sets of sets of sets of sets to sets of sets. We need to check that these agree.

The first way begins by using $m$ on the left. That is, we take a set of sets of sets of sets of sets of sets and use $m$ to produce a function from this to a set of sets of sets of sets, where we focus attention on the stuff in boldface and let the rest go along for the ride. Then we use $m$ to provide a map from the resulting set of sets of sets of sets to a set of sets. We compose these two maps.

The second way begins by using $m$ on the right. That is, we take a set of sets of sets of sets of sets of sets and use $m$ to to produce a function from this to a set of sets of sets of sets, where we focus attention on the stuff in boldface and let the rest go along for the ride. Then we use $m$ to provide a map from the resulting set of sets of sets of sets to set of sets. We compose these two maps.

Then we check to see whether these two composite maps agree.

Maybe what you did is actually equivalent to doing this. But I don’t see it.

Posted by: John Baez on June 11, 2018 2:16 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

I seem to have confused you by abusing notation in a way that I’d hoped would just avoid unnecessary clutter.

Because every component of the natural transformation $m$ does essentially the same thing, I’m not writing $m_X$ or $m_{T(X)}$ or whatever to specify the function’s domain and codomain, I’m just writing all such functions as an unsubscripted $m$. They all just take the union of the elements $n$-deep in whatever you feed them, where $n$ is the power of $P$ we are considering.

So when I write :

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

that’s just a less cluttered way of writing:

$m_X(T(m_X)(S)) = m_X(m_{T(X)}(S))$

where $S \in T^3(X)$. Does that make things any clearer?

Posted by: Greg Egan on June 11, 2018 4:20 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Okay, good. When I talk about associativity I expect to see three of something, in this case three $T$s.

Now that I understand what you’re saying, I’ll actually think about what you said!

Posted by: John Baez on June 11, 2018 4:25 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Posted by: John Baez on June 10, 2018 9:36 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

I thought about Greg’s argument, drew lots of pictures, and now see how it works! In fact it’s a completely general thing:

Theorem. Suppose $x$ is an object in a strict monoidal category equipped with a morphism $m : x \otimes x \to x$ that is associative:

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

Letting $X = x \otimes x$, the morphism $M : X \otimes X \to X$ given by

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

is associative too:

$M(M \otimes 1_X) = M(1_X \otimes M)$

Proof. We can draw $m$ as a string diagram with two strings merging into one as they go down the page. Then $M$ looks like this:

The associative law for $M$ then says

and it follows from the associativity of $m$. $\quad \blacksquare$

Posted by: John Baez on June 12, 2018 6:50 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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.

Posted by: John Baez on June 12, 2018 7:03 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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\}\}$

Posted by: Greg Egan on June 13, 2018 12:09 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Thanks for carefully checking that $M \ne M'$.

Basically I got my formula by working painstakingly through an example where I expressed an element of $P^6(S)$ as a tree, as in the video. I got the feeling that your multiplication $M: P^4 \to P^2$ had to be expressible in terms of operations I already understood… like $m: P^2 \to P$. And I wanted this to be true, since that might let us derive the associativity of $M$ from that of $m$.

Before you showed me the right way, I had tried another guess, which is beautifully symmetrical:

$M\!'' = m \otimes m .$

It fails miserably, as a string diagram calculation quickly reveals.

Posted by: John Baez on June 13, 2018 4:29 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Thanks for noticing our little result :)

Yes, John is right: we never mention associativity, and also associative transformations $m:P^2P^2\Rightarrow P^2$ exist for rather general reasons.

The obstacle to $P^2$ being a monad lies elsewhere: there are no transformations $e:Id\Rightarrow P^2$ and $m:P^2P^2\Rightarrow P^2$ (associative or not) such that $e$ would be a double-sided unit for $m$.

Posted by: Bartek Klin on June 13, 2018 2:54 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

There is another powerset functor: the contravariant one. Its square being covariant, we can ask whether it has a monad structure. I have no idea whether it does, but the naturality constraints look less stringent, so there is hope.

Also, this contravariant version looks more natural: for instance, if $f: X \to Y$, then $P Pf$ maps a topology on X to the associated final topology on Y, if I’m not mistaken.

Also, there are the related questions for comonad structures.

Posted by: Benoit on June 14, 2018 12:02 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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}$.

Posted by: Mike Shulman on June 14, 2018 4:25 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

Right, and this positively answers a natural variation of the original question: is there an algebraic theory for which the free algebra on $n$ generators is size $2^{2^n}$? Yes, the theory of Boolean algebras.

One could ask the same question about any integer sequence $(s_n)_n$. Is there an algebraic theory for which the free algebra on $n$ generators is size $s_n$? I don’t think I know whether there’s a trivial or known answer in general.

Posted by: Sam S on June 15, 2018 6:20 AM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

$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?

Posted by: John Baez on June 14, 2018 6:37 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

$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.)

Posted by: Mike Shulman on June 14, 2018 11:03 PM | Permalink | Reply to this

Re: Sets of Sets of Sets of Sets of Sets of Sets

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.

Posted by: John Baez on June 15, 2018 12:58 AM | Permalink | Reply to this

Groupoids of groupoids of …

This conversation reminds me that I’ve been wondering recently about whether facts like this categorify. There are a lot of ways one might try to do that. Most of them run into size problems, but with enough scare quotes we can hope for analogous statements. For instance, the covariant presheaf-category functor is a “monad” and has total categories as its “algebras”; that’s an analogue of the covariant powerset monad having suplattices as its algebras.

But what about the double presheaf-category “functor”; is that a “monad” on $Cat$? What about the analogous doubly-iterated functor $X\mapsto U^{U^X}$ on $\infty Gpd$, or more generally on any $(\infty,1)$-topos, where $U$ is “the” object classifier?

(One reason to wonder about this is the question of whether we can construct colimits without assuming them in an elementary $(\infty,1)$-topos, the way we can in an elementary 1-topos. In the latter case, a nice way to phrase the construction is using the monadicity of the contravariant powerobject functor.)

Posted by: Mike Shulman on June 15, 2018 3:48 PM | Permalink | Reply to this

Re: Groupoids of groupoids of …

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.

Posted by: Mike Shulman on June 25, 2018 5:01 PM | Permalink | Reply to this

Post a New Comment