Binary Relations

From social hierarchies and family trees to the logical flow of a computer program, our world is defined by a complex web of connections. How can we talk about these relationships with precision? Is there a common language that can capture the structure of "is an ancestor of," "is less than," and "is connected to" using the same fundamental building blocks? This challenge of formalizing the intuitive notion of "relatedness" represents a significant gap between our everyday language and the rigorous world of science and mathematics.

This article introduces the binary relation, a beautifully simple yet profoundly powerful concept from set theory that provides the answer. By treating relationships as concrete mathematical objects, we unlock a new way to analyze, classify, and manipulate connections of any kind. This exploration will guide you through the core principles of this concept and its surprising reach across various scientific disciplines.

We will begin in the first chapter, ​​Principles and Mechanisms​​, by defining what a binary relation is, exploring the fundamental properties that give them structure, and uncovering the elegant algebra that governs their interactions. In the second chapter, ​​Applications and Interdisciplinary Connections​​, we will see these abstract ideas in action, discovering how binary relations serve as the foundational grammar for fields ranging from computer science and database theory to the very architecture of mathematics itself.

Imagine you want to describe every possible relationship between a group of people. Who is friends with whom? Who is taller than whom? Who is a sibling of whom? At first, this seems like a messy, purely linguistic task. But what if I told you that all of these intricate webs of connection—from the ordering of numbers to the structure of a social network—can be captured by a single, breathtakingly simple mathematical idea? This idea is the ​​binary relation​​, and its power lies in turning the fuzzy concept of "relatedness" into a concrete object we can analyze, manipulate, and understand with absolute precision.

So, what is a relation, really? In mathematics, we have to be precise. We can’t just rely on the dictionary. The brilliant insight of set theory is to define a relationship by listing all the instances where it holds true. We start with a collection of objects, which we call a set, let's say $X$. Then we consider all possible ​​ordered pairs​​ $(a, b)$ of elements from that set. An ordered pair is not just a jumble of two things; the order matters. The pair $(a, b)$ is different from $(b, a)$, just as "Alice follows Bob" is different from "Bob follows Alice". The collection of all possible ordered pairs from a set $X$ is called the ​​Cartesian product​​, denoted $X \times X$.

Now for the main idea: a ​​binary relation​​ on $X$ is simply any subset of this Cartesian product $X \times X$. That’s it! If the pair $(a, b)$ is in our chosen subset, we say "$a$ is related to $b$". If it’s not, they aren't related in this specific way.

For example, let our set be the numbers $A = \{1, 2, 3\}$. The Cartesian product $A \times A$ is the set of all nine possible ordered pairs: $\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}$. The relation "less than" would be the subset $R_{<} = \{(1,2), (1,3), (2,3)\}$. The relation "is a divisor of" would be a different subset, $R_{div} = \{(1,1), (1,2), (1,3), (2,2), (3,3)\}$. A function, too, is just a special kind of relation where every element in the starting set is paired with exactly one element in the destination set. This definition is incredibly powerful. It takes the abstract notion of a relationship and turns it into a set—an object we can count, combine, and study.

Once you define something as a set, a physicist's or a mathematician's first instinct is to ask: "How many are there?" Let's think about a small social network with $n$ users. A "follow" relationship is a binary relation on this set of users. For any two users, say Alice and Bob, there are two possibilities: Alice follows Bob, or she doesn't. This corresponds to the ordered pair (Alice, Bob) either being in our relation set or not.

How many possible pairs are there in total? If there are $n$ users, there are $n$ choices for the first person in the pair and $n$ choices for the second, giving $n \times n = n^2$ possible ordered pairs. For each of these $n^2$ potential connections, we have an independent choice: "yes" or "no". This means the total number of possible "follow" configurations is $2 \times 2 \times \dots \times 2$, repeated $n^2$ times. The total number of distinct binary relations on a set of $n$ elements is therefore a staggering $2^{n^2}$.

Let this sink in. For a tiny group of 5 people, the number of possible relationship networks is $2^{5^2} = 2^{25}$, which is over 33 million. For a group of 20 people, the number $2^{400}$ is a number with 121 digits, vastly exceeding the estimated number of atoms in the observable universe. We are dealing with a combinatorial explosion of unimaginable scale. Out of this chaotic, boundless universe of possible relations, how do we find the ones that are meaningful and structured? We look for patterns.

The way we navigate this vast universe is by classifying relations based on their fundamental properties. These properties are simple rules that impose structure on the network of connections. Think of them as the laws of physics for relationships.

• ​​Reflexivity​​: Is every element related to itself? In a diagram, this means every point has a loop pointing back to itself. The relation "is less than or equal to" ($\le$) on numbers is reflexive, since $x \le x$ is always true. The relation "is taller than" is not. The formal statement is beautifully concise: a relation $R$ on a set $A$ is reflexive if for every element $x \in A$, the pair $(x,x)$ is in $R$. In shorthand: $\forall x \in A, xRx$.

• ​​Symmetry​​: Is the connection always a two-way street? If $x$ is related to $y$, is $y$ always related to $x$? "Is a sibling of" is symmetric. "Is a parent of" is not. A symmetric link is like a handshake; it requires both parties. Formally: $\forall x, y \in A, (xRy \implies yRx)$.

• ​​Anti-symmetry​​: This is the opposite of symmetry for distinct elements. It insists on one-way streets. If there's a link from $x$ to $y$ and also a link from $y$ to $x$, then it must be that $x$ and $y$ were the same element all along. The relation "is less than or equal to" ($\le$) is anti-symmetric. If $x \le y$ and $y \le x$, then we know $x=y$.

• ​​Transitivity​​: This is the property of shortcuts. If you can get from $x$ to $y$, and from $y$ to $z$, can you get directly from $x$ to $z$? "Is an ancestor of" is transitive. If your grandfather is an ancestor of your father, and your father is an ancestor of you, then your grandfather is an ancestor of you. "Is a friend of" is famously not transitive. A friend of your friend is not necessarily your friend. Formally: $\forall x, y, z \in A, ((xRy \land yRz) \implies xRz)$.

These properties are the building blocks for creating structured mathematical worlds like orders, hierarchies, and equivalence classes.

Now, here is where the real fun begins. What happens when we demand that a single relation obey more than one of these rules? Sometimes, the consequences are powerful and deeply surprising.

Consider a system of secure data links between processing nodes. Suppose the rules of the system demand two properties simultaneously:

1. ​​Symmetry​​: If there's a link from node $P_i$ to $P_j$, there must be a link back from $P_j$ to $P_i$.
2. ​​Anti-symmetry​​: If there are links in both directions between $P_i$ and $P_j$, they must be the same node ($i=j$).

At first glance, this seems like a contradiction. How can a connection be both a two-way street and a one-way street? Let's follow the logic. Suppose we try to establish a link between two distinct nodes, $P_i$ and $P_j$. The instant we create the link $(P_i, P_j)$, the symmetry rule forces us to also create the link $(P_j, P_i)$. But now we have links in both directions. The anti-symmetry rule looks at this situation and says, "Ah, but this is only allowed if $i=j$". This contradicts our starting assumption that the nodes were distinct! The logical conclusion is inescapable: no link can ever be established between two distinct nodes. The only links permitted are self-loops of the form $(P_i, P_i)$.

This is a fantastic result! Two simple, abstract rules, when combined, completely determine the structure of the entire network, forcing it into its simplest possible form. This same principle explains why a relation that is both an ​​equivalence relation​​ (reflexive, symmetric, transitive) and a ​​partial order​​ (reflexive, anti-symmetric, transitive) can only be the simple identity relation, where every element is related only to itself. The clash between symmetry and anti-symmetry annihilates all other connections.

Just as we have an algebra for numbers (add, subtract, multiply), we can define an algebra for relations. Since relations are just sets of pairs, we can immediately use standard set operations:

• ​​Union ($R \cup S$)​​: The set of pairs that are in $R$ or in $S$.
• ​​Intersection ($R \cap S$)​​: The set of pairs that are in both $R$ and $S$.

We can also define operations unique to relations:

• ​​Inverse ($R^{-1}$)​​: This simply reverses the direction of every connection. If $(a, b) \in R$, then $(b, a) \in R^{-1}$. If $R$ is the "parent of" relation, $R^{-1}$ is the "child of" relation. These operations often behave in very elegant ways. For example, it's a general truth that the inverse of an intersection is the same as the intersection of the inverses: $(R \cap S)^{-1} = R^{-1} \cap S^{-1}$.

• ​​Composition ($S \circ R$)​​: This is the most interesting operation. It represents chaining connections. A pair $(a, c)$ is in the composition $S \circ R$ if there is an intermediate stop, a 'stepping stone' $b$, such that you can get from $a$ to $b$ using $R$, and then from $b$ to $c$ using $S$. It's the relation of "friend of a friend" or "a flight connection". There's even an ​​identity relation​​, $I_A = \{(x,x) \mid x \in A\}$, which acts like the number 1 in multiplication: composing any relation $R$ with the identity leaves it unchanged.

These operations allow us to build complex new relations from simpler ones, just as we build complex formulas from numbers and operators.

This "algebra" of relations is powerful, but one must be careful. The properties of relations do not always behave as one might intuitively expect under these operations. It's a landscape full of beautiful patterns but also treacherous pitfalls.

For instance, if you take the union of two transitive relations, is the result still transitive? It seems plausible. But consider this simple counterexample on the set $\{1, 2, 3\}$. Let $R = \{(1, 2)\}$ and $S = \{(2, 3)\}$. Both $R$ and $S$ are trivially transitive (they don't have any "chains" to test). However, their union is $R \cup S = \{(1, 2), (2, 3)\}$. This new relation has the chain $1 \to 2 \to 3$, but it's missing the shortcut $(1, 3)$. Therefore, the union is not transitive.

What about composition? If you compose two symmetric relations, is the result symmetric? Again, this seems reasonable. If all your base connections are two-way streets, shouldn't any journey you build from them be reversible? The answer is no. Consider two symmetric relations on $\{a, b, c\}$: $R = \{(a, b), (b, a)\}$ and $S = \{(b, c), (c, b)\}$. In the composition $S \circ R$, we can go from $a$ to $b$ (via $R$) and then from $b$ to $c$ (via $S$), creating the composed link $(a, c)$. But is the reverse link, $(c, a)$, in our composition? To get from $c$ to $a$, we'd need to find a stepping stone $y$ such that $(c, y) \in R$ and $(y, a) \in S$. No such stepping stone exists in our example. So, $(a, c)$ is in the composition, but $(c, a)$ is not. The composition of two symmetric relations is not necessarily symmetric!

These examples show the subtlety of relations, but they also point toward a deeper, more unified structure. Let's look again at transitivity. What does it really mean in the language of our new algebra? The composition $R \circ R$, which we can write as $R^2$, represents all the two-step journeys you can take using only connections from $R$. The property of transitivity says that for any such two-step journey from $x$ to $z$, there must have already been a direct, one-step connection $(x, z)$ in the original relation $R$.

This means that every pair in the set of two-step journeys, $R^2$, must also be a pair in the set of one-step journeys, $R$. In the language of sets, this is simply: $R^2 \subseteq R$

This short, elegant statement is perfectly equivalent to the logical definition of transitivity. It unifies the property-based view (the $\forall x, y, z$ definition) with the operational view (composition). It reveals that transitivity is fundamentally a statement about how a relation behaves when composed with itself. This is the kind of profound and beautiful unity that mathematicians strive for—finding a single, powerful idea that illuminates a concept from multiple angles at once. The simple notion of a "set of pairs" unfolds into a rich and complex world, governed by elegant rules and filled with surprising discoveries.

Having acquainted ourselves with the formal machinery of binary relations—their definitions, properties, and operations—we can now turn to the far more exhilarating question: What are they for? It is one thing to assemble the gears and levers of a new mathematical idea, and quite another to see the marvelous engines it can build. You might suspect that such an abstract concept is a mere curiosity, a plaything for logicians. But nothing could be further from the truth. The binary relation is one of the most powerful and unifying ideas in all of science. It is the fundamental grammar we use to describe connections, structure, and order in the world. It is the language in which the scripts of computation, the laws of logic, and even the architecture of mathematics itself are written.

Our journey through its applications will begin with the most tangible and direct uses and climb towards vistas of breathtaking abstraction, revealing at each stage how this single, simple idea provides a common thread weaving through disparate fields.

At its heart, a binary relation is a way to talk about how things are connected. Think of a social network. The statement "Alice follows Bob" can be captured by an ordered pair, $(Alice, Bob)$. The entire "follows" network is simply a vast collection of such pairs—a binary relation on the set of all users. This is not just a change in terminology; it is a profound shift in perspective. By modeling the network as a formal relation, we can now use the precise and powerful tools of logic to ask questions about it.

For instance, a database administrator might need to verify that a newly provisioned network is empty, with no connections at all. In the language of logic, this question becomes a crisp, unambiguous sentence. If we denote the "follows" relation by $E$, the condition "no one follows anyone" is expressed as $\forall x \forall y (\neg E(x, y))$. This sentence asserts that for any two users $x$ and $y$, it is not the case that $x$ follows $y$. This is logically equivalent to stating that there does not exist any pair $(x,y)$ such that $E(x,y)$ holds: $\neg(\exists x \exists y E(x, y))$. What was an informal requirement is now a formal query that a computer can check. This translation of real-world properties into logical sentences about relations is the bedrock of database theory and automated verification.

This descriptive power goes much deeper. We can use relations as a kind of primordial clay from which we sculpt more specialized mathematical objects. Consider the familiar concept of a function. What is a function, really? It is a rule that assigns to each input a unique output. But this "rule" can be perfectly described as a special kind of binary relation. If a relation $F$ is to represent a function on a domain $D$, it must satisfy two conditions: totality (every element in $D$ has an output) and single-valuedness (no element in $D$ has more than one output). We can write these conditions down in first-order logic, effectively creating a "function-ness" filter that a relation must pass through. A function, in this light, is not a fundamentally new entity, but simply a binary relation that happens to be well-behaved in a particular way.

We can even perform a kind of "algebra" on relations themselves, combining them to produce new ones. Let's take the relations "less than" ($<$) and "less than or equal to" ($\le$) on the real numbers. Both are subsets of $\mathbb{R} \times \mathbb{R}$. What happens if we take the set difference; that is, if we take all the pairs in the $\le$ relation and remove the ones that are also in the $<$ relation? The pairs $(x,y)$ for which $x < y$ are removed. The only pairs left are those where $x \le y$ is true but $x < y$ is false. The only possibility is, of course, $x=y$. The resulting relation is nothing other than the equality relation, $=$. This elegant result shows that relations are not static descriptions but dynamic objects that can be manipulated, revealing the hidden connections between fundamental mathematical ideas.

The role of binary relations in computer science extends far beyond databases. They form the very scaffolding upon which our understanding of computation and complexity is built. Many of the most famous problems in computer science—problems that are easy to state but fiendishly hard to solve—are fundamentally questions about the existence of certain relational structures within a given graph or system.

A wonderful illustration comes from Fagin's Theorem, a landmark result connecting logic and computation. In simple terms, the theorem states that a problem is in the complexity class NP (the set of problems whose solutions can be verified quickly) if and only if it can be described by a sentence in a logical language called Existential Second-Order Logic ($\Sigma_1^1$). Such a sentence has the form: "There exists a relation $R$ such that... [some first-order property] holds." The computational problem of finding a solution corresponds to the logical problem of finding a witness relation $R$.

Let's compare two famous NP-complete problems: 3-Colorability and Hamiltonian Cycle.

• ​​3-Colorability​​ asks: Can we color the vertices of a graph with three colors such that no two adjacent vertices share the same color? To express this in logic, we can say: "There exist three sets of vertices, $C_1, C_2, C_3$, such that they form a partition of all vertices and no edge connects two vertices within the same set." A set is just a unary relation. We are essentially tagging each vertex with a color property.
• ​​Hamiltonian Cycle​​ asks: Is there a path in the graph that visits every vertex exactly once and returns to the start? A solution to this is not a set of tags on the vertices; it is a global structure, an ordering of all the vertices. To describe this, we need more than just sets. We need to say: "There exists a binary relation $S$ that acts as a 'successor' function, linking each vertex to the next one in the cycle...".

This distinction is profound. The nature of the computational problem is mirrored in the logical tools needed to describe it. Problems about assigning properties to individual objects can often be handled by quantifying over sets (unary relations). But problems about imposing a global order, a path, or a sequence require us to quantify over a full-blown binary relation. The arity of the relation—whether it connects one object to a property or two objects to each other—marks a fundamental jump in descriptive complexity.

We have seen relations as a language for describing external structures. But in a beautiful turn of self-reference, mathematicians also study the universe of relations itself, discovering that this universe possesses its own rich and elegant architecture.

Let's start by thinking about relations probabilistically. On a set of, say, three elements, there are $2^{3 \times 3} = 512$ possible binary relations. What is the probability that if we pick one at random, it has some nice property, like being symmetric or reflexive? These are not just whimsical questions; they open the door to the probabilistic method in combinatorics. We can calculate, for instance, that if we know a relation is symmetric, the probability of it also being reflexive is precisely $\frac{1}{8}$ on a 3-element set. The number of possible equivalence relations on a set is given by the famous Bell numbers, connecting the study of relations to a deep vein of combinatorial mathematics. The set of all equivalence relations on the infinite set of natural numbers is itself uncountably infinite, having the same cardinality as the real numbers—a truly mind-boggling result.

The structure becomes even clearer when we equip these collections of relations with operations. Consider the set of all binary relations on a set $S$. If we take relation composition as our operation, this system forms a monoid. This is an algebraic structure with an associative operation (composition is associative) and an identity element—the simple equality relation $I = \{(x,x) \mid x \in S\}$. This is a stunning piece of unity: the relations we use to describe other things are themselves the elements of a classical algebraic object.

The structure is even more refined if we focus only on equivalence relations. Ordered by refinement (i.e., set inclusion), the set of all equivalence relations on a set $X$ forms a lattice. This means that for any two equivalence relations $E$ and $F$, there is always a unique greatest lower bound (their "meet," which is simply their intersection $E \cap F$) and a unique least upper bound (their "join," which is the transitive closure of their union). The world of equivalence relations is not a chaotic jumble; it is an orderly, crystalline structure, a lattice.

Perhaps the most dramatic application of a simple relational structure lies at the foundations of modern analysis. To prove that every Hilbert space (a type of infinite-dimensional vector space) has an orthonormal basis, one typically invokes a powerful axiom of set theory called Zorn's Lemma. The lemma applies to partially ordered sets. The entire, formidable proof is set in motion by a remarkably simple first step: one defines a collection $\mathcal{S}$ of all orthonormal subsets of the space, and then defines a binary relation on $\mathcal{S}$ by simple set inclusion, $A \preceq B$ if and only if $A \subseteq B$. This relation $\preceq$ is a partial order, and it is this humble structure that allows the great engine of Zorn's Lemma to turn, ultimately yielding one of the cornerstone theorems of functional analysis.

From describing social networks to underpinning the theory of computation and structuring the very foundations of abstract mathematics, the binary relation reveals itself not as a niche topic, but as a central, unifying concept. It is a testament to the power of abstraction—the art of seeing the common pattern of "connectedness" that runs through nearly every intellectual landscape we seek to explore.