# 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]