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.
@John Baez you might remember that a while back i was considering kan extensions along of functors that pick out commutative monoids & that you remarked on an apparent similarity to how one gets finitary monads out of Lawvere theories
well, i finally got around to figuring out how those tie together
in particular: if you have a lawvere theory , and you put the cocartesian monoidal structure on the category of models , then there's a canonical commutative monoid structure for the free model on one generator (since there's a canonical commutative monoid structure for every object when the monoidal product is +)
then if you use this commutative monoid with the construction i was considering—you take the functor from FinSet that picks it out, and then you take the left Kan extension along the inclusion into Set—you get the free-model-of-Q functor Set → QMod
Oh wow, I think this is a different connection than the one I was imagining, or trying to hint at.
is it?
the main thing that seemed common to me was doing some sort of left kan extension from FinSet to Set and/or the phenomenon of "summing over fibers" that seems to pop up as an action on morphisms
I would need to read our original conversation to know what I was thinking, exactly.
But I feel on the brink of making up something...
here's the end of it, btw https://twitter.com/johncarlosbaez/status/1291476247290114051
@sarah_zrf You mean when your symmetric monoidal category is also cocomplete? This reminds me a lot of how Lawvere theories induce monads on Set.... but it's different I think. Definitely worth looking at! I don't think I've seen it!
- John Carlos Baez (@johncarlosbaez)(and this is what you get, at least in the case of a commutative monoid in (Set, ×) https://twitter.com/sarah_zrf/status/1292140904862625792)
anyway, though, i'm kinda interested in poking a bit further at my original construction anyway—something is intriguing to me about the way a "summing over fibers" operation drops out of doing a left kan extension, when left kan extensions are themselves kind of a categorified "integrating over fibers" operation
i'm wondering about, like... hm
This is nice. It feels like the way that clubs take the free model on 1 and extend it to all categories.
well, it's unclear to me whether there's any way of interpreting a summation over fibers like the one above as being itself a left kan extension (as opposed to the image of a morphism under a functor that is a left kan extension)
so like... we have something that looks sort of microcosm-y, but i dont see how to interpret the small thing as a case of the same concept as the big thing
the pattern here is eluding me
um, maybe this sounds incomprehensible outside of my head :sweat_smile:
Okay, thanks. One thing I was thinking about is that for any Lawvere theory , the category is the category of free finitely generated models of . So, it comes with an embedding
.
We also have a functor
sending each finite set to its free -model.
Now, if we left Kan extend
along the inclusion
I think we get the functor from to sending each set to the -model it freely generates.
right, j ∘ F here is exactly the functor that picks out the monoid i mentioned
Okay... so do you think you're describing the same thing I just did, but in a slicker way? (E.g. I didn't offer proofs of some facts which may be obvious in your approach.)
yeah, because the reasoning i followed was to work out the same thing you just wrote, and then notice that it preserved finite coproducts :)
Okay. I think the "usual" approach to these things (like in Lawvere's thesis) doesn't use anything about FinSet being the Lawvere theory for commutative monoids, or about how every object in a category with finite coproducts gets to be a commutative monoid.
oh sure, i had to go from noticing that it preserved finite coproducts to going "oh huh i guess that means it's the functor corresponding to some monoid in the cocartesian monoidal structure"
i dont think this is necessarily a more natural way to think about it!
but it certainly connects the two constructions
I like to annoy people by telling them the real reason finite sets are important is that FinSet is the free symmetric monoidal category on a commutative monoid object. Maybe you've found more evidence that this is true! :upside_down:
surely the real reason is that the subcategory of finite sets is where we get β from...?
:upside_down:
Let's fight about it.
I thought it was important because it's the opposite of the free Cartesian monoidal category on one object.
so you're siding with john?
Oh, am I?
possibly
youd have to give me a second to decide whether those are the same intension
It sounds slightly different, although they're important for similar reasons.
It's basically the same thing...
Because it's de Bruijn indexing.
In a cocartesian category every object becomes a commutative monoid in a natural way - natural in the technical sense.
Starting from a symmetric monoidal category, we can form its category of commutative monoid objects, and this is a cocartesian category.
So, it's not surprising that the free cocartesian category on one object is the free symmetric monoidal category on a commutative monoid object.
Oh okay.
The second description sounds more complicated, but it's nice because the free symmetric monoidal category on a plain old object is the groupoid of finite sets and bijections.
/me mumbles something about the schanuel topos
That's too fancy for starting out.
dont you do pl
you should like the schanuel topos
I do. But you think about FinSet first before that.
fair enough!
Or plain FinSet.
Eventually you can get really fancy with co de Bruijn, which uses semisimplicial types, I think.
ooo elaborate
oh wait
that sounds suspiciously similar to PSh(FinSet_mono^op)
what does orderedness give you?
dont you want to be able to permute names
No. Permuting names just gives you redundant representations of the same thing.
I mean, it is very similar to , clearly. But more canonical.
what does it classify?
the topos i mean
Anyhow, the idea is that instead of keeping track of variables in scope and then saying which one you use at a leaf, you keep track of which variables are used lower in the tree, and progressively thin things out as you go down. Then at the leaf you just say 'variable', because only one is still in scope.
I don't know what it classifies. I just know it's the structure used. Finite linear orders and monotone injections.
Apparently homotopy folks care about them, too, though, so they must be important.
oh i bet it classifies something like objects w/ decidable equality equipped w/ linear orders
or maybe the linear order is decidable too
anyway yeah i buy the thing abt subtrees/leaves
seems like a pain to have a non-symmetric monoidal structure tho?
well okay i guess thats sort of the point?
The point is to have a unique representation for α-equivalent terms, because that's nice on a computer.
Just check equality, not equality up to n! possible different representations.
If you forget about that part, you can probably do the same thing in the Schanuel topos, or species.
Dan Doel said:
Eventually you can get really fancy with co de Bruijn, which uses semisimplicial types, I think.
I found a paper by Conor McBride which mentions a certain category of semisimplicial types. Is that what you're referring to here?
Yes.
I don't know if this is what you guys are talking about, but in the seminar paper of Lafont, he shows the (probably folklore) result that the free pro of a monoid represents finite ordinals and monotone maps under the coproduct; and similarly, the free prop of a commutative monoid represents finite ordinals and functions under the coproduct. Moreover, the free pro(p) on the unit of the monoid are the monics, and the free pro(p) for the multiplication of the monoid are the epics. And the unit equation is just the epi-mono factorization.
This is a famous folklore result, but it's really good to find locations of actual proofs of these results! I'm currently typing some into the nLab, so thanks!
Here is what I wrote about descriptions of FinSet, including FinSet as the prop for commutative monoids:
I'll add the ref to Lafont's paper.
I think Lafont's paper is worth mentioning, because he extends this representation to more interesting categories, being motivated by these more simple folklore results.
I am working on a dictionary for different props and their semantics, because these things quickly build up in terms of structure/computational expressiveness in a very modular way. From commutative monoids:FinSet, special commutative frobenius algebras:CoSpan(FinSet), commutative bialgebras:Span(FinSet), then quite quickly you get interacting hopf algebras:Linear relations and even more. All of these results are contained in different papers, and when you put things all together, one realizes that there are gaps in the literature!
I consider myself sort of an expert on all these props, and I've decided I had better enter information about them into the nLab before I forget all this stuff. I also plan to write a paper on a bunch of them. So I have to ask: how is your dictionary coming along, how will it be organized, and how it will be accessible? Maybe we could cooperate a bit.
@John Baez
We have organized the paper into various different sections (with the help of @Aleks Kissinger ), although it is nowhere near finished, with most of the proofs not being worked out fully. For each section, we consider a semantic prop and its syntactic presentation and then consider the epimorphisms, monomorphisms, as well as things like the partial isomorphisms (spans of monomorphisms), as well as the spans, cospans, relations and corelations---building things up à-la composing props style of Lack, using distributive laws and pushouts and stuff to build larger props. The idea is to build up the presentations from large to small, so that at each step, only a few new equations are added.
For the different base categories, we start with , then go to , and then , and then , all of these models are strictly included in each other.
By , I mean affine matrices over a field . And by , I mean the full subcategory of with objects generated by for .
There are some technical problems, like the fact that doesn't actually have pullbacks, but these inconsistencies between models can be mostly resolved.
The motivation is from the ZX-calculus side of things, so so far, most of the paper I have only managed to work out fixing and , but I am sure that these things will generalize nicely. But this is not a limiting factor, just where my intuition is coming from. And many of the gaps come from the fact that lots of the things are only worked out in the "qubit" case. But the case of , and are mostly already in the literature.
Also, we intend to discuss the relation to Lagrangian relations, which I know you are very much farmiliar with, because these when these props get more complicated, they quickly start to resemble things in physics. And of course, this is closely related to the stabilizer fragment of the ZX-calculus,
It will be great if we could cooperate, because, I think this is a well-needed resource. As well as finding more props and their semantics that fit into this picture.
I don't know where this should go, because this started as an informal talk and has bloated into a massive dictionary.
This sounds very interesting! I'd love to hear a bit more about it. (I also find it frustrating that all the details are spread throughout the literature, and that's true even just for Lawvere theories.)
By "syntax", do you mean string diagrams, or term calculi/type theories?
(Or both.)
@Nathanael Arkor
Yes, all of the "base" categories are Lawvere theories, but that is the easy part.
By syntax I mean props presented in terms of generators and relations... and the way this is written up is with string diagrams for aesthetic reasons.
@John Baez I am curious which props you had in mind, and if the ones that we are writing up are largely the same.
By Lawvere theory, I really meant the theory of Lawvere theories, as one very particular kind of PROP. The literature is spread out enough for that kind, so if you're considering many more varieties, I can imagine there are many spots to fill!
The motivation is documenting all the syntax and semantics of various props that arise as categories of spans and relations, pretty much. There are many more props out there, but obviously one can't present them all in one place.
Like much of the work on the ZX calculus is closely related to such categories, but the axioms had been discovered in a more-or-less ad hoc way. But there are "canonical" presentations of the different fragments of the ZX calculus, where the axioms arise in very nice ways.
For example, the phase-free fragment of the ZX calculus arises as spans of matrices over , which is a special case of a general presentation of such props in @Fabio Zanasi's thesis https://arxiv.org/abs/1805.03032
And the natural number H-box fragment of the ZH calculus arises as the full subcategory of spans of of finite ordinals and functions where the objects are generated by for https://arxiv.org/abs/2004.05287
I'm biased, but having a type theoretic presentation alongside the string diagrams would be very helpful too :)
I think they both give helpful perspectives, which can be non-obvious just by seeing one.
Indeed as Cole says, in my PhD thesis I documented lots of these syntax -> semantics results for Props, including various that were folklore. So it's probably a good source to look them up.
Other places where there are others being documented (mostly around spans and cospans) are:
Also, @John Baez As you are interested in AffMat, it may be worth checking out this recent paper, which axiomatises Affine linear relations (and so including affine matrices):
Cole wrote:
this started as an informal talk and has bloated into a massive dictionary.
How big so far?
Cole Comfort said:
John Baez I am curious which props you had in mind, and if the ones that we are writing up are largely the same.
I'm currently very interested in props that are sub-props of FinRel, FinCorel, FinSpan and FinCospan. (Maybe I don't need to keep saying "Fin" if we're talking about props, since the objects are always finite numbers.)
I have a story I want to tell about these, and I should probably tell it somewhere and then contribute that information to your massive dictionary.
By the way, the prop Mat(k) is very nice not only when k is a field, but whenever k is a commutative rig. I got Wadsley and Woods to write a paper about it:
I hope you take the information in here and add it to your massive dictionary.
"We are the Borg. Lower your shields and surrender your ships. We will add your biological and technological distinctiveness to our own."
I also hope you suck the juice out of this paper:
In particular we say super-precisely what it means to have a presentation of a prop in terms of generators and relations, and say when a symmetric monoidal category is equivalent to a prop (see Appendix A and B). But also we have some nice examples of props.
I don't know where this should go...
Where have you considered? It might make a nice paper for Compositionality if you can't think of anything better. Is it big enough to become a book?
John Baez said:
Cole wrote:
this started as an informal talk and has bloated into a massive dictionary.
How big so far?
I mean I think it is starting to turn into my phd thesis.
John Baez said:
Cole Comfort said:
John Baez I am curious which props you had in mind, and if the ones that we are writing up are largely the same.
I'm currently very interested in props that are sub-props of FinRel, FinCorel, FinSpan and FinCospan. (Maybe I don't need to keep saying "Fin" if we're talking about props, since the objects are always finite numbers.)
By this do you mean wrt sets and the coproduct?
John Baez said:
By the way, the prop Mat(k) is very nice not only when k is a field, but whenever k is a commutative rig. I got Wadsley and Woods to write a paper about it:
I hope you take the information in here and add it to your massive dictionary.
"We are the Borg. Lower your shields and surrender your ships. We will add your biological and technological distinctiveness to our own."
The only issue with this is that you can't take pushouts or pullbacks because, as far as I know, according to me reading @Fabio Zanasi's thesis, you only get these in general when the ring is a PID.
Now that I am discovering these gaps it is probably worthwhile separating this classification into different papers, because there is lots of original work to be done.
I'm not completely sure what you mean by "the only issue with this". It's definitely true that Mat(k) is a prop whenever k is a commutative rig. (Not just a ring - a rig!)
Other more fancy constructions may require pushouts and pullbacks, and yes, Mat(k) won't have those unless k is reasonably nice.
Let's think about when Mat(k) has pullbacks. Mat(k) is equivalent to the category of free finitely generated k-modules, so let's think about that. I will only try the case where k is a commutative ring, though I love rigs.
Since the category of free finitely generated k-modules has binary products, it will have pullbacks iff it has equalizers, which when k is a ring are the same as "kernels". So for k a commutative ring, Mat(k) will have pullbacks iff the kernel of any map between free finitely generated k-modules is a free finitely generated k-module. If k is a commutative ring, every submodule of a free module is free iff k is a principal ideal domain, and in this case every submodule of a free finitely generated module is also finitely generated.
From all this we get: if k is a PID, Mat(k) has pullbacks.
I'm not sure this is an "if and only if", because I don't know that every submodule is a kernel.
Now I am curious about k case of commutative rigs, e.g. .
Cole Comfort said:
John Baez I am curious which props you had in mind, and if the ones that we are writing up are largely the same.
I'm currently very interested in props that are sub-props of FinRel, FinCorel, FinSpan and FinCospan. (Maybe I don't need to keep saying "Fin" if we're talking about props, since the objects are always finite numbers.)
By this do you mean wrt sets and the coproduct?
Yes, I mean finite sets and disjoint union. I'm in the mood for combinatorics these days.
John Baez said:
I'm not completely sure what you mean by "the only issue with this". It's definitely true that Mat(k) is a prop whenever k is a commutative rig. (Not just a ring - a rig!)
Just that it is nice to be able to be able to take pushouts/pullbacks. I guess the right way to make the dictionary is to start with matrices over a semiring, and then once you want to take pullbacks, then restrict your attention to PIDs.
John Baez said:
I'm not sure this is an "if and only if", because I don't know that every submodule is a kernel.
Yeah, I am not sure either, but I just don't know what class of (semi)rings you could generalize this to and still get this.
It's an interesting question. The proof that when k is a commutative ring,
"every submodule of a finitely generated free k-module is free" k is a PID
is so ridiculously simple (I linked to one) that it should be easy to generalize this direction and discover some sort of "PID rigs".
Anyway, I may be more into this sort of algebra than you, so maybe I should do that.
I think already for it breaks down.
John Baez said:
Cole Comfort said:
John Baez I am curious which props you had in mind, and if the ones that we are writing up are largely the same.
I'm currently very interested in props that are sub-props of FinRel, FinCorel, FinSpan and FinCospan. (Maybe I don't need to keep saying "Fin" if we're talking about props, since the objects are always finite numbers.)
By this do you mean wrt sets and the coproduct?
Yes, I mean finite sets and disjoint union. I'm in the mood for combinatorics these days.
Aren't these examples relatively simple compared to the linear props. Is the idea that you use different generators than the usual ones so that, for example, you can consider the category generated by the "cnot gate" in spans, in the sense that you chain together the multiplication and comultiplication? I am trying to imagine some of the less obvious sub-props.
John Baez said:
I think already for it breaks down.
Yes, @Robin Piedeleu talks about this in his thesis, which is another good resource for such things.
Cole Comfort said:
Aren't these examples relatively simple compared to the linear props?
Yes, they're simple and thus they show up throughout mathematics - there's usually an inverse relation between complexity and pervasiveness - but there are some fascinating ways in which they're all related to each other I guess I should fairly quickly write a nice explanation of what I mean here... maybe a blog article or quick paper.
As you can see, I feel a bit possessive about my ideas... but once I get them out I'll be glad to contribute them to your massive dictionary.
By the way: if it becomes a PhD thesis, that's a great thing. You can put it on the arXiv, then try to publish it as a book or long paper.
John Baez said:
As you can see, I feel a bit possessive about my ideas... but once I get them out I'll be glad to contribute them to your massive dictionary.
Looking forward to it!