# Equivalence Relation Consider the fraction $\frac{2}{4}$. Any student of arithmetic will insist that $\frac{2}{4}$ and $\frac{1}{2}$ are "the same number," yet the two expressions are plainly different as pairs of integers. The passage from the pair $(2, 4)$ to the rational number $\frac{1}{2}$ requires a precise notion of when two representations should be regarded as interchangeable. The same tension arises throughout mathematics: two $n \times n$ matrices $A$ and $B$ may describe the same [linear map](/page/Linear%20Map) in different bases, two integers may leave the same remainder upon division by $7$, two [continuous](/page/Continuity) paths may be deformable into one another. In each case, we have a collection of objects, a criterion for when two of them should be treated as identical for a given purpose, and a need to pass from the original collection to a smaller one in which redundant copies have been collapsed. The equivalence relation is the abstraction that makes all of this precise. [motivation] ### The problem of redundant representations Mathematics is full of situations where distinct objects encode the same information. The integers $3$ and $10$ are different, but modulo $7$ they behave identically: they leave the same remainder, and any arithmetic statement about remainders that holds for one holds for the other. The matrices \begin{align*} A = \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}, \qquad B = \begin{pmatrix} 5 & -4 \\ 4 & -2 \end{pmatrix} \end{align*} are different as arrays of numbers, but they represent the same linear transformation in different bases ($B$ has eigenvalues $1$ and $2$ as well). The pairs $(1, 2)$ and $(3, 6)$ in $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ are different, but both represent the rational number $\frac{1}{2}$. In each example, we want to declare certain distinct objects to be "equivalent" and then work with the resulting collapsed collection. ### Ad hoc identification fails Without a unifying framework, each branch of mathematics must independently invent its own procedure for collapsing redundant representations. Number theorists define congruence classes. Linear algebraists define similarity classes. Topologists define homotopy classes. Each time, the same pattern appears: define a relation, verify that it behaves well (in particular, that "equivalent to equivalent" remains equivalent), form the collection of classes, and check that operations on the original objects descend to operations on classes. The logical structure is identical in every case, which suggests that a single definition should capture all of them. ### Three properties, one definition What properties must a relation $\sim$ on a set $X$ satisfy for "collapsing $X$ by $\sim$" to be sensible? First, every object should be equivalent to itself, since no representation should be excluded from its own equivalence class --- this is reflexivity. Second, if $a$ is equivalent to $b$, then $b$ should be equivalent to $a$, since equivalence is a symmetric notion --- this is symmetry. Third, if $a$ is equivalent to $b$ and $b$ is equivalent to $c$, then $a$ should be equivalent to $c$, since chains of equivalences should not break --- this is transitivity. These three conditions turn out to be exactly the right axioms. Any relation satisfying all three induces a clean decomposition of $X$ into non-overlapping classes, and conversely, any such decomposition arises from a unique equivalence relation. This is the content of the fundamental correspondence between equivalence relations and partitions. [/motivation] ## Relations on a Set Before defining equivalence relations, we fix the language of relations. A **relation** on a set $X$ is a subset $R \subseteq X \times X$. We write $x \mathrel{R} y$ to mean $(x, y) \in R$. Three properties of relations will be central. A relation $R$ on $X$ is called **reflexive** if $x \mathrel{R} x$ for every $x \in X$. It is called **symmetric** if $x \mathrel{R} y$ implies $y \mathrel{R} x$ for all $x, y \in X$. It is called **transitive** if $x \mathrel{R} y$ and $y \mathrel{R} z$ together imply $x \mathrel{R} z$ for all $x, y, z \in X$. It is worth pausing to compare these axioms with those of a partial order. A partial order on $X$ is a relation that is reflexive, **antisymmetric** ($x \mathrel{R} y$ and $y \mathrel{R} x$ imply $x = y$), and transitive. The axioms share reflexivity and transitivity, but diverge at the second condition: symmetry declares that the relation cannot distinguish between $x$ and $y$, while antisymmetry declares that it can always distinguish them (unless they are equal). Equivalence relations and partial orders are, in a sense, opposite responses to the same structural question. ## Formal Definition [definition:Equivalence Relation] Let $X$ be a set. An **equivalence relation** on $X$ is a relation $\sim \;\subseteq X \times X$ satisfying: 1. **Reflexivity.** For every $x \in X$, $x \sim x$. 2. **Symmetry.** For all $x, y \in X$, if $x \sim y$ then $y \sim x$. 3. **Transitivity.** For all $x, y, z \in X$, if $x \sim y$ and $y \sim z$, then $x \sim z$. [/definition] The notation $x \sim y$ is read "$x$ is equivalent to $y$." When multiple equivalence relations are in play, we write $x \sim_R y$ or $x \equiv y \pmod{R}$ to distinguish them. [example:Congruence Modulo N] Fix a positive integer $n \geq 1$. Define a relation $\equiv_n$ on $\mathbb{Z}$ by declaring $a \equiv_n b$ if and only if $n \mid (a - b)$, that is, $a - b = kn$ for some $k \in \mathbb{Z}$. **Reflexivity.** For any $a \in \mathbb{Z}$, $a - a = 0 = 0 \cdot n$, so $n \mid (a - a)$. **Symmetry.** If $a - b = kn$, then $b - a = (-k)n$, so $n \mid (b - a)$. **Transitivity.** If $a - b = kn$ and $b - c = \ell n$, then $a - c = (a - b) + (b - c) = (k + \ell)n$, so $n \mid (a - c)$. Therefore $\equiv_n$ is an equivalence relation on $\mathbb{Z}$. The equivalence classes are the residue classes $[0], [1], \ldots, [n-1]$, where $[r] = \{r + kn : k \in \mathbb{Z}\}$. [/example] [example:Equality Is An Equivalence Relation] On any set $X$, the **equality** relation $=$ (formally, the diagonal $\Delta_X = \{(x, x) : x \in X\} \subseteq X \times X$) is an equivalence relation. Reflexivity, symmetry, and transitivity of equality are axioms of first-order logic. Each equivalence class is a singleton: $[x] = \{x\}$. This is the finest possible equivalence relation on $X$ --- it identifies no distinct elements. At the other extreme, the **total** relation $X \times X$ is also an equivalence relation (every element is equivalent to every other). It has a single equivalence class, namely $X$ itself. This is the coarsest possible equivalence relation on $X$. [/example] ## Equivalence Classes and Partitions Given an equivalence relation $\sim$ on a set $X$ and an element $x \in X$, the **equivalence class** of $x$ is the set of all elements equivalent to $x$. [definition:Equivalence Class] Let $\sim$ be an equivalence relation on a set $X$ and let $x \in X$. The **equivalence class** of $x$ is \begin{align*} [x] = \{y \in X : x \sim y\}. \end{align*} [/definition] By reflexivity, $x \in [x]$, so every equivalence class is nonempty. The equivalence classes interact in a particularly rigid way: any two classes are either identical or disjoint. There is no possibility of partial overlap. This rigidity is what makes the entire theory work, and it is precisely the content of the next definition and theorem. [definition:Partition] Let $X$ be a set. A **partition** of $X$ is a collection $\mathcal{P} = \{P_i\}_{i \in I}$ of nonempty subsets of $X$ (called **parts** or **blocks**) such that: 1. **Covering.** $\displaystyle X = \bigcup_{i \in I} P_i$. 2. **Disjointness.** For all $i, j \in I$ with $i \neq j$, $P_i \cap P_j = \varnothing$. [/definition] Equivalently, every element of $X$ belongs to exactly one block of $\mathcal{P}$. Partitions arise naturally whenever we sort objects into non-overlapping categories: students into tutorial [groups](/page/Group), integers into residue classes, points of the plane into horizontal lines. The following theorem is the central result of this article. It establishes that equivalence relations and partitions are two descriptions of the same mathematical structure --- one algebraic (a relation satisfying axioms), one geometric (a decomposition into disjoint pieces). [quotetheorem:762] The power of this correspondence lies in its being a genuine bijection. Start with an equivalence relation $\sim$ on $X$. The equivalence classes $\{[x] : x \in X\}$ form a partition $\mathcal{P}_\sim$ of $X$ (the classes cover $X$ by reflexivity, and they are disjoint by the overlapping-classes argument: if $z \in [x] \cap [y]$, then $z \sim x$ and $z \sim y$, so $x \sim y$ by symmetry and transitivity, which forces $[x] = [y]$). Now start with a partition $\mathcal{P}$ and define the relation $\sim_\mathcal{P}$ by declaring $a \sim_\mathcal{P} b$ if and only if $a$ and $b$ belong to the same block. This relation is an equivalence relation. The two constructions are inverse: $\mathcal{P}_{\sim_\mathcal{P}} = \mathcal{P}$ and ${\sim_{\mathcal{P}_\sim}} = {\sim}$. There is no loss of information in either direction. This result is the structural analogue of a phenomenon that reappears throughout algebra. In group theory, the cosets of a subgroup partition the group; in topology, the fibres of a continuous surjection partition the domain. ## The Quotient Set and Canonical Projection Once we know that the equivalence classes of $\sim$ form a partition of $X$, we can form a new set whose elements are the classes themselves. [definition:Quotient Set] Let $\sim$ be an equivalence relation on a set $X$. The **quotient set** (or **quotient** of $X$ by $\sim$) is \begin{align*} X/{\sim} \;=\; \{[x] : x \in X\}, \end{align*} the set of all equivalence classes of $\sim$. [/definition] The quotient set comes equipped with a natural map. [definition:Canonical Projection] The **canonical projection** (or **quotient map**) is the surjection \begin{align*} \pi : X &\to X/{\sim} \\ x &\mapsto [x]. \end{align*} [/definition] The map $\pi$ is surjective by definition (every class $[x] \in X/{\sim}$ is the image of $x$), but it is generally not injective: $\pi(x) = \pi(y)$ precisely when $x \sim y$. The fibres of $\pi$ are the equivalence classes, so $\pi$ encodes the same information as the partition. The quotient map satisfies a universal property that governs how [functions](/page/Function) interact with equivalence relations. Suppose $f : X \to Y$ is a function that is **compatible** with $\sim$, meaning $x \sim y$ implies $f(x) = f(y)$. Then $f$ descends to a well-defined function on the quotient: [theorem:Universal Property Of The Quotient] Let $\sim$ be an equivalence relation on a set $X$ and let $f : X \to Y$ be a function satisfying $f(x) = f(y)$ whenever $x \sim y$. Then there exists a unique function $\bar{f} : X/{\sim} \to Y$ such that $f = \bar{f} \circ \pi$, where $\pi : X \to X/{\sim}$ is the canonical projection. Explicitly, $\bar{f}([x]) = f(x)$. [/theorem] [proof] **Well-definedness.** We must check that $\bar{f}$ does not depend on the choice of representative. If $[x] = [y]$, then $x \sim y$, so $f(x) = f(y)$ by the compatibility hypothesis. Therefore $\bar{f}([x]) = f(x) = f(y) = \bar{f}([y])$. **Existence.** Define $\bar{f}([x]) = f(x)$. For any $x \in X$, $\bar{f}(\pi(x)) = \bar{f}([x]) = f(x)$, so $f = \bar{f} \circ \pi$. **Uniqueness.** Suppose $g : X/{\sim} \to Y$ also satisfies $f = g \circ \pi$. For any $[x] \in X/{\sim}$, $g([x]) = g(\pi(x)) = f(x) = \bar{f}([x])$. Since this holds for every class, $g = \bar{f}$. [/proof] This universal property is the engine behind every "well-definedness check" in algebra. When we define addition on $\mathbb{Z}/n\mathbb{Z}$ by $[a] + [b] = [a + b]$ and then verify that the result is independent of the choice of representatives, we are verifying that addition on $\mathbb{Z}$ is compatible with $\equiv_n$ and therefore descends to the quotient. [example:The Integers Modulo N] Let $n \geq 2$ be a positive integer and consider the equivalence relation $\equiv_n$ on $\mathbb{Z}$. The quotient set is \begin{align*} \mathbb{Z}/n\mathbb{Z} = \{[0], [1], \ldots, [n-1]\}. \end{align*} Define addition and multiplication on $\mathbb{Z}/n\mathbb{Z}$ by $[a] + [b] = [a + b]$ and $[a] \cdot [b] = [ab]$. These operations are well-defined by the universal property. Indeed, if $a \equiv_n a'$ and $b \equiv_n b'$, then $n \mid (a - a')$ and $n \mid (b - b')$. For addition: $(a + b) - (a' + b') = (a - a') + (b - b')$, which is divisible by $n$. For multiplication: $ab - a'b' = (a - a')b + a'(b - b')$, and both summands are divisible by $n$. With these operations, $\mathbb{Z}/n\mathbb{Z}$ is a commutative ring with identity $[1]$. [/example] ## Congruence Relations in Algebra When the set $X$ carries algebraic structure --- a group operation, ring multiplication, module scalar action --- a bare equivalence relation is not enough. We need the equivalence relation to be **compatible** with the algebraic operations, so that the quotient set inherits those operations. An equivalence relation with this compatibility is called a **congruence relation**. For groups, the compatibility condition has a clean characterisation. Let $G$ be a group and $H \leq G$ a subgroup. Define the relation $\sim_H$ on $G$ by $a \sim_H b$ if and only if $a^{-1}b \in H$, or equivalently, $aH = bH$. This relation is always an equivalence relation --- its equivalence classes are precisely the left cosets $gH$ for $g \in G$. [quotetheorem:782] Lagrange's theorem is, at its core, a counting argument built on the equivalence-relation/partition correspondence. The left cosets of $H$ partition $G$ (this is an instance of the fundamental theorem applied to $a \sim_H b \iff a^{-1}b \in H$). Since each coset has the same cardinality as $H$ (via the bijection $h \mapsto gh$), counting gives $|G| = |G:H| \cdot |H|$. The result constrains the possible subgroups of a finite group: no subgroup can have an order that fails to divide $|G|$. But the left cosets $gH$ form a group under the operation $aH \cdot bH = abH$ only when $H$ is a **normal** subgroup ($H \unlhd G$). Normality is exactly the condition that ensures the coset multiplication is well-defined --- that is, compatible with the equivalence relation. When $H$ is not normal, the set of cosets $G/H$ is still a well-defined quotient set, but it does not inherit a group structure from $G$. The deepest structural result about quotient groups is the First Isomorphism Theorem, which identifies the "right" equivalence relation on a group: the one induced by the kernel of a homomorphism. [quotetheorem:791] The First Isomorphism Theorem says that every group homomorphism $\vartheta : G \to H$ factors through the quotient $G/\ker(\vartheta)$: the induced map $\bar{\vartheta} : G/\ker(\vartheta) \to \operatorname{Im}(\vartheta)$ defined by $g\ker(\vartheta) \mapsto \vartheta(g)$ is an isomorphism. The kernel is exactly the equivalence class of the identity --- it consists of all elements that $\vartheta$ "cannot see." Quotienting by the kernel removes precisely the redundancy that prevents $\vartheta$ from being injective, producing a bijective homomorphism onto the image. The same pattern repeats for rings, with ideals playing the role of normal subgroups. [quotetheorem:851] The structural parallel is exact. In a group, the "compatible" equivalence relations are those given by normal subgroups; in a ring, they are those given by ideals. In both cases, the First Isomorphism Theorem says that every homomorphism factors through the quotient by its kernel. The same template extends further to modules. [quotetheorem:862] This repeated pattern --- congruence relation, quotient construction, isomorphism theorem --- is one of the organising principles of abstract algebra. ## Constructing New Objects via Equivalence Classes Beyond organising existing algebraic structures, equivalence relations serve as a primary **construction** tool: many of the fundamental objects in mathematics are built as quotient [sets](/page/Set). [example:Construction Of The Rationals] Let $S = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ and define $\sim$ on $S$ by \begin{align*} (a, b) \sim (c, d) \quad \iff \quad ad = bc. \end{align*} **Verification that $\sim$ is an equivalence relation.** *Reflexivity.* For $(a, b) \in S$, $ab = ba$, so $(a, b) \sim (a, b)$. *Symmetry.* If $ad = bc$, then $cb = da$, so $(c, d) \sim (a, b)$. *Transitivity.* Suppose $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$, so $ad = bc$ and $cf = de$. Multiply the first equation by $f$ and the second by $b$: \begin{align*} adf = bcf = bde. \end{align*} Since $d \neq 0$ and $\mathbb{Z}$ is an [integral](/page/Integral) domain, we may cancel $d$ to obtain $af = be$, giving $(a, b) \sim (e, f)$. The quotient $S/{\sim}$ is the set of rational numbers $\mathbb{Q}$. The equivalence class of $(a, b)$ is written $\frac{a}{b}$, and the operations $\frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}$ and $\frac{a}{b} \cdot \frac{c}{d} = \frac{ac}{bd}$ are well-defined and make $\mathbb{Q}$ into a field. [/example] This construction generalises to an arbitrary integral domain. [quotetheorem:866] The field of fractions construction is a paradigmatic example of building a new algebraic object via equivalence classes. The integral domain $R$ lacks multiplicative inverses for non-zero elements; the equivalence relation on $R \times (R \setminus \{0\})$ identifies pairs that represent the same "fraction," and the resulting quotient is the smallest field containing $R$. The cancellation law in the integral domain (which comes from the absence of zero divisors) is essential for transitivity, which is why the construction fails for rings with zero divisors. ## Equivalence Relations Beyond Algebra The equivalence relation framework extends far beyond algebraic quotient constructions. Three examples from analysis, topology, and linear algebra illustrate the range. **Functions equal almost everywhere.** Let $(X, \mathcal{A}, \mu)$ be a measure space and let $f, g : X \to \mathbb{R}$ be measurable functions. Define $f \sim g$ if and only if $f(x) = g(x)$ for $\mu$-almost every $x \in X$. This is an equivalence relation. The $L^p$ spaces are defined as quotient sets: $L^p(X, \mu) = \{f : \|f\|_p < \infty\}/{\sim}$. Without this quotient, the $L^p$ "norm" would only be a seminorm, and $L^p$ would not be a genuine normed space. **Similar matrices.** Let $M_n(K)$ denote the set of $n \times n$ matrices over a field $K$. Define $A \sim B$ if and only if there exists $P \in \mathrm{GL}_n(K)$ such that $B = P^{-1}AP$. Two matrices are similar precisely when they represent the same linear map in different bases. The equivalence classes are the **similarity classes**, and a major goal of linear algebra is to find canonical representatives --- the [Jordan normal form](/theorems/864) over algebraically closed fields, or the [rational canonical form](/theorems/863) over arbitrary fields. **Homotopy of paths.** Let $X$ be a [topological](/page/Topology) space. Two continuous paths $\gamma, \delta : [0, 1] \to X$ with the same endpoints are **homotopic** if there exists a continuous deformation from one to the other. Homotopy is an equivalence relation. The quotient set of loops at a basepoint $x_0$, equipped with concatenation, is the **fundamental group** $\pi_1(X, x_0)$. Here the equivalence relation is not merely a bookkeeping device but a topological invariant: it detects "holes" in $X$. ## References - S. Lang, *Algebra*, 3rd edition, Springer, 2002. - T. W. Hungerford, *Algebra*, Springer, 1974. - P. R. Halmos, *Naive Set Theory*, Springer, 1960.