Special bimonoid | Graphical Linear Algebra

There is a cute graphical/algebraic way of understanding functions and relations between finite sets, and it deserves to be more widely known. The (formal) diagrams involved closely resemble the (informal) pictures that lecturers often draw when first explaining these concepts to undergraduates.

Although somewhat tangential to the main spine of the story of graphical linear algebra, the diagrammatic treatments of functions and relations give us two additional, simple examples where well-known mathematical structures are characterised as free PROPs. We have already seen two examples: the isomorphisms between Mat and B (Episodes 15 and 16) and between Mat_Z and H (Episode 19). We will see several more in future episodes.

Now is a good time for a discussion about functions and relations: as we discussed in the last episode, relations play a very important role in graphical linear algebra; this episode thus also serves as a little primer/reminder.

First, let’s fix some notation. A bold number n represents a finite set that contains the elements 0, … , n-1. So for example

1 = { 0 }, 2 = { 0, 1 }, 3 = { 0, 1, 2 }

and so on. 0 is the empty set, that is, it has no elements.

A function f from m to n, often written f: m → n, is a kind of “rule”; we can evaluate it by giving it an element k in m (i.e. 0 ≤ k < m). The result is denoted f(k) and it is an element in n (i.e. 0 ≤ f(k) < n).

The definition does not specify how f works, and a function is considered to be equal to another precisely when the two have the same domain and codomain, and act the same way on all possible inputs. This is sometimes called the extensionality property of functions: in more mathematical jargon, if f and g have the same type, we have that:

∀x. f(x) = g(x) implies f = g (extensionality)

So the only interesting information about a function is (1) its type and (2) where it takes each of its arguments.

I remember that when I first encountered the notion of function, I found it a bit weird. Shouldn’t there at least be some kind of formula or algorithm that calculates it? The functions that I remembered from high school always had a rule, and usually a simple one, say f(x) = x².

I also remember finding the extensionality property strange at first. I can write two very different computer programs to calculate, say the factorial of a natural number. Extensionality says that they are considered to be the same thing when thought of as functions. So, if you like to think in terms of algorithms, it can be useful to think of a function as a kind of idealised specification, which may have zero or more implementations.

There are finitely many functions from any finite set to another. To get the total number of functions from m to n, the crucial insight is that we only care about where the elements from the domain go. We have n choices where to send 0, n choices where to send 1, etc. Since each choice is independent, the total is just n multiplied by itself m times, i.e. n^m.

For example, here are pictures of the four functions from 2 to 2.

Let Fun denote the PROP where the arrows from m to n are functions from m to n. Composition in Fun is composition of functions: if f: m₁ → m₂ and g: m₂ → m₃ then their composition, often written g ○ f or f ; g is a function m₁ → m₃. We just apply one rule after the other:

(g ○ f) (k) := g(f(k))

Pictorially, this means plugging in the output of the first function as the input of the second. So for example, composing the “twist” function with itself is the function

which is the identity, by extensionality, since each argument ends up being taken to itself.

The monoidal product in Fun is similarly simple: it is “stacking one function on top of the other”. Pictorially, this is very simple to visualise, e.g.

We can write a somewhat less enlightening formula for this. If f₁: m₁→n₁ and f₂: m₂→n₂ then

The permutations of Fun are the obvious things–they are simply traditional permutations, viewed as functions. And it is not difficult to show that all the properties required of PROPs hold.

So what is the theory that characterises Fun? It turns out that we have met it already on this blog.

Let’s call the PROP that arises from the equations above M. Then M and Fun are isomorphic as PROPs. By the way, in this episode we colour all diagram nodes gray: this is so that we don’t get our intuitions confused, since our convention is that the white structure is “adding” while the black structure is “copying”.

The proof that M is isomorphic to Fun is not very difficult, but we will skip it for now. We will probably come back to it when discussing distributive laws, because they also rear up here. For now, to convince you that this has a chance of being true, I’ve drawn the diagrams that represent each of the functions from 2 to 2 that we enumerated previously.

See what I meant about the diagrams looking very much like the pictures one draws of functions?

The isomorphism between M and Fun means that to give a function from m to n is the same thing as to give a diagram in M. And two diagrams are equal via diagrammatic reasoning exactly when they define the same function.

I took discrete maths course as a first year undergrad. That’s where I first encountered functions in the abstract, set theoretical sense.

Taking discrete maths was a fun experience, and challenging in some ways; even though the computations were not very complicated, it was my first exposure to abstract mathematics. We went through the basics of naive set theory, including the notions of cardinality, functions and relations, then went on to matrices, vector spaces, simple combinatorics, etc. I guess that the recipe is similar in most maths/CS degrees around the world.

Five years ago I found myself having to teach them in a Southampton variant of a discrete maths course. And I found out that teaching discrete maths, which I expected to be a breeze, is actually quite challenging.

In fact, the whole idea of abstract, untyped sets and basic operations on them can be quite strange for students straight out of high school. Once they get the basics though, functions are a breeze. But when we get to relations… there’s always trouble. And no matter how much time I spend on them, it seems that for some people it’s difficult to grasp; even when I keep repeating “remember, a relation is simply a subset of the cartesian product”.

I think that it’s got something to do with psychology: people already have a feel for functions, even before they know the formal definition. Rules are something familiar, it’s that inputs and outputs idea again. The world of relations, in comparison, seems strange and much less intuitive—even if the definitions are extremely simple.

If X and Y are sets, then a relation R from X to Y, written R: X ⇸ Y, is a subset of the cartesian product X×Y. What this means is that R is a collection of pairs of the form (x, y) where x is an element in X and y is an element in Y.

Just as with functions, it’s pretty easy to count the total number of relations between finite sets. For example, to figure out the number of relations from m to n, first we observe that the total number of pairs (x,y) where x is in m and y is in n is simply mn, since there are m choices for x and n choices for y. Second, a relation is a subset of the cartesian product, and a finite set of cardinality k has 2^k subsets. It follows that there are 2^mn such relations.

Let’s draw the relations from 2 to 2, there should be 2⁴ = 16 of them. In the pictorial representation, a line connects x to y precisely when (x,y) is in the represented relation.

There is one interesting thing to notice: if you look at the pictures of functions 2 → 2, we can find similar pictures amongst the relations: (h), (i), (j) and (k). This is because every function from m to n can be thought of as a relation. This relation is sometimes called the graph of the function, and it’s defined to be the subset { ( k, f(k) ) | 0 ≤ k < m }. It’s therefore quite natural to think of functions as special kinds of relations.

The PROP where arrows from m to n are relations from m to n is called Rel. Composition in Rel is, as expected, composition of relations. If you haven’t come across this before, it’s very simple. If R: m₁ ⇸ m₂ and S: m₂ ⇸ m₃ then R ; S is the relation m₁ ⇸ m₃ defined:

R ; S = { (x,z) | there exists y such that (x,y) ∈ R and (y,z) ∈ S }

Again, pictorially, this is pretty simple to explain: we put the two relations we are composing side by side, and include a connection from the starting point to the end point if there is a path that takes us there. We don’t care about the precise number of paths, as long as it’s greater than 0. Here are some examples:

As we observed before, every function gives rise to a relation, and it’s not difficult to see that relational composition is compatible with composition of functions: if I compose two functions and look at the resulting relation then it is the same one as if I composed the two functions as relations.

The monoidal product in Rel is also similar to the one in Fun: again, we stack relations on top of each other. For example:

The permutations are the graphs of permutations. Again, it’s not difficult to verify that Rel satisfies all the conditions required of PROPs.

The fact that composition and monoidal product are compatible in Fun and Rel can be captured succinctly by the observation that there is a faithful homomorphism Fun → Rel. Obviously this homomorphism is not full, because, in general, not every relation from m to n is the graph of a function.

As was the case with functions, we have also seen almost all we need to understand how to characterise relations diagrammatically. The theory that does the job is the following.

We have seen most of these equations before. Taking (S) away, it is just the theory B, and we went though all of its equations in detail in Episode 8. We know that B is isomorphic to the PROP Mat of natural number matrices.

The equation (S) is sometimes called the “special” equation. It’s not a great name, but it seems to have stuck so we will use it. If we think in terms of natural number matrices, (S) seems to be saying that

2 = 1

which may look… a bit weird. But, thinking about the graphical interpretation it makes sense. We saw in Episode 9 that the diagrammatic way of understanding natural number matrices has to do with counting paths. Similarly, when composing relations we also have to keep track of paths, it’s just that we are only interested in the Yes or No question “Is there a path?”, and we don’t care about the number. This is one interpretation of (S): it ensures that having 100 paths is the same as having 1 path (but different to no paths).

Again, we won’t prove that the PROP generated by the theory of special bimonoids is isomorphic to Rel. Let’s save that for later. For now, here is a picture of how some of the pictures of relations from before look as diagrams in the theory.

I wrote a part of this episode during my holidays on a train from Yerevan, the capital of Armenia, to Tbilisi, the capital of Georgia. The train trip was quite an experience.

It was an old Soviet relic from I would guess the 60s or the 70s. The weather was very warm, in the high 30s, but fortunately the train was equipped with air conditioning. Unfortunately, it was controlled by a matronly, but friendly, Russian lady who was in charge of the carriage. If she judged that the sun was not shining hard enough, she simply turned the aircon off and walked along the corridor, opening windows. Once the train heated up (way) past the point of comfort, the ritual was reversed.