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: categorical probability

Topic: non-weird algebras

Nathaniel Virgo (May 07 2022 at 09:11):

I'm splitting this off the "expectation" thread, because it's maybe worth discussing in its own right.

Nathaniel Virgo said:

More generally, algebras of the distribution monad are convex spaces, and some convex spaces behave like convex subsets of $\mathbb{R}^n$, while others don't. Regardless of whether we use the word expectation for the ones that have this kind of property, it would be interesting to know what extra axioms are needed to rule out the "weird" ones that lack it, for general probability monads rather than just the distribution monad.

In other words, terminology issues aside, are there extra axioms that we could impose on algebras of a probability monad that would rule out the "weird" ones and leave us only with the algebras that behave like convex subsets of vector spaces?

I don't know how useful it is to impose such extra axioms - I agree with Tobias Fritz that most results about expectations seem to generalise easily to general algebras - but I feel like I'd understand algebras better if I knew how to identify the non-weird ones at the category-theoretic level.

Paolo Perrone (May 07 2022 at 11:37):

What is known: recall that a monoid can be embedded in a group if and only if it is cancellative (ab = ac implies b=c).
A theorem due to Stone, similarly, says that a convex space, possibly "weird", can be embedded into a vector space if and only if it is cancellative in the convex sense, meaning that if ra + (1-r)b = ra + (1-r)c for r < 1, then b=c.

Paolo Perrone (May 07 2022 at 11:44):

Maybe another thing worth mentioning: in many situations, the operation of "taking the support" defines a mapping from "convex-combination-like things" to "subset-like-things", and it induces a morphism of monads. By general abstract nonsense, the algebras of the "subset" monad (which are semilattices of some kind) are then also algebras of the "convex combination" monad.

Jules Hedges (May 07 2022 at 11:53):

Am I right in guessing that the category of cancellative convex sets is not the category of algebras of a monad on $\mathbf{Set}$?

Jules Hedges (May 07 2022 at 11:54):

This seems intuitive because all free convex sets are cancellative

Paolo Perrone (May 07 2022 at 11:57):

Yeah exactly. I think this fact that "all free convex sets are cancellative" can be made into a precise proof using Beck's monadicity theorem.

Oscar Cunningham (May 07 2022 at 12:14):

Could we define a general notion of what it means for an algebra of a monad to be cancellative?

Oscar Cunningham (May 07 2022 at 12:16):

Something like 'all operations that depend nontrivially on one of their arguments are monic in that argument'

Paolo Perrone (May 07 2022 at 12:21):

Sounds like something one might be able to do for a Lawvere theory.

Zhen Lin Low (May 07 2022 at 12:37):

"Depends non-trivially" is doing a lot of work there... but anyway even groups do not have that property. (Consider the operation of squaring an element.)

Oscar Cunningham (May 07 2022 at 12:45):

For 'depends on nontrivially' I was thinking about something like an element of $T(S+1)$ that wasn't in the image of $T(S)$.

Oscar Cunningham (May 07 2022 at 12:46):

But you're right about the squaring thing

Zhen Lin Low (May 07 2022 at 13:42):

Anyway, it seems clear how to define cancellative operation: say an $n$-ary operation $o : X^n \to X$ is cancellative in its $k$-th argument if the map $X^n \to X^n$ given by $o$ and the $(n - 1)$ projections other than the $k$-th one is a monomorphism. So cancellative natural operations are related to epi-endomorphisms of free algebras.

James Deikun (May 07 2022 at 16:32):

It seems like a non-cancellative monoid won't have any nontrivial cancellative operation ...

Oscar Cunningham (May 08 2022 at 11:26):

If there were a good definition of nontrivial operation, there would also be an analogy between irreducible elements of a monoid (which can't be written nontrivially as a product) and extremal elements of a convex space (which can't be written nontrivially as a convex combination).

Tobias Fritz (May 08 2022 at 12:03):

Oscar Cunningham said:

If there were a good definition of nontrivial operation, there would also be an analogy between irreducible elements of a monoid (which can't be written nontrivially as a product) and extremal elements of a convex space (which can't be written nontrivially as a convex combination).

That can be achieved more elegantly without a definition of nontrivial operation: an element is irreducible/extremal whenever it appears in every generating set!