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: Characterising free algebras

Nathaniel Virgo (Jan 28 2025 at 13:18):

I have a monad $(P,\mu,\delta)$ on a cartesian category $\mathcal{C}$ (in fact the Giry monad on the category of standard Borel spaces, which may or may not be relevant) and I have an algebra of that monad, $(A,\varepsilon)$ .

I hope to show that my algebra is free, i.e. that there exists some object $X$ of $\mathcal{C}$ such that $(A,\varepsilon)$ is isomorphic to $(P(X),\mu)$ as an algebra. However, I don't know what $X$ is a priori. (In fact I want to define something as the unique-up-to-iso $X$ such that $A$ is free on $X$ , assuming it is indeed unique.)

So I'm hoping for a result along the lines of "an algebra of a monad is free if and only if ...", where assessing the "..." doesn't require finding the object $X$ on which it's free. If there is such a characterisation then maybe I can use it to prove that $A$ is free. Does anyone know of one?

(edit: as usually happens after I post something publicly, I think I've solved my problem a different way ... edit 2: actually that didn't work, so I think I do still need this)

Tobias Fritz (Jan 28 2025 at 14:14):

I'd expect that projectivity is a necessary condition: along every surjective morphism of algebras $B \to C$ , it must be possible to lift every algebra morphism $A \to C$ to an algebra morphism $A \to B$ .

Tobias Fritz (Jan 28 2025 at 14:14):

This is obviously necessary for algebras of any monad on Set to be free: in your notation, if $A$ is free then algebra morphisms out of $A$ are in bijection with arbitrary maps out of $X$ , and these can be lifted by the axiom of choice. Since standard Borel measurable spaces behave set-like in many ways, I'd hope that this still applies.

For some monads this projectivity condition is both necessary and sufficient for an algebra to be free, and intuitively I'd wager that the Giry monad is one of them.

Edit: Thanks to @Areeb SM for pointing out that what I said wasn't obvious at all (and probably not quite right). Should be fixed now.

Mike Shulman (Jan 28 2025 at 18:07):

Another necessary condition for being a free algebra is being a coalgebra for the comonad on the category of algebras induced by the free-forgetful adjunction. If the monadic adjunction is also comonadic, then this condition is sufficient, and the object $X$ on which a coalgebra algebra $A$ is free can be recovered as the equalizer of the coalgebra structure map and the unit of the monad.

Tobias Fritz (Jan 28 2025 at 18:26):

That reminds me of another necessary condition: a free Giry algebra $A$ has a "codiagonal" algebra morphism $A \to A \otimes A$ , which is basically the EM algebra version of the copy map in a Markov category. This codiagonal has the characteristic property that composing with the projection $A \to I$ on either tensor factor gives the identity $A \to A$ . Some people call such a thing a broadcasting map, because it "broadcasts" elements of $A$ to both tensor factors. It need not be commutative or associative though, just counital.

Tobias Fritz (Jan 28 2025 at 18:28):

The fact that not all Giry algebras have a broadcasting map is closely related to the no-cloning theorem in quantum theory. (I can go into more details if anyone wants to see them.)

Tobias Fritz (Jan 28 2025 at 18:30):

Morally speaking, the no-broadcasting theorem for general probabilistic theories says that the existence of a broadcasting map characterizes the free algebras. Technically, it's slightly different because they don't formally consider Giry algebras. But I'm fairly sure that the same result holds for Giry algebras, even if I wouldn't know how to prove it offhand.

JS PL (he/him) (Jan 28 2025 at 18:42):

Mike Shulman said:

Another necessary condition for being a free algebra is being a coalgebra for the comonad on the category of algebras induced by the free-forgetful adjunction. If the monadic adjunction is also comonadic, then this condition is sufficient, and the object $X$ on which a coalgebra algebra $A$ is free can be recovered as the equalizer of the coalgebra structure map and the unit of the monad.

Bart Jacobs has a paper on this topic, and how these coalgebra structures can be interpreted as bases: https://arxiv.org/pdf/1309.0844

Mike Shulman (Jan 28 2025 at 18:47):

Tobias Fritz said:

That reminds me of another necessary condition: a free Giry algebra $A$ has a "codiagonal" algebra morphism $A \to A \otimes A$ , which is basically the EM algebra version of the copy map in a Markov category. This codiagonal has the characteristic property that composing with the projection $A \to I$ on either tensor factor gives the identity $A \to A$ . Some people call such a thing a broadcasting map, because it "broadcasts" elements of $A$ to both tensor factors. It need not be commutative or associative though, just counital.

That's curious! Up until your last sentence I was thinking "that must be just because the free algebra functor is strong monoidal, so it preserves comonoids, and the monoidal structure of the base category is cartesian, so every object is a comonoid". That's what happens in lots of other cases like vector spaces, for instance. But if the broadcast map is not commutative or associative, it must come from somewhere else?

Tobias Fritz (Jan 28 2025 at 19:22):

Oh for free algebras it is commutative and associative, and does come from the strong monoidal structure. I see that my phrasing with "need not" was confusing; I just meant that these conditions are not part of the definition of a broadcasting map!

Tobias Fritz (Jan 28 2025 at 19:22):

So there seems to be the following dichotomy:

A free Giry algebra has a broadcasting map that is even associative and commutative.
A non-free Giry algebra has no broadcasting map at all. (This part is conjectural, but proven in a slightly different technical setting.)

Mike Shulman (Jan 28 2025 at 19:25):

Ah, I see. So if every broadcasting map that actually exists is associative and commutative, why do people define the notion of "broadcasting map" that isn't associative or commutative? (-:

Tobias Fritz (Jan 28 2025 at 19:27):

Great question! I think that was based on the "operational" intuition by physicists that a broadcasting is a process that creates two copies of some piece of information in such a way that when you ignore or forget one, then you recover the original information. The fact that this counitality was enough for them to disprove the existence in non-free cases must have been why they didn't consider additional conditions.

Paolo Perrone (Jan 31 2025 at 07:23):

Here's another thing that might help: given a free algebra $PX$ , the image of $\eta:X\to PX$ (for a convenient choice of $X$ ) can be taken to be the set of extreme points of $PX$ . Those are exactly the points $p\in PX$ such that if $p=\mu(\pi)$ for some $\pi\in PPX$ , then necessarily $\pi=\eta(p)$ .

(There are a few other characterizations, but the one above is the one more readily generalizable outside the free case.)

Now let $(A,e)$ be an algebra and let $A'$ be the set of its extreme points (same definition as above, but with $e$ in place of $\mu$ ), with the induced sigma-algebra. $A$ is free if and only if any of the following equivalent conditions hold:

Every point of $A$ is a unique convex mixture of extreme points (i.e. of a probability measure supported on $A'$ )
The usual universal property holds: there's a bijection $\mathrm{Meas}(A', B)\cong\mathrm{Alg}(A,B)$ , natural in $B$ , given in the left direction by precomposition with the inclusion.

(There are other equivalent conditions.)

Paolo Perrone (Jan 31 2025 at 08:06):

(The idea of "extreme points" is specific to the Giry monad, and of a few other probability monads, it does not hold in general. It may be related to the explicit basis property.)