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: theory: category theory

Topic: What are string diagrams really?

Nathaniel Virgo (Jan 13 2022 at 11:17):

It seems like there should be a nice slick definition of string diagrams, but if there is it seems like it might not be known, so I thought I'd start a conversation about it. The motivation is to see if I can do something with this idea:

https://twitter.com/NathanielVirgo/status/1481063056645963778?s=20

@_julesh_ Here's a vague thought. One way to think about the wires in a string diagram is as infinite strings of identity morphisms, i.e. f;id;id;id;id;g. Now suppose h is idepotent. Then we should be able to do the same thing, h;h;h;h etc. So idempotent morphisms should have extent.

- Nathaniel Virgo (@NathanielVirgo)

Consider first string diagrams for just a category. These are one-dimensional. The following probably isn't really the right way to set them up, but gives some idea of the sort of thing I'm looking for.

Let $\mathcal{C}$ be a free category. Then define a string diagram on $\mathcal{C}$ as a map $D$ from half-open sub-intervals of $[0,1)$ to morphisms of $\mathcal{C}$ such that if $D([a,b))=f$ and $D([b,c))=g$ then $f$ and $g$ are composable and $D([a,c)) = f;g$. I think that gives you what you should expect for a string diagram: identity morphisms can take up open intervals of $[0,1)$, but other morphisms can only take up single points.

(This is very nearly a functor from $[0,1)$ as a poset to $\mathcal{C}$, except that that would require each point in $[0,1)$ to map to an identity morphism, which isn't what we want.)

The point is that the identity morphisms being the wires sort of happens automatically. If we decide to relax the requirement that $\mathcal{C}$ is a free category then other things can happen, such as the stretching out of idempotent morphisms that I mentioned in my tweet. This suggests to me that it's sort of vaguely on the right track.

Then the question is, how do we go from there to string diagrams for 2-categories (and hence monoidal categories)? It seems like we should be able to iterate the same process, to get a sort of homotopy-like map from $[0,1)$ to maps $[0,1)\to\mathcal{C}$ as described above. Some requirement of continuity needs to be in there somehow.

I probably don't have the experience in topology to guess at the right idea, so I figured I'd post this sketch and see if someone else can see the idea I'm grasping towards and help figure out the details.

The hoped-for end goal is a recipe for graphical languages where you can just sort of turn the crank, putting in the equations you want to model and getting out the topological rules they correspond to, or vice versa. That's probably far too ambitious for what amounts to a hobby project, but it would be pretty cool if it existed.

Jules Hedges (Jan 13 2022 at 11:38):

I think the first problem with this sort of thing is that there's always multiple equivalent formulation as diagrams, and they're all useful for different things and not completely trivial to convert between them. In particular there's topological definitions (like this one) and combinatorial definitions

Jules Hedges (Jan 13 2022 at 11:40):

One version of saying the same thing you're saying is it's a labelled graph equipped with a graph embedding in a 1-dimensional manifold

Fawzi Hreiki (Jan 13 2022 at 11:47):

Wouldn’t it be 2-dimensional?

Jules Hedges (Jan 13 2022 at 12:10):

1-dimensional for free categories

Nathaniel Virgo (Jan 13 2022 at 12:34):

But I guess you wouldn't get this sort of thing if you defined it as a graph embedding directly:

The point is that the identity morphisms being the wires sort of happens automatically. If we decide to relax the requirement that \mathcal{C}C is a free category then other things can happen, such as the stretching out of idempotent morphisms that I mentioned in my tweet. This suggests to me that it's sort of vaguely on the right track.

This is really the hope, that by formulating it the right way you get a recipe for constructing graphical languages "automatically", without having to define them separately each time.

Jules Hedges (Jan 13 2022 at 13:09):

Ah, now I see what you mean, this is interesting :thinking:

Jules Hedges (Jan 13 2022 at 13:15):

I wonder if you can formulate this data as a sheaf on the line

Jules Hedges (Jan 13 2022 at 13:20):

A basic open is an interval $(a, b)$ and we send it to a morphism $f$. If we have 2 overlapping intervals $(a, c)$ and $(b, d)$ with $a < b < c < d$, then the union $(a, d)$ had better be sent to a morphism that's equal to that you get by composing the pieces.... struggling to write down what I mean exactly. It probably isn't a sheaf, but it sounds sort of vaguely sheafy to me

Jules Hedges (Jan 13 2022 at 13:29):

I think this might be a functor from the topology of the line to the twisted arrow category of $\mathcal C$ that satisfies the sheaf condition. If we have an inclusion of intervals $(b, c) \subseteq (a, d)$, then we want to get a restriction morphism $F (a, d) \to F (b, c)$. This morphism must contain whatever's at $(a, b]$ and whatever's at $[c, d)$. Now if we have 2 intervals that overlap we can use these restriction maps to talk about what it means to agree on the overlap

Nathaniel Virgo (Jan 13 2022 at 13:40):

I was thinking earlier that it should be something sheaf-like, but I couldn't see how to make it work. Can you spell out more explicitly what the sheaf condition works out to here?

Jules Hedges (Jan 13 2022 at 13:48):

Not right now because I'm heavily hand-waving... this is an interesting question so I'll probably come back to it later

Simon Burton (Jan 13 2022 at 13:50):

I was chatting with Todd Trimble recently about this, and he mentioned these notes: https://ncatlab.org/toddtrimble/published/Surface+diagrams

Antonin Delpeuch (Jan 13 2022 at 13:51):

I have the feeling that in general, going from the definition of an algebraic structure to a useful definition of the members of the free such structure on a signature is a really non-trivial process. Even in the case of say, monoids: compare the definition of a monoid to the inductive definition of lists: it's already pretty far off! So for rich structures like monoidal categories, it is not so surprising that there is such a long road between the two.
So although I would really love to see a principled way to go from the algebraic definition to a useful description of the corresponding free structure, I am not too hopeful…

Jules Hedges (Jan 13 2022 at 13:57):

This is a lesson I learned from @Conor McBride, that the fact that free monoids are an inductive datatype is an extremely magical fact that should be considered non-trivial, and fails to generalise to higher dimensions. That is, the free monoid monad $F : \mathbf{Set} \to \mathbf{Set}$ has the property that $F(X)$ is the initial algebra of the polynomial functor $G_X : \mathbf{Set} \to \mathbf{Set}$, $G_X (A) = 1 + X \times A$

Tim Hosgood (Jan 13 2022 at 14:42):

back to the sheaf though, it sounds like a sheaf on the cech nerve to me (up to some hand waving), because you want to pick a thing over each open subset, and then an order for those things on each intersection, and then…. etc

Tim Hosgood (Jan 13 2022 at 14:43):

i would normally have absolutely nothing to say in a conversation about this topic, but these “simplicial sheaves” turned up out of the blue in a discussion with some string diagram people at cqc last year

Tim Hosgood (Jan 13 2022 at 14:44):

(as always, i’m half writing a preprint about it, but it’s lingering in a state of abandonment)

Nathaniel Virgo (Jan 14 2022 at 04:22):

I'm not sure if this makes any sense, sorry.

Maybe this works for the sheaf condition, following on from Jules' idea.

For a category $\mathcal{C}$ and a morphism $f \in \mathcal{C}_1$, consider the set of factorisations of $f$, that is, $\operatorname{fact}(f) = \{(a,g,b)\in \mathcal{C}_1\times \mathcal{C}_1\times \mathcal{C}_1 \mid a;g;b = f\}$. I think this extends to a functor $\operatorname{Fact}\colon \operatorname{Tw}(\mathcal{C})\to \mathbf{Set}^\text{op}$, where $\operatorname{Tw}(\mathcal{C})$ is the twisted arrow category.

Then I think we probably want a functor from the topology of the real line to $\operatorname{Tw}(\mathcal{C})$ such that when composed with $\operatorname{Fact}$ it forms a sheaf.

Does that sound right and/or does it relate to the other approaches mentioned? If it's right the next step is to figure out how to extend it to free 2-categories.

Jules Hedges (Jan 15 2022 at 11:06):

What goes wrong with what you crossed out @Nathaniel Virgo ?

Nathaniel Virgo (Jan 15 2022 at 12:03):

I'm still sort of confused about it, but the functor I was thinking of has type $\operatorname{Tw}(\mathcal{C})\to\mathbf{Set}$ and not $\operatorname{Tw}(\mathcal{C})\to \mathbf{Set}^\text{op}$ - it's zooming out that gives you more factorisations, but to be a sheaf it should be the other way round.

(Do we want a single string diagram to be a sheaf anyway? That sounds kind of weird since normally it would be a sheaf of the things you're interested in. But maybe it changes when you're dealing with a sheaves that are valued in something other than sets?)

Tim Hosgood (Jan 15 2022 at 14:18):

i would like to believe that there is a sheaf of diagrams, and a specific string diagram is given by a section of the sheaf

Tim Hosgood (Jan 15 2022 at 14:18):

(at least, this is the framework that one specific example i’ve looked at fits into)

Joshua Meyers (Jan 18 2022 at 02:25):

I think this is just a functor from the posetal category $\mathbb{R}$ to $\mathcal{C}$, i.e. an $\mathbb{R}$-diagram.

Nathaniel Virgo (Jan 18 2022 at 03:46):

@Joshua Meyers it isn't quite. Each point $x\in \mathbb{R}$ has an identity morphism (i.e. $x\le x$), and that has to map to an identity morphism in $\mathcal{C}$. But conceptually at least we want some isolated points in $\mathbb{R}$ to map to non-identity morphisms instead.

In fact it does work if we consider a functor of that type, but it's a bit weird. Let $\mathcal{C}$ be the category with two objects $A$ and $B$ and one non-identity morphism $f\colon A\to B$. Then we can define such a functor as follows. We need a morphism in $\mathcal{C}$ for each pair of real numbers $(x,y)$ such that $x\le y$. Let that be given by

• $\mathrm{id}_A$ if $x\le 0$ and $y\le 0$

• $\mathrm{id}_B$ if $x>0$ and $y>0$

• $f$ otherwise

This is weird though because each point in $\mathbb{R}$ - that is, pairs $(x,x)$ - is mapped to an identity morphism, with the morphism $f$ seeming to exist not at the point 0 (because that maps to $\mathrm{id}_A$) but "infinitesimally above it". I found this hard to make sense of, so in my original post I defined something a bit weaker than a functor, essentially a functor of that type but without the requirement that identities map to identities or even exist at all - I'll explain it in more detail in another post shortly.

Nathaniel Virgo (Jan 18 2022 at 03:49):

I spent a bit of time trying to see if my original idea could be formulated in a more elegant way that might give the expected results when extended to 2-categories.

I realised that my idea can be expressed as a morphism of partial semigroups, aka partial associative magmas. There are some different options for what that could mean, but for now I'm assuming it means a set with a partial binary operation such that if one of $f*(g*h)$ or $(f*g)*h$ is defined then so is the other and they are equal. This is the same as saying it's a semigroup in the category of partial maps.

The point is that the morphisms in a category form a partial semigroup, since two morphisms might not have the right type to be composable, but composition is associative where it's defined. This kind of partial associative composition seems to be a minimal requirement for string diagrams to make sense.

We also have a partial semigroup of half-open subintervals of $[0,1)$, where the composition $[a,b)*[c,d)$ is given by $[a,d)$ if $b=c$, and undefined otherwise.

The idea is that a string diagram for a category is a morphism of partial semigroups from the partial semigroup of half-open intervals to the partial semigroup formed from the morphisms of a free category. This makes sense to me because it says that each sub-interval corresponds to a morphism, and given two with matching end-points we can glue them together to get a larger one.

For a given free category we can consider the set of all string diagrams, defined this way - it's a hom-set of the category of partial semigroups. But in order to move to string diagrams for monoidal categories or 2-categories we probably want that hom-set to be a topological space instead of just a set.

This is why I was thinking about partial continuous maps recently. I figured if we can define a satisfactory notion of partial topological semigroup then we can formulate this in terms of those instead. We can give the partial semigroups induced by categories the indiscrete topology so that all maps into them will be continuous. Hopefully that would give a way to put a topology on the space of string diagrams in a category, which feels like the first step in defining proper two-dimensional string diagrams.

But I got a bit stuck on working out exactly what a partial topological semigroup ought to be - see this other thread for details - and will probably have to come back to this another time, but if anyone has insights in the meantime that would be great.

Nathaniel Virgo (Jan 18 2022 at 03:57):

The idea about sheaves is different from this, and I'm also keen to figure that one out. It does feel like there ought to be something sheaf-like hiding here.

Joshua Meyers (Jan 18 2022 at 14:51):

A partial associative semigroup is very similar to a category --- add a right and left identity for each element I think it might even become a category. So I think you might get the same problem. To use the same category $\mathcal{C}$ that you describe, we could send $(a,0]$ to ${\sf id}_A$ for all $a<0$ and $(0,b]$ to $f$ for all $b>0$. We would also send $(b,c]$ to ${\sf id}_B$ for all $0<b<c$. So it seems like the same situation --- the morphism $f$ is located infinitesimally above $0$. I'm not sure how to get out of this atm

Joshua Meyers (Jan 18 2022 at 14:56):

The problem conceptually with having $f$ exactly at $0$ is that then the morphisms corresponding to the intervals $[a,0]$ and $[0,b]$ are not defined.

Jules Hedges (Jan 18 2022 at 15:32):

In case it helps, I think it's standard-ish to call the height of a non-identity morphism in a diagram a "singular level" and everything else a "regular level"

Jules Hedges (Jan 18 2022 at 15:32):

At least Jamie Vicary and co use that terminology, and I got it from them..... I think it might come from Morse theory or something

Nathaniel Virgo (Jan 19 2022 at 00:51):

Joshua Meyers you're right of course. Hmm, so then the options would be to just live with non-identity morphisms living "in between" elements of the reals instead of on them (which might be fine - I've no idea if it actually causes any problems, and it could end up being the right way to think about it), or find some other paradigm (sheaf-based?) that doesn't have that issue.

Jules Hedges (I guess "height" means what I'm picturing as $x$ position.) Thanks, that's really helpful, it suggests the "in between the reals" thing is maybe not as weird as I thought.

Nathaniel Virgo (Jan 19 2022 at 01:11):

So if we decide we're ok with non-identity morphisms living "in between" the reals, then we might as well use a functor from the reals as a poset, as Joshua Meyers suggested. I'm wondering what happens if we do that internally to Top. Then we shouldn't need all the stuff about partial continuous maps, because we can just think in terms of topological categories instead, which are well understood. (Albeit not necessarily by me.)