# Transformational Music Theory (18): binary relations, relational presheaves

I got a paper published online last month in Journal of Mathematics and Music, and I thought I could write a general explanation about it here. The paper can be accessed directly on the website:

• Popoff, A., On the use of relational presheaves in transformational music theory, Journal of Mathematics and Music, 2020,

As its title says, I examine the use of relational presheaves, a fancy term for a system of sets and binary relations between them. In fact, you may have already seen those in a previous post about networks in transformational music theory, and how they can be defined when binary relations are involved. However the focus on networks involved notions in category theory  that overshadowed the role of sets and binary relations themselves. In fact, I should have written this article first, and then the article about networks !

Anyway, we are going to get rid of the network part and focus specifically here on the part about binary relations. But first, why would we need binary relations at all ? In all the previous blog posts, we always have considered functions between sets of musical elements, often bijective ones : for example, the well-known $P$, $L$, and $R$ operations of neo-Riemannian theory. If you recall the definition of these operations, they switch from major triads to minor triads (or minor to major) by keeping two notes identical while moving the third one. Which two notes remain identical is determined by the choice of $P$, $L$, or $R$, but if you don’t care about this specific detail and are just interested in the fact that one chord moves to another by a singe note difference, then you would wish to somehow ‘collapse’ these three operations into a single one, which we would call $\mathcal{C}_2$, as in ‘Common 2 tones’.

But how do we do that ? Say for example that we have a C major chord. By the $P$ operation, it is sent to C minor, by the $L$ operation, it is sent to E minor, and by the $R$ operation, it is sent to A minor. If we simply want to examine where the C major chord would be sent by our ‘common 2 tones’ $\mathcal{C}_2$ ‘operation’, we could say it is sent to all these three chords. But that it is not a function ! A function on a set has a single image for each element of the set, not three ! That’s where binary relations get involved. The binary relation $\mathcal{C}_2$ is such that two elements $x$ and $y$ (two chords) are related by $\mathcal{C}_2$ if they share two tones in common. But one chord could be related to many others. Thus, instead of speaking of the image of the C major chord, as if it were a single element, we will now speak of its image set, which we will define in this case as the set {C minor, E minor, A minor}. In mathematical terms, binary relations between two sets $X$ and $Y$ can be defined as functions from $X$ to $\mathcal{P}(Y)$, the powerset of $Y$: the set {C minor, E minor, A minor} is an element of the powerset of the set of major and minor triads. If you like category theory, this definition of sets and binary relations between them gives a category which is the Kleisli category for the powerset monad. We will call this category $\mathbf{Rel}$, just as we have a category $\mathbf{Sets}$ of sets and ordinary functions between them.

In all the previous blog posts about transformational music theory, we have mainly worked in $\mathbf{Sets}$: we have defined sets of musical elements, multiple musical transformations between them (functions on these sets), and studied the groups, monoids, groupoids, or even categories they generate. Quite generally (and this is a point of view I have put forward in the previous posts), we have studied functors from a relevant category $\mathbf{C}$ of musical morphisms to the category $\mathbf{Sets}$. In category theory, this is called a presheaf (depending on the definitions… usually it is defined as a functor $\mathbf{C}^{\text{op}} \to \mathbf{Sets}$, but this is not important). Because we want to do more, we are replacing $\mathbf{Sets}$ by $\mathbf{Rel}$, hence the name ‘relational presheaf‘.

Relational presheaves have appeared numerous times in the scientific literature. For example, they can also be viewed as ‘labelled transition systems’ as shown in the article below.

• Sobociński, P., Relational Presheaves as Labelled Transition Systems, In Coalgebraic Methods in Computer Science, 2012, edited by Dirk Pattinson and Lutz Schröder, Berlin, Heidelberg, 40–50. Springer Berlin Heidelberg.

More importantly, it has been an important part of social network analysis, though the categorical point of view was not explictly formulated. You can find a lot of information about their use in the following book.

• Pattison, P., Algebraic Models for Social Networks, 1993, Structural Analysis in the Social Sciences, Cambridge University Press.

Before I turn to music theory, I’d like to borrow from the field of social network analysis and to demonstrate a simple example showing how relational presheaves are used. Say we have a set of four persons, Alice, Sarah, Mark, and John. We could look at who likes who: this will define a binary relation $\mathcal{L}$ (as in ‘like’) on this set. We can represent this graphically (more on that later):

Mark and Sarah like each other. Sarah also likes Alice, who likes John just as Mark does. But John doesn’t like anybody (in other words, the binary relation $\mathcal{L}$ is not reflexive). What if Marks wants to know who the people he likes like ? You can compose binary relations ! The image set of ‘Mark’ by $\mathcal{L}$ is the set {Sarah, John}, and the image sets for these two elements is {Mark, Alice}, and {} (yes, the empty set), respectively. So the image set of ‘Mark’ by $\mathcal{L}^2=\mathcal{L} \circ \mathcal{L}$ is {{Mark,Alice},{}}, that is {Mark, Alice} (how I got rid of those extra brackets is exactly contained in the definition of the powerset monad, but let’s not care too much about that). So, the people Mark likes also like him and Alice. We can do this further, and study the monoid $M_{\mathcal{L}}$ generated by $\mathcal{L}$: it has four elements $\mathcal{L}$, $\mathcal{L}^2$, $\mathcal{L}^3$, and the identity $e$, subject to the relation $\mathcal{L}^4=\mathcal{L}^2$.

Note that when we have a relational presheaf $S \colon \mathbf{C} \to \mathbf{Rel}$ where the category $\mathbf{C}$ is a monoid, we can give a precise definition of the graphs we draw. More exactly, if we select a subset $R$ of elements of the monoid, we can define the graph as having elements of the image $X$ of the single object of $\mathbf{C}$ by $S$ as its vertices, and an edge of color $r$ in $R$ each time two elements $x$ and $y$ in $X$ are related by $S(r)$. As shown in the article, when $R$ is the set of generators of the monoid, this also gives us a correspondance between paths in the graphs and elements of the monoid. There is also a result in the article regarding the correspondance between automorphisms of such graph leaving the edge colors invariant, and automorphisms of the corresponding functor $S$; I’m leaving this result out in this post.

But why limit ourselves to just one binary relation ? We could also look at who owes who money, by definining another binary relation $\mathcal{O}$, which we represent in yellow below.

We now have two generators, and the monoid $M_{\mathcal{L},\mathcal{O}}$ they generate contains nine elements: the identity $e$, $\mathcal{L}$, $\mathcal{O}$, $\mathcal{L}^2$, $\mathcal{O}^2$, $\mathcal{O}\mathcal{L}$, $\mathcal{L}\mathcal{O}$, $\mathcal{L}\mathcal{O}\mathcal{L}$, and $\mathcal{L}^3$, subject to the relations $\mathcal{L}^4=\mathcal{L}^2$, $\mathcal{O}\mathcal{L}^2=\mathcal{O}$, $\mathcal{O}^3=\mathcal{O}^2=\mathcal{L}^2\mathcal{O}=\mathcal{L}\mathcal{O}^2=\mathcal{O}^2\mathcal{L}=\mathcal{O}\mathcal{L}\mathcal{O}$. Each element of the monoid encode a specific social interaction: for example, $\mathcal{O}\mathcal{L}$ encodes “who do the people I like owe money to ?”, and can be depicted in our case as follows (check it !).

The relations of the monoid indicate social interaction which are the same : for example $\mathcal{O}\mathcal{L}^2=\mathcal{O}$ says that the people to which Mark, John, Sarah and Alice owe money to are the same as the people to which the people liked by the people they like owe money to (hmpf, that wasn’t easy to write…).

We can also work from the point of view of people, and ask by which elements of the monoid two people are related. Does this remind you of anything ? It should ! That’s what we do all the time in transformational music theory: “what are the possible transformations between this chord and that chord ?”. So for example, Mark and John are related by the $\mathcal{L}$ relation (that we knew from the definition), $\mathcal{L}^3$, $\mathcal{L}\mathcal{O}$, and $\mathcal{O}\mathcal{L}$. Indeed, Mark likes John, Mark likes Sarah who likes Alice who likes John, Mark likes Sarah who owes money to John, and Mark owes money to Alice who likes John. Notice that for each of these relations we can find a corresponding path from Mark to John in the graph above, following the black and yellow arrows.

Let’s now turn to music theory. There are a lot of cases where binary relations can be used: we have seen the $\mathcal{C}_2$ common-tone binary relation above, and in previous posts we have also seen the $\mathcal{P}_{1,0}$ relation of Douthett and Steinbach, which relates two chords if they differ by the movement of a single note by a semitone only. We can study the restriction of these two binary relations on the set of major, minor, and augmented triads: let’s call them $\mathcal{D}$ and $\mathcal{S}$ respectively (as in “double common notes” and “semitone movement” — this notation is different from the one in the article where I considered additional cases).

The $\mathcal{D}$ relation on the set of major, minor, and augmented triads (which include the traditional neo-Riemannian operations as sub-relations) generate a monoid of six elements subject to the relation $\mathcal{D}^6=\mathcal{D}^4$, and the corresponding graph is as follows.

The $\mathcal{S}$ relation on the set of major, minor, and augmented triads generate a monoid of seven elements subject to the relation $\mathcal{S}^7=\mathcal{S}^5$, and the corresponding graph is as follows. Note that this is the well-known ‘Cube Dance’ graph of Douthett and Steinbach.

You can check on this graph that for each path of length 7 from one chord to another (i.e. going from one chord to another in seven steps), you can always find a path of length 5 between these same chords: this is exactly what the relation $\mathcal{S}^7=\mathcal{S}^5$ tells us ! In the same way as we did above, we can look for elements in the monoids which relate two chords. For example, the C major chord and the F major chord are related by $\mathcal{D}^2$ on one hand (among other possibilities), and by $\mathcal{S}^3$ on the other hand. This indicates the difference between moving between chords by keeping two common notes, in which case two steps only are required, or moving between chords by single displacements of a semitone, in which case one cannot go from C major to F major in less than three steps (if we consider only major, minor, and augmented triads only, of course, since this is the set on which $\mathcal{S}$ and $\mathcal{D}$ are defined). Notice also that the fact that C major and F major are related by $\mathcal{S}^3$ doesn’t tell us anything about a preferential path between them, only that there exists at least one path of length 3 in the graph: in this case, it could either be C major to A flat augmented to A minor to F major, or C major to A flat augmented to F minor to F major.

But again, why limit ourselves to one generator ? In the example above, since the neo-Riemannian $P$ and $L$ operations are sub-relations of $\mathcal{S}$, we could well want to make them appear explicitly. In other words, we would define relational analogues of these operations, as well as an additional third one indicating how augmented chords are related to major and minor chords. This is what we did in a previous post where we defined the three relations $\mathcal{P}$, $\mathcal{L}$, and $\mathcal{U}$ giving rise to the edge-colored graph below and which generate a monoid $M_{\mathcal{U},\mathcal{P},\mathcal{L}}$ of 40 elements.

In the article, I examine an additional issue: the $\mathcal{U}$ operation is defined on all elements in the set of major, minor, and augmented triads. However, the neo-Riemannian operations are defined originally on major and minor triads only. We need therefore to extend them to augmented triads as well. The choice taken above considers that the relations $\mathcal{P}$ and $\mathcal{L}$ are the identity on augmented triads. However, there is another option which is given by the properties of binary relations, namely to consider that the neo-Riemannian operations $P$ and $L$ are undefined on such triads. This gives us two alternatives $\mathcal{S}_{P}$ and $\mathcal{S}_{U}$ binary relations which, together with $\mathcal{U}$, generate a smaller monoid of 27 elements. However, in this monoid we do not have ${\mathcal{S}_{P}}^2={\mathcal{S}_{L}}^2=e$ anymore as we would have with the usual neo-Riemannian operations. Moreover, any monoid element of the form $m\mathcal{S}_{L}\mathcal{S}_{U}$ is the empty relation on major and minor triads, which is rather uninformative.

The problem of defining binary relations on all elements of a given set of musical elements gets worse when one adds more elements. The article considers the case of the set of major, minor, augmented, and sus4 suspended triads. If one wants to consider analogues of the neo-Riemannian $P$ and $L$ operations, as well as additional binary relations indicating how augmented and suspended triads, one is faced with the question of extending these binary relations to all elements. A consequence is that the size of the monoids quickly gets huge: depending on how you’ve defined the generators, you can get monoids of 600, 473293, or even 994624 elements ! This is clearly intractable for practical musical purposes.

A solution to avoid the definition of binary relations on all elements is to consider categories rather than monoids, i.e. to consider distinct sets for each type of chord instead of a single one containing all of them. In that case, you have to define more generators but this limits the explosion in number of elements. The article shows one way to do it in the case of major, minor, augmented, and sus4 triads, leading to a category with 4 objects and 172 morphisms, in which any two of triads in which one of them is major, minor, or sus4, is related by two morphisms only, simplifying the analysis.

I hope this will make a case for a larger use of relational presheaves in transformational music theory. It also raises a number of interesting mathematical, and possibly musical, perspectives. For example, a generalization of this approach is to study generalized binary relations in a quantale. A quantale $Q$ is a join complete partial order $Q$ with a monoid structure $(Q,*)$ such that multiplication distributes over arbitrary joins, i.e., we have

$x*(\bigvee\limits_{i \in I} y_i) = \bigvee\limits_{i \in I} x*y_i$ and $(\bigvee\limits_{i \in I} y_i)*x = \bigvee\limits_{i \in I} y_i*x.$

For a given quantale $Q$ we can then form the category $\mathbf{Rel}(Q)$ with finite sets as objects and $Q$-valued relations as morphisms, i.e., functions $X \times Y \to Q$, the composition of two morphisms $\mathcal{R} \colon X \times Y \to Q$ and $\mathcal{S} \colon Y \times Z \to Q$ being given by

$(\mathcal{S} \circ \mathcal{R}) (x,z) = \bigvee\limits_{y \in Y} \mathcal{S}(y,z)*\mathcal{R}(x,y).$

The category $\mathbf{Rel}$ is in fact the category $\mathbf{Rel}(B)$ where $B$ is the boolean algebra $B=\{0,1\}$, but there are others, such as the interval quantale or the Lawvere quantale.

Another perspective is to look at the 2-category structure of $\mathbf{Rel}$: binary relations can be included into other binary relations, thus giving 2-morphisms between them. Therefore, we would have to consider the notion of a lax relational presheaf to account for these 2-morphisms. As of now, it is not totally clear if there are interesting musical applications where such 2-morphisms would appear and be relevant. But who knows ?