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: Directed graph as a functor I -> Span(Set)?

Eric Forgy (Dec 24 2020 at 11:34):

Hi,

I've been struggling a bit to figure out exactly what category I'm in for a problem I'm working on. I should end up in a category whose objects are bimodules and morphisms are bimodule homomorphisms. The catch is that I want to freely construct this functorially starting with a directed graph.

A directed graph is often defined as a functor

$G: X\to\mathsf{Set},$

where $X$ is a category with two objects $X^0,X^1$ and two morphisms $s,t: X^1\to X^0.$ This doesn't work for me because I don't see any way that $s,t$ can map to bimodule homomorphisms.

I just had a thought :light_bulb:

What if instead, we defined a directed graph as a functor

$G: I\to\mathsf{Span_1(Set)}$

from the interval category $I$ with two objects $0,1$ and 1 non-identity morphism $0\to 1$.

This would map

$0\mapsto G^0$

$1\mapsto G^1$

and the one morphism maps to the span

$G^0\leftarrow G^1\rightarrow G^0.$

This plays nicer with my bimodule category because that morphism as a span maps to a bimodule morphism.

Is that crazy?

Matteo Capucci (he/him) (Dec 24 2020 at 11:36):

It feels correct

Eric Forgy (Dec 24 2020 at 11:37):

Yeah. Same here. Composing that morphism with itself $n$ times generates [Edit: consists of] paths of length $n$.

Matteo Capucci (he/him) (Dec 24 2020 at 11:40):

What do you mean by 'composing'?

Matteo Capucci (he/him) (Dec 24 2020 at 11:41):

Oh I see. You can compose $G(0 \to 1)$ with itself as spans

Eric Forgy (Dec 24 2020 at 11:41):

I mean the usual composition of spans via pullback.

Eric Forgy (Dec 24 2020 at 11:41):

Yeah

Eric Forgy (Dec 24 2020 at 11:42):

$G^1\otimes_{G^0} G^1$ consists of paths of length 2.

Eric Forgy (Dec 24 2020 at 11:43):

This feels nice :+1:

Amar Hadzihasanovic (Dec 24 2020 at 12:37):

Functors from the interval category classify morphisms, so if $\mathsf{Span}_1(\mathsf{Set})$ is the category whose objects are sets and morphisms spans of sets, then a functor from $I$ is a span between two possibly different sets. Rather it's endomorphisms that correspond to directed graphs.

Amar Hadzihasanovic (Dec 24 2020 at 12:38):

The “classifier for endomorphisms” would be the monoid $\mathbb{N}$. Maybe that's what you want.

Amar Hadzihasanovic (Dec 24 2020 at 12:42):

Then, yeah, a functor $\mathbb{N} \to \mathsf{Span}_1(\mathsf{Set})$ is determined by what the image of $1$ is, and that's a directed graph. The image of $n$ is the directed graph whose edges are length-$n$ paths in the image of $1$.

John Baez (Dec 24 2020 at 17:19):

Eric wrote:

I should end up in a category whose objects are bimodules and morphisms are bimodule homomorphisms.

Bimodules of some particular specified algebra(s) that you're not telling us?

John Baez (Dec 24 2020 at 17:20):

People don't usually say things like what you just said: they might say "a category whose objects are (A,B)-bimodules and whose morphisms are bimodule homomorphisms" for some algebras A and B...

John Baez (Dec 24 2020 at 17:21):

or if A = B, you might say "(A,A)-bimodules" or maybe "A-bimodules".

John Baez (Dec 24 2020 at 17:22):

I just feel like adding that there's a super-important bicategory where:

• objects are algebras over some field k,
• morphisms from A to B are (A,B)-bimodules,
• 2-morphisms are bimodule homomorphisms.

So here we aren't choosing a particular A and B: we're choosing all of them!

Dan Doel (Dec 24 2020 at 17:50):

Is that part of a framed bicategory, even?

John Baez (Dec 24 2020 at 19:05):

Yes! These days the politically correct term is "fibrant double category".

Dan Doel (Dec 24 2020 at 19:14):

So there are three different names now?

John Baez (Dec 24 2020 at 19:14):

What's the third one?

Dan Doel (Dec 24 2020 at 19:14):

Proarrow equipment.

John Baez (Dec 24 2020 at 19:14):

Oh, right! I knew that.

John Baez (Dec 24 2020 at 19:15):

"Framed bicategory" was deprecated by topologists, who use "framed" to mean "equipped with a trivialization of the normal bundle" - and @Mike Shulman's original work at this was aimed to some extent at homotopy theorists (like his thesis advisor).

John Baez (Dec 24 2020 at 19:16):

Since it's a kind of double category it probably does make sense to call it a ".... double category".

John Baez (Dec 24 2020 at 19:17):

"Proarrow equipment" has its own advantages but it really brings a completely different set of mental associations to mind: it makes me feel like I'm generalizing $\mathbf{Cat}$ and profunctors!

John Baez (Dec 24 2020 at 19:17):

In my work on network theory I say "fibrant double category".

John Baez (Dec 24 2020 at 19:18):

In those applications the "proarrows" are the guys you really focus on: they're the "open systems".

Dan Doel (Dec 24 2020 at 19:23):

Yeah. The 'proarrow' mindset seems like it probably has plenty of examples, though. Like various combinations of homomorphisms and 'relations' into a single category

Mike Shulman (Dec 24 2020 at 19:24):

Of course, "fibrant double category" is not without its own problems. For instance, the category of double categories admits at least half a dozen different model structures, and as far as I know these are not the fibrant objects in any of them!

Dan Doel (Dec 24 2020 at 19:25):

Where is the quote from, by the way? nlab's "fibrant double category" just links to framed bicategory.

Dan Doel (Dec 24 2020 at 19:25):

Oh, I guess it wasn't a direct quote of anyone?

Mike Shulman (Dec 24 2020 at 19:26):

I think John probably meant to say "framed bicategory" -- I haven't heard anyone say "framed double category" except by accident.

Dan Doel (Dec 24 2020 at 19:28):

I think I just saw fewer quotation marks than are there, so thought he was quoting something about topologists not liking "framed bicategory".

John Baez (Dec 24 2020 at 19:28):

When I said

"Framed double category" was deprecated by topologists,...

I meant

"Framed bicategory" was deprecated by topologists,...

That was me talking.

John Baez (Dec 24 2020 at 19:29):

And yeah, I kinda hate how "fibrant double categories" aren't fibrant objects in some famous model structure on some category of double categories.

John Baez (Dec 24 2020 at 19:31):

If it weren't so long I'd probably say something like "double categories with twistable arrows".

Dan Doel (Dec 24 2020 at 19:31):

Where does the name come from? Are the objects of the double category somehow considered to be fibrant? Like, is the promotion of an arrow to a proarrow like a lifting property?

John Baez (Dec 24 2020 at 19:40):

The name comes from @Mike Shulman, so I'll let him answer that!

Eric Forgy (Dec 24 2020 at 19:46):

Good morning :coffee:

Thank you Matteo. Thank you Amar. Thank you (as always) John :raised_hands:

Although I feel I am on the right track, I woke up thinking "Oops!". A functor $F: I\to C$ maps to two objects $F(0)$, $F(1)$ in $C$ and one morphism $F(0)\to F(1)$ in $C$. That isn't what I want :thinking: So I am happy to see some corrections / help :santa: :pray:

I woke up not in despair though because I thought I could fix it by considering, instead of $I$, a category $X$ with two objects $X^0$,$X^1$ and one morphism being a span $X^0\overset{s}{\leftarrow} X^1\overset{t}{\rightarrow}X^0$. Then despair started to sink in again when I thought about how that is an endomorphism and how to deal with its powers, i.e. compositions with itself?

But, Amar, thank you for removing my despair again with

Amar Hadzihasanovic said:

Then, yeah, a functor $\mathbb{N} \to \mathsf{Span}_1(\mathsf{Set})$ is determined by what the image of $1$ is, and that's a directed graph. The image of $n$ is the directed graph whose edges are length-$n$ paths in the image of $1$.

That sounds like it is definitely in the right direction for me :raised_hands:

John Baez said:

People don't usually say things like what you just said: they might say "a category whose objects are (A,B)-bimodules and whose morphisms are bimodule homomorphisms" for some algebras A and B...

You're right. Sorry. I really need to pin this down once and for all. All this time, I thought I was working with $(A,A)$-bimodules, but now I'm not so sure because $A$ can be decomposed trivially into separate algebras, i.e.

$A = \bigoplus_{t\in\mathbb{Z}} A_t.$

Each $A_t$ is a commutative associative unital algebra with a prescribed basis $e^i_t$ (coming from nodes of a directed graph) and unit element $1_t = \sum_{i} e^i_t$ so that the unit element of $A$ is $1 = \bigoplus_{t} 1_t.$ The product is defined by how it acts on these basis elements, i.e.

$(e^i_t) (e^{i'}_{t'}) = \delta^{i,i'} \delta_{t,t'} e^i_t.$

I don't know if this decomposition is worth thinking about though :thinking:

If I do this, then I have $(A_t,A_{t+n})$-bimodules $\Omega^n$ that connect "nodes of $A_t$" to "nodes of $A_{t+n}$".

The algebra $A_t$ can be interpretted as the algebra generated by the set of nodes at time $t$.

I need to think about this some more :thinking:

Mike Shulman (Dec 24 2020 at 19:49):

Dan Doel said:

Where does the name come from? Are the objects of the double category somehow considered to be fibrant? Like, is the promotion of an arrow to a proarrow like a lifting property?

A double category is fibrant, in this sense, if and only if the (source, target) functor $D_1 \to D_0\times D_0$ is a Grothendieck fibration.

Mike Shulman (Dec 24 2020 at 19:50):

(And if and only if that same functor is an opfibration.)

Mike Shulman (Dec 24 2020 at 19:50):

That's in the original framed bicategories paper.

John Baez (Dec 24 2020 at 19:50):

@Eric Forgy wrote:

. Sorry. I really need to pin this down once and for all. All this time, I thought I was working with $(A,A)$-bimodules, but now I'm not so sure because $A$ can be decomposed trivially into separate algebras, i.e.

$A = \bigoplus_{t\in\mathbb{Z}} A_t.$

Sounds like an $(A,A)$-bimodule will do just fine. If $A$ breaks up as you suggest, then I bet you can use that to automatically break up any $(A,A)$-bimodule as you suggest - so those details are not something you need to carry around your neck all the time.

Dan Doel (Dec 24 2020 at 20:05):

Oh, okay.

Eric Forgy (Dec 24 2020 at 20:14):

John Baez said:

Sounds like an $(A,A)$-bimodule will do just fine. If $A$ breaks up as you suggest, then I bet you can use that to automatically break up any $(A,A)$-bimodule as you suggest - so those details are not something you need to carry around your neck all the time.

Cool. Thank you :pray:

If I am ok to stick with $(A,A)$-bimodules, then looking at:

John Baez said:

I just feel like adding that there's a super-important bicategory where:

• objects are algebras over some field k,
• morphisms from A to B are (A,B)-bimodules,
• 2-morphisms are bimodule homomorphisms.

So here we aren't choosing a particular A and B: we're choosing all of them!

If I am only concerned with one algebra $A$, then I would have just one object and $(A,A)$-bimodules as endomorphisms, but $A$ itself is trivially (I think) an $(A,A)$-bimodule, so I shifted this down one step with

• Objects are $(A,A)$-bimodules (since $A$ is an $(A,A)$-bimodule)
• Morphisms are $(A,A)$-bimodule endomorphisms

More specifically, my category consists of (all objects are $(A,A)$-bimodules):

• Objects $A^{\otimes_K r}$: Tensor powers (over $K$) of $A$ (a $K$-algebra)
• Objects $(\Omega^1)^{\otimes_A r}$: Tensor powers (over $A$) of $\Omega^1$ (a subbimodule of $A\otimes_K A$) (Note: I am pretty sure this must be coming from a span somewhere)
• Objects $\Omega^n$: Subbimodules of $(\Omega^1)^{\otimes_A n}$
• Objects being various tensor products of the above
• Morphisms being $(A,A)$-bimodule homomorphisms

The data to freely construct all of the above is contained in a directed graph (with possible restrictions, e.g. no loops, no cycles, so I'm thinking "directed acyclic graphs"). Putting all the pieces together seems too manual, so I am trying to find a clean and concise magical free functor. This isn't even the whole story because I also have daggers $\dagger$ that reverse the direction of edges that let us define an inner product etc so I think I end up with some kind of Hilbert bimodule.

Eric Forgy (Dec 24 2020 at 20:46):

To explain a little more, we know there is a free functor

$F: \mathsf{Alg} \to \mathsf{DiffAlg}.$

A differential algebra freely constructed this way is "universal", i.e.

$F(A) = (A,\tilde\Omega^1,\tilde d: A\to\tilde\Omega^1).$

We also know (since $\tilde d: A\to\tilde\Omega^1$ is universal) that any other differential algebra $(A,\Omega^1,d: A\to\Omega^1)$ factors through this one and there is a unique $(A,A)$-bimodule morphism

$\phi: \tilde\Omega^1\to\Omega^1$

with

$d = \phi \circ \tilde d.$

If $A$ is generated from the vertices of a directed graph, then the $(A,A)$-bimodule morphism $\phi$ is generated from the "adjacency matrix" of the directed graph we call the "graph operator" $G \subset A\otimes_K A$ given by

$G = \sum_{i,j} G(i,j) e^i\otimes_K e^j$

where $G(i,j) = 1$ if there is a directed edge $i\to j$ and zero otherwise.

So to summarize, if I only give you a set of vertices, I can construct a "universal differential algebra" on that set which corresponds to the complete graph. To get another differential algebra besides the universal one, we need to set some of the directed edges to zero. That is captured by $G$ so we need the full data of a directed graph to construct a general differential algebra.

John Baez (Dec 24 2020 at 20:50):

Eric Forgy said:

To explain a little more, we know there is a free functor

$F: \mathsf{Alg} \to \mathsf{DiffAlg}.$

A differential algebra freely constructed this way is "universal", i.e.

$F(A) = (A,\tilde\Omega^1,\tilde d: A\to\tilde\Omega^1).$

That gunk just says you've got a differential $d$ from your algebra to this $A$-module $\tilde\Omega^1$. It doesn't say anything about why this guy $\tilde\Omega^1$ is "universal". So I object to your use of the words "i.e." here: you're not actually explaining what's "universal" about it.

Yes, I'm nitpicking.. but you're in an audience of category theorists, who take universal properties seriously... so they'll wonder what universal property you're alluding to... and I just want to make it clear to them that you're not explaining that (and also you, in case you thought you were).

Eric Forgy (Dec 24 2020 at 21:20):

Sure :+1: I'll try to :pray:

What I'm talking about is spelled out in

• Bourbaki's Elements of Mathematics, Algebra I, Chapter 3, Section 10.10, Universal problem for derivations : non-commutative case

and I fumbled around with it until I felt I understood it here (where I also pasted the relevant paragraphs from EoA).

In a nutshell, given an associative unital $K$-algebra $A$, $\tilde\Omega^1$ is the kernel of the product $m: A\otimes_K A\to A$ with $m(a\otimes_K b) := ab$, i.e. the product in $A$, and

$\tilde d: a \mapsto 1\otimes_K a - a\otimes_K 1$

generates $\tilde\Omega^1$ as a left module (Proof is a couple lines in Bourbaki).

If $\phi: \tilde\Omega^1\to\Omega^1$ is an $(A,A)$-bimodule homomorphisms, then

$d = \phi\circ \tilde d: A\to\Omega^1$

is a derivation. So given $\phi$, we get a derivation $d$.

Conversely, given a derivation $d:A\to\Omega^1$, since $(x,y)\mapsto x\, dy$ is $K$-bilinear, there is a unique morphism $\phi: A\otimes_K A\to\Omega^1$ given by $\phi(x\otimes_K y) = x\,dy.$ This can be restricted to $\tilde\Omega^1$ so that given a derivation $d:A\to\Omega^1$, we obtain a unique $(A,A)$-bimodule homomorphism $\phi:\tilde\Omega^1\to\Omega^1$ and we have

$\mathsf{Hom}_{(A,A)}(\tilde\Omega^1,\Omega^1)\cong \mathsf{Der}_K(A,\Omega^1).$

What I'm doing is aplying this to the case where $A$ is generated by vertices of a directed graph.

Eric Forgy (Dec 24 2020 at 21:45):

I am throwing in a bit of a twist though because if $A$ is generated from vertices of a directed graph, we have $\Omega^1$ constructed from the adjacency of the directed graph as I mentioned above.

To see this, let

$\tilde G := 1\otimes_K 1 = \sum_{i,j} e^i\otimes_K e^j$

then

$\begin{aligned} \tilde d a :&= [\tilde G, a] \\ &= (1\otimes_K 1)a - a(1\otimes_K 1) \\ &= 1\otimes_K a - a\otimes_K 1.\end{aligned}$

$\tilde G$ is a sum over all pairs of vertices and corresponds to a complete graph.

Now, let $\phi: \tilde\Omega^1\to\Omega^1$ be an $(A,A)$-bimodule homomorphism that simply maps some pairs (edges) $e^i\otimes_K e^j$ to zero, then we have our graph operator

$G = \phi(\tilde G) = \phi(1\otimes_K 1)$

which gives rise to the unique derivation $d: A\to\Omega^1$ given by

$d: a\mapsto [G,a],$

which can also be written as

$d = \phi\circ \tilde d.$

Eric Forgy (Dec 24 2020 at 22:12):

(Note: If that :point_of_information: made any sense at all, I feel like I've gained some super powers :muscle: I've been thinking about this on and off for the last 20+ years and have never been able to state that much as succinctly before.)

John Baez (Dec 24 2020 at 22:32):

Nice!

Eric Forgy (Dec 25 2020 at 09:37):

Amar Hadzihasanovic said:

Then, yeah, a functor $\mathbb{N} \to \mathsf{Span}_1(\mathsf{Set})$ is determined by what the image of $1$ is, and that's a directed graph. The image of $n$ is the directed graph whose edges are length-$n$ paths in the image of $1$.

I've never seen the functor

$\mathbb{N}\to\mathsf{Span_1(Set)}$

before, but it looks pretty interesting. Does it have a name? Does it fit into any other interesting machinery?

But for the image of the morphism $1$ to be a directed graph, wouldn't the domain category need to consist of two objects? :thinking:

If I understand (big "if"), $\mathbb{N}$ has one object so it seems like the image of $1$ would be a span $S\leftarrow S\rightarrow S$ in $\mathsf{Set}.$ :thinking:

Amar Hadzihasanovic (Dec 25 2020 at 09:45):

An object in $\mathsf{Span}_1(\mathsf{Set})$ is a set $S$. A morphism from $S$ to $T$ is a pair of a set $E$ and a span $S \leftarrow E \rightarrow T$.

Amar Hadzihasanovic (Dec 25 2020 at 09:48):

So the image of the unique object $\bullet$ of $\mathbb{N}$ is a set $S$, and the image of the morphism $1$ is an "endospan" $S \leftarrow E \rightarrow S$.

Amar Hadzihasanovic (Dec 25 2020 at 09:48):

Which I think is what you want.

Eric Forgy (Dec 25 2020 at 09:50):

Yeah, but do $S$ and $E$ need to be in the image of the functor? If $F(\bullet) = S$, then where did $E$ come from? :thinking:

Eric Forgy (Dec 25 2020 at 09:52):

The image of $F$ in $\mathsf{Span_1(Set)}$ has just one object $F(\bullet) = S$ so would $F(1)$ be a span involving just one set, i.e. $S\leftarrow S\rightarrow S?$

Eric Forgy (Dec 25 2020 at 09:58):

It almost seems like the domain should be the monoid $\mathbb{Z}$ plus one object $\bullet$ such that $\bullet_{\mathbb{Z}}\mapsto S$, $\bullet\mapsto E$ and $1\mapsto S\leftarrow E\rightarrow S.$

Amar Hadzihasanovic (Dec 25 2020 at 09:59):

The other set $E$ is part of the data of a morphism!

Amar Hadzihasanovic (Dec 25 2020 at 10:01):

The fact that the domain of the functor has a single object just means that all morphisms in the image will have the same source and target.

Amar Hadzihasanovic (Dec 25 2020 at 10:03):

I think you're getting confused by the fact that an endomorphism in the category of spans is given by the data of two functions which are not themselves endomorphisms in $\mathsf{Set}$.

Eric Forgy (Dec 25 2020 at 10:04):

That makes sense. Thank you :blush:

It feels a little weird that the image of a functor from a monoid has more than 1 object, but if we can consiser it part of the data of the morphism, then I think I'm ok with it :+1:

Eric Forgy (Dec 25 2020 at 10:07):

Amar Hadzihasanovic said:

I think you're getting confused by the fact that an endomorphism in the category of spans is given by the data of two functions which are not themselves endomorphisms in $\mathsf{Set}$.

That helps :+1:

I was actually ok with the idea that those two functions were part of the data and not endomorphisms so I should have also been fine with the idea that the other object $E$ is also part of the data. Thanks for helping me see that :pray:

Eric Forgy (Dec 25 2020 at 10:09):

Back to my other question...

Does the functor

$\mathbb{N}\to\mathsf{Span_1(Set)}$

have a name? Does it fit into any other interesting machinery (that I can read about)?

Eric Forgy (Dec 25 2020 at 10:17):

It is cool how $F(1)$ is a directed graph and $F(n)$ consists of "evolving paths of length $n-1$".

Where a directed edge $(i,j)$ in $F(1)$ has source $s(i,j) = i$ and target $t(i,j) = j,$ a 2-path $(i,j,k)$ in $F(2)$ has a source $s(i,j,k) = (i,j)$ and a target $t(i,j,k) = (j,k).$

Eric Forgy (Dec 25 2020 at 10:21):

This is also nice because $\mathsf{Span_1(Set)}$ is a $\dagger$-category.

Morgan Rogers (he/him) (Dec 25 2020 at 10:24):

Eric Forgy said:

Does the functor

$\mathbb{N}\to\mathsf{Span_1(Set)}$

have a name? Does it fit into any other interesting machinery (that I can read about)?

It isn't a unique functor, so there's no reason for it to have a special name..! Amar was pointing out that there is a correspondence between directed graphs and such functors, so you could call it "the functor $F$ corresponding to the directed graph $G$"?

Eric Forgy (Dec 25 2020 at 10:33):

Yeah. I was just thinking. According to the nLab, a directed graph is already a functor

$G: X\to \mathsf{Set}$

but where $X$ has two objects $X^0,X^1$ and two morphisms $s,t:X^1\to X^0$.

The functor

$P: \mathbb{N}\to\mathsf{Span_1(Set)}$

seems at least as unique as that (and cooler) so I wouldn't be surprised if it had a name, but I also wouldn't be surprised if it doesn't have a name. I'm just curious :blush:

Eric Forgy (Dec 25 2020 at 10:36):

Anyway, thank you Amar :pray:

That functor gives me a lot to think about :blush:

Amar Hadzihasanovic (Dec 25 2020 at 12:35):

The reason why one usually considers functors $X \to \mathsf{Set}$ (in your notation) as directed graphs is that their natural transformations correspond to what people usually consider to be morphisms of graphs, namely, assignments of vertices to vertices and edges to edges that are compatible with source and target. That is, the functor category $[X, \mathsf{Set}]$ “is” the category of directed graphs.

Amar Hadzihasanovic (Dec 25 2020 at 12:37):

Whereas natural transformations of functors $\mathbb{N} \to \mathsf{Span}_1(\mathsf{Set})$ are a bit strange as a notion of morphism between directed graphs.

Amar Hadzihasanovic (Dec 25 2020 at 12:41):

If I'm not mistaken, if you take two such functors corresponding to graphs $G = (E,V)$ and $G' = (E',V')$, a natural transformation between $G$ and $G'$ may be pictured as a third, bipartite graph $H = (F, V+V')$ where the source of each edge of $H$ is a vertex of $G$ and its target is a vertex of $G'$, with the property that there is a bijection between

• paths $(f, e')$ consisting of an edge of $H$ followed by an edge of $G'$, and
• paths $(e, f')$ consisting of an edge of $G$ followed by an edge of $H$.

Amar Hadzihasanovic (Dec 25 2020 at 12:43):

So the functor category $[\mathbb{N}, \mathsf{Span}_1(\mathsf{Set})]$ is not the “usual” category of directed graphs.

Eric Forgy (Dec 25 2020 at 21:35):

Amar Hadzihasanovic said:

So the functor category $[\mathbb{N}, \mathsf{Span}_1(\mathsf{Set})]$ is not the “usual” category of directed graphs.

Oh. For sure :+1: Thanks for your note :pray:

This functor is definitely different, but I think it is cool :+1: If there is no existing name, I'd be tempted to call this functor (if the name wasn't already taken :tm: ) a "path space" and the functor category is the "category of path spaces". $P(1)$ is a directed graph, i.e. 1-path space, and $P(n)$ is an $n$-path space.

Replacing $\mathsf{Set}$ with some other (special type of) category $C$, we have functors

$\mathbb{N}\to \mathsf{Span_1}(C),$

which I might call a "path space in $C$" :thinking:

I actually think this is a better "path space" than the standard path space, but oh well :blush:

Maybe a good name for this would be "discrete path space" :thinking:

I'm still thinking about this so thanks for your thoughts :pray:

John Baez (Dec 25 2020 at 21:42):

"Path space" is a very widely used term...

Eric Forgy (Dec 25 2020 at 21:43):

Yeah. I definitely won't use that :blush:

John Baez (Dec 25 2020 at 21:44):

In case you're wondering, I didn't follow your conversation with Amar: I don't get what you're talking about.

John Baez (Dec 25 2020 at 21:45):

That's mainly because I just look here now and then, and if people are engaged in a complicated conversation with a lot of back-and-forth, I usually don't have the energy to figure out what's going on.

John Baez (Dec 25 2020 at 21:48):

In particular I don't know what the category $\mathsf{Span}_1(\mathsf{Set})$ is.

John Baez (Dec 25 2020 at 21:50):

Amar seemed to be saying it's the category of with sets as objects and spans of sets as morphisms. Is that all? That's usually called $\mathsf{Span}(\mathsf{Set})$.

Eric Forgy (Dec 25 2020 at 21:53):

True. I should probably start a new topic and leave this one behind because we kind of settled on a new understanding after my initial question / idea was a dead end and Amar was kind enough to give a way forward. Basically, I ran into a problem because the usual definition of directed graph as a functor $X\to\mathsf{Set}$ is not compatible with bimodules and bimodule homomorphisms (since source and target maps can never be bimodule homomorphisms), so I was looking for something that gives directed graphs, but works nicely with bimodules. I knew it should involve mapping something to spans, but my first guess was wrong so now we are talking about functors:

$\mathbb{N} \to \mathsf{Span_1(Set)}$

where $\mathsf{Span_1(Set)}$ is the 1-category of spans in $\mathsf{Set}$ with objects sets and morphisms isomorphism classes of spans.

Eric Forgy (Dec 25 2020 at 21:57):

John Baez said:

Amar seemed to be saying it's the category of with sets as objects and spans of sets as morphisms. Is that all? That's usually called $\mathsf{Span}(\mathsf{Set})$.

Yeah. Almost. From the nLab:

The 1-category of spans

Let $C$ be a category with pullbacks and let $\mathsf{Span_1}(C):=(\mathsf{Span}(C))_{∼1}$ be the 1-category of objects of $C$ and isomorphism class of spans between them as morphisms.

Then

$\mathsf{Span}_1(C)$ is a dagger category.

Next assume that $C$ is a cartesian monoidal category. Then clearly $\mathsf{Span}_1(C)$ naturally becomes a monoidal category itself, but more: then

$\mathsf{Span}_1(C)$ is a dagger compact category.

John Baez (Dec 25 2020 at 21:57):

Okay - yeah, when I said "it's the category of with sets as objects and spans of sets as morphisms" I really meant "it's the category of with sets as objects and isomorphism classes of spans of sets as morphisms."

John Baez (Dec 25 2020 at 21:59):

I think the subscript $1$ is only useful if you're talking both about the category and the bicategory and worried that people will mix them up... people don't usually do that; the nLab is just trying to be ultra-precise.

John Baez (Dec 25 2020 at 21:59):

And even if you're talking about both, you have to say what the subscript 1 means, or nobody will guess.

John Baez (Dec 25 2020 at 21:59):

Just sociology of mathematics here...

Eric Forgy (Dec 25 2020 at 22:00):

Thank you for helping me in my attempt to be a good citizen :blush:

John Baez (Dec 25 2020 at 22:00):

the usual definition of directed graph as a functor $X \to \mathsf{Set}$ is not compatible with bimodules and bimodule homomorphisms (since source and target maps can never be bimodule homomorphisms)

John Baez (Dec 25 2020 at 22:01):

I don't know what "compatibility" you want...

John Baez (Dec 25 2020 at 22:01):

Anyway, if you got things to work out with Amar I don't need to get involved.

John Baez (Dec 25 2020 at 22:02):

But if not, I could help out.

Eric Forgy (Dec 25 2020 at 22:02):

Amar got me to the starting point. Your input is always appreciated :pray:

John Baez (Dec 25 2020 at 22:03):

If you want, you can tell me what "compatible with" means here....

Eric Forgy (Dec 25 2020 at 22:15):

John Baez said:

I don't know what "compatibility" you want...

So I recently explained (above) what I meant by directed graphs giving rise to differential algebras. I think there should be some way to express this as a functor.

A directed edge $(i,j)$ in a graph corresponds to the basis element $e^i\otimes_K e^j$ in $\tilde\Omega^1.$

It seems intuitive that the source and target maps on directed graphs should map to "morphisms" $s,t: \tilde\Omega^1\to A$ in a differential algebra with

$s(e^i\otimes_K e^j) = e^i\quad$ and $\quad t(e^i\otimes_K e^j) = e^j$

and extended linearly. However, these are not bimodule morphisms so they don't live in my category.

Eric Forgy (Dec 25 2020 at 22:24):

I "think" Amar's suggestion solves this problem for me, but it is still a fresh idea in my mind and I'm just thinking about it now.

That messy looking category I described above involves spans so I think there should be some functor

$\mathbb{N}\overset{P}{\to} \mathsf{Span_1(Set)} \overset{F}{\to} B$,

where $B$ is that messy looking category above with objects $A$-bimodules and morphisms $A$-bimodule homomorphisms (not sure what to call that either).

Eric Forgy (Dec 25 2020 at 22:38):

As an intermediate step, I think it makes sense to look at

$\mathbb{N}\overset{P}{\to} \mathsf{Span_1(Set)} \overset{F_{\mathsf{Alg}}}{\to} \mathsf{Alg}$,

so that

$A = F_{\mathsf{Alg}}\circ P(\bullet)$

$A\otimes_K A = F_{\mathsf{Alg}}\circ P(1).$

$(A\otimes_K A) \otimes_A (A\otimes_K A) = F_{\mathsf{Alg}}\circ P(2)$

$\cdots$

Eric Forgy (Dec 25 2020 at 22:42):

That looks right, so then a next logical step would be

$\mathbb{N}\overset{P}{\to} \mathsf{Span_1(Set)} \overset{F_{\mathsf{Alg}}}{\to} \mathsf{Alg} \overset{F_{\mathsf{DiffAlg}}}{\to} \mathsf{DiffAlg}.$

Eric Forgy (Dec 25 2020 at 22:44):

That also looks right, so then we go one more step

$\mathbb{N}\overset{P}{\to} \mathsf{Span_1(Set)} \overset{F_{\mathsf{Alg}}}{\to} \mathsf{Alg} \overset{F_{\mathsf{DiffAlg}}}{\to} \mathsf{DiffAlg}\overset{F_{\mathsf{DGAlg}}}{\to} \mathsf{DGAlg}.$

Eric Forgy (Dec 25 2020 at 22:46):

I'm not sure if I should throw some $\mathsf{Span_1}\text{s}$ in there, but this feels like the right direction :+1:

Eric Forgy (Dec 25 2020 at 22:51):

I think the steps

$\mathbb{N}\overset{P}{\to} \mathsf{Span_1(Set)} \overset{F_{\mathsf{Alg}}}{\to} \mathsf{Alg} \overset{F_{\mathsf{DiffAlg}}}{\to} \mathsf{DiffAlg}$

are all pretty well established and the last step

$\mathsf{DiffAlg}\overset{F_{\mathsf{DGAlg}}}{\to} \mathsf{DGAlg}$

is also understood, but I have a twist that involved "diamonds" :large_blue_diamond: that is pretty cool if I say so :nerd:

Eric Forgy (Dec 25 2020 at 23:09):

By the way, in hindsight, this seems related to Scott Wilson's (student of Dennis Sulliven) presentation

• Some algebra related to mapping spaces and applications

that I recently mentioned here, where he describes a commutative differential graded algebra as a monoidal functor
$\mathsf{FinSet}\to \mathsf{Ch},$
where $\mathsf{Ch}$ is the category of chain complexes and chain maps. It is curious that Scott and I both derive the Navier-Stokes equation as almost a tautology of the formalism.

John Baez (Dec 25 2020 at 23:11):

I find this pretty complicated, but here's my instant reaction:

You are very interested in this thing:

$d: A \to \tilde{\Omega^1}$

There's a category $\mathsf{Vect}^\to$ where the objects are short chain complexes: pairs of vector spaces equipped with a linear map between them, like this:

$d : V \to W$

I'm writing the linear map as $d$ just to make you interested in it - in general it's just any linear map. Similarly, the phrase "short chain complex" is supposed to give you ideas about why we care about this, but it's just a name for two vector spaces and a linear map!

The category $\mathsf{Vect}^\to$ is just the category where

• objects are functors from $\to$ (the category with two objects and one non-identity morphism, which goes from one object to the other)
• morphisms are natural transformations.

The category of graphs is very similar: it's $\mathsf{Set}^{\Rightarrow}$ where

• objects are functors from $\Rightarrow$ (the category with two objects and two non-identity morphisms, which goes from the first object to the second)
• morphisms are natural transformations.

I would write $\Rightarrow$ more beautifully if I easily could: it's supposed to be a picture of two objects and two morphisms going from the first object to the second! You're using some other name for this category.

There's an important functor

$X: \mathsf{Set}^{{\Rightarrow}} \to \mathsf{Vect}^{{\rightarrow}}$

which takes a graph $s,t: E \to V$ and turns it into a short chain complex. YOU KNOW THIS FUNCTOR - YOU'RE USING IT ALL THE TIME!

There's a lot more to say; people know a lot about this....

John Baez (Dec 25 2020 at 23:15):

I'll just say one more thing: the functor $X$ is equal to a more fundamental functor

$Y: \mathsf{Set}^{{\Rightarrow}} \to \mathsf{Vect}^{{\Rightarrow}}$

John Baez (Dec 25 2020 at 23:15):

composed with a functor

$Z: \mathsf{Vect}^{{\Rightarrow}} \to \mathsf{Vect}^{{\rightarrow}}$

John Baez (Dec 25 2020 at 23:16):

The stuff about algebras can also easily be worked into this story.

Eric Forgy (Dec 25 2020 at 23:19):

There's a lot more to say; people know a lot about this....

Yeah. This seems like such low hanging fruit. I believe the math is well-known, but no one I am aware of has ever used this to produce numerical algorithms and write actual code for scientific computation, which just feels like a shame. I am trying to bridge this gap in a way "scientists and engineers" (like myself) can understand :pray: :blush:

John Baez (Dec 25 2020 at 23:20):

The math is well-known, and I feel people like Robert Kotiuga have done a lot to produce numerical algorithms for it, though he's less interested in the category theory than some.

Eric Forgy (Dec 25 2020 at 23:20):

The one person I know who even thinks about this is your old friend Robert Kotiuga, but even he has only scratched the surface of what can be done.

John Baez (Dec 25 2020 at 23:21):

Have you read his book?

https://www.amazon.com/Electromagnetic-Theory-Computation-Mathematical-Publications/dp/0521801605

John Baez (Dec 25 2020 at 23:22):

He's mainly interested in electromagnetism, but he does a lot with that....

Eric Forgy (Dec 25 2020 at 23:23):

John Baez said:

Have you read his book?

https://www.amazon.com/Electromagnetic-Theory-Computation-Mathematical-Publications/dp/0521801605

No. I haven't seen this. It was published after I got sucked into a new life of finance. Will check it out :blush: I should reconnect with Robert.

John Baez (Dec 25 2020 at 23:23):

Yeah, I'd forgotten you knew him.

Eric Forgy (Dec 25 2020 at 23:24):

I know he was taking advantage of cohomology to be able to solve Maxwell's equations using just the vector potential.

Eric Forgy (Dec 25 2020 at 23:26):

As far as I know, he wasn't using this stuff to construct new numerical methods (which is what I'm trying to do). Him and Alain Bossavit were both in the "mimectic" camp, but I think they still only scratched the surface. There is so much that can be done.

John Baez (Dec 25 2020 at 23:26):

He's been involved in a lot of numerical methods stuff, I think. Here's a paper that's quicker to get ahold of:

• Valtteri Lahtinen, P. Robert Kotiuga, Antti Stenvall, An electrical engineering perspective on missed opportunities in computational physics.

I haven't read it, but the grumbling tone of the title should appeal to you. Here's the abstract:

We look at computational physics from an electrical engineering perspective and suggest that several concepts of mathematics, not so well-established in computational physics literature, present themselves as opportunities in the field. We emphasize the virtues of the concept of elliptic complex and highlight the category theoretical background and its role as a unifying language between algebraic topology, differential geometry and modelling software design. In particular, the ubiquitous concept of naturality is central. We discuss the Galerkin finite element method as a way to achieve a discrete formulation and discuss its compatibility with so-called cochain methods. Despite the apparent differences in their underlying principles, in both one finds a finite-dimensional subcomplex of a cochain complex. From such a viewpoint, compatibility of a discretization boils down to preserving properties in such a process. Via reflection on the historical background and the identification of common structures, forward-looking research questions may be framed.

John Baez (Dec 25 2020 at 23:28):

A quote from the first paragraph:

Through articulating physics via such concepts as natural differential operatorsand elliptic complexes, the framework of category theory provides a sense of synthesis to the seemingly scattered field. At first glance, the concepts of category theory may steer the reader’s thoughts towards foundations of mathematics. However, on a closer look, it is also the glue and common ground throughout computational physics.

Eric Forgy (Dec 25 2020 at 23:28):

Yes. The finite element method has some tantalizing mimectic properties, but you definitely lose the algebraic characteristics as currently formulated. Discrete differential geometry (as formulated by Urs and I) maintain this.

John Baez (Dec 25 2020 at 23:29):

You should definitely talk to Robert, since either he will convince you that your ideas are already known, or he'll get excited to hear about them.

Eric Forgy (Dec 25 2020 at 23:29):

The main ingredient missing is "diamonds" :blush:

Eric Forgy (Dec 25 2020 at 23:35):

It was so fun hanging out with Robert and Alain. "I was a contender." We were doing cool things in computational electromagnetics. I regret giving that up.

Eric Forgy (Dec 25 2020 at 23:36):

If I get this paper written up and start generating new numerical results, it would mark my return :pray:

John Baez (Dec 25 2020 at 23:43):

Sounds good.

Alain who? Connes?

Eric Forgy (Dec 25 2020 at 23:43):

Alain Bossavit

John Baez (Dec 25 2020 at 23:44):

(I didn't really think you were hanging out with Alain Connes.)

Eric Forgy (Dec 25 2020 at 23:56):

Bossavit was a pioneer in computational electromagnetics focusing on topological aspects. Mainly the nilpotency of $d$ and the duality via Stokes' theorem with the boundary map $\partial$, which translates to conservation of charge among other things. Naive discretizations do not necessarily satisfy $d^2=0.$ However, it is generally assumed that you can't maintain the algebraic aspects, but I never accepted that. Discrete differential geometry insists that we work with associative DGAs (Wilson's DGAs are not associative on cochains).

Eric Forgy (Dec 26 2020 at 00:01):

Finitary associative DGAs are noncommutative (but noncommutative in a cool way). Finitary commutative DGAs are nonassociative. Only in the continuum limit do associative DGAs become commutative (like a classical limit in QM).

John Baez (Dec 26 2020 at 18:52):

That's cool. Of course there are plenty of finite-dimensional (super)commutative associative DGAs, but I guess they don't do what you want. It could be nice for the theorem-proving crowd to make that into a theorem, by turning "what you want" into some precise hypotheses. (Maybe you've already done it.)

Eric Forgy (Dec 26 2020 at 21:17):

Good morning :coffee:

John Baez said:

That's cool. Of course there are plenty of finite-dimensional (super)commutative associative DGAs, but I guess they don't do what you want. It could be nice for the theorem-proving crowd to make that into a theorem, by turning "what you want" into some precise hypotheses. (Maybe you've already done it.)

Working on it :blush:

If a theorem-proving person was interested, there are two theorems I'd love to have proofs for, but I can't even state them clearly enough for anyone to start thinking about proofs yet.

Roughly speaking, the first theorem would relate to the "No go" statement above that a finitary DGA cannot be both (super)commutative and associative at the same time. The big challenge is to define precisely what I mean by "finitary DGA" and that is what I'm working on now. In our paper, we explicitly construct a simple / restricted example but it already spans 20+ pages and lacks a succinct statement like "A finitary DGA is a functor from $X$ to $Y$." I need to pin down exactly what are $X$ and $Y$. After help here from Amar, I'm pretty sure $X$ should be $\mathbb{N}$ and I think $Y$ is probably a category of $A$-bimodules and bimodule homomorphisms, but still working on it :pray: I'm pretty sure the functor I'm after should be a composition with $\mathbb{N}\to\mathsf{Span(Set)}$ (which I'm tentatively calling "directed paths" - suggestions welcome).

The second theorem I'd love to be able to state and prove (or disprove) is what I call "diamonation", but I don't want to think about that right now :sweat_smile: (Note: I see on that page, I describe a diamond as a directed cube, but I recently discovered diamonds are more general than that and that is the cool new result I'll put into this paper I'm working on :blush: :runner: )