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: hypergraph categories

Henry Story (Nov 11 2020 at 17:52):

@David Spivak wrote a very nice and easy to read article higher dimensional models of networks in 2011 on graphs, hypergraphs, graphs based on globes, simplical sets...
For globes you have an implementation in Agda of Globes.
I am believe that 3-uniform hypergraphs $s, r, o : A \to N$ give rise to 2-globes, ie graphs with arrows between arrows. This is known from RDF, which has that structure and has relations between relations named rdf:subPropertyOf.

Ralph Sarkis (Nov 11 2020 at 18:03):

Henry Story said:

David Spivak wrote a very nice and easy to read article higher dimensional models of networks in 2011 on graphs, hypergraphs, graphs based on globes, simplical sets...

From a quick glance at this paper, there is no mention of polygraphs/computads. I was going to suggest to look into those as well as I believe they are more general than globular sets, but I feel I am missing something if they are not mentioned in a paper on higher-dimensional networks.

Henry Story (Nov 11 2020 at 18:11):

Ah I did not know about those :-) I am happy for references to papers that are written in such an easy to approach style. He also wrote a paper in 2019 with @Brendan Fong Hypergraph Categories but that is a lot less easy to get into as it uses string diagrams. Indeed I would not have known had I not been told so that the notion of hypergraph described there is the same as the concept from the 2011 paper.
Note: It turns out (according to nlab) that the category of hypergraphs is equivalent to the category of spans...

One thing I am not clear about from the 2011 paper is the claim that simplicity sets are better for modeling groups. Since RDF is a first order logic, that would mean that one can express with simplicial sets something that is not easy to express in FOL. I wonder how that becomes evident.

John Baez (Nov 11 2020 at 19:48):

Avi Craimer said:

Thanks. If I'm understanding the Wikipedia page right, globular sets are sub-class of the higher-order graph structure where there can only be higher order edges between "parallel" edges.

Yes. I've never thought about higher-order edges between nonparallel edges.

Dan Doel (Nov 11 2020 at 19:51):

You could say that other shapes do that sort of thing, like simplices and cubes. They have to be bordered by other edges in those cases, though.

John Baez (Nov 11 2020 at 19:52):

Henry Story said:

Ah I did not know about those :-) I am happy for references to papers that are written in such an easy to approach style. He also wrote a paper in 2019 with Brendan Fong Hypergraph Categories but that is a lot less easy to get into as it uses string diagrams.

People who like string diagrams tend to think they're very easy to understand - e.g. @Bob Coecke wrote a paper "Kindergarten quantum mechanics" based on the idea that even young kids could understand quantum mechanics if it were explained using string diagrams. But I guess everything needs to be explained well before it's easy to understand.

John Baez (Nov 11 2020 at 19:53):

Anyway, hypergraph categories are a class of categories where the string diagram calculus has extra nice features - precisely the features we take for granted in electrical circuit diagrams.

John Baez (Nov 11 2020 at 19:55):

But while hypergraph categories are connected to hypergraphs, learning about hypergraph categories is not the most direct way to learn about hypergraphs!

Jules Hedges (Nov 11 2020 at 19:55):

John Baez said:

Yes. I've never thought about higher-order edges between nonparallel edges.

Presumably, it's what you get if you have eg. a cubical higher category and forget all the composition structure

Dan Doel (Nov 11 2020 at 20:00):

Also, I once saw a paper where you start with the arrow-only definition of categories, and throw away the $\mathsf{dom}\circ\mathsf{dom} = \mathsf{dom}$ parts. That might give you something along those lines.

Dan Doel (Nov 11 2020 at 20:02):

That gives you something that looks 'higher', but in a way where you can only go to 'lower' dimensions from a high dimensional thing.

Dan Doel (Nov 11 2020 at 20:03):

Although there is also nothing ensuring you ever reach a bottom.

Henry Story (Nov 11 2020 at 20:10):

John Baez said:

People who like string diagrams tend to think they're very easy to understand - e.g. Bob Coecke wrote a paper "Kindergarten quantum mechanics" based on the idea that even young kids could understand quantum mechanics if it were explained using string diagrams. But I guess everything needs to be explained well before it's easy to understand.

I found a simple version of string diagrams very nicely explained in Knowledge Representation in Bicategories of Relations which looks at the hyper-graphs formed by the $s, r, o : A \to N$ structure of RDF, and explains how the rdf:subProperty relation between arrows is the basis of inference. But I am not yet fluent in string diagrams, so there is an extra cognitive cost associated with reading papers described that way, (e.g. I can't so easily tell what it is speaking about by quickly glancing at it). It will come with a bit more exercising (but now I am training in Agda) :-)
Weird that Logic and electrical circuits come together in hyper-graphs...

Avi Craimer (Nov 11 2020 at 20:45):

John Baez said:

Yes. I've never thought about higher-order edges between nonparallel edges.

I was thinking of a higher-order graph expressing the inner workings of a functor. Where each strand of the functorial mapping is either an edge between objects (so a 1_edge) or an edge between morphisms, so a 2_edge. In this case, the 2_edges aren't exactly parallel. Let the strand of the functor F mapping a morphsim g: A->B to F(g) as a directed 2-edge be called $F_g$. Then $s_1 \circ s_2(F_g) = A$ in the source category, then $s1 \circ t2(F_g) = F(A)$ in the target category. Thus, it doesn't seem to follow the globular set equations.

I am sorry if I didn't explain this right. It's easier for me to think about it visually.

John Baez (Nov 11 2020 at 21:55):

Henry Story said:

Weird that logic and electrical circuits come together in hyper-graphs...

Here's the basic idea of a hypergraph category.

When we have a wire we can "branch" it - attach it to two other wires, so that the current flowing in the original wire equals the sum of the currents flowing out the two wires going out. We can also have it "dead end" - just end it, so the current flowing down this wire is zero.

And these two operations, branching and dead-ending, obey a bunch of rules:

axioms for a special commutative frobenius monoid

And these rules are built into the definition of a hypergraph category!

James Wood (Nov 11 2020 at 22:13):

Isn't it even easier – we care about voltage, and voltage in parallel is equal?

John Baez (Nov 11 2020 at 23:39):

It works both for current and voltage. We sum currents (a monoid) and duplicate voltages (a comonoid). All this is in Brendan's and my paper A compositional framework for passive linear circuits.

John Baez (Nov 11 2020 at 23:41):

Kirchhoff's current and voltage laws involve two different hypergraph category structures on the category where morphisms are linear relations.

Henry Story (Nov 12 2020 at 06:47):

That string diagrams have something special to say about hypergraph categories is interesting to me, as RDF has the structure not just of a 3-uniform hypergraph but also of a 4-uniform hypergraph (n-quads or datasets), and by extension it would be interesting to see what 5-quads gives us. I was not aware of that close relation with hyper-graphs, but then I only really started thinking about hypergraphs recently.

Henry Story (Nov 12 2020 at 07:29):

One way I am thinking of it is that from the $s, r, o : A \to N$ category, giving us functors to set that are 3-uniform hypergraphs (Where $A$ stands for Arrow and $N$ for Node, the new $r$ relation gives us a way to color arrows in a graph, or find commonalities between arrows (eg we can express that two arrows are the knows relation and others are the name relation, because they pick out the same object in $N$ via $r$. But since $s$ , $t$ and $r$ have the same codomain $N$, it is possible for some arrows to have start and end points objects that appear as relations for other arrows. This gives a 2 globe $\sigma, \tau : \mathbb{A} \to A$ where $\mathbb{A}$ is not empty.

Henry Story (Nov 12 2020 at 07:36):

Then I am thinking of 4 uniform hypergraphs as giving ways to color groups of arrows together, allowing one to group graphs together. See the illustration here: TimBL_Quads_HyperGraph_Color.pdf. This allows one to then say where information came on the web as shown in this illustration, where the boxes represent computers on the internet LinkedDataHyperGraphs.pdf.

John Baez (Nov 12 2020 at 21:13):

I haven't seen hypergraph categories saying anything interesting to say about n-uniform hypergraphs or other topics in hypergraph theory. It's conceivable that they could - but I haven't seen it yet.

Fabrizio Genovese (Nov 12 2020 at 22:37):

Ralph Sarkis said:

Henry Story said:

David Spivak wrote a very nice and easy to read article higher dimensional models of networks in 2011 on graphs, hypergraphs, graphs based on globes, simplical sets...

From a quick glance at this paper, there is no mention of polygraphs/computads. I was going to suggest to look into those as well as I believe they are more general than globular sets, but I feel I am missing something if they are not mentioned in a paper on higher-dimensional networks.

@Amar Hadzihasanovic 's PhD thesis, first chapter, is a nice place to learn about polygraphs.

Fabrizio Genovese (Nov 12 2020 at 22:43):

The very handwavy idea is that you can see polygraphs as an approach to give you free n-categories, with n going up to $\infty$.

• You can generate a set by just listing its elements. In this sense, sets coincide with their generators and are trivially free.
• In "traditional" category theory, you can generate a free category by giving the objects and some generating morphisms. Then you add identities and you take all the possible compositions of all the generating morphisms, recursively. In practice, this amounts to specify all the possible paths on a given graph. The graph "generates the category" and if you want to be really precise you can say this neatly by saying that there is a monadic adjunction between the category of graphs and the category of categories.
• In 2-category theory, you do the same but also specify some 2-morphisms generators. Now you see that you can't just "add all the possible compositions you can form" because 2-morphisms need to respect some (possibly up to isomorphism) equations, e.g. coherence conditions relating horizontal and vertical composition of 2-morphisms.
• As you go up, these coherence conditions become heavier and heavier. It is impossible to explicitly list them very quickly. Already the full definition of a weak 3-category is a nightmare.
  Polygraphs are a nice tool to express, up to infinity-categories, how to form a free n-category over some generators (for 0-cells, 1-cells, all the way up to n-cells). So for instance they take automatically care of the fact that you cannot give an n-generator $a \xrightarrow{f} b$ if you haven't already specified n-1 generators $a$ and $b$, and so on

sarahzrf (Nov 13 2020 at 00:42):

lol, i was about to say "isnt that what computads are for" and then i glanced up and saw "polygraphs/computads"

sarahzrf (Nov 13 2020 at 00:42):

speaking of which, i have a relevant question https://twitter.com/sarah_zrf/status/1326565832433029120

so is a computad approximately the same as the defining data of a higher inductive type

- category fibered in sarahzrfs (@sarah_zrf)

Dan Doel (Nov 13 2020 at 02:19):

Probably not the same as the ones Agda allows.

sarahzrf (Nov 13 2020 at 02:20):

how so?

Dan Doel (Nov 13 2020 at 02:26):

You can have pretty fancy higher constructors. Like PathP (λ i → P i → T) con1 con2 where P : Path U A B con1 : A → T con2 : B → T

sarahzrf (Nov 13 2020 at 02:40):

oh my

Dan Doel (Nov 13 2020 at 03:18):

I was trying to use stuff like that for something. Delooping maybe.

Henry Story (Nov 16 2020 at 11:38):

It looks like small categories with two points and a number n of arrows from one to the other are also called kronecker quivers (e.g. the article Representations Of The Generalized Kroneckerquiver With Countably Many Arrows).
I wonder what domain of mathematics that comes from. It seems to be the same structure as that of hypergraphs, as far as I can see.

Henry Story (Nov 16 2020 at 11:42):

John Baez said:

I haven't seen hypergraph categories saying anything interesting to say about n-uniform hypergraphs or other topics in hypergraph theory. It's conceivable that they could - but I haven't seen it yet.

As I understand in Category Theory the category in which an object is embedded determines through its network of relations to other objects in the category all that can be said about an object. If the hypergraph category has hypergraphs as objects (or a Kronecker Quivers?) then should the Category of Hypergraphs not tell us everything there is to know about the hypergraphs? Or is it perhaps that there are other more interesting categories in which those appear that could tell us more?

Jens Hemelaer (Nov 16 2020 at 12:49):

Directed graphs are used for studying representations of algebras, and then they are called quivers. For a quiver $\Gamma$, the category of representations is the functor category $\mathrm{Fun}(\Gamma,\mathbf{Vect})$ into the category of vector spaces, and this category is equivalent to the category of representations of the path algebra. The representation theory of the Kronecker quiver on $n$ arrows is, I think, easy for $n=1$, more difficult for $n=2$, and "wild" for $n \geq 3$ (classification is as least as difficult as classifying representations for any other finite-dimensional algebra).

John Baez (Nov 16 2020 at 16:06):

Henry Story said:

John Baez said:

I haven't seen hypergraph categories saying anything interesting to say about n-uniform hypergraphs or other topics in hypergraph theory. It's conceivable that they could - but I haven't seen it yet.

As I understand in Category Theory the category in which an object is embedded determines through its network of relations to other objects in the category all that can be said about an object. If the hypergraph category has hypergraphs as objects..

I wasn't talking about the category with hypergraphs as objects. I wasn't talking about "the hypergraph category". I was talking about "hypergraph categories". A hypergraph category is not a category with hypergraphs as objects.

A hypergraph category is a category where the string diagrams depicting morphisms in the category can be seen as hypergraphs. But that's not the easy way to understand hypergraph categories! The easy way is this:

John Baez said:

Here's the basic idea of a hypergraph category.

When we have a wire we can "branch" it - attach it to two other wires, so that the current flowing in the original wire equals the sum of the currents flowing out the two wires going out. We can also have it "dead end" - just end it, so the current flowing down this wire is zero.

And these two operations, branching and dead-ending, obey a bunch of rules:

axioms for a special commutative frobenius monoid

And these rules are built into the definition of a hypergraph category!

Henry Story (Nov 16 2020 at 16:49):

Ah, I see. I think @Evan Patterson describes RDF as a hypergraph category, understood as "one where the string diagrams form a hypergraph" as you say, in Knowledge Representation in Bicategories of Relations. At least that is where I first read about a Frobenius monoid and the word hypergraph is used once there.

Since RDF is also 3-uniform hypergraph, or 3 arrowed Quiver Instance (to Set) I was thinking these were just different presentations of the same idea.

I guess the first question is: Is Evan's Bicategory of relations a hypergraph category in your sense? If yes, the second question would be: is there some obvious/automatic way to extend this to RDF Quads which is based on 4-arrowed Quivers...

John Baez (Nov 16 2020 at 17:16):

I don't know "Evan's bicategory of relations", but a hypergraph category is a category, not a bicategory, so your question doesn't quite parse.

The usual category of sets and relations between sets is not a hypergraph category, unless I'm sorely confused.

The usual category of sets and corelations between sets is a hypergraph category.

The category of vector spaces and linear relations between vector spaces is a hypergraph category.

The latter two facts should be in Fong's paper Hypergraph categories.

I suspect that you should not concern yourself with hypergraph categories, since everything I'm saying is orthogonal to what you actually care about.

Jules Hedges (Nov 16 2020 at 17:26):

John Baez said:

The usual category of sets and relations between sets is not a hypergraph category, unless I'm sorely confused.

I think it is... I think that the relation $\Delta : X \to X \times X$ given by $x \Delta (x, x)$ for all $x$, and the relation $\nabla : X \times X \to X$ given by $(x, x) \nabla x$ form the comonoid and monoid of a s.c. frobenius algebra

Dan Doel (Nov 16 2020 at 17:35):

Rel is one of the examples on nlab.

Cole Comfort (Nov 16 2020 at 17:35):

Oops, I read it as FRel before, but it is true for Rel as well, I am quite sure. I think this is true for the tensor induced by the product of sets, because it is compact closed, but I am not so sure for the coproduct. The only equation to check would be the infinite case(s).

Chad Nester (Nov 16 2020 at 17:40):

Brendan Fong’s paper (linked above) defines a hypergraph category to be a symmetric monoidal category in which every object is equipped coherently with the structure of a commutative special Frobenius algebra. Rel is absolutely one of these.

Jules Hedges (Nov 16 2020 at 17:42):

Rel also has the nice property that you can just define arbitrary spiders directly: the spider relation $X^{\otimes i} \to X^{\otimes j}$ for $i, j > 0$ is given by $(x_1, \ldots, x_i) R (x'_1, \ldots, x'_j)$ iff $x_1 = \cdots = x_i = x'_1 = \cdots = x'_j$

Jules Hedges (Nov 16 2020 at 17:43):

As Bob put it once: hypergraph categories are really about spiders, "special commutative frobenius algebra" is just the thing that you name drop if you're writing a LiCS paper and want to show off

Cole Comfort (Nov 16 2020 at 17:44):

Jules Hedges said:

As Bob put it once: hypergraph categories are really about spiders, "special commutative frobenius algebra" is just the thing that you name drop if you're writing a LiCS paper and want to show off

I mean, I like the name hyper-edges, because spiders don't immediately convey the topological information of the definition.

John van de Wetering (Nov 16 2020 at 20:20):

To me the name hyper-edge implies that it is not the important thing, but rather the stuff that is connecting the important things (if that makes sense). While the weirdness of the name 'spider' implies that that is indeed the thing you should care about.
With the name hyper-edge it also doesn't really imply for me how they compose and even that you should be able to compose them, while the name spider and the visual image that gives suggests a central hub (the spider body) with wires coming out (its legs) that obviously compose by connecting the legs.

John van de Wetering (Nov 16 2020 at 20:20):

Maybe this is just incoherent rambling, but I don't like the term hyper-edge for this :P

John Baez (Nov 17 2020 at 04:36):

Jules Hedges said:

John Baez said:

The usual category of sets and relations between sets is not a hypergraph category, unless I'm sorely confused.

I think it is... I think that the relation $\Delta : X \to X \times X$ given by $x \Delta (x, x)$ for all $x$, and the relation $\nabla : X \times X \to X$ given by $(x, x) \nabla x$ form the comonoid and monoid of a s.c. frobenius algebra

Interesting! I was talking about $(\mathsf{FinRel}, +)$. You seem to be talking about $(\mathsf{FinRel}, \times)$.

I am claiming that $(\mathsf{FinRel}, +)$ is not a hypergraph category. I'm completely sure that $(\mathsf{FinCorel}, +)$ is a hypergraph category.

You seem to be claiming that $(\mathsf{FinRel}, \times)$ is a hypergraph category. That's interesting if true. I'll check it out!

The nLab page is too vague on this issue.

John Baez (Nov 17 2020 at 04:41):

(Here by the way I'm using $+$ and $\times$ to mean the monoidal structures coming from coproducts and products in $\mathsf{FinSet}$. It's a bit confusing because the $+$ monoidal structure on $\mathsf{FinRel}$ is both the coproduct and product in $\mathsf{FinRel}$.)

Jules Hedges (Nov 17 2020 at 10:43):

$(Rel, +)$ is not a hypergraph category because its monoidal product is cartesian, which implies that it is not compact closed

John Baez (Nov 17 2020 at 16:17):

Okay, good - that's a clean proof.

sarahzrf (Nov 18 2020 at 05:17):

John Baez said:

(Here by the way I'm using $+$ and $\times$ to mean the monoidal structures coming from coproducts and products in $\mathsf{FinSet}$. It's a bit confusing because the $+$ monoidal structure on $\mathsf{FinRel}$ is both the coproduct and product in $\mathsf{FinRel}$.)

maybe use ⊗ and ⊕?

sarahzrf (Nov 18 2020 at 05:18):

it's a good analogy to Vect, i think

sarahzrf (Nov 18 2020 at 05:18):

(...barely an analogy, even)

John Baez (Nov 18 2020 at 05:53):

Yes, that'd be good. We're dealing with free modules of the rig of booleans and homomorphisms between these, after all!

sarahzrf (Nov 18 2020 at 07:12):

booleans if you take LEM, perhaps (:

Cole Comfort (Nov 18 2020 at 10:13):

Everyone knows that $({\sf FinRel},+)$ is presented by the prop for the free special bicommutative bialgebra. Is it possible to give a presentation for the skeleton of $({\sf Rel},+)$, where say, one only considers the countably infinite set, in terms of generators and relations as a symmetric monoidal theory? Or even just ${\sf FinSet}$?

Nathanael Arkor (Nov 18 2020 at 11:15):

FinSet is equivalent to the free category with binary/finite coproducts on a single generator, while Set is obtained by replacing "finite" with "small". Similarly, wouldn't you obtain Rel by switching from binary tensors to infinitary tensors?

sarahzrf (Nov 18 2020 at 13:33):

wouldn't it be finite coproducts?

Nathanael Arkor (Nov 18 2020 at 13:42):

Yes, I meant to describe both FinSet and Set, and ended up merging the two somehow :sweat_smile: Thanks.

Chad Nester (Nov 18 2020 at 15:14):

Nathanael Arkor said:

FinSet is equivalent to the free category with binary/finite coproducts on a single generator, while Set is obtained by replacing "finite" with "small". Similarly, wouldn't you obtain Rel by switching from binary tensors to infinitary tensors?

I find the fact that Set is equivalent to the free category with coproducts on a single generator quite surprising. Is there somewhere I can read about this?

Nathanael Arkor (Nov 18 2020 at 15:20):

I don't know if there's a classic reference, but it comes up in the study of algebraic theories. @Todd Trimble discusses it here, for instance.

Nathanael Arkor (Nov 18 2020 at 15:21):

Intuitively, it comes from the fact that we can build sets up by taking a disjoint union of singleton sets, one for each element.

Chad Nester (Nov 18 2020 at 15:22):

That makes sense. Thanks!

Dan Doel (Nov 18 2020 at 16:10):

Pretty sure it's false in my world. :)

John Baez (Nov 18 2020 at 16:47):

@Cole Comfort - What do you mean by "only considers the countably infinite set"? Are you talking about a variant of $\mathsf{Rel}$: the category of countable sets and relations?

Cole Comfort (Nov 18 2020 at 17:52):

John Baez said:

Cole Comfort - What do you mean by "only considers the countably infinite set"? Are you talking about a variant of $\mathsf{Rel}$: the category of countable sets and relations?

Yes, I imagine that uncountable sets would maybe make it harder; or at least further away from my intuition for the finite case

John Baez (Nov 18 2020 at 20:11):

Okay.

I doubt uncountable sets are really harder than countable ones. One annoying thing is that $\mathsf{Rel}$ is a large category and there's no upper bound on the cardinality of the sets involved, so some size issues intervene.

But if we stick to sets of cardinality $\lt \kappa$ for some cardinal $\kappa$ we should be fine. And I doubt it matters a whole lot whether $\kappa = \aleph_1$ (which gives the countable case) or some other cardinal.

John Baez (Nov 18 2020 at 20:11):

Then I imagine we can do something like this: we say the object $1$ is a "special bicommutative $\kappa$-bimonoid".

John Baez (Nov 18 2020 at 20:13):

By this I mean it comes with an $\alpha$-ary multiplication and comultiplication for every cardinal $\alpha \lt \kappa$, obeying some analogues of the usual rules for a special bicommutative bimonoid.

John Baez (Nov 18 2020 at 20:17):

By the way, there's a bunch of stuff about "infinitary Lawvere theories" on the nLab, where we allow operations of infinite arities $\le \kappa$ for some $\kappa$. They work a lot like ordinary Lawvere theories.

But now you're getting us into "infinitary props". I don't recall anyone studying these yet.

John Baez (Nov 18 2020 at 20:19):

To study them really nicely, I think you might need a generalization of symmetric monoidal category that allows for infinite tensor products. I don't recall anyone studying that yet.... except of course for infinite cartesian products (or cocartesian coproducts).

Dan Doel (Nov 18 2020 at 20:21):

They'd be a bit odd, for the scenarios I'm familiar with, at least.

John Baez (Nov 18 2020 at 20:23):

There's been a bunch of work on infinite tensor products of vector spaces...

John Baez (Nov 18 2020 at 20:24):

... they show up in quantum physics. Von Neumann wrote about infinite tensor products of Hilbert spaces, and so did my thesis advisor Irving Segal, so I happen to know a bit about that stuff.

Dan Doel (Nov 18 2020 at 20:25):

E.G. for algebraic effects, you use infinitary products to pass a value to a continuation, which is equivalent to projecting from an infinite product. But if you put that in a linear logic scenario, you probably still want it to be an infinite cartesian product, not an infinite tensor product.

Cole Comfort (Nov 18 2020 at 20:27):

John Baez said:

By the way, there's a bunch of stuff about "infinitary Lawvere theories" on the nLab, where we allow operations of infinite arities $\le \kappa$ for some $\kappa$. They work a lot like ordinary Lawvere theories.

I wasn't aware of this, thanks for the insight!

John Baez (Nov 18 2020 at 20:33):

I was scared of them at first but then I realized they work just the same way as ordinary Lawvere theories, just replacing the set $\{0,1,2,\dots\}$ by a bigger cardinal:

https://ncatlab.org/nlab/show/algebraic+theory#infinitary_operations

Henry Story (Nov 24 2020 at 23:05):

One difficulty I had initially when working with Category and the Semantic Web was that I liked to think of RDF relations spacially: as arrows in the real world between individual entities. (I may have gotten that from some thinking from David Lewis on Mereology). When we write :tim foaf:knows :VintCerf . I can imagine an arrow going from Tim Berners Lee the individual to Vint Cerf in space(time?).On the other hand, when working in Functional Programming the main category is that of Sets and functions, and there we have sets related to other sets via functions. Individuals can be retrieved one is told as functions from the final object $\mathbb{1}$. In Set the arrows seem to be occurring in a more Platonic realm: we are more interested in schemas and generalities than individuals. So for a long time I was wondering how come the graph based constructions of RDF that seemed so close to that of Category Theory came together.
Reading Spivak's work on Functorial Databases the great discovery was that any functor from a small category of schemas to Set, also gives rise to what is known as a Grothendieck Construction, a category where individuals from the sets are related by uniquely typed arrows. The same idea can be transposed to Rel and the bicategories of relations following Evan Patterson's article. So here we have something much closer to my initial intuition.
As I understand Grothendieck was working on bringing topology and algebra together. What was the big idea mathematically behind the Grothendieck construction? Is it really a topological move? It must be an important concept to have received his name.
(This could be another reason I can add for me dig into @Tai-Danae Bradley's book on topology when I manage to get some spare time.)

John Baez (Nov 24 2020 at 23:49):

What was the big idea mathematically behind the Grothendieck construction? Is it really a topological move? It must be an important concept to have received his name.

I've heard people say it's a surprisingly simple concept to have received his name. Of course it could be simple yet important.

I think he was considering examples very much like this: for each ring you have a category of modules, and for each homomorphism of rings you get a functor between these categories. You would like to "glue together" all these categories and get a single category where an object is a ring and a module of that ring. That's what the Grothendieck construction does.

John Baez (Nov 24 2020 at 23:51):

In general, the construction just answers this question:

"For each thing $x$ I have a category $M(x)$, and for each map of things $f: x \to y$ I have a functor $M(f) : M(x) \to M(y)$. How can I combine all these categories $M(x)$ into one big category?"

Tobias Fritz (Jan 19 2024 at 18:01):

Is there any literature on a weaker version of hypergraph categories where the Frobenius structures on the objects are not required to be special? The paradigmatic example I have in mind would be the Kleisli category of the multiset monad. Intuitively, that's a category similar to $\mathsf{Rel}$, but with "multirelations" instead of relations, that is where two things can be related in any nonnegative integer number of ways.

Tobias Fritz (Jan 19 2024 at 18:02):

I just would like to be able to point to the definition, so I'm not really looking for anything beyond that.

John Baez (Jan 19 2024 at 23:24):

I've never seen anything about that. But: in exactly the same way that Fong and Spivak related hypergraph categories in an elegant manner to the symmetric monoidal category $\mathsf{FinCospan}$ of cospans between finite sets (with the "disjoint union" monoidal structure), we should be able to relate your proposed "subhypergraph" categories to the symmetric monoidal category $\mathsf{2Cob}$ of 2d cobordisms. The point is that:

1) just as $\mathsf{FinCospan}$ is (equivalent to) the prop for special commutative Frobenius algebras (see Coya and Fong and references therein), $\mathsf{2Cob}$ is the prop for commutative Frobenius algebras.

2) Fong and Spivak described hypergraph categories as algebras of an operad built from $\mathsf{FinCospan}$ via a construction that can, I believe, easily be adapted to $\mathsf{2Cob}$.

John Baez (Jan 19 2024 at 23:27):

So you may have to do some work yourself, but it should be fairly elegant and nice.

Before the Fong-Spivak paper, defining hypergraph categories was a somewhat suspicious business - suspicious because each object is required to have a special commutative Frobenius algebra structure, but the morphisms are not required to preserve this sturcture.

Tobias Fritz (Jan 20 2024 at 01:46):

Right, great point!