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: Initial algebras as heteromorphisms

Bruno Gavranović (Nov 14 2022 at 18:52):

Since functors need not be endofunctors, is there a reason why endofunctor algebras (defined as morphisms) can't be functor algebras (defined as heteromorphisms)?

That is, given an endofunctor $F : \mathcal{C} \to \mathcal{C}$ we define an algebra of it as a choice of $A : \mathcal{C}$ and a morphism in $\textsf{Hom}_{C}(F(A), A)$.

Now, for heteromorphisms, they're defined as follows. Given a functor $G : \mathcal{C} \to \mathcal{D}$ and two objects $C : \mathcal{C}$ and $D : \mathcal{D}$ we can, following nLab, define a set of heteromorphisms as $\textsf{Het}_{\mathcal{C}, \mathcal{D}}(C, D) \coloneqq \textsf{Hom}_{\mathcal{D}}(G(C), D)$.

I'm wondering what happens if we try to define functor algebras precisely as these heteromorphisms above. Of course now we don't go back to where we started, but that's okay since the idea is about generalising endo-maps to hetero-maps.

Of course, one could argue that we get much less out now with this generalisation, and I think I agree, but conceptually it seems like a unexplored concept. Has anyone written anything about it?

I'm asking because it looks like this is a step towards generalising this to the dependent setting, which is the one I'm really interested in.

Dylan Braithwaite (Nov 14 2022 at 19:03):

In 'Monads need not be Endofunctors' they define algebras for relative monads. So that's one (less general) treatment of algebras for heterofunctors

Bruno Gavranović (Nov 14 2022 at 19:04):

Ah, thanks. Is this less general precisely in the ways that an algebra for a monad is less general than an algebra for an endofunctor?

Dylan Braithwaite (Nov 14 2022 at 19:09):

Yeah. I just meant that they're defined only for relative monads, and subject to laws similar to the laws for an algebra over an ordinary monad

Mike Shulman (Nov 14 2022 at 19:12):

Possibly related: [[dialgebra]]

Bruno Gavranović (Nov 14 2022 at 19:14):

Ah, I was always wondering what happens if we take the definition of a natural transformation as an end and instead take the coend of the same functor. It looks like we get a dialgebra.

Mike Shulman (Nov 14 2022 at 19:17):

Well, we get a quotient of the set of all dialgebras.

Bruno Gavranović (Nov 14 2022 at 19:23):

I'm also finding there's a notion of an algebra for a profunctor.

Nathanael Arkor (Nov 14 2022 at 20:47):

Bruno Gavranovic said:

Ah, thanks. Is this less general precisely in the ways that an algebra for a monad is less general than an algebra for an endofunctor?

If you drop the compatibility laws for the unit and multiplication, then you should get a notion of algebra for a functor that generalises algebras for a relative monad in the same way an algebra for an endofunctor generalises algebras for a monad.

Nathanael Arkor (Nov 14 2022 at 20:48):

And your motivation seems similar to the original motivation for relative monads.

Morgan Rogers (he/him) (Nov 15 2022 at 06:20):

@Bruno Gavranovic beware that if you form a category out of heteromorphisms you now have to specify morphisms at both the domain and codomain to complete a square (which will produce a lot more morphisms unless you constrain or quotient somehow), whereas for algebras or dialgebras one only defines a single morphism.

Bruno Gavranović (Nov 22 2022 at 00:12):

Mike Shulman said:

Well, we get a quotient of the set of all dialgebras.

I remembered that a way to not quotient is instead to compute the lax coend $\square\int^{X} \text{discr}(\mathcal{D}(FX, GX))$, where $\square\int$ is the lax coend, $F, G : \mathcal{C} \to \mathcal{D}$ and $\text{discr} : \mathbf{Set} \to \mathbf{Cat}$. I believe this gets us the category of $F, G$-dialgebras .

Mike Shulman (Nov 22 2022 at 01:23):

Really? It seems to me that the morphisms in that lax coend from $x : FX \to GX$ to $y : FY \to GY$ would be generated by pairs $(\phi : X\to Y, z : FY \to GX)$ such that $G \phi \circ z = y$ and $z \circ F\phi = x$. A dialgebra morphism would instead be a pair $(\phi : X\to Y, w : FX \to GY)$ such that $y \circ F\phi = w$ and $G\phi \circ x = w$.

Matteo Capucci (he/him) (Nov 22 2022 at 10:09):

Ist $(F,G)$-$\bf Dialg$ 'just' $F \downarrow G$?

fosco (Nov 22 2022 at 10:15):

@Matteo Capucci (he/him) no, the comma category is larger: an object in the comma is a triple $(A,B,FA\to GB)$, whereas in $F,G\text{-Dialg}$ $A=B$.

Mike Shulman (Nov 22 2022 at 10:22):

2-categorically, it's the [[inserter]] of $F$ and $G$.

Matteo Capucci (he/him) (Nov 22 2022 at 16:27):

fosco said:

Matteo Capucci (he/him) no, the comma category is larger: an object in the comma is a triple $(A,B,FA\to GB)$, whereas in $F,G\text{-Dialg}$ $A=B$.

I see

Bruno Gavranović (Nov 23 2022 at 08:58):

Mike Shulman said:

Really? It seems to me that the morphisms in that lax coend from $x : FX \to GX$ to $y : FY \to GY$ would be generated by pairs $(\phi : X\to Y, z : FY \to GX)$ such that $G \phi \circ z = y$ and $z \circ F\phi = x$. A dialgebra morphism would instead be a pair $(\phi : X\to Y, w : FX \to GY)$ such that $y \circ F\phi = w$ and $G\phi \circ x = w$.

Ah, the lax coend picks out the other diagonal. I see what you mean

Bruno Gavranović (Dec 02 2022 at 19:11):

Is it the case the a dialgebra is to a relative monad what an algebra is for a monad? Both dialgebras and relative monads generalise endomaps to not-endo-maps. And just as dialgebras are algebras when one of the functors is identity, so do relative monads reduce to usual monads when one of the functors is identity.

Nathanael Arkor (Dec 02 2022 at 19:18):

There is a definition of algebra for a relative monad, and it's not the same as a dialgebra.