We spent the last few episodes assembling our toolbox of equations. The game in graphical linear algebra is as follows: we consider two diagrams to be equal exactly when we can use the equations and graphical reasoning to prove it. If we cannot, we will consider them to be different. A mathematician would say that we are considering the free system on this set of equations.
If this idea is not clear, then imagine playing a board game: the things that you are allowed to do are only those that are specified in the rules. If something is not in the rules, then it is not allowed. Board game rulebooks typically do not include every possible way of how one could break the rules. People are way too creative at cheating; no wonder that law is such a complicated mess! In a similar way, we are usually not going to explicitly say when two diagrams are different: we consider them to be different if it is not possible to show, using the rules, that they are equal.
Anyway, here’s a convenient cheat sheet for the equations we have met so far, to save unnecessary clicking between episodes.
I hinted back in Episode 3 that graphical linear algebra has something to say about counting. That’s the plan for today. We will focus our attention on a very particular class of diagrams: those with exactly one dangling wire on the left and on the right. As it turns out, such diagrams are very closely related to natural numbers: that is, non-negative integers 0, 1, 2 and so on. For example it makes a lot of sense to associate the following diagrams with the corresponding numbers:
Remember the intuition about numbers travelling on wires? Well, associating numbers to diagrams is compatible with all that. For example, let’s consider sending a number x on the left dangling wire of the diagram that we are associating with the number 3.
The output is x + x + x = 3x. So, whatever the input, the diagram acts by multiplying it by 3. If you look at the diagrams for 0, 1 and 2, the idea is the same.
There is also a nice graphical intuition at play here: the number associated to a diagram is the number of paths from the dangling point on the left to the dangling point on the right. So, in the diagram to 0 there are no paths from left to right, in 2 there are two different paths, and so on. This graphical intuition is very important and we will come back to it again soon.
Although this is all quite cute, the correspondence between numbers and diagrams is not merely skin deep. As we will discover, the algebra of diagrams allows us to perform the basic operations of arithmetic: addition and multiplication. Thus, while our slogan so far is that linear algebra is all about what happens when adding and copying meet, we can actually be more extreme: even the basic idea of natural numbers is explained by adding and copying!
We start by defining a translation from numbers to diagrams, which will be useful for us as a syntactic sugar. The expression “syntactic sugar” is probably quite familiar to you if you are a programmer: it means a construction that is useful to have as part of your language, but that does not actually add anything new: the language does not become any more expressive. Syntactic sugar can always be translated away to phrases that we had before, but having it may be convenient for several reasons. This is exactly the case that we have before us.
Our syntactic sugar is a family of special diagram components, one for each natural number. We start with our good friend 0. We use the special := notation to indicate that we are actually defining the thing to the left in terms of things that we already know about.
The reason for the name (base) is that we will define the syntactic sugar recursively, and the definition above is the base case of the recursion. The recursive case is:
Maybe you have not seen the use of recursion before. It is something that many first year Computer Science undergraduates are very scared of; I know from personal experience! The reason is that, if you look at (rec), we are trying to define something (the left hand side), but we are using it again in the definition (the right hand side). This looks circular and weird — but don’t worry, it makes sense, and is not very difficult. The best way to get the hang of it is to experiment with some concrete examples.
So let’s understand the first few numbers, starting with 1.
We use (rec) to get the first equality, then (base), then (Unit), then (Counit). So the diagram that corresponds to 1 is simply the identity.
Let’s do 3 now.
We use (rec), then (rec) again, and then we use our knowledge of the diagram for 1, which as we have discovered above, is simply the identity.
It is important not to confuse the syntactic sugar for a natural number with a number travelling on the wire, as per our standard intuition. In fact, the sugar acts by multiplying its input by the number it represents, like so:
Let’s prove this!
But how does one prove something about all natural numbers? We could start showing that it holds for individual cases, say n = 13, but that would not be very satisfactory. Maybe we got lucky with that particular choice, maybe it’s not true for n = 12?
The trick is to use mathematical induction: if we show that the above is true for n = 0 (the base case) and whenever it is true for n = k then it is also true for n = k + 1 (the inductive step), then we can conclude that it holds for all natural numbers n. It’s kind of a bootstrapping process: how do I know that it’s true for n = 13492? Well, we know it’s true for n = 0. But because it’s true for n = 0, it must be true for n = 1, using the inductive step. But because it’s true for n = 1, it must be true for n = 2. And so on, until eventually we get to n = 13492.
We start with the base case, n = 0. Using (base) we need to check the behaviour of the following circuit.
And indeed, according to our established intuition about how the generators behave, a number x arrives on the left, is discarded, and a 0 is produced by the zero generator. But 0 = 0x, so the effect of the 0 sugar is to multiply its input by 0, as we are claiming.
Now let’s assume that this works as advertised for n = k and try to show that it holds for n = k + 1. The assumption is called the inductive hypothesis. For the k + 1 circuit, we use its defining equation (rec) and consider the behaviour of the following.
Again a number x arrives on the left, and is copied. The first copy is fed into the k sugar, which, by the inductive hypothesis, multiplies its input by k, resulting in the output kx. The second copy of x is untouched, and so kx and x are fed into addition, resulting in the output kx + x. But kx + x = (k + 1)x, which is what we want!
This concludes the induction and the proof. We will do many more induction proofs, so if all this is new to you then you will have plenty of examples to get comfortable!
We now move to the meat of this episode: showing how the algebra of diagrams can be used to express some familiar operations on numbers. Let’s start with adding: we willl prove that the following equality holds for all natural numbers m, n:
One way of understanding (sum) is that it show that ordinary, old-fashioned addition of natural numbers is already a part of our language: we can understand it with the basic operations of graphical linear algebra.
So let’s start by looking at what happens when n = 0, the base case of the induction.
We first use (base), then (Unit) and (Counit) together in a single step. Finally m = m + 0, as we all know. This shows that, no matter what m is, (sum) is true when n = 0.
Next, let’s look at the inductive step: remember, we can assume that what we want to prove, (sum), is true whenever n = k, and simply show that it is true for n = k + 1. Here we go:
First we use (rec), then (Assoc), then (CoAssoc). Next comes the use of our inductive hypothesis, and finally we use (rec) again. This completes the induction, and the proof of (sum).
We are going to prove a few more things in this episode. The first is the following useful equation, which holds for any number m.
Again the proof is by induction. For m = 0, it suffices to use (B4), the bone equation.
Next the inductive step.
First we use (rec), then (B2), then the inductive hypothesis, and finally (Counit). That’s (discarding) proved then.
The next property that we need is the following.
Let’s do the induction. For the base case, we have:
The proof of the inductive step is long, but not very complicated. We just need to apply (CoAssoc) a number of times and (CoComm) once to get the right alignment of the copies on the left. In the third step we use the inductive hypothesis. It is not super important to follow all the steps, so feel free to skip it.
If you did go through the proof carefully, maybe you spotted the one step where I cheated. It was the point at which I used (sliding) — remember that we are allowed to slide generators along wires. The reason why I was being slightly naughty is that the diagram for the number k is not, strictly speaking, a generator: it is syntactic sugar. However, because it is built from basic generators, one can show without too much difficulties that it can also be slid. In fact, it is not too difficult to show that any diagram whatsoever can be slid along wires.
Here’s a claim which I will not prove, because you have seen enough of examples of how to prove things by induction to be able to do it yourself. The claim is this:
For any natural number n, the bizarro version of the diagram for n is itself.
This is a useful fact to note, because we immediately get the following two things for free:
The reason why we know that (zero) and (adding) hold is because they are the bizarro versions of (discarding) and (copying). We can simply repeat each step in the proofs of (discarding) and (copying), but in the bizarro world.
We should spend a little bit of time discussing (adding), because it seems contrary to our expectation that the adding generator ought to be adding things. So why isn’t m + m = 2m? Well, let’s come back to our intuition of numbers on wires. Consider the left hand side of (adding), it has two dangling wires on the left on which we can send two numbers x and y. Next, remember from the introduction that the diagram for m acts by multiplying its input by m. Then the two outputs are fed into the adding operation, like so:
What about the right hand side? Performing the individual operations gives us the following behaviour:
But multiplication distributes over addition, so m(x + y) = mx + my; the behaviour of the two sides of (adding) is the same. We have, of course, already seen how to add natural numbers in graphical linear algebra, and it is handled by a combination of the adding and copying generators, as demonstrated in (sum).
There is just one more thing to prove in this episode, and it concerns another famous operation on natural numbers.
Just like (sum) can be understood as saying that ordinary addition of natural numbers can expressed using graphical linear algebra, (multiplication) is saying that ordinary multiplication of natural numbers is just composition.
To prove it—you guessed it!—we will use induction. The base case is the following, and we have the chance to use the (zero) property.
Next comes the inductive step, where we use both (adding) and (sum).
This completes the proof of (multiplication).
We have shown how natural numbers, addition and multiplication arise in graphical linear algebra. But there is one point about which you may be nervous: we have shown all kinds of useful properties, but what if actually 2 = 3 in graphical linear algebra? What if every number is equal to every other number? Maybe there is some crazy graphical proof that shows this? And how do we show that one cannot prove something, anyway? This is where the graphical intuition about counting paths comes in, and we will come back to this in the next episode.
Another question that you may have is the following. We have shown that all natural numbers can be understood as certain diagrams with one dangling wire on the left and one on the right. But are there some diagrams of this kind which are not equal to one that represents a natural number? In fact, this is not the case: this class of diagrams is in 1-1 correspondence with the natural numbers: every diagram with one dangling wire on the left and right is equal to one that comes from a number. There are several ways to show this, and we will explore some of these techniques in subsequent episodes.
Continue reading with Episode 10 – Paths and Matrices
17 thoughts on “9. Natural numbers, diagrammatically”
Axiom adding seems to be incorrect. m + m = 2m, no?
Thanks for spotting this, actually it is correct, but it’s slightly counterintuitive. Using the “numbers on wires” intuition, that lemma says that mx+my=m(x+y).
Thanks for the quick answer. I think I get it.
I stumbled on the same issue and needed to get back to (sum) to get it. Maybe worth a comment?
Definitely, I’ll add an explanation; thanks!
The usage of the copy generator from this blog entry and onwards is confusing me. When it was defined in”Copying, Discarding, and the Slogan” you said “Copy takes one argument and has two results, and it lives up to its name by – wait for it – copying”. The example was 42 comes in on the left wire, and 42 goes out on each of the right wires.
But now, it seems to behave differently. In the (rec) definition, it looks like whatever value is on the left wire goes out as K on the top right wire and identity on the bottom. Further, in the (sum) definition, whatever is on the left wire goes out as M and N on the right wires. Both of these cases don’t seem to be doing any copying.
I’ve really been enjoying this series, and this is the first thing that’s confused me. I hope I’m missing something obvious!
LikeLiked by 1 person
Thanks a lot for this! It’s great to get some feedback on what is confusing, and many other people have been confused by this.
I added a new section just after the point at which the syntactic sugar for natural numbers is introduced, explaining and proving the behaviour: it is just after the point where the definition of 3 is unfolded.
Let me know if this helps, and thanks again!
Yes – it’s much clearer now! Emphasizing that the natural number syntactic sugar is multiplying the underlying value on the wire has made it click.
The links to (sum) don’t work for me.
Thanks, I fixed it now.
“Linear algebra is the mathematics of adding and copying”. One thing I want to understand better is what “is” adding and copying. After all, we have an axiomatic theory here. We call it adding and copying, but this is just intuition. Really, all we have is just the axioms. Now one of the fascinating things about the axioms is that they are self-dual. If I read from right to left instead of from left to right, adding becomes copying and copying becomes adding. So, it seems that adding and copying are the same thing in a way. But this is not intuitive anymore! So what is going on here?
We started with some pretty straightforward ideas about moving numbers along wires and ended with a beautiful symmetry between adding and copying that seems entirely non-intuitive and mysterious?
Yes indeed. In fact, once you get to the full system of equations for Graphical Linear Algebra, white and black are entirely interchangeable! It’s one of the two symmetries of GLA, the other being that any equation mirrored is still an equation. You’ll get a better feel for the colour symmetry if you read the post on orthogonality. This is one of my favourite things abut the language of GLA — these beautiful symmetries of linear algebra just stare at you in the face instead of being hidden by notation and arbitrary choices in presentation.
To break the symmetry you need to go to inequations, and in fact only one inequation suffices. It is the one that says that the white lollipop (0) is less than the black lollipop (everything). I don’t have anything on the blog about it, but the proof is really simple and is in the CONCUR 18 paper with Bonchi, Holland and Pavlovic.
Perhaps I’m missing something, but seems like we need to assume the associativity of the “bizarro” operation in order to prove the inductive step of proving “For any natural number n, the bizarro version of the diagram for n is itself.” I guess it seems obvious that “bizarrify” is associative, but did we ever prove that?
To be clear, in the inductive step we take [k + 1] and split it into [k] and a parallel wire using (rec). By inductive hyp bizarro[k] = k and bizzaro the rest of the diagram equals itself, but I don’t think we ever proved that you can do the next step of moving everything inside one bizarro operation.
I’m not sure what you mean by “associative” since “bizzarify” is not a binary operation. But you’re right that there’s a certain amount of hand-waving: what one should really do is to prove that it is a (contravariant) identity-on-objects monoidal functor. But this is easy, and you are right, the (easy) proof is inductive because “bizzarify” can itself be defined recursively!
LikeLiked by 1 person
I’m sorry yes, not “associative” but linear in ⊕… Biz( x ⊕ y) = Biz(x) ⊕ Biz(y)
LikeLiked by 1 person