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: morphisms vs objects

ctt (May 27 2021 at 21:07):

f relates x to y. Sometimes this is depicted with f as a node, and sometimes with f as an edge. How do I know when to use which? Naively I would think "x and y can be edges only if there's an object on the other end of those edges". But then I see pictures like image.png which doesn't have that property. What is going on in this picture, and how should I think about this distinction between objects and morphisms in general?

Spencer Breiner (May 27 2021 at 21:49):

Hi @ctt

The two most common kinds of diagrams to see in this area are commutative diagrams (CDs) and string diagrams (SDs). To a first approximation (as you note) these are graph duals; CDs have objects as nodes and arrows as edges, and the reverse for SDs. The two types of diagrams are useful for different things. CDs are good for showing lots of equations between arrows in one compact package; SDs are good at describing one (composite) arrow at a time, with equations visible as differences between diagrams.

An example helps:
boxes2.jpg

From this it's not obvious why string diagrams are useful. This comes in once we start talking about processes with multiple inputs or outputs (in a monoidal category).
boxes3.jpg

You can write these down using commutative diagram notation, but it's hard to read because of the need to insert a bunch of identities. The lower diagram below would become a string of edges like this:
$X\times Z\stackrel{f\times id_Z}{\longrightarrow} X'\times Y\times Z\stackrel{id_{X'}\times g}{\longrightarrow}X'\times Y'\times Z'\stackrel{f'\times id_{Z'}}{\longrightarrow}X''\times Z'$
That's a lot harder to parse than the SD notation.

James Wood (May 27 2021 at 21:54):

Commutative diagrams and string diagrams are two distinct graphical languages denoting roughly the same mathematical constructions. Before you read a diagram, you have to know which language it's in, which you'll learn from visual cues. An analogy: you can't understand text without knowing whether it's written in English or French, but given a text and a bit of knowledge, you can soon work out which language it's in. But you can still talk about the same concepts in both English and French.

ctt (May 27 2021 at 22:20):

That's helpful. I guess there must be also a diagram where all of them are nodes $\overset x \bullet - \overset f \bullet - \overset y \bullet$, and another where all of them are edges $\bullet \overset x - \bullet \overset f - \bullet \overset y - \bullet$ (or maybe three edges on the same node) . How do these fit into the schema above?

Jason Erbele (May 27 2021 at 23:43):

I will not immediately discount that the "all nodes" and "all edges" diagrams may be useful, but I would be wary of them without seeing a good example of their utility. Objects and morphisms are usually thought of as different kinds of things, and both commutative diagram and string diagram notations give you the visual cues to distinguish one from the other. The two notations you proposed make it harder to make the distinction.

Jason Erbele (May 27 2021 at 23:59):

On the other hand, I think there are some formalisms that put everything into the nodes, e.g., but the nodes have different shapes to distinguish different kinds of things.

John Baez (May 28 2021 at 00:00):

ctt said:

I guess there must be also a diagram where all of them are nodes $\overset x \bullet - \overset f \bullet - \overset y \bullet$, and another where all of them are edges $\bullet \overset x - \bullet \overset f - \bullet \overset y - \bullet$ (or maybe three edges on the same node) . How do these fit into the schema above?

I've never seen anyone use this notation. I don't see any advantage to using notation that makes it hard to tell what's a morphism and what's an object.

Here you using the fact that when we see the letter "x" we think "object", and when we see the letter "f" we think "morphism" - but that's a bad thing to rely on.

John Baez (May 28 2021 at 00:21):

In a "string diagram" we draw objects as edges and morphisms as nodes like the triangle here:

There are books and papers on string diagrams; you can get some starting here:

• Wikipedia, String diagram.

This particular string diagram strongly reminds me of one I drew in my recent talk Symmetric monoidal categories: a Rosetta stone.

Jason Erbele (May 28 2021 at 00:28):

@John Baez, it looks like you linked to the wikipedia article twice. Some of the aesthetics of that simple string diagram (like the subtle blue shading of the $F$ triangle) seemed familiar to me, too. :smirk:

ctt (May 28 2021 at 01:17):

That talk is indeed where that image comes from.

I think I might be asking not just about the "syntax" of the different diagram types, but about the interpretation of a situation where f relates x to y with f as a morphism and x/y as objects, vs the interpretation with x/y as morphisms and f as an object, if that makes sense.

John Baez (May 28 2021 at 01:30):

I'm not sure exactly what you're asking, so I'll just say some stuff.

In string diagrams the nodes are morphisms in a monoidal category and the edges are objects; in "ordinary" category theoretic diagrams the nodes are objects in a category and the edges are morphisms.

It becomes clearer what's going on if you treat both of these ideas using 2-categories, since both monoidal categories and categories are each a special case of 2-categories - but in a way that's mildly confusing at first.
Then you can see that the two kinds of diagrams are "Poincare duals" of each other. There's a surprisingly clear explanation on Wikipedia, with pictures.

John Baez (May 28 2021 at 01:35):

("Surprisingly clear" because often they're not very clear.)

ctt (May 28 2021 at 04:30):

Is a wiring diagram (like the one shown above) a kind of string diagram that only applies to simpler situations?

John Baez (May 28 2021 at 04:44):

I don't see any wiring diagrams in this thread.

John Baez (May 28 2021 at 04:49):

A wiring diagram is an operation in the "operad of wiring diagrams". For the relation between wiring diagrams and string diagrams, the introduction here may be helpful:

• Evan Patterson, David I. Spivak and Dmitry Vagner, Wiring diagrams as normal forms for computing in symmetric monoidal categories.

Spencer Breiner (May 28 2021 at 16:23):

ctt said:

That's helpful. I guess there must be also a diagram where all of them are nodes $\overset x \bullet - \overset f \bullet - \overset y \bullet$, and another where all of them are edges $\bullet \overset x - \bullet \overset f - \bullet \overset y - \bullet$ (or maybe three edges on the same node) . How do these fit into the schema above?

The "everything is a node" perspective comes up in the recent paper on The Cost of Compositionality by Wilson & Zanasi (though they don't draw things that way). They transform their string diagrams into bipartite graphs, with strings and boxes as the bi-parts. They do this to take advantage of existing algorithms for (sparse-matrix representations of) graphs.

Spencer Breiner (May 28 2021 at 16:40):

John Baez said:

I don't see any wiring diagrams in this thread.

I'd also quibble with this: a bit pedantic, if not misleading. I see no reason you couldn't call the diagram @_ctt posted a "wiring diagram".

First of all, I doubt there is any clear distinction conveyed by the two terms that would be agreed on by a plurality of the community. At least, I use the terms more-or-less interchangeably. Obviously various authors have used the terms more strictly (e.g., Coecke & Kissinger limits "string diagrams" to compact-closed categories, I think, because we can bend strings), but I'm skeptical that those specializations are either broadly useful or coherent with one another.

Second, insisting on a distinction obscures the fact that both viewpoints interact: string diagrams form an operad of wiring diagrams! In practice/historically, I think "string diagram" terminology is more common if we are doing "horizontal composition" (outputs->inputs) and "wiring diagram" when we are doing "vertical composition" (zooming in/out), but I don't see how that means some particular representation needs to be one or the other.

Jules Hedges (May 28 2021 at 16:44):

Yeah, I agree, the terminology is pretty fluid in practice

Jules Hedges (May 28 2021 at 16:44):

If I remember correctly, Bob and Aleks use "circuit diagram" for string diagrams in a mere monoidal category

Spencer Breiner (May 28 2021 at 16:48):

Indeed. I am more comfortable with limiting the meaning of "circuit diagram" (and almost mentioned this) because here we want to maintain consistency with existing usage in computing which (I think) assumes $\rm{dom}(f)=\rm{cod}(f)$ for generators and only feed-forward composition (no splitting/bending).

John Baez (May 28 2021 at 16:52):

Okay, I never heard of "wiring diagrams" until Spivak introduced the operad of wiring diagrams. I think of "string diagram" as a general term for diagrams depicting morphisms in monoidal categories or 2-morphisms in bicategories, as in the Wikipedia article.

I don't know who introduced the term "string diagram" - I thought it was Ross Street but I can't find the locus classicus.

Jules Hedges (May 28 2021 at 16:52):

I asked this exact question on this exact forum at some point, and I think it was inconclusive

John Baez (May 28 2021 at 16:59):

Spencer Breiner said:

The "everything is a node" perspective comes up in the recent paper on The Cost of Compositionality by Wilson & Zanasi (though they don't draw things that way). They transform their string diagrams into bipartite graphs, with strings and boxes as the bi-parts. They do this to take advantage of existing algorithms for (sparse-matrix representations of) graphs.

Interesting!

There's nothing really wrong the "everything is a node" perspective if the bipartiteness of the graph is threated as a structure rather than a mere property.

Less obscurely: I can handle it if you draw your objects as red dots and your morphisms as green dots, or something like that, so I can instantly tell what's an object and what's a morphism. I won't enjoy it, but there's nothing really wrong with it. What perturbed me is that @ctt didn't do anything like that.

Returning to my original obscure comment: when a graph theorist says a graph is "bipartite", sometimes they mean it's possible to label some nodes red and some green, such that no edges connect two red dots, or two green dots. That's a mere property of a graph, and it doesn't let you say which nodes are red and which are green. For the kind of stuff I do, it's much better to make bipartiteness into a structure, where you actually do label some nodes red and some green, such that no edges connect two red dots, or two green dots.

John Baez (May 28 2021 at 17:01):

A similar ambiguity afflicts the term "planar graph" - is it a graph that can be embedded into the plane, or a graph that is embedded into the plane (up to isotopy)?

Some use "plane graph" to mean the structure, "planar graph" to mean the property.