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: event: Topos Colloquium

Topic: Richard Garner: "Comodels of an algebraic theory"

Tim Hosgood (Feb 09 2021 at 14:15):

This coming Thursday will see the second talk in the Topos Institute Colloquium: Richard Garner will be speaking about "Comodels of an algebraic theory". For more details, see the webpage (which has moved to https://topos.site/topos-colloquium )

Tim Hosgood (Feb 09 2021 at 14:15):

(old links to topos.site/seminars should redirect, but I'm trying to slowly phase them out)

Tim Hosgood (Feb 09 2021 at 14:16):

Here's the abstract:

In 1991 Eugenio Moggi introduced the monadic approach to computational effects; this is the mechanism by which purely functional programming languages such as Haskell can express computations with side-effects such as output, input, or interaction with an external store.

Around 2000, Plotkin and Power refined the Moggi perspective by looking not at monads, but the equational algebraic theories which generate them: this amounts to specifying not just a kind of side-effect, but a set of primitive operations by which one can program with these side-effects.

Algebraic theories have models, not only in the category of sets, but also in any category with finite products. In particular, one can look at comodels of a theory: a model in the opposite of the category of sets. A crucial insight of Power and Shkaravska is that, if T is a theory encoding interaction with an environment, then a T-comodel is a state machine providing an instance of the environment with which T interacts.

The objective of this talk is to explain this history, and to prove a new result: the category of comodels of any algebraic theory T is a presheaf category [B,Set], where B is a small category, which can be computed explicitly, that encodes the static and dynamic properties of the side-effects encoded by T.

Tim Hosgood (Feb 09 2021 at 14:17):

it takes place at 21:00 UTC this week (NB the times are a bit all over the place while things get settled, so be sure to follow the community calendar (or some other wonderful such helper))

John Baez (Feb 09 2021 at 17:17):

a new result: the category of comodels of any algebraic theory T is a presheaf category [B,Set], where B is a small category, which can be computed explicitly, that encodes the static and dynamic properties of the side-effects encoded by T.

Wow!

John Baez (Feb 09 2021 at 17:32):

I would like to understand this:

A crucial insight of Power and Shkaravska is that, if T is a theory encoding interaction with an environment, then a T-comodel is a state machine providing an instance of the environment with which T interacts.

I should take a simple example.

If T is the theory of monoids, a T-comodel is just a set!

If T is the theory of commutative monoids, a T-comodel is just a set!

I'm not learning much yet. :upside_down:

Tim Hosgood (Feb 09 2021 at 17:41):

John Baez said:

I'm not learning much yet. :upside_down:

then it sounds like you should maybe come to the talk :wink:

John Baez (Feb 09 2021 at 19:10):

Isn't that cheating? I thought you were supposed to just read the abstract and figure out everything based on that!

Eigil Rischel (Feb 11 2021 at 15:39):

Actually, aren't ther "T-comodels" when T=monoids, precisely the empty set? Since products in $Set^{op}$ are coproducts, and so the unit would be a map $X \to \emptyset$ - ruling out nonempty sets.

Morgan Rogers (he/him) (Feb 11 2021 at 16:02):

To be fair, the resulting category is still a presheaf topos, just an even less exciting one :joy:

John Baez (Feb 11 2021 at 17:09):

Eigil Rischel said:

Actually, aren't the "T-comodels" when T=monoids, precisely the empty set? Since products in $Set^{op}$ are coproducts, and so the unit would be a map $X \to \emptyset$ - ruling out nonempty sets.

Yes, @Mike Stay observed this over on our private ACT@UCR Zulip, and we started wondering about what it meant. Any Lawvere theory with constants (= 0-ary operations) has only empty comodels.

And then someone pointed out the trick where for any Lawvere theory with constants, you can find a theory without constants that has exactly the same models and one more: the empty model! This trick was invented by Lawvere in his thesis:

• John Baez, The group with no elements, and especially this comment by Thomas Read.

John Baez (Feb 11 2021 at 17:10):

I have not tried to understand what the comodels of the Lawvere theory of "possibly empty groups" looks like.

Morgan Rogers (he/him) (Feb 11 2021 at 17:20):

Going for possibly empty monoids, a comodel in Set is a set $X$ equipped with:

• A comultiplication $n: X \to X+X$
• A morphism $e: X \to X$ (replacing the identity element)

subject to the conditions of:

• coassociativity, so $(n + \mathrm{id}) \circ n = (\mathrm{id} + n) \circ n$, and
• left and right coidentities, $(\mathrm{id} + e) \circ n = \iota_1$ and $(e + \mathrm{id}) \circ n = \iota_2$,
  where $\iota_1,\iota_2: X \to X+X$ are the respective coproduct inclusions.

Morgan Rogers (he/him) (Feb 11 2021 at 17:25):

Certainly there is an empty comodel. There is no comodel on the one element set, since there are only two possibilities for $n$, and neither of them is coassociative.

Morgan Rogers (he/him) (Feb 11 2021 at 17:31):

When $X = 2 := \{0,1\}$ is a two-element set, we have a mapping $2 \to 2+2$ mapping $0$ to $0$ in the first copy and $1$ to $1$ in the second copy which is coassociative, which gives us a comodel of the theory of semigroups at least.

But considering this makes one realise that the coidentity conditions can never be realised for an inhabited comodel! If $n$ takes any element of $X$ to the left hand copy in the coproduct $X+X$, then there is no way that we can have $(e + \mathrm{id}) \circ n = \iota_2$, and similarly on the other side!!

Morgan Rogers (he/him) (Feb 11 2021 at 17:32):

So even the comodels of the theory of possibly empty monoids (and hence of possibly empty groups) are automatically trivial.

John Baez (Feb 11 2021 at 18:00):

Nice!

John Baez (Feb 11 2021 at 18:01):

So comodels of the theory of possibly empty monoids are necessarily empty.

Tim Hosgood (Feb 11 2021 at 20:08):

YouTube link for the talk (starting in just under an hour): https://youtu.be/8yGNs97FFck

Morgan Rogers (he/him) (Feb 11 2021 at 20:32):

It's too late for me; how soon will the recording be available?

Matthias Hutzler (Feb 11 2021 at 20:46):

Morgan Rogers (he/him) said:

There is no comodel on the one element set, since there are only two possibilities for $n$, and neither of them is coassociative.

I think the two possibilities for $n$ are in fact coassociative, aren't they? (But of course your point about the coidentities remains valid.)

Tim Hosgood (Feb 11 2021 at 20:49):

Morgan Rogers (he/him) said:

It's too late for me; how soon will the recording be available?

it should be available as soon as youtube has processed the live stream, but I'll post a message in here when it's done

Tim Hosgood (Feb 11 2021 at 20:50):

the Zoom link, just in case anybody had any issues last week: https://topos-institute.zoom.us/j/96259940169?pwd=WU0xMDlxb1hMQjNySGEySkZLS1k2QT09

Morgan Rogers (he/him) (Feb 11 2021 at 20:54):

Matthias Hutzler said:

Morgan Rogers (he/him) said:

There is no comodel on the one element set, since there are only two possibilities for $n$, and neither of them is coassociative.

I think the two possibilities for $n$ are in fact coassociative, aren't they? (But of course your point about the coidentities remains valid.)

Oh, you're right, I miscalculated. Plenty of comodels of semigroups, then!

Matthias Hutzler (Feb 11 2021 at 20:57):

Comodels of semigroups should be pairs of two sets (separated according to the comultiplication), each with an idempotent unary operation, right? (Which is indeed a presheaf category. :grinning_face_with_smiling_eyes: )

Tim Hosgood (Feb 11 2021 at 22:35):

both the slides and the entire recording are now online: details at https://topos.site/topos-colloquium

Tim Hosgood (Feb 11 2021 at 22:36):

or, to save you a click, the video is at https://www.youtube.com/watch?v=8yGNs97FFck and the slides are at https://topos.site/topos-colloquium/assets/slides-2021-02-11.pdf