Equivalence Relations

In science and mathematics, a fundamental task is to classify objects—to sort a complex universe into meaningful groups by asking, "Which of these are fundamentally the same?" An equivalence relation provides the precise, formal language for this task, acting as the grammar of "sameness." It addresses the core challenge of abstracting away irrelevant details to reveal deeper underlying structures. This article explores this powerful concept in two main parts. First, under "Principles and Mechanisms," we will dissect the three simple rules that define an equivalence relation—reflexivity, symmetry, and transitivity—and uncover the profound connection between these rules and the partitioning of a set into distinct classes. Following this, the "Applications and Interdisciplinary Connections" chapter will demonstrate how this abstract tool is used to build new mathematical worlds in topology and algebra, and to map complex landscapes in fields like graph theory, turning tangled networks into clear, structured diagrams.

At its heart, much of science and mathematics is about classification. We look at a bewildering universe of objects—stars, animals, numbers, shapes—and we try to sort them into meaningful groups. We ask, "Which of these are fundamentally the same?" An ​​equivalence relation​​ is the physicist's and mathematician's precise and powerful tool for answering this question. It is the grammar of "sameness."

Imagine you have a giant box of LEGO bricks of all different shapes, sizes, and colors. Your first instinct might be to sort them. You decide that two bricks are "the same" if they have the same color. What are the rules of this game of "sameness"? You might not think about it, but you're implicitly using three fundamental principles.

1. ​​Reflexivity:​​ Any brick is the same color as itself. This sounds laughably obvious, but in logic, we must build from the ground up. For any element $a$, we must have $a \sim a$, where the tilde symbol $\sim$ means "is equivalent to."

2. ​​Symmetry:​​ If brick A is the same color as brick B, then brick B is the same color as brick A. The relationship is mutual. If $a \sim b$, then it must be that $b \sim a$.

3. ​​Transitivity:​​ This is the most powerful rule. If brick A is the same color as brick B, and brick B is the same color as brick C, then brick A must be the same color as brick C. This creates a chain of "sameness." If $a \sim b$ and $b \sim c$, then it must follow that $a \sim c$.

Any relationship that obeys these three rules—reflexivity, symmetry, and transitivity—is called an ​​equivalence relation​​. These aren't just arbitrary rules; they are the very definition of what it means for a comparison to be consistent. If a "sameness" rule violates any of these, our sorting attempt would descend into chaos.

Here is where the magic happens. Any time you define a valid equivalence relation on a set of objects, you automatically chop that set up into a collection of neat, non-overlapping bins. Each bin contains all the items that are "the same" as each other. This collection of bins is called a ​​partition​​, and each individual bin is an ​​equivalence class​​.

Let's see this in action with numbers. Consider the set of all integers, $\mathbb{Z}$. Let's invent a rule: two integers $x$ and $y$ are equivalent, written $x \sim y$, if their squares leave the same remainder when divided by 5. That is, $x^2 \equiv y^2 \pmod{5}$. Let's test some numbers:

• $1^2 = 1$, and $4^2 = 16$, which has a remainder of 1 when divided by 5. So, $1 \sim 4$.
• $2^2 = 4$, and $3^2 = 9$, which has a remainder of 4 when divided by 5. So, $2 \sim 3$.
• $5^2 = 25$, which has a remainder of 0. So does $0^2$. So, $0 \sim 5$.

If we continue this, we find that every integer falls into one of exactly three bins based on the value of its square modulo 5:

• ​​Class 1 (squares are $\equiv 0 \pmod 5$):​​ $\{..., -5, 0, 5, 10, ...\}$ — all multiples of 5.
• ​​Class 2 (squares are $\equiv 1 \pmod 5$):​​ $\{..., -4, -1, 1, 4, 6, 9, ...\}$ — all numbers ending in 1, 4, 6, or 9.
• ​​Class 3 (squares are $\equiv 4 \pmod 5$):​​ $\{..., -3, -2, 2, 3, 7, 8, ...\}$ — all numbers ending in 2, 3, 7, or 8.

These three sets form a partition of all integers. Every integer belongs to exactly one of these classes. Notice how the three simple rules of an equivalence relation guarantee this perfect division. The most crucial property, which arises from transitivity and symmetry, is that ​​two equivalence classes are either completely separate (disjoint) or they are the exact same set​​. There is no "partial overlap." If two bins of your sorted LEGOs share even one brick, it implies they must actually be the same bin! For instance, if we had two proposed classes $\{v, w, z\}$ and $\{w, x, z\}$, their overlap on $w$ and $z$ would, by transitivity, force $v$ and $x$ to be related, collapsing the two distinct classes into one—a contradiction unless they were identical to begin with.

This leads to one of the most beautiful ideas in the subject: an equivalence relation and a partition are not just related; they are two different ways of describing the exact same underlying structure.

• Every equivalence relation gives you a partition (its equivalence classes).
• Every partition gives you an equivalence relation (the rule "are in the same block of the partition").

This is a perfect one-to-one correspondence, a ​​bijection​​ in mathematical terms. Thinking about partitions gives us a powerful combinatorial handle on equivalence relations. For instance, to find all possible equivalence relations on a tiny set like $\{1, 2, 3\}$, we just need to find all the ways to partition it:

1. Put all three elements in one box: $\{\{1, 2, 3\}\}$. (1 way)
2. Put two in one box and one in another: $\{\{1, 2\}, \{3\}\}$, $\{\{1, 3\}, \{2\}\}$, $\{\{2, 3\}, \{1\}\}$. (3 ways)
3. Put each in its own box: $\{\{1\}, \{2\}, \{3\}\}$. (1 way)

Adding these up, we find there are $1+3+1=5$ possible partitions, and therefore exactly 5 distinct equivalence relations on a set of three elements.

What happens when we have more than one way to sort a set? Can we combine them? This question leads us to a fascinating "algebra" of relations. Let's say we have two equivalence relations, $R_1$ and $R_2$, on the same set.

The Meet: A More Refined View

Suppose we have two relations on the integers from 0 to 8: $R_1$ relates numbers if they have the same parity ($a \equiv b \pmod{2}$), and $R_2$ relates them if they have the same remainder modulo 3 ($a \equiv b \pmod{3}$). What if we define a new relation, $R$, where two numbers are related only if they are related under both $R_1$ and $R_2$? This is the ​​intersection​​ of the relations, $R = R_1 \cap R_2$.

It turns out that the intersection of two equivalence relations is always a new, perfectly valid equivalence relation. In our example, $a \sim b$ means $a \equiv b \pmod{2}$ AND $a \equiv b \pmod{3}$. By the Chinese Remainder Theorem, this is equivalent to $a \equiv b \pmod{6}$. The new partition is a refinement of the original two; each of its classes is a subset of a class from $R_1$ and a class from $R_2$. This operation is called the ​​meet​​ of the relations.

The Join: A Coarser View

What about the "or" case? What if we try to relate two elements if they are related by $R_1$ or $R_2$? This is the ​​union​​ of the relations, $R_1 \cup R_2$. Here, we run into a problem. The union is reflexive and symmetric, but it often fails to be transitive. Consider the set $\{1, 2, 3\}$. Let $R_1$ relate 1 and 2, and $R_2$ relate 2 and 3. In the union, we have $1 \sim 2$ and $2 \sim 3$. For transitivity, we would need $1 \sim 3$, but the union itself doesn't guarantee that.

To fix this, we must create the ​​transitive closure​​ of the union. We take the union and keep adding pairs by following chains: if $a \sim b$ and $b \sim c$, we must add the pair $(a,c)$. We continue this "friend-of-a-friend" process until no more pairs can be added. The result is the smallest possible equivalence relation that contains both $R_1$ and $R_2$. This is called the ​​join​​ of the two relations.

A stunning example of this is seen when we join the relation "congruence modulo 6" with "congruence modulo 9" on a set of integers. The process of chaining these relations together merges classes until we are left with a partition corresponding to "congruence modulo $\gcd(6,9)=3$". Similarly, if we define an equivalence relation on the integer grid $\mathbb{Z}^2$ by allowing "steps" of $(3, 5)$ and $(2, -1)$, the join operation tells us exactly which points are mutually reachable, partitioning the entire plane into a finite number of classes.

The existence of these meet and join operations for any pair of equivalence relations means that the set of all possible partitions on a set forms an elegant mathematical structure called a ​​lattice​​. This provides a powerful framework for understanding how different ways of classifying the world relate to one another, moving from finer to coarser perspectives and back again, all governed by the simple, beautiful rules of "sameness."

Now that we've grappled with the formal machinery of equivalence relations—the reflexivity, symmetry, and transitivity that define them—you might be left with a nagging question: "So what?" It is a fair question. In science, as in life, we are less interested in definitions for their own sake and more interested in what they do. What doors do they unlock? What new worlds do they allow us to see?

The true power of an equivalence relation is not in its definition, but in its use as one of the most fundamental tools of abstraction in all of mathematics and science. It is a universal lens for simplifying complexity. It allows us to take a sprawling, bewilderingly detailed set of objects, decide on a criterion for what makes two of them "the same" for our purposes, and then collapse all the members of each group into a single, new conceptual entity. By ignoring irrelevant differences, we can reveal a deeper, simpler, and often more profound structure underneath. In this chapter, we will embark on a journey to see this principle at work, from building new geometric shapes to mapping the very limits of measurement itself.

Perhaps the most intuitive way to understand this constructive power is to do some building ourselves. Imagine you have a flat, square sheet of paper, which we can think of as the set of points $(x,y)$ where both $x$ and $y$ run from 0 to 1. How could you turn this into a cylinder? The answer lies in declaring certain points to be "the same." We define an equivalence relation: two points are equivalent if they have the same height ($y_1=y_2$) and are on opposite vertical edges ($x_1=0, x_2=1$) or if they are the very same point. All the points in the middle of the square are only equivalent to themselves. This act of "gluing" the left edge to the right edge by identifying pairs of points $\{(0, y), (1, y)\}$ for every height $y$ transforms the square into a cylinder. We have built a new object, the quotient space, not by physical manipulation, but by a simple act of definition. This very same idea allows topologists to construct a menagerie of fascinating objects—a torus (a donut) by gluing both pairs of opposite edges of a square, a Möbius strip by gluing one pair with a twist, and even more exotic spaces that are impossible to build in our three-dimensional world but are perfectly well-defined mathematically.

This "gluing" is not just for geometry. It is one of the most powerful construction methods in abstract algebra. Consider a group $G$, which is a set with a well-behaved notion of multiplication (like the integers with addition, or rotations of a square). Now, pick a subgroup $H$ inside it. We can ask a natural question: when should we consider two elements $a$ and $b$ of the larger group $G$ to be "the same" from the perspective of the subgroup $H$? A brilliant answer is to say $a \sim b$ if you can get from $a$ to $b$ by multiplying by something from $H$. More precisely, the relation is defined by $a \sim b$ if and only if $a^{-1}b \in H$. This is a bona fide equivalence relation, and its equivalence classes are the famous cosets of $H$. The revolutionary step is to treat these entire cosets as single elements in a new, smaller group called a quotient group. This process of forming quotient groups is central to understanding the structure of all groups and is a cornerstone of modern algebra.

Beyond building new things, equivalence relations are an unparalleled tool for classification—for drawing maps of complex systems. Think of a directed graph, like a map of one-way streets in a city, the hyperlink structure of the internet, or a social network showing who follows whom. A crucial question is: which parts of the network are truly interconnected? We can define an equivalence relation: two nodes $u$ and $v$ are equivalent if you can travel from $u$ to $v$ and you can travel from $v$ back to $u$.

The equivalence classes that emerge from this relation are called the strongly connected components of the graph. Each component is an "island" of mutual reachability. Within an island, you can get from any point to any other point. But if you leave an island for another, you might not be able to get back. This partitioning is immensely practical. Search engines use it to analyze the web, logisticians use it to understand supply chains, and social scientists use it to identify cohesive communities. By declaring "mutual reachability" as our standard for sameness, we transform a tangled mess of arrows into a clear map of distinct, meaningful regions.

The landscapes we map need not be so concrete. Consider the vast, abstract space of all possible bounded functions on an interval, say $[0, 1]$. Some of these functions are smooth and continuous, others are wild and jumpy. How can we bring order to this chaos? One way is to classify them by their "bad behavior." Let's define two functions $f$ and $g$ to be equivalent if their set of discontinuities is exactly the same. This groups together all functions that are "pathological" in the same places. A function that is discontinuous only at $x = \frac{1}{2}$ is in a different class from one that is discontinuous at every rational number. The question then becomes: how many such classes are there? The answer, which requires a deep dive into real analysis, is astonishing. The number of different possible sets of discontinuities—and therefore the number of equivalence classes—is the cardinality of the continuum, $\mathfrak{c}$. There are just as many "types" of discontinuous behavior as there are real numbers. This is a profound insight into the structure of function space, revealed by the simple act of defining an equivalence relation.

Equivalence relations are so powerful that they can take us to the very frontiers of mathematical thought, revealing both startling truths and subtle dangers. One of the most famous and mind-bending results of the 20th century is the existence of non-measurable sets, and equivalence relations are at the heart of the story.

To have a "measure" is to have a consistent way to assign a "size" (length, area, volume) to sets. We expect this measure to have certain properties, like the size of a set not changing if we shift it around (translation invariance). The Vitali set construction begins by defining an equivalence relation on the numbers in $[0, 1)$: $x \sim y$ if their difference $x-y$ is a rational number. This partitions the interval into a vast number of dense, interwoven classes. Using the (controversial) Axiom of Choice, we construct a new set, $V$, by picking exactly one member from each class. The shocking result is that this set $V$ cannot be assigned a Lebesgue measure. If its measure were zero, then countable translated copies of it (which should cover the whole interval) would still have measure zero. If its measure were positive, then a finite number of disjoint translated copies would have a total measure greater than the interval they are inside. Both are contradictions. A similar construction, based on rotating points on a circle by irrational amounts, also produces a non-measurable set. The key insight is that the group of transformations defining the equivalence relation (rational translations vs. a cyclic group of irrational rotations) gives the constructions slightly different flavors, but the core idea is the same: partition a space so cleverly that our intuition about "size" breaks down.

This power to reshape spaces, however, comes with a warning. Just because we start with a "nice" space doesn't mean our new quotient space will be equally well-behaved. Consider the "line with two origins." We start with two separate copies of the real number line—a perfectly nice, Hausdorff space (meaning any two distinct points can be separated by disjoint open "bubbles"). We then define an equivalence relation that identifies every point $x$ on the first line with the corresponding point $x$ on the second line, except for the origin, 0. The result is a new space that is like a single line, but with two distinct origins that are infinitesimally close. In this bizarre new space, the two origins are distinct points, yet any open bubble you draw around one will inevitably overlap with any open bubble you draw around the other. They cannot be separated. The space is not Hausdorff. This cautionary tale teaches us that the process of abstraction is not magic; by gluing things together, we can lose crucial properties.

From the simple cylinder to the structure of groups, from analyzing the internet to confronting the paradoxes of measure, the concept of an equivalence relation is a golden thread running through the fabric of mathematics. It is the formal embodiment of the simple, powerful question, "What do we mean by 'the same'?" By choosing our answer, we choose the world we wish to study.