Polarities (Part 5)

Azimuth 2024-11-14

Today I’d like to dig a little deeper into some ideas from Part 2. I’ve been talking about causal loop diagrams. Very roughly speaking, a causal loop diagram is a graph with labeled edges. I showed how to ‘pull back’ and ‘push forward’ these labels along maps of graphs. But it turns out that to make pulling back and pushing forward functorial, we need to take two very different approaches to graphs with labeled edges:

We can ignore the meaning of the edge labels—treat them as elements of an arbitrary set—and declare that a map between labeled graphs is any map of graphs that preserves these labels. That makes pulling back easy.
Or we can think of the labels as something we can add, and declare that when a bunch of edges map to a single edge, we add their labels. This makes pushing forward easy. But for this, we had better use graphs with edges labeled by elements of a commutative monoid, so we can add the labels—and for the sums to be well-defined, we should work with finite graphs.

While approach 2 is more complicated, I believe it’s more useful for the applications I’ve been talking about. I explained in Part 2 that for these applications we want graphs with edges labeled by elements of a rig. The commutative monoid I’m talking about in approach 2 is the one coming from addition in this rig. Multiplication in this rig gives another monoid, which is important for other purposes, as explained in Part 1.

I might as well explain both approaches, 1 and 2, because they’re worth comparing. We’ll see they’re ‘dual’ in a certain way!

I’m afraid this post may not make much sense unless you’re reasonably comfortable with category theory. You see, today I feel the need to strip away the veils and talk in a way that more closely resembles how I’m thinking about this stuff. For example, I’ll show that approach 1 gives a ‘discrete fibration’, while approach 2 gives a ‘discrete opfibration’. These are concepts that warm the hearts of category theorists. I’ll explain them. But if they don’t warm your heart, don’t give up: future posts in this thread are unlikely to rely on the technical details of this one!

Graphs with edges labeled by elements of a set

For any set L there is a category of L-labeled graphs where:

• an object is a graph $s, t \colon E \to V$ together with an L-labeling $\ell \colon E \to L.$

• a morphism is a map of graphs that preserves the L-labeling: each edge is mapped to an edge with the same label.

We can also think about L-labelings in a fancier way. There is a graph $G_L$ with one vertex and with one edge for each element of L. An L-labeling of a graph $G$ the same as a map of graphs

$G \to G_L$

Using this, we can see that the category of L-labeled graphs is the slice category $\mathsf{Gph}/G_L:$ that is, the category of graphs equipped with a map to $G_L.$

There is a functor

$q \colon \mathsf{Gph}/G_L \to \mathsf{Gph}$

that sends each L-labeled graph to its underlying graph. It just forgets the labeling of edges.

In fact this functor $q$ is a ‘discrete fibration’, and this is why we can pull back L-labelings along maps of graphs.

Let me explain this. For each $G \in \mathsf{Gph}$ the fiber of $q$ over $G$ is the set of L-labelings of that graph. It’s called a fiber because the formula for it resembles the formula for other things called ‘fibers’:

$q^{-1}(G) = \{ X \in \mathsf{Gph}/G_L \; \vert \; q(X) = G \}$

In general the fibers of a functor are categories, but for a so-called ‘faithful’ functor they are categories where the only morphisms are identity functors, so we can treat them as sets. The functor $q$ is indeed faithful: a map of L-labeled graphs is uniquely determined by its underlying map of graphs. Thus, I’m treating the fiber $q^{-1}(G)$ as a set.

In fact we have an isomorphism

$q^{-1}(G) \cong \text{hom}(G, G_L)$

Why? Here’s why: elements of $q^{-1}(G)$ correspond to L-labelings of $G,$ which in turn correspond to maps from $G$ to $G_L.$

Thus, we can treat the fiber $q^{-1}(G)$ as the result of applying the functor

$\text{hom}(-, G_L) \colon \mathsf{Gph}^{\text{op}} \to \mathsf{Set}$

to the graph $G.$ This makes the fiber contravariantly functorial. That is, any map of graphs

$f \colon G \to H$

gives rise to a map

$\text{hom}(f, G_L) \colon \text{hom}(H, G_L) \to \text{hom}(G, G_L)$

which in turn gives a map we could call

$q^{-1}(f) \colon q^{-1}(H) \to q^{-1}(G)$

We say this map lets us pull back any L-labeling of $H$ along any map of graphs $f \colon G \to H$ to get an L-labeling of $G.$

Thus, we’ve defined the fiber not just on graphs, but on maps between graphs—and it’s a contravariant functor! This functor deserves the name

$q^{-1} \colon \mathsf{Gph}^{\text{op}} \to \mathsf{Set}$

Category theorists would summarize the whole situation by saying three things:

1) The functor assigning to each graph $G$ its fiber $q^{-1}(G)$ is representable by $G_L$ .

This means

$q^{-1} \cong \text{hom}(-, G_L)$

as functors from $\mathsf{Gph}^{\text{op}}$ to $\mathsf{Set}.$

2) The category of L-labeled graphs is the category of elements of the contravariant functor $q^{-1}.$

This means:

• an L-labeled graph amounts to the same thing as a graph $G$ together with an element $\ell \in q^{-1}(G).$

• a map of L-labeled graphs from $(G,\ell)$ to $(H, m)$ is the same as a map of graphs $f \colon G \to H$ such that

$q^{-1}(f)(m) = \ell$

3) By general theory, it follows that the functor $q$ is a discrete fibration. This means that for each L-labeled graph $Y$ and each map of graphs $f \colon G \to q(Y)$ there exists a unique map of L-labeled graphs $g \colon X \to Y$ such that $q(g) = f.$

This implies $q(X) = G.$ As a further consequence, $X$ is the result of pulling back $Y$ along $f.$

These three facts, 1)–3), mean the whole situation is peachy-keen and we have a vast arsenal of tools available to work with it!

Graphs with edges labeled by elements of a commutative monoid

Things work quite differently if we try to push forward L-labeled graphs along maps of graphs. We can’t do it when our map sends two or more edges with different labels to a single edge: there’s no way to decide which label to use!

Luckily we can take a different approach when our set L of labels is a commutative monoid. We just add the labels. And as I explained in Part 2, this is exactly what we want in applications. If infinitely many edges get mapped to the same edge it may not make sense to add their labels, but we can avoid that simply by restricting attention to finite graphs (i.e. graphs with finitely many vertices and edges).

So, let’s see what happens in this approach. We need to switch from our previous category of L-labeled graphs to a new category, which I’ll call the category of L-graphs. But then everything works nicely.

For any commutative monoid L there is a category $L\mathsf{Gph}$ where:

• an object is an L-graph: a finite graph $s, t \colon E \to V$ together with an L-labeling $\ell \colon E \to L.$

• a morphism is a map of L-graphs: that is, a map between their underlying graphs such that the L-labeling of each edge in the target graph is the sum of the L-labelings of the edges that map to it.

There is a functor

$p \colon L\mathsf{Gph} \to \mathsf{Gph}$

that sends each L-graph to its underlying graph.

As we’ll see, this functor $p$ is a ‘discrete opfibration’, and this lets us ‘push forward’ L-labelings along maps of graphs.

Let me explain what that means. The whole story is parallel to the previous one, but different in various ways.

Like the functor $q,$ the functor $p$ is faithful: a map between L-graphs is uniquely determined by its underlying map between graphs. This is easy to see from the definitions.

Thus we can think of the fibers of $p$ as sets, and the fiber of $p$ over a graph $G$ is

$p^{-1}(G) = \{ X \in L\mathsf{Gph} \; \vert \; p(X) = G \}$

This is simply the set of L-labelings of $G.$

Further, $p$ is a discrete opfibration. This means that for each L-graph $X$ and each map of finite graphs $f \colon p(X) \to H$ there exists a unique map of L-graphs $g \colon X \to Y$ such that $p(g) = f.$ Again, this is easy to see from the definitions.

As a further spinoff, because $p(g) = f,$ we must have

$p(Y) = H$

Thus, any map between finite graphs

$f \colon G \to H$

gives rise to a map between fibers

$p^{-1}(f) \colon p^{-1}(G) \to p^{-1}(H)$

that sends $X \in p^{-1}(G)$ to $Y \in p^{-1}(H)$ defined as above. We say this map lets us push forward any L-labeling of $G$ along $f$ to get an L-labeling of $H.$

Thus, we’ve now defined the fiber not just on finite graphs but on maps between them—and it’s a covariant functor! This functor deserves the name

$p^{-1} \colon \mathsf{FinGraph} \to \mathsf{Set}$

Category theorists would summarize the whole situation by saying two things:

1) The category of L-graphs is the category of elements of the covariant functor $p^{-1}.$

This means:

• an L-graph amounts to the same thing as a finite graph $G$ together with an element $\ell \in p^{-1}(G).$

• a map of L-labeled graphs from $(G,\ell)$ to $(H,m)$ is the same as a map of graphs $f \colon G \to H$ such that

$p^{-1}(f)(\ell) = m$

2) By general theory, it follows that the functor $p$ is a discrete opfibration.

Note: we just have two facts this time, not three. That’s because the covariant functor $p^{-1}$ is not representable, while the contravariant functor $q^{-1}$ was. The reason is that the procedures this time use the fact that our set of labels is a commutative monoid. It’s possible I’m missing a trick or two.

Still, pulling back and pushing forward labelings are remarkably parallel!