Relation Composition

We intuitively understand the world through chains of connection—the "friend of a friend," the "colleague of a colleague." While we grasp this idea informally, mathematics provides a precise and powerful tool to formalize and analyze it: ​​relation composition​​. This concept is the engine for discovering hidden, indirect pathways within any system of relationships. Many recognize connections but lack the formal framework to systematically map and understand their implications. This article bridges that gap by providing a thorough exploration of relation composition.

This article will guide you through the fundamental machinery and expansive utility of this concept. In the first section, ​​"Principles and Mechanisms,"​​ we will dissect the formal definition of relation composition, explore its unique algebraic properties, and see how it generalizes the familiar idea of function composition. Following that, in ​​"Applications and Interdisciplinary Connections,"​​ we will see this abstract tool come to life, uncovering its surprising and profound impact in fields as diverse as computer science, social network analysis, and even music theory. By the end, you will see that relation composition is not just a formula, but a fundamental lens for viewing the interconnected structure of the world.

Have you ever thought about how you're connected to, say, the actor Kevin Bacon? You might not know him personally, but perhaps you know someone who worked on a movie with someone who was in a film with him. This chain of connections—the "friend of a friend" principle—is something we grasp intuitively. In mathematics, we have a wonderfully precise and powerful tool for describing exactly this idea: ​​relation composition​​. It's the art of chaining relationships together to discover new, indirect ones.

Imagine a complex system, like a piece of modern technology, built in layers. You have a set of components in Layer 1, another in Layer 2, and so on. A component from Layer 1 isn't directly compatible with one from Layer 4, but it can be connected through a chain of compatible parts in the intermediate layers.

Let's make this concrete. Suppose we have four sets of components, $A, B, C,$ and $D$.

• $R$ is the relation of "compatibility" between $A$ and $B$.
• $S$ is the relation of "compatibility" between $B$ and $C$.
• $T$ is the relation of "compatibility" between $C$ and $D$.

We want to find the overall "end-to-end compatibility" from $A$ to $D$. We can do this step-by-step. First, we compose $R$ and $S$ to find all workable paths from $A$ to $C$. We'll call this composite relation $S \circ R$. A pair $(a, c)$ is in $S \circ R$ if there exists some intermediate component $b \in B$ such that $(a, b)$ is a valid connection in $R$ and $(b, c)$ is a valid connection in $S$.

Formally, given relations $R \subseteq A \times B$ and $S \subseteq B \times C$, their composition is: $S \circ R = \{ (a, c) \in A \times C \mid \text{there exists some } b \in B \text{ such that } (a, b) \in R \text{ and } (b, c) \in S \}$

Notice the order: we write $S \circ R$, but when reading it, we apply $R$ first, then $S$. This convention matches the way we write function composition, which, as we'll see, is a special case of this very idea.

To get all the way from $A$ to $D$, we just repeat the process. We take our newly found relation $S \circ R$ and compose it with $T$. The final relation, $U = T \circ (S \circ R)$, gives us every pair $(a, d)$ for which a complete, valid chain of components exists. The real power here is that this isn't just a conceptual exercise; it's a computable procedure that can reveal all possible end-to-end pathways in a complex system.

If this idea of chaining feels familiar, it should! You have almost certainly encountered it as ​​function composition​​. Consider a function $f$ that takes a binary string and gives its integer value, and another function $g$ that takes that integer and maps it to a symbol. For example, $f(\text{"101"}) = 5$ and $g(5) = \beta$. The composite function $g(f(\text{"101"}))$ gives $\beta$.

A function can be thought of as a special kind of relation—one where each input is related to exactly one output. If we represent our functions $f: A \to B$ and $g: B \to C$ as relations $R_f \subseteq A \times B$ and $R_g \subseteq B \times C$, then the relational composition $R_g \circ R_f$ is precisely the relation corresponding to the function composition $g \circ f$.

This reveals something profound: relation composition is a generalization of function composition. It allows for relationships where one element can be connected to multiple others, or even none at all. It's like upgrading from a deterministic, single-track railway to a sprawling network of roads with countless intersections and branching paths.

Just like numbers have an algebra (addition, multiplication, etc.), relations have their own set of rules for how they combine. Exploring this "algebra" reveals the deep structure of how relationships behave.

​​Order is Everything (Non-Commutativity)​​ When you multiply numbers, $3 \times 5$ is the same as $5 \times 3$. With relations, this is rarely the case. Composition is generally ​​not commutative​​.

Imagine a grid of data centers. Let $N$ be the relation "is directly North of" and $E$ be "is directly East of". Let's think about the meaning of $E \circ N$ and $N \circ E$.

• A path from $c$ to $a$ exists in $E \circ N$ if we can go from $c$ to an intermediate point $b$ via $N$ (i.e., $b$ is North of $c$), and then from $b$ to $a$ via $E$ (i.e., $a$ is East of $b$). This means we go North, then East.
• A path from $c$ to $a$ exists in $N \circ E$ if we go East, then North.

It's clear from a simple drawing that these two protocols describe different paths to get from a starting point $c$ to an endpoint $a$ in the North-East quadrant. They are not the same! $E \circ N \neq N \circ E$. The order in which we apply relations fundamentally changes the result.

​​Special Elements: Identities and Annihilators​​ In arithmetic, the number 1 is the multiplicative identity ($x \times 1 = x$), and 0 is the annihilator ($x \times 0 = 0$). Relational composition has analogous concepts.

• The ​​identity relation​​ on a set $A$, denoted $I_A$, contains all pairs $(x, x)$ for $x \in A$. It's the "is the same as" relation. Composing any relation $R$ with the identity has no effect: $R \circ I_A = R$ and $I_B \circ R = R$ (assuming $R \subseteq A \times B$). It's like taking a step in your journey but ending up exactly where you started before taking the next one.
• The ​​empty relation​​, $\emptyset$, is a relation with no pairs. If you try to compose any relation with the empty relation, the result is always empty. For a pair $(a, c)$ to be in $R \circ \emptyset$, there must exist a $b$ such that $(a, b) \in \emptyset$ and $(b, c) \in R$. But no such $(a, b)$ exists! The chain is broken from the start.

​​Interaction with Other Operations​​ How does composition play with standard set operations like union and intersection? The results are subtle and revealing.

• ​​Union:​​ Composition ​​distributes over union​​. In a recommendation system, if a user's interest is inferred by liking items from a "primary" category list ($C_1$) or an "experimental" list ($C_2$), it's the same as inferring interest from the combined list ($C_1 \cup C_2$). Formally, $L \circ (C_1 \cup C_2) = (L \circ C_1) \cup (L \circ C_2)$.
• ​​Intersection:​​ Composition ​​does not distribute over intersection​​. A user's inferred interest from items present in both lists is not necessarily the same as the intersection of interests inferred from each list separately. This is because the "intermediate" item establishing the connection might be different in each case.
• ​​Converse:​​ The ​​converse​​ of a relation $R$, denoted $R^{\smile}$, is obtained by flipping all the pairs. So if $(x,y) \in R$, then $(y,x) \in R^{\smile}$. How does the converse interact with composition? It follows the famous "socks and shoes" principle: to undo the action of putting on socks then shoes ($S \circ R$), you must first take off the shoes ($S^{\smile}$) and then the socks ($R^{\smile}$). Formally, this gives the beautiful identity: $(S \circ R)^{\smile} = R^{\smile} \circ S^{\smile}$.

​​A Word of Caution:​​ It's tempting to assume that if the relations you're composing have a nice property, the result will too. This is a dangerous assumption! For example, even if $R$ and $S$ are both symmetric relations (if $x$ is related to $y$, then $y$ is related to $x$), their composition $S \circ R$ is not guaranteed to be symmetric.

What happens when we compose a relation with itself? We get $R^2 = R \circ R$. This represents all the "two-step" connections within a set. For example, if $R$ is the relation "is a parent of," then $R^2$ is the relation "is a grandparent of." We can continue this to find $R^3$ ("is a great-grandparent of") and so on.

This leads to a wonderfully elegant way to define one of the most important properties of a relation: ​​transitivity​​. A relation $R$ is transitive if, whenever $(a, b) \in R$ and $(b, c) \in R$, it must be that $(a, c) \in R$. In the language of composition, this is simply stated as: a relation $R$ is transitive if and only if $R^2 \subseteq R$. All two-step paths must already be included as direct one-step paths. The union of all powers of $R$, $\bigcup_{k=1}^{\infty} R^k$, gives us the ​​transitive closure​​ of $R$, which contains all pairs $(x, y)$ such that there is a path of any length from $x$ to $y$.

Perhaps the most beautiful application of relation composition is its ability to transfer structure from one set to another. Imagine you have a set of people $A$ and a function $f$ that maps each person to their city of birth, a set $B$. On the set $B$, we have an equivalence relation $E$, say "is in the same state as." So, $(b_1, b_2) \in E$ if cities $b_1$ and $b_2$ are in the same state.

Now, we can define a new relation $S$ on the set of people $A$ using the following composition: $S = f^{-1} \circ E \circ f$. Let's unpack this. For two people $a_1$ and $a_2$ to be related under $S$, we follow the chain:

1. Apply $f$: find their birth cities, $f(a_1)$ and $f(a_2)$.
2. Apply $E$: check if their birth cities are related by $E$ (i.e., are in the same state).
3. Apply $f^{-1}$: come back to the people.

So, $(a_1, a_2) \in S$ if and only if $f(a_1)$ and $f(a_2)$ are in the same state. We have used composition to "pull back" the relation from the set of cities to the set of people. And here is the magic: because the original relation $E$ was an equivalence relation (reflexive, symmetric, and transitive), the new relation $S$ that we constructed is also guaranteed to be an equivalence relation. Composition acts as a perfect conduit, transferring the entire algebraic structure from one world to another.

From simple chains of connections to the formal construction of abstract structures, relational composition is a fundamental concept that reveals the hidden pathways and unified architecture of the mathematical world. It is the engine that connects the dots.

Now that we have grappled with the machinery of relation composition, we might be tempted to put it away in a box labeled "abstract mathematics." But to do so would be to miss the entire point! This concept is not a mere formula; it is a powerful lens through which we can view the world, a tool for uncovering the hidden architecture of the systems all around us. We have seen that composition is the art of chaining relationships together. Let us now embark on a journey to see what surprising and profound connections we can unearth by following these chains.

In our modern world, we are all nodes in a vast, interconnected web. Relation composition is the native language for describing how we navigate this web.

Consider the World Wide Web itself. We can define a relation $L$ where $(a, b) \in L$ means "website $a$ has a hyperlink to website $b$." The composition $L \circ L$, or $L^2$, is easy to understand: it represents all the websites you can get to in exactly two clicks. But the real magic begins when we combine composition with other operations. What about the relation $L \circ L^{-1}$? Let's trace it. A pair $(w_1, w_2)$ is in this relation if there exists some other website, let's call it $u$, such that $(w_1, u) \in L^{-1}$ and $(u, w_2) \in L$. The first part, $(w_1, u) \in L^{-1}$, simply means $(u, w_1) \in L$—that is, website $u$ links to $w_1$. The second part, $(u, w_2) \in L$, means $u$ also links to $w_2$. So, what have we found? Two websites $w_1$ and $w_2$ are related by $L \circ L^{-1}$ if they are both "endorsed" by a common source page $u$. This isn't just a curiosity; it's the core idea behind co-citation analysis, a technique used by search engines and researchers to gauge the relatedness and authority of documents. Two pages linked to by the same high-quality source are likely to be related and important.

This same logic extends deep into the engine room of the software that powers our world. Imagine a package manager juggling thousands of software packages. We can define a relation $D$ where $(A, B) \in D$ means "package $A$ directly depends on package $B$." Developers often want to identify "sibling packages"—two distinct packages that rely on the same component. How can we express this? Two packages, $X$ and $Y$, are siblings if there exists a third package $Z$ such that $(X, Z) \in D$ and $(Y, Z) \in D$. This is a pattern of convergence. We can capture it with a clever composition: $(D^{-1} \circ D) \setminus I$. Let's break it down. A pair $(X, Y)$ is in $D^{-1} \circ D$ if there's an intermediate $Z$ such that $(X, Z) \in D$ and $(Z, Y) \in D^{-1}$. And as we've seen, $(Z, Y) \in D^{-1}$ is the same as $(Y, Z) \in D$. This is exactly our condition! We then subtract the identity relation $I$ to ensure we're only finding pairs of distinct packages. With one elegant expression, we have defined a complex and useful relationship.

From networks of code, we can move to networks of people. In academia, who collaborates with whom? We can define relations for "co-authored with" ($P$) and "cited" ($C$). A funding agency might want to find researchers who are ripe for "downstream collaboration." They might define this as a scholar $x$ who has cited a scholar $z$, who in turn has co-authored a paper with a scholar $y$. This creates a path of influence: $x \xrightarrow{C} z \xrightarrow{P} y$. By the very definition of composition, this chain of relationships is captured by the composite relation $P \circ C$. Suddenly, we have a formal tool to map the flow of ideas and identify hidden avenues for scientific progress.

The power of relation composition truly blossoms when we realize it's not just a descriptive tool, but a computational one. This is made possible by representing relations as matrices. If we have a set of items, we can create a grid, or matrix, where a '1' in a cell $(i, j)$ means item $i$ is related to item $j$, and a '0' means it is not.

Remarkably, the composition of relations corresponds to matrix multiplication! If you have the matrix $M_R$ for a relation $R$, the matrix for the two-step relation $R^2 = R \circ R$ is just $M_R$ multiplied by itself (using Boolean rules for addition and multiplication). This bridges the abstract world of logic with the concrete world of computation. To find all the microservices that can communicate in a two-step path, you don't need to trace paths by hand; you just square the permissions matrix. To figure out which students have access to specialized software through their club memberships, you can compose the "student-is-in-club" relation with the "club-uses-software" relation by simply multiplying their respective matrices. The resulting matrix instantly tells you every student-software link, no matter how indirect.

This framework allows us to model more complex structures, like a company's hierarchy. Let $D$ be the "directly reports to" relation. The relation "is a subordinate of" is the transitive closure, $D^*$, which is like the sum of all powers: $D \cup D^2 \cup D^3 \cup \dots$. It captures paths of any length. Now, let's introduce another relation, $S$, for "works in the same department." What does the composition $S \circ D^*$ represent? A pair $(x, y)$ is in this relation if we can find an intermediary, $w$, such that $x$ is a subordinate of $w$ (i.e., $(x, w) \in D^*$) and $w$ works in the same department as $y$ (i.e., $(w, y) \in S$). This complex query—finding all employees who are subordinate to someone in a given employee's department—is expressed with beautiful simplicity through the language of relation composition.

Lest we think this tool is only for logicians and computer scientists, let's take a detour to the conservatory. It turns out that the rules of harmony and the structure of music are deeply connected to relation composition.

We can model musical pitches as integers and an interval as a relation. For example, let the relation $T_n$ mean "is $n$ semitones higher than." So, $(x, y) \in T_n$ if $y = x+n$. A Perfect Fourth is $T_5$, and a Perfect Fifth is $T_7$. What happens when we compose these relations? If we start at a note $x$, go up a perfect fourth to $y=x+5$, and then go up a perfect fifth from $y$ to $z=y+7$, our final note is $z = (x+5)+7 = x+12$. A jump of 12 semitones is an octave! So, we find that $T_7 \circ T_5 = T_{12}$. The composition of musical intervals corresponds to the simple addition of their sizes. This reveals a profound isomorphism between the structure of relations and the structure of numbers. The abstract algebra of composition is the very thing that makes music "make sense." This lets us solve musical puzzles. For example, the sequence "go down a perfect fifth, then up a perfect fourth, then up a perfect fifth" sounds complicated. In relational terms, this corresponds to the composition $T_7 \circ T_5 \circ T_{-7}$. Using our composition-as-addition rule, this simplifies to $T_{(-7)+5+7} = T_5$, which is just a Perfect Fourth. The complexity dissolves, revealing a simple, elegant truth.

The idea of composition is so fundamental that we can stretch it into new domains. So far, our relationships have been black and white: either they exist or they don't. But what about relationships that have shades of gray?

This leads us to the idea of fuzzy relations, where the "truth" of a relationship is a value between 0 and 1, representing its strength or certainty. How do we compose such relations? We need a new rule. The most common is the "max-min" composition. To find the strength of a two-step path from $i$ to $k$ through some intermediary $j$, we reason that the path is only as strong as its weakest link, so its strength is $\min(M_{ij}, M_{jk})$. But there could be many intermediaries! So, to find the overall strength of connection from $i$ to $k$, we should take the path through the intermediary that gives the strongest possible connection. This leads to the rule: $(M^2)_{ik} = \max_j \{ \min(M_{ij}, M_{jk}) \}$. This beautiful piece of logic allows us to find the "best" path in a network where every connection is weighted with uncertainty.

With all this power, it is easy to assume that composition is always a well-behaved operation, preserving any nice properties our original relations had. This, however, is a crucial mistake. Consider equivalence relations—the gold standard of "nice" relations, which are reflexive, symmetric, and transitive, and neatly partition a set into disjoint groups. Surely the composition of two such tidy relations must also be an equivalence relation? The answer is a resounding no. If we take one relation that groups $\{1,2\}$ and $\{3\}$ and compose it with another that groups $\{1\}$ and $\{2,3\}$, the resulting relation can fail to be symmetric or transitive. The act of composition can shatter these perfect partitions, creating a new, messier structure. This is a profound lesson: composition is a creative, and sometimes transformative, force. It doesn't just connect things; it builds entirely new structures that may not resemble their parents.

We have journeyed from software to symphonies, from corporate ladders to the fuzzy edges of logic. Is there a common thread, a grand viewpoint from which all these applications are just different shadows cast by the same object? The answer is yes, and it lies in the esoteric-sounding field of category theory.

Category theory is, in a sense, the mathematics of mathematics. It studies systems of objects and the "arrows" (or morphisms) that go between them. One of the most fundamental categories is called ​​Rel​​. In ​​Rel​​, the objects are simply sets. And the arrows from a set $A$ to a set $B$? They are, you may have guessed, the binary relations from $A$ to $B$.

The final, unifying revelation is this: the rule for composing arrows in the category ​​Rel​​ is precisely the definition of relation composition we have been using all along. It is not some arbitrary operation we invented; it is the natural, fundamental way to chain relational arrows together. The fact that this same composition rule appears in software engineering, social network analysis, and music theory is no accident. It is because all these systems can be seen as specific instances of structures living inside this one, grand category. Relation composition is the universal glue that holds this part of the mathematical cosmos together, a testament to the profound and often surprising unity of abstract thought.