<![CDATA[Network Theory (Part 31)]]>

<![CDATA[Network Theory (Part 31)]]>Last time we came up with a category of labelled graphs and described circuits as ‘cospans’ in this category.

Cospans may sound scary, but they’re not. A cospan is just a diagram consisting of an object with two morphisms going into it:

We can talk about cospans in any category. A cospan is an abstract way of thinking about a ‘chunk of stuff’ $\Gamma$ with two ‘ends’ $I$ and $O.$ It could be any sort of stuff: a set, a graph, an electrical circuit, a network of any kind, or even a piece of matter (in some mathematical theory of matter).

We call the object $\Gamma$ the apex of the cospan and call the morphisms $i: I \to \Gamma, o : O \to \Gamma$ the legs of the cospan. We sometimes call the objects $I$ and $O$ the feet of the cospan. We call $I$ the input and $O$ the output. We say the cospan goes from $I$ to $O,$ though the direction is just a convention: we can flip a cospan and get a cospan going the other way!

If you’re wondering about the name ‘cospan’, it’s because a span is a diagram like this:

Since a ‘span’ is another name for a bridge, and this looks like a bridge from $I$ to $O,$ category theorists called it a span! And category theorists use the prefix ‘co-‘ when they turn all the arrows around. Spans came first historically, and we will use those too at times. But now let’s think about how to compose cospans.

Composing cospans is supposed to be like gluing together chunks of stuff by attaching the output of the first to the input of the second. So, we say two cospans are composable if the output of the first equals the input of the second, like this:

We then compose them by forming a new cospan going all the way from $X$ to $Z$ :

The new object $\Gamma +_Y \Gamma'$ and the new morphisms $i'', o''$ are built using a process called a ‘pushout’ which I’ll explain in a minute. The result is cospan from $X$ to $Z,$ called the composite of the cospans we started with. Here it is:

So how does a pushout work? It’s a general construction that you can define in any category, though it only exists if the category is somewhat nice. (Ours always will be.) You start with a diagram like this:

and you want to get a commuting diamond like this:

which is in some sense ‘the best’ given the diagram we started with. For example, suppose we’re in the category of sets and $Y$ is a set included in both $\Gamma$ and $\Gamma'.$ Then we’d like $A$ to be the union of $\Gamma$ and $\Gamma.$ There are other choices of $A$ that would give a commuting diamond, but the union is the best. Something similar is happening when we compose circuits, but instead of the category of sets we’re using the category of labelled graphs we discussed last time.

How do we make precise the idea that $A$ is ‘the best’? We consider any other potential solution to this problem, that is, some other commuting diamond:

Then $A$ is ‘the best’ if there exists a unique morphism $q$ from $A$ to the ‘competitor’ $Q$ making the whole combined diagram commute:

This property is called a universal property: instead of saying that $A$ is the ‘best’, grownups say it is universal.

When $A$ has this universal property we call it the pushout of the original diagram, and we may write it as $\Gamma +_Y \Gamma'.$ Actually we should call the whole diagram

the pushout, or a pushout square, because the morphisms $i'', o''$ matter too. The universal property is not really a property just of $A,$ but of the whole pushout square. But often we’ll be sloppy and call just the object $A$ the pushout.

Puzzle 1. Suppose we have a diagram in the category of sets

where $Y = \Gamma \cap \Gamma'$ and the maps $i, o'$ are the inclusions of this intersection in the sets $\Gamma$ and $\Gamma'.$ Prove that $A = \Gamma \cup \Gamma'$ is the pushout, or more precisely the diagram

is a pushout square, where $i'', o''$ are the inclusions of $\Gamma$ and $\Gamma$ in the union $A = \Gamma \cup \Gamma'.$

More generally, a pushout in the category of sets is a way of gluing together sets $\Gamma$ and $\Gamma'$ with some ‘overlap’ given by the maps

And this works for labelled graphs, too!

Puzzle 2. Suppose we have two circuits of resistors that are composable, like this:

and this:

These give cospans in the category $L\mathrm{Graph}$ where

$L = (0,\infty)$

(Remember from last time that $L\mathrm{Graph}$ is the category of graphs with edges labelled by elements of some set $L.$ ) Show that if we compose these cospans we get a cospan corresponding to this circuit:

If you’re a mathematician you might find it easier to solve this kind of problem in general, which requires pondering how pushouts work in $L\mathrm{Graph}.$ Alternatively, you might find it easier to think about this particular example: then you can just check that the answer we want has the desired property of a pushout!

If this stuff seems complicated, well, just know that category theory is a very general, powerful tool and I’m teaching you just the microscopic fragment of it that we need right now. Category theory ultimately seems very simple: I can’t really think of any math that’s simpler! It only seem complicated when it’s unfamiliar and you have a fragmentary view of it.

So where are we? We know that circuits made of resistors are a special case of cospans. We know how to compose cospans. So, we know how to compose circuits… and in the last puzzle, we saw this does just what we want.

The advantage of this rather highbrow approach is that a huge amount is known about composing cospans! In particular, suppose we have any category $C$ where pushouts exist: that is, where we can always complete any diagram like this:

to a pushout square. Then we can form a category $\mathrm{Cospan}(C)$ where:

• an object is an object of $C$

• a morphism from an object $I \in C$ to an object $O \in C$ is an equivalence classes of cospans from $I$ to $O:$

• we compose cospans in the manner just described.

Why did I say ‘equivalence class’? It’s because the pushout is not usually unique. It’s unique only up to isomorphism. So, composing cospans would be ill-defined unless we work with some kind of equivalence class of cospans.

To be precise, suppose we have two cospans from $I$ to $O$ :

Then a map of cospans from one to the other is a commuting diagram like this:

We say that this is an isomorphism of cospans if $f$ is an isomorphism.

This gives our equivalence relation on cospans! It’s an old famous theorem in category theory—so famous that it’s hard to find a reference for the proof—that whenever $C$ is a category with pushouts, there’s a category $\mathrm{Cospan}(C)$ where:

• an object is an object of $C$

• a morphism from an object $I \in C$ to an object $O \in C$ is an isomorphism class of cospans from $I$ to $O.$

• we compose isomorphism classes of cospans by picking representatives, composing them and then taking the isomorphism class.

This takes some work to prove, but it’s true, so this is how we get our category of circuits!

Next time we’ll do something with this category. Namely, we’ll cook up a category of ‘behaviors’. The behavior of a circuit made of resistors just says which currents and potentials its terminals can have. If we put a circuit in a metaphorical ‘black box’ and refuse to peek inside, all we can see is its behavior.

Then we’ll cook up a functor from the category of circuits to the category of behaviors. We’ll call this the ‘black box functor’. Saying that it’s a functor mainly means that

$\blacksquare(f g) = \blacksquare(f) \blacksquare(g)$

Here $f$ and $g$ are circuits that we can compose, and $f g$ is their composite. The black square is the black box functor, so $\blacksquare(fg)$ is the behavior of the circuit $f g.$ There’s a way to compose behaviors, too, and the equation above says that the behavior of the composite circuit is the composite of their behaviors!

This is very important, because it says we can figure out what a big circuit does if we know what its pieces do. And this is one of the grand themes of network theory: understanding big complicated networks by understanding their pieces. We may not always be able to do this, in practice! But it’s something we’re always concerned with.

]]>