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: ACT20

Topic: July 7: Mario Román's talk

Paolo Perrone (Jul 02 2020 at 02:25):

Hello all! This is the thread of discussion for the talk of Mario Román, "Open Diagrams via Coend Calculus".
Date and time: Tuesday July 7, 11:40 UTC.
Zoom meeting: https://mit.zoom.us/j/7055345747
YouTube live stream: https://www.youtube.com/watch?v=MIfh-LndWv8&list=PLCOXjXDLt3pZDHGYOIqtg1m1lLOURjl1Q

Paolo Perrone (Jul 07 2020 at 11:30):

The talk will start in 10 minutes!

Eigil Rischel (Jul 07 2020 at 11:59):

@Sophie Libkind @Toby Smithe @Jules Hedges : I feel like these "diagrams with holes" are connected to the sort of operations that should be supported on "contexts". Like, given a 'comb', and a context for the outside, one should get a context for the inside.

Jules Hedges (Jul 07 2020 at 12:02):

Yes, for sure. The early part of this stuff was all developed in parallel live on twitter

Jules Hedges (Jul 07 2020 at 12:03):

My talk was reverse engineered from my reworking the foundations of game theory in terms of comb diagrams, which was part of what got everyone thinking about open diagrams in general

Guillaume Boisseau (Jul 07 2020 at 12:05):

@Aleks Kissinger The answer to your question is no in general. What profunctor optics tell us is that two optics are the same iff they coincide on all tambara modules. What you are asking is to have them coincide only on the particular modules that describes morphisms with some auxiliary wires. In general that's not enough

Guillaume Boisseau (Jul 07 2020 at 12:07):

Actually, I don't have a counter-example in mind, but I strongly suspect that it wouldn't be enough

Toby Smithe (Jul 07 2020 at 12:08):

@Eigil Rischel Yeah, there's loads to say on this. I'll talk a bit about it in my talk, but not in any special depth. I'll basically just demonstrate what you described, for Jules' games, using Mario's diagrams.

Mario Román (Jul 07 2020 at 12:09):

Jules Hedges said:

My talk was reverse engineered from my reworking the foundations of game theory in terms of comb diagrams, which was part of what got everyone thinking about open diagrams in general

In fact, the first moment I started going on this direction is on a twit https://twitter.com/mroman42/status/1178781604304637954

For the record, ∫ᵂ (A → W ⊗ B)×(C ⊗ W → D) ≅ ⟨ Duals ⟩ ∫ᵂ (A → W ⊗ B)×(W → C* ⊗ D) ≅ ⟨ Yoneda ⟩ A → (C* ⊗ D) ⊗ B ≅ ⟨ Duals, symmetry ⟩ I → A* ⊗ B ⊗ C* ⊗ D

- Mario Román (@mroman42)

Mario Román (Jul 07 2020 at 12:11):

Guillaume Boisseau said:

Actually, I don't have a counter-example in mind, but I strongly suspect that it wouldn't be enough

Oh, I remember that you had told me something about this, but I was not sure if the counterexample was there. Also the question "What do we need for this?" seems a nice direction.

Guillaume Boisseau (Jul 07 2020 at 12:48):

Almost-counterexample: if two lenses coincide as combs on all morphisms, then we get that their puts coincide, but we only get that get_0 \times !_a = get_1 \times !_a. So if a is "empty" we might not recover that the lenses are equal

Guillaume Boisseau (Jul 07 2020 at 13:19):

Oooops scratch that, we do actually recover that the lenses are equal. Same for prisms.

Tobias Fritz (Jul 07 2020 at 14:04):

Hi all. Perhaps I'm misunderstanding the question, but how about considering combs with a "hole" of type $I \to I$, i.e. the case $B = C = I$ in Mario's notation? Then plugging in morphisms into the hole doesn't really do anything, and the question amounts to asking merely whether morphisms $A \to D$ are in bijection with composable pairs of morphisms $A \to W \to D$ modulo the equivalence $(f,gh) \sim (hf,g)$. Right?

Assuming that this is correct, then this happens if and only if every commutative square, with $A$ top left and $D$ bottom right, has a diagonal filler (bottom left to top right). The monoidal structure now doesn't even play a role anymore. And of course, in most categories it's easy to find particular squares which have no such lift, for example in Set or Rel.

This phenomenon feels vaguely related to Hochschild homology, and perhaps there is a precise relation to the cohomology of the nerve of the category under consideration, but I'm not sure.

Guillaume Boisseau (Jul 07 2020 at 14:08):

It actually is the case that $C(x, z)$ is in bijection with $\int^y C(x, y) \times C(y, z)$ in any category. That's an instance of coend calculus/Yoneda. What you're missing is that W is not fixed here, and that makes the bijection go through. So when the hole has type $I \rightarrow I$ the property always holds.

Tobias Fritz (Jul 07 2020 at 14:13):

I know that $W$ isn't fixed, but I forgot to take the transitive-symmetric closure of the relation $(f,gh)\sim(hf,g)$. Whoops! Then yes, I agree that considering holes of type $I \to I$ doesn't work.

Guillaume Boisseau (Jul 07 2020 at 14:20):

A fake counter-example is traversals: it doesn't even make sense to talk about auxiliary wires in that case, so the only morphisms we can plug in are the $f: C(a, b)$. Then the property doesn't hold, because eg two traversals that differ in the order of iteration will give the same map for all such $f$.
But that's sad: what I'd really want is a counter-example in the non-cartesian monoidal case. I don't have examples sadly. Maybe the probabilistic lenses in Bayesian Open Games?

Aleks Kissinger (Jul 07 2020 at 14:57):

I think it will be true any time a category has a faithful monoidal embedding into a compact closed category. so, a possible place to look for counter-examples are categories with no such faithful embedding. i only know artificial examples of this. e.g. categories you build from generators and relations where adding caps and cups enable more "non-convex" ways to match rules than you had before

Aleks Kissinger (Jul 07 2020 at 14:59):

e.g. a PROP where you have X : 2 -> 0, Y : 0 -> 2, and a rule whose LHS and (Y+id);(id+SWAP);(X+id), where '+' is monoidal product here

Aleks Kissinger (Jul 07 2020 at 15:01):

then, suppose there is also a Z : 1 -> 1. Then Y;(1+Z);X may or may not contain a redex for the rule, depending on whether caps/cups are allowed

Guillaume Boisseau (Jul 07 2020 at 15:14):

Aleks Kissinger said:

I think it will be true any time a category has a faithful monoidal embedding into a compact closed category

I don't think that's true. If we monoidally embed, we get two combs that coincide only on the image of the embedding. And this image does not contain the cups and caps we need to deduce that the original optics are equal.

Mario Román (Jul 07 2020 at 16:48):

I have uploaded the expanded slides here together with some questions: https://www.ioc.ee/~mroman/talks/opendiagrams-act20.pdf

Guillaume Boisseau (Jul 07 2020 at 17:17):

Really pretty slides btw!

Tobias Fritz (Jul 07 2020 at 18:25):

So here's a (rather degenerate) way of constructing different optics of the same type which are contextually equivalent in @Aleks Kissinger sense, meaning that they behave the same with respect to plugging in any morphism (with external wires) into their "hole". Hopefully it's correct now.

Let $\mathcal{M}$ be any commutative monoid, written additively, and consider the symmetric monoidal category with $\mathcal{M}$ as its monoid of objects and only identity morphisms. Then the set of optics

$\int^W \mathrm{Hom}(A,W \otimes B) \times \mathrm{Hom}(W \otimes C, D)$

degenerates to

$\{W \in \mathcal{M} \mid A = W + B \: \land \: D = W + C \}.$

Since any two parallel morphisms are equal, the contextual equivalence with respect to plugging in morphisms with external wires into the holes is trivial: any two optics of the same type are contextually equivalent. However, they nevertheless need not be equal: it's easy to find $\mathcal{M}$ for which the above equations for $W$ can have multiple solutions. For example, take $\mathcal{M}$ to be a monoid of subsets of a fixed ground set with respect to union as addition, and take $A = B = C = D$.

If this construction looks too degenerate to be interesting, then try to consider the skeleton of your favourite SMC, and there's a good chance that you'll find instances where the equations $A \cong W \otimes B$ and $D \cong W \otimes C$ will have multiple non-isomorphic solutions for $W$. This happens for example in the category of abelian groups, where $\mathbb{Z}/n\mathbb{Z} \otimes \mathbb{Z}/m\mathbb{Z} \cong 0$ as soon as $m$ and $n$ are coprime.

Mario Román (Jul 07 2020 at 19:34):

Tobias Fritz said:

So here's a (rather degenerate) way of constructing different optics of the same type which are contextually equivalent in Aleks Kissinger sense, meaning that they behave the same with respect to plugging in any morphism (with external wires) into their "hole". Hopefully it's correct now.

Let $\mathcal{M}$ be any commutative monoid, written additively, and consider the symmetric monoidal category with $\mathcal{M}$ as its monoid of objects and only identity morphisms. Then the set of optics

$\int^W \mathrm{Hom}(A,W \otimes B) \times \mathrm{Hom}(W \otimes C, D)$

degenerates to

$\{W \in \mathcal{M} \mid A = W + B \: \land \: D = W + C \}.$

Since any two parallel morphisms are equal, the contextual equivalence with respect to plugging in morphisms with external wires into the holes is trivial: any two optics of the same type are contextually equivalent. However, they nevertheless need not be equal: it's easy to find $\mathcal{M}$ for which the above equations for $W$ can have multiple solutions. For example, take $\mathcal{M}$ to be a monoid of subsets of a fixed ground set with respect to union as addition, and take $A = B = C = D$.

If this construction looks too degenerate to be interesting, then try to consider the skeleton of your favourite SMC, and there's a good chance that you'll find instances where the equations $A \cong W \otimes B$ and $D \cong W \otimes C$ will have multiple non-isomorphic solutions for $W$. This happens for example in the category of abelian groups, where $\mathbb{Z}/n\mathbb{Z} \otimes \mathbb{Z}/m\mathbb{Z} \cong 0$ as soon as $m$ and $n$ are coprime.

Thank you, @Tobias Fritz. I think this works; and the coend degenerates into a coproduct. That was a really nice question.

Paolo Perrone (Jul 07 2020 at 19:42):

Here's the video!
https://www.youtube.com/watch?v=qnkDtBkHdHA&list=PLCOXjXDLt3pYot9VNdLlZqGajHyZUywdI

Guillaume Boisseau (Jul 07 2020 at 22:07):

@Tobias Fritz Niiice thanks that does seem to work!