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: theory: category theory

Topic: Ref request: monad for boolean algebras

Ralph Sarkis (May 20 2023 at 15:34):

I have only found in the literature a description of the Lawvere theory for boolean algebras. Is there a nice monad presented by the theory of boolean algebras (preferrably with a reference describing it)?

In this nlab page, it seems that we could extract a monad structure on the double finite powerset functor whose algebras will be boolean algebras, but I am not totally convinced.

John Baez (May 20 2023 at 15:52):

I don't know a reference. It would be nice to find one. But if we can't find one, what needs to be added to the nLab page to totally convince you that the square of the finite powerset functor can be made into a monad whose algebras are boolean algebras?

John Baez (May 20 2023 at 15:55):

A proof, obviously. :upside_down:

But what spot(s) in the argument already there seem weak?

Ralph Sarkis (May 20 2023 at 18:16):

That page only describes the free boolean algebra right? But what tells me that all algebras for this monad are boolean algebras. The free cancellative monoid on $X$ is $X^*$, but algebras of $X^*$ are (possibly not cancellative) monoids.

After reading again, I think the argument in the [[Boolean ring]] page convinces me. I see that the monad that is implicit in [[BoolAlg]] is the monad for boolean rings, and then the equivalence between boolean rings and boolean algebras does it. That is a neat example of distributive law between monads!

John Baez (May 20 2023 at 19:17):

I'm willing to improve the nLab a bit and try to clarify this.

Todd Schmid (he/they) (May 20 2023 at 19:52):

@Ralph Sarkis I think the way to see that the double powerset is the free Boolean algebra on a set $X$ is to go via the presentation definition I showed you on that picnic bench ;D You want to think of the exponent-side powerset as being the set of conjunctions over literals from $X$. So, rewrite an element $\{x_1,\dots, x_n\} \in \mathcal P_f X$ as $x_1 \wedge x_2 \wedge\cdots \wedge x_n \wedge \bigwedge_{y \neq x_i}\neg y$. Then an element of $\mathcal P_f\mathcal P_f X$ is a disjunction of these terms (in ``normal form'', say). There is clearly exactly one BA homomorphism that lifts each map from $X$ into a Boolean algebra.

I haven't read the nLab article though. Maybe this is already there.

Edit: I said conjunction in the lower layer when I meant disjunction!

Graham Manuell (May 20 2023 at 20:01):

Ralph Sarkis said:

That page only describes the free boolean algebra right? But what tells me that all algebras for this monad are boolean algebras. The free cancellative monoid on $X$ is $X^*$, but algebras of $X^*$ are (possibly not cancellative) monoids.

But Boolean algebras are algebras, so they are clearly monadic over set unlike cancellative monoids, so I'm not sure I understand the issue. Or are you thinking of them as special posets or something?

Ralph Sarkis (May 20 2023 at 20:39):

Graham Manuell said:

Ralph Sarkis said:

That page only describes the free boolean algebra right? But what tells me that all algebras for this monad are boolean algebras. The free cancellative monoid on $X$ is $X^*$, but algebras of $X^*$ are (possibly not cancellative) monoids.

But Boolean algebras are algebras, so they are clearly monadic over set unlike cancellative monoids, so I'm not sure I understand the issue. Or are you thinking of them as special posets or something?

True, I did not remember this problem was because cancellative monoids are not algebraic.

John Baez (May 20 2023 at 20:41):

Todd Schmid (he/they) said:

Ralph Sarkis I think the way to see that the double powerset is the free Boolean algebra on a set $X$

Nice explanation - thanks!

It's clear you meant this, but just for beginners I'll reiterate that the free boolean algebra on $X$ is the double finite powerset: the set of finite subsets of finite subsets of $X$.

Ralph Sarkis (May 20 2023 at 21:12):

Todd Schmid (he/they) said:

So, rewrite an element $\{x_1,\dots, x_n\} \in \mathcal P_f X$ as $x_1 \wedge x_2 \wedge\cdots \wedge x_n \wedge \bigwedge_{y \neq x_i}\neg y$. Then an element of $\mathcal P_f\mathcal P_f X$ is a conjunction of these terms (in ``normal form'', say).

Sorry Todd, I don't understand this. I am not sure how to think of the lifting to terms using possibly infinite conjunction $\bigwedge_{y\neq x_i}$ (because Boolean algebras don't have infinite conjuctions). And your terms seem to use intersection in both layers of the powerset, which is not what the nlab page suggests.

Todd Schmid (he/they) (May 20 2023 at 21:20):

Sorry, typo! I meant to say "disjunction" the second time.

About the no-infinite-conjunctions business, you make a good point. I'm used to the situations where either $X$ is finite or the intention is to build a complete Boolean algebra. It is my suspicion that the free complete Boolean algebra is also the free Boolean algebra, but would have to check.

Todd Schmid (he/they) (May 20 2023 at 21:22):

Actually, I take that back: $\mathcal P_f \mathcal P_f X$ is not complete at all...

Ralph Sarkis (May 20 2023 at 21:35):

Todd Schmid (he/they) said:

I meant to say "disjunction" the second time.

I don't think that works either, because union and intersection are two semilattice operations on $\mathcal{P}_f X$ and you cannot compose the free semilattice monad with itself (see the no-go theorems by Zwart and Marsden). The nlab page suggests to take another monad structure on $\mathcal{P}_f$ presented by (I believe) a binary operation $\Delta$ and a constant $\emptyset$ satisfying

$$A \mathrel{\Delta} B = B \mathrel{\Delta} A\\ A \mathrel{\Delta} (B \mathrel{\Delta} C) = (A \mathrel{\Delta} B) \mathrel{\Delta} C\\ (A \mathrel{\Delta} B) \mathrel{\Delta} (B \mathrel{\Delta} C) = A \mathrel{\Delta} C\\ A \mathrel{\Delta} A = \emptyset\\ A \mathrel{\Delta} \emptyset = A$$

The binary operation will be interpreted as the symmetric difference of sets and $\emptyset$ as the empty set. To compose this monad with the usual monad on $\mathcal{P}_f$ (free semilattices where the binary operation should be interpreted as intersection), there should be a distributive law presented by the equation $A \wedge (B \mathrel{\Delta} C) = (A \wedge B) \mathrel{\Delta} (A \wedge C)$.

Todd Schmid (he/they) (May 20 2023 at 21:44):

@Ralph Sarkis Yeah, this is a lot more complicated than I thought initially. Although, I'm not convinced the no-go theorem is relevant here: We're not asking for the free distributive lattice on a set of generators, we're asking for a somewhat unrelated structure.

At least for finite $X$, the construction I suggest does work. But yes, for infinite $X$, the situation is less nice, and I'm not sure how to fix it. I will think about this for a bit... I have successfully been nerd sniped

John Baez (May 21 2023 at 16:05):

Ralph is sketching out the situation in a way that agrees with what I gather from the nLab. The one thing that bothers me is this.

John Baez (May 21 2023 at 16:42):

Ralph, following the nLab, mentions

the usual monad on $\mathcal{P}_f$ (free semilattices where the binary operation should be interpreted as intersection)

But the unit for intersection of subsets of $X$ is the whole set $X$, which is not generally a finite subset!

Ralph Sarkis (May 21 2023 at 16:44):

Right, we should change that to union (which is also a semilattice operation), but we need to find the corresponding distributive law.

John Baez (May 21 2023 at 16:54):

This seems sad, at least now, since the distributive law for intersection over symmetric difference is just the classic distributive law we're used to in rings.... and we are, in the end, trying to get the monad for Boolean rings!

John Baez (May 21 2023 at 16:55):

But we seem forced into coming up with a new way of thinking about Boolean rings, with a new distributive law.

John Baez (May 21 2023 at 19:11):

Actually maybe everything is fine. Let me try again.

John Baez (May 21 2023 at 19:17):

There is a Lawvere theory for [[boolean algebras]] and one for [[boolean rings]], but these Lawvere theories are isomorphic (as you can show by following hints in the second link) so let us work with the latter.

John Baez (May 21 2023 at 19:18):

Anything described by a Lawvere theory can be described by a finitary monad and vice versa, so there is some finitary monad for boolean rings.

John Baez (May 21 2023 at 19:21):

Claim. The monad for boolean rings is isomorphic to $M \circ S$ where are two different finitary monads related by a distributive law. Moreover the underlying functors $M, S: \mathsf{Set} \to \mathsf{Set}$ are both naturally isomorphic to the finite powerset functor $\mathcal{P}_f : \mathsf{Set} \to \mathsf{Set}$.

John Baez (May 21 2023 at 19:29):

Proof Sketch.

Consider two monads on $\mathsf{Set}$:

1. Let $M$ be the monad for [[semilattices]]: that is, commutative monoids where the monoid operation $\cdot$ is idempotent: $x \cdot x = x$.
2. Let $S$ be the monad for vector spaces over the field with 2 elements, $\mathbb{F}_2$. These are equivalent to commutative monoids where the monoid operation $+$ obeys $x+x = 0$.

John Baez (May 21 2023 at 19:31):

These two algebraic structures are described by Lawvere theories, so they are algebras of finitary monads $M,S$ on $\mathsf{Set}$. One might wonder how these two monads both have underlying functors isomorphic to $\mathcal{P}_f$.

For 1. we need to see how for any set $X$, $\mathcal{P}_f X$ can be made into the free semilattice on $X$. To do this we think of monoid operation $\cdot$ as the union of finite subsets, $\cup$, and the unit of this monoid operation as $\emptyset$. Note $\cup$ is associative, commutative, unital and idempotent: $S \cup S = S$.

For 2. we need to see how for any set $X$, $\mathcal{P}_f X$ can be made into the free $\mathbb{F}_2$-vector space over $X$. To do this we think of addition $+$ as the symmetric difference of finite sets, $\Delta$, and the unit of this monoid operation as $\emptyset$. Note $\Delta$ is associative, commutative, unital and has $S \Delta S = \emptyset$.

John Baez (May 21 2023 at 19:33):

Assuming we are happy with this, we can now forget about $\mathcal{P}_f$: we now need to find the distributive law $M \circ S \Rightarrow S \circ M$ that makes $S \circ M$ into the monad for boolean rings.

John Baez (May 21 2023 at 19:34):

This is just the classic distributive law for rings, which maps a product of sums to a sum of products!

John Baez (May 21 2023 at 19:40):

So, to finish off, we need to check that $S \circ M$ is (isomorphic to) the monad for boolean rings.

John Baez (May 21 2023 at 19:44):

This amounts to checking that a boolean ring is a set $X$ with

1. a constant $1$ and binary operation $\cdot$ making that set into a semilattice: that is a commutative monoid where $x \cdot x = x$

2. a constant $0$ and binary operation $+$ making that set into a vector space over $\mathbb{F}_2$: that is, a commutative monoid where $x + x = 0$

together with the usual distributive laws ensuring that $(X, 1, \cdot, 0, +)$ is a commutative ring.

Ralph Sarkis (May 21 2023 at 20:45):

We need to actually check that the natural transformation $MS \Rightarrow SM$ is actually a distributive law. Too many mistakes have been made when not being careful with distributive laws.

Ralph Sarkis (May 21 2023 at 20:47):

Also, how do we interpret the constants in $PPX$? Both are the empty set?

John Baez (May 21 2023 at 21:06):

Ralph Sarkis said:

We need to actually check that the natural transformation $MS \Rightarrow SM$ is actually a distributive law. Too many mistakes have been made when not being careful with distributive laws.

Theoretically we need to check it, but it's the usual distribution of products over sums in a ring, specialized to the case where multiplication obeys $xx = x$ and addition obeys $x + x = 0$. So I don't see how it could fail.

John Baez (May 21 2023 at 21:07):

Ralph Sarkis said:

Also, how do we interpret the constants in $PPX$? Both are the empty set?

Note that I'm carefully avoiding thinking about $\mathcal{P}_f \mathcal{P}_f X$ and instead thinking about $SMX$, which is isomorphic.

John Baez (May 21 2023 at 21:08):

This is just to avoid getting confused by various things, like the question you just asked.

John Baez (May 21 2023 at 21:09):

In the free Boolean ring on $X$, namely $S M X$, we have two distinct constants, $0$ and $1$.

John Baez (May 21 2023 at 21:10):

You can then trace these through the isomorphisms that I described, $S \cong \mathcal{P}_f$ and $M \cong \mathcal{P}_f$.

John Baez (May 21 2023 at 21:11):

You will inevitably find that $0$ and $1$, being distinct in $SMX$, correspond to two different elements of $\mathcal{P}_f \mathcal{P}_f X$.

John Baez (May 21 2023 at 21:56):

Luckily for any infinite set $X$ there are exactly two elements of $\mathcal{P}_f \mathcal{P}_f X$ preserved by all permutations of $X$.

John Baez (May 21 2023 at 21:59):

So we know these must be the elements that correspond to 0 and 1 in the free boolean ring on $X$, even before we start calculating.

John Baez (May 21 2023 at 22:07):

By the way, I added a lot of detail about the monad for boolean algebras to the nLab, in the section free boolean algebras.

Sam Staton (May 22 2023 at 08:16):

Hi, Are you sure the other monad structure (from $S$) has the same functorial action of $\mathcal P_f$ as the one from $M$? I thought it would be something like
$\mathcal P_f(g)(U)=\{x~|~\#(g^{-1}(x)\cap U)~is~odd\}$.

Sam Staton (May 22 2023 at 08:19):

By the way, I thought $2^{2^n}$ was the free Boolean algebra in terms of the contravariant powerset. I hope this is right: $2^-:\mathbf{FinSet}^{op}\to\mathbf{FinSet}$ is monadic by (say) Pare's theorem, and $\mathbf{FinSet}^{op}\simeq \mathbf{FinBool}$ by Stone duality. Maybe there are many different angles on this.

Ralph Sarkis (May 22 2023 at 14:55):

We are looking at the free boolean algebra over $\mathbf{Set}$.

Todd Schmid (he/they) (May 22 2023 at 15:22):

Sam Staton said:

By the way, I thought $2^{2^n}$ was the free Boolean algebra in terms of the contravariant powerset. I hope this is right: $2^-:\mathbf{FinSet}^{op}\to\mathbf{FinSet}$ is monadic by (say) Pare's theorem, and $\mathbf{FinSet}^{op}\simeq \mathbf{FinBool}$ by Stone duality. Maybe there are many different angles on this.

This is essentially what I had in mind above, although a bit hidden behind the finite Stone duality-type statement here.

Todd Schmid (he/they) (May 22 2023 at 15:22):

Since I'm on category theory social media, let me clarify my previous contribution as follows: @Ralph Sarkis is right that the finite covariant power set does not distribute over itself. But the covariant $\circ$ covariant structure is not the only covariant functor structure one can put on $2^{2^{(-)}}$, or even $\mathcal P_f \circ 2^{(-)}$ for that matter. In the last case, thinking of $2$ as $\mathbb F_2$ (as @John Baez suggests) clarifies the situation a lot.

Todd Schmid (he/they) (May 22 2023 at 15:22):

Does the distributive law amount to the construction of the semilattice of finite and cofinite dimensional subspaces (plus the empty subspace)? To @Ralph Sarkis 's question about the constants: $0$ would be the "empty subspace" and $1$ would be the whole space.

Jules Hedges (May 22 2023 at 16:37):

My understanding is that the monad structure on $\mathcal P^2$ that gives you boolean algebras is (what computer scientists call) the continuation monad, which comes from the adjunction between $\mathbf{Set}$ and $\mathbf{Set}^{\mathrm{op}}$ given by the contravariant powerset functor

Jules Hedges (May 22 2023 at 16:38):

(This is probably what's already been said, slightly too many pages to read in a hurry)

Jules Hedges (May 22 2023 at 16:38):

I have a related question: on a cartesian closed category, $K_R (X) = (X \to R) \to R$ is a monad for any $R$, and I don't know what are its algebras except when your category is $\mathbf{Set}$ and $R = 2$

Sam Staton (May 22 2023 at 17:07):

Jules Hedges said:

I have a related question: on a cartesian closed category, $K_R (X) = (X \to R) \to R$ is a monad for any $R$, and I don't know what are its algebras except when your category is $\mathbf{Set}$ and $R = 2$

When the base category is $Set$, then $Alg(K_R)\simeq Set^{op}$ for any $R\geq 2$! See e.g. Proposition 10 of Combining algebraic effects with continuations.

John Baez (May 22 2023 at 17:57):

Sam Staton said:

By the way, I thought $2^{2^n}$ was the free Boolean algebra in terms of the contravariant powerset. I hope this is right: $2^-:\mathbf{FinSet}^{op}\to\mathbf{FinSet}$ is monadic by (say) Pare's theorem, and $\mathbf{FinSet}^{op}\simeq \mathbf{FinBool}$ by Stone duality. Maybe there are many different angles on this.

All this sounds right to me, but Ralph was asking about possibly infinite boolean algebras. Then the argument you're sketching can be adapted to show that the square of the contravariant powerset functor can be made into the monad for complete atomic boolean algebras, or CABAs. The category of CABAs is equivalent to $\mathsf{Set}^{\text{op}}$. But right now we weren't wanting to describe CABAs as algebras of a monad on $\mathsf{Set}$: we were wanting to describe boolean algebras.

John Baez (May 22 2023 at 18:05):

Jules Hedges said:

My understanding is that the monad structure on $\mathcal P^2$ that gives you boolean algebras is (what computer scientists call) the continuation monad, which comes from the adjunction between $\mathbf{Set}$ and $\mathbf{Set}^{\mathrm{op}}$ given by the contravariant powerset functor

No, this trick gives you a special kind of boolean algebras called complete atomic boolean algebras or CABAs. These are boolean algebras with infinitary 'ands', infinitary 'ors', both distributing over each other, and such that every element is an infinitary or of 'atoms', meaning propositions that are implied by nothing other than themselves and 'false'.

Every finite boolean algebra is a complete atomic boolean algebra, so if you don't mess with infinite sets none of this matters.

Sam Staton (May 22 2023 at 19:19):

Thanks @John Baez, I see. Still, it's fascinating that your distributive-laws description also applies to $\mathbf{FinSet}$, and so there seem to be two very different views on the same monad on $\mathbf{FinSet}$.

Sam Staton (May 22 2023 at 19:19):

Do you agree that the functorial actions of $M$ and $S$, when transported to $\mathcal P_f$, are actually different? I think this is right?

John Baez (May 22 2023 at 19:32):

@Sam Staton - I don't know what "functorial actions" means. I believe $M$ and $S$ are (naturally isomorphic to) the same functor from the category of sets to itself, the finite power set functor, but they are made into monads in two different ways.

John Baez (May 22 2023 at 19:33):

I.e., the multiplication on these monads is different (and maybe the unit too).

Ralph Sarkis (May 22 2023 at 19:47):

I think Sam is right to say that $M$ and $S$ should not be the same functor, they have the same action on objects, but not on morphisms. For the free $\mathbb{F}_2$-vector space monad, the multiplication takes a finite set of finite subsets of $X$ to a finite subset of by taking the symmetric difference, i.e. $\mu_X(\{S_1, \dots, S_n\}) = S_1 \mathrel{\Delta} \cdots \mathrel{\Delta} S_n$. Another way to say this is that it takes the "multiunion" and keeps only elements appearing an odd amount of times.

Now, this means that $\mathcal{P}_f(f)$ for a function $f: X \to Y$ is not the usual image map because e.g. the following naturality square does not commute when $X = Y = \mathbb{N}$ and $f: X \to Y$ takes $1$ and $2$ to $1$.

image.png

John Baez (May 22 2023 at 19:56):

Oh, okay - I didn't understand Sam's point! I knew that M and S had different multiplications, so the interesting point I hadn't understood is that they act differently on morphisms. So part of what I said (and wrote in the nLab) is wrong: S is not what I'd normally call the finite power set functor. On the other hand, I still believe M is the finite powerset functor.

Just to be clear: for me the finite powerset functor $\mathcal{P}_f : \mathsf{Set} \to \mathsf{Set}$ maps any set $X$ to the set $2^X$, and it maps any function $f : X \to Y$ to the function $2^X \to 2^Y$ sending any subset $S \subseteq X$ to its image under $f$.

Sam Staton (May 22 2023 at 21:37):

Great, I agree. It also seems these two monads ($M$ and $S$) are the free-module monads corresponding to the two different possible rig structures on the two element set.

John Baez (May 22 2023 at 22:28):

Oh, that's very nice. That makes it seems more natural somehow.

John Baez (May 22 2023 at 23:23):

I fixed the nLab article discussing this:

• BoolAlg: free boolean algebras

John Baez (May 22 2023 at 23:23):

It would still be nice to get a reference for this stuff! It should be classical (pardon the pun).

Todd Schmid (he/they) (May 23 2023 at 03:18):

Jules Hedges said:

I have a related question: on a cartesian closed category, $K_R (X) = (X \to R) \to R$ is a monad for any $R$, and I don't know what are its algebras except when your category is $\mathbf{Set}$ and $R = 2$

If you take $R$ to be a monoid, do you get a free semiring structure of some kind? Just judging from the discussion above.