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.
Jonathan Castello (Mar 24 2020 at 06:02):Is there a preexisting notion for morphisms between more than two objects? I know you can do (marginally) fancy things in (marginally) fancy categories using products and adjunctions and whatnot to juggle various parts of your domain and codomain objects, but without bringing that into the mix — without “encoding” these generalized morphisms into a more standard category — does the concept stand on its own?
Jonathan Castello (Mar 24 2020 at 06:04):I’m sure there are other reasons for morphisms between two objects, but the most obvious one to me is that we write in a linear format rather than a graphical one, so we only have the “left” site and the “right” site of a morphism to compose at. I’m wondering if that’s strictly necessary.
Jonathan Castello (Mar 24 2020 at 06:05):Certainly one notational problem is that the number of open sites grows as you compose such generalized widgets — two widgets with three sites may compose naively to make a widget with four.
Jonathan Castello (Mar 24 2020 at 06:06):(EDIT: fixed, had to go to the desktop app.) ARGH is there some way to fix my auto”correct” in the topic title from “morphine” to “morphism”?
Vinay Madhusudanan (Mar 24 2020 at 06:14):So are you thinking like graphs → hypergraphs with edges → hyperedges, so categories → "hypercategories"(?) with morphisms → hypermorphisms?
Evan Patterson (Mar 24 2020 at 06:17):If the "hypermorphisms" are undirected, you may be looking for an operad or a cylic operad. If they are directed, maybe a polycategory.
Jonathan Castello (Mar 24 2020 at 06:27):Hmm — unclear whether these would be directed. There’s some sense of orientedness, so that only dual sites can compose, but I’m not sure I’d go so far as to call that directedness.
Jonathan Castello (Mar 24 2020 at 06:28):Operads seem to have n-ary composition operators, but I still want binary composition between two “hypermorphisms”.
Jonathan Castello (Mar 24 2020 at 06:31):If I have two “hypermorphisms” with composition sites “left”, “right”, and “center”, where composition is defined between matching left/right sites (as normal) and between matching center sites, I want to be able to compose them on any pair of matching sites.
(You end up with a four-limbed hypermorphism, and it isn’t clear how to define which pairs of sites compose with which others in a self-consistent way... can any left site compose with any right site? Feels vaguely like cobordisms.)
Evan Patterson (Mar 24 2020 at 06:34):Operads can be defined in two equivalent ways. The "full" style is what you reference. I believe the "partial" style is what you're after.
Evan Patterson (Mar 24 2020 at 06:34):See Def 11 here: https://arxiv.org/abs/math/0601129
Evan Patterson (Mar 24 2020 at 06:36):If you want to be able to compose along any site, you need a cyclic operad. See Sec 6 of that paper.
Jonathan Castello (Mar 24 2020 at 06:39):I’ll give that a read; thanks!
Also, props to the authors for using the word “autochthonous”.
...Haha, get it? PROPs! :joy::sob:
Evan Patterson (Mar 24 2020 at 06:44):No problem. Other things to look at, if you're not familiar with them, are Spivak on undirected wiring diagrams (https://arxiv.org/abs/1305.0297) and Fong and Spivak on graphical regular logic (https://golem.ph.utexas.edu/category/2019/08/graphical_regular_logic.html)
Vinay Madhusudanan (Mar 24 2020 at 06:51):Perhaps if we could think of a natural way in which these hypermorphisms arise, then it'd be clear how we would want them to compose, etc.
Vinay Madhusudanan (Mar 24 2020 at 06:53):A typical example of hypergraph is collaboration networks, where using a graph (in the obvious way) would only tell us which pairs of people have collaborated, but using a hypergraph we can specify which people collaborated on the same project (making them all part of a single hyperedge — so each project corresponds to one hyperedge)
Jonathan Castello (Mar 24 2020 at 06:55):I'm thinking rather abstractly in terms of software components -- not just functions, but other computational abstractions. I was recently building up a recognizer for JSON documents matching a particular schema, and I was designing the composable "sub-parsers" by thinking about the different ways in which I'd want to fit them together (with other parsers, or with other things like the input document itself).
Jonathan Castello (Mar 24 2020 at 06:55):I'm somewhat familiar with hypergraphs -- specifically "partitive hypergraphs" (or "partitive set families"). I don't think they're what I'm after, although I could be convinced.
Jonathan Castello (Mar 24 2020 at 07:02):I somewhat suspect that the "right" way to model what I'm thinking of is a category with tensor products and a suitable means of moving object components between the domain and the codomain to isolate the site to compose on. (Like how is isomorphic(*) to in some categories -- you can isolate the component you want to compose on.)
I'm just trying to see how far I can push things without resorting to an "encoding" of this kind.
(*) I am probably using the wrong word here, because isomorphisms are morphisms and I'm properly referring to hom-sets. I think it's "adjoint" but I don't know enough about adjoints :sweat_smile:
Vinay Madhusudanan (Mar 24 2020 at 07:07):Yeah. it's adjoint associativity or tensor-hom adjunction. Those hom sets are naturally isomorphic
Jonathan Castello (Mar 24 2020 at 07:34):Spivak's paper on undirected wiring diagrams is really interesting. So far, it seems like it's unimportant that there's a single "outer interface" and multiple "inner interfaces" for the diagrams -- you could imagine inverting the outer circle so that you have a graph of holes and cables connecting two or more holes. (Heh, almost a hypergraph, except that cables connect to holes at indexed points on the hole.)
John Baez (Mar 24 2020 at 16:53):If one is interested in "morphisms between more than 2 objects", one should certainly learn about multicategories, polycategories and cyclic operads. They're all explained in the nLab, I think.
Joachim Kock (Mar 28 2020 at 11:54):Vinay Madhusudanan said:
So are you thinking like graphs → hypergraphs with edges → hyperedges, so categories → "hypercategories"(?) with morphisms → hypermorphisms?
This intuition can be formalised, and then the missing notion of 'hypercategories' is that of properads. There is a separate discussion thread on properads (although the discussion there eventually went in other directions).
Joachim Kock (Mar 28 2020 at 12:06):There is one subtle point, which may be worth a remark: when seeing categories as directed graphs with extra structure, the objects are nodes and the arrows are edges. But when we go to more complicated structures such as operads (multicategories) and various generalisations, the objects are the edges and the operations (multi-arrows) are the nodes!
This discrepancy is solved when we arrive at (directed) hypergraphs and properads. The point is simply that the notion of hypergraph is self-dual, in the sense that one can interchange the roles played by nodes and hyperedges and get a hypergraph again. This means that the category of ordinary directed graphs admits two embeddings into the category of directed hypergraphs. The most obvious one simply interprets edges as hyperedges. The second embedding sends edges to (1,1)-nodes (and sends nodes to hyperedges). From the viewpoint of categories and properads, this second embedding is more relevant: there is a notion of free properad on a directed hypergraph, defining a free-properad monad on the category of directed hypergraphs. This monad restricts along the second embedding to give precisely the familiar free-category monad on directed graphs.
(Details can be found in my paper Graphs, hypergraphs, and properads.)
Joachim Kock (Mar 28 2020 at 12:16):Jonathan Castello said:
Hmm — unclear whether these would be directed. There’s some sense of orientedness, so that only dual sites can compose, but I’m not sure I’d go so far as to call that directedness.
Yes, when giving up the notion of directedness, the notion of duality -- involutive structure -- is a very good substitute, in order to keep some control on how building blocks can be put together.
Jonathan Beardsley (Mar 28 2020 at 12:43):Also go check out #basic questions>properads
Joachim Kock (Mar 28 2020 at 13:58):Joachim Kock said:
Yes, when giving up the notion of directedness, the notion of duality -- involutive structure -- is a very good substitute, in order to keep some control on how building blocks can be put together.
Sorry, I think that was not a very helpful remark. Let me try to explain it with an example. To any tree T there is associated a free operad: the colours are the edges, and the operations are the T-trees. A T-tree is a morphism from any tree to T. A morphism takes nodes to nodes and edges to edges, respecting all incidences and arities of the nodes. One quickly sees that T-trees are in fact just subtrees in T: because of the direction inherent in the notion of rooted trees, one cannot run backwards. This means that free operads on trees are nice finite objects; they play a crucial role in the theory of operads: for example one can characterise operads a sheaves on the category of (free operads on) trees.
Suppose now we try to do the same thing for unrooted (hence undirected) trees and (coloured) cyclic operads. The following annoying phenomenon now occurs: T-trees are no longer just subtrees, and are not necessarily finite. As an example, take T to be the 2-corolla, that is, the tree with one vertex and two open-ended edges attached to it. Call these edges i and j. Now a possible T-tree is any linear tree L. This admits a tree morphism to T by mapping the edges of L to i and j alternatingly. The lack of direction (or the lack of distinction between in and out), allows us to run around in T as long as we want. In particular, the free cyclic operad on T is not finite.
This problem is fixed if we change the whole set-up and demand the set of colours of cyclic operads to be involutive sets, so that each colour has a dual colour. This is very natural also for undirected graphs and trees:
Define an undirected graph or tree to be a configuration consisting of: a set V of vertices, a set-with-a-fixpoint-free-involution A of arcs, and an incidence relation between them A <- M -> V (and some axioms depending on what you exactly want to model). The upshot is that each undirected edge is encoded by two arcs interchanged by the involution, say a <-> a'. The way an edge connects two vertices v and w is given by v being incident to a and w being incident to a'. Maybe all this looks a bit weird at first sight, but soon it will look quite natural.
Now let us come back to the 2-corolla T: it has one vertex v, and four arcs i, i', j, j'; the involution is indicated with primes. The arcs i' and j are incident to v. The arcs i and j' are the ports, now explicitly part of the data. Now the involutions prevent us from running back and forth like in the naive set-up. (So see this, try the linear tree L with two vertices v and w, arcs i, i', j, j', k, k', and the following incidences: v is incident to i' and j, while w is incident to j' and k. (This means that the whole tree L has two ports, i and k'.) Since a map of trees must respect the incidence as well as the involution, it is clear that L cannot map to T. In the involutive set-up, the notion of free cyclic operad on a unrooted trees works as desired, and there is again a nerve theorem characterising cyclic operads as sheaves.
It should be noted that you can still have cyclic operads with ordinary sets of colours: just take involutive sets with trivial involution. The fixpoint-free condition is mostly important to get the combinatorics right.