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’ with two ‘ends’ and 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 the apex of the cospan and call the morphisms the legs of the cospan. We sometimes call the objects and the feet of the cospan. We call the input and the output. We say the cospan goes from to 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 to 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 to :
The new object and the new morphisms are built using a process called a ‘pushout’ which I’ll explain in a minute. The result is cospan from to 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 is a set included in both and Then we’d like to be the union of and There are other choices of 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 is ‘the best’? We consider any other potential solution to this problem, that is, some other commuting diamond:
Then is ‘the best’ if there exists a unique morphism from to the ‘competitor’ making the whole combined diagram commute:
This property is called a universal property: instead of saying that is the ‘best’, grownups say it is universal.
When has this universal property we call it the pushout of the original diagram, and we may write it as Actually we should call the whole diagram
the pushout, or a pushout square, because the morphisms matter too. The universal property is not really a property just of but of the whole pushout square. But often we’ll be sloppy and call just the object the pushout.
Puzzle 1. Suppose we have a diagram in the category of sets
where and the maps are the inclusions of this intersection in the sets and Prove that is the pushout, or more precisely the diagram
is a pushout square, where are the inclusions of and in the union
More generally, a pushout in the category of sets is a way of gluing together sets and 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:
These give cospans in the category where
(Remember from last time that is the category of graphs with edges labelled by elements of some set ) 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 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 where pushouts exist: that is, where we can always complete any diagram like this:
to a pushout square. Then we can form a category where:
• an object is an object of
• a morphism from an object to an object is an equivalence classes of cospans from to
• 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 to :
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 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 is a category with pushouts, there’s a category where:
• an object is an object of
• a morphism from an object to an object is an isomorphism class of cospans from to
• 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
Here and are circuits that we can compose, and is their composite. The black square is the black box functor, so is the behavior of the circuit 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.