Equivalence relations and partitions

The idea that mathematical objects can be grouped by shared properties is far older than the formal language of set theory. Ancient Greek mathematicians implicitly partitioned integers into even and odd, while Gauss's 1801 Disquisitiones Arithmeticae built the entire theory of modular arithmetic on the notion that two integers are 'alike' when they leave the same remainder upon division. Yet the abstract framework that unifies all such constructions—equivalence relations and their corresponding partitions—crystallized only in the late nineteenth and early twentieth centuries as set theory matured.

The central question that equivalence relations address is deceptively simple: given a set of objects, how can we rigorously define what it means for two objects to be 'the same in some respect,' and how does such a definition automatically slice the set into non-overlapping groups? Understanding this correspondence is essential not only for algebra and number theory but also for computer science (e.g., type checking and union-find data structures), logic, and combinatorics.

An equivalence relation on a set S is a binary relation ∼ ⊆ S × S that satisfies three axioms, each of which mirrors a basic intuition about what 'sameness' should mean. Together, these axioms guarantee that ∼ behaves like equality in the relevant respect, even though the objects being related may differ in other ways. Meanwhile, a partition of S is a collection of non-empty, pairwise disjoint subsets whose union equals S. The deep insight is that these two notions—an algebraic property of a relation and a set-theoretic decomposition—are two perspectives on exactly the same structure.

The following diagram illustrates the correspondence between an equivalence relation on a six-element set S = {1, 2, 3, 4, 5, 6} and the partition it induces. On the left, the relation is depicted as a directed graph (with bidirectional arrows representing symmetry and self-loops representing reflexivity). On the right, the same set is shown decomposed into three equivalence classes, visually confirming that the classes are disjoint and exhaustive.

Observe several critical features in the diagram. First, every node has a self-loop, confirming reflexivity. Second, every edge is bidirectional, reflecting symmetry. Third, within the violet cluster, the edges among 2, 5, and 6 form a complete subgraph (a clique), which is exactly the graphical signature of transitivity. In fact, the connected components of the relation graph (ignoring self-loops) correspond precisely to the blocks of the partition on the right. This is no coincidence; it is a consequence of the fundamental theorem that we will state formally in Section 4.

We now state the three axioms formally and develop the key theorem that equivalence relations and partitions are two sides of the same coin. Let S be a non-empty set and let ∼ be a binary relation on S, i.e., a subset of S × S.

The Fundamental Theorem

The Fundamental Theorem of Equivalence Relations establishes a bijection between equivalence relations on S and partitions of S. Specifically, if ∼ is an equivalence relation on S, then the set of equivalence classes S/∼ = {[a] : a ∈ S} is a partition of S. Conversely, if 𝒫 = {A_i} is a partition of S, then the relation defined by a ∼ b if and only if a and b belong to the same block A_i is an equivalence relation on S. Moreover, these two constructions are inverses of each other.

The most classical example of an equivalence relation is congruence modulo n, defined on the integers ℤ. For a fixed positive integer n, we say a ≡ b (mod n) if and only if n divides (a − b). This relation satisfies all three axioms: reflexivity (n | 0), symmetry (if n | (a − b) then n | (b − a)), and transitivity (if n | (a − b) and n | (b − c), then n | (a − c) by adding). The equivalence classes are the residue classes [0], [1], …, [n − 1], and they form the partition of ℤ into n infinite subsets. Below, we visualize the partition of integers under congruence modulo 3.

This example generalizes broadly. Any time you encounter a mathematical construction that groups objects by a shared feature—triangles by similarity, matrices by rank, integers by divisibility pattern—you are almost certainly looking at an equivalence relation in disguise. The partition perspective is equally useful: it tells you that the number of distinct 'types' under a given classification equals the number of equivalence classes, a quantity often denoted |S/∼| and called the index of the equivalence relation.

Let S = {a, b, c, d, e} and define the relation R = {(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (b,a), (d,e), (e,d)}. Determine whether R is an equivalence relation, and if so, find the equivalence classes and the corresponding partition.

Equivalence relations occupy a specific niche among binary relations. Students often confuse them with partial orders or with relations that satisfy only two of the three axioms. The following table contrasts equivalence relations with several common relation types to clarify where they differ and what structural consequences follow.

A crucial distinction is that partial orders use antisymmetry (if a ≤ b and b ≤ a then a = b) in place of symmetry. This makes partial orders suitable for hierarchical structures such as divisibility on the natural numbers or subset inclusion on a power set, whereas equivalence relations model flat, non-hierarchical groupings. Meanwhile, a preorder is reflexive and transitive but neither symmetric nor antisymmetric in general. Interestingly, every preorder naturally induces an equivalence relation—define a ∼ b when both a ≤ b and b ≤ a—and the quotient set under this equivalence becomes a partial order.

Equivalence relations and partitions serve as the launching point for several deep ideas in abstract algebra, topology, and theoretical computer science. The quotient set S/∼ is not merely a collection of subsets; when S carries algebraic structure (group, ring, vector space), the quotient often inherits that structure, yielding quotient groups, quotient rings, and quotient spaces. This construction is formalized through the notion of a congruence relation—an equivalence relation that is also compatible with the algebraic operations.

In computer science, the union-find (disjoint-set) data structure maintains a partition of a finite set under two operations: find(x) returns the representative of the equivalence class containing x, and union(x, y) merges the classes of x and y. With path compression and union by rank, this structure supports nearly-constant-time operations, making it indispensable in algorithms for minimum spanning trees (Kruskal's algorithm), connected components in graphs, and DFA minimization. Mastering the equivalence-relation/partition duality gives you the conceptual foundation for all of these applications.