Equivalence Relation

An equivalence relation is a binary relation on a set that is reflexive, symmetric, and transitive. It formalizes the idea that objects may count as the same under a specified criterion without being identical. In mathematics, equivalence relations generalize equality and organize elements into nonoverlapping groups called equivalence classes. Each relation determines a partition of its underlying set, and each partition determines an equivalence relation. (judsonbooks.org)

Definition and notation

In the language of set theory, a relation $R$ on a set $X$ is a subset of the Cartesian product $X\times X$. Writing $x\sim y$, or $xRy$, means that $(x,y)\in R$. The relation is an equivalence relation precisely when it satisfies these three conditions:

• Reflexivity: $x\sim x$ for every $x\in X$.
• Symmetry: if $x\sim y$, then $y\sim x$.
• Transitivity: if $x\sim y$ and $y\sim z$, then $x\sim z$.

These conditions apply to all elements involved, not merely to selected examples. The symbols $\sim$, $\equiv$, and $\cong$ commonly denote particular equivalence relations, with their meanings determined by context. (judsonbooks.org)

Equality is an equivalence relation: each element is related only to itself. By contrast, the relation $x\leq y$ on the real numbers is reflexive and transitive but not symmetric. Checking the three conditions therefore distinguishes equivalence from other ways of comparing objects. (terpconnect.umd.edu)

Equivalence classes and partitions

For $x\in X$, its equivalence class is

Reflexivity guarantees that $x\in[x]$, so every class is nonempty. Symmetry and transitivity imply the fundamental identity

Consequently, two classes are either identical or disjoint; they cannot overlap partially. Every element belongs to exactly one class. (terpconnect.umd.edu)

The collection of distinct classes is a partition of the set: a collection of nonempty, pairwise disjoint subsets whose union is $X$. Conversely, given a partition, define $x\sim y$ when both elements belong to the same part. This relation is reflexive because every element belongs to a part, symmetric because sharing a part is mutual, and transitive because the part containing any element is unique. These constructions establish a one-to-one correspondence between partitions and equivalence relations on a fixed set. (bookdown.org)

An element used to name a class is called a representative. Different representatives can name the same class. For example, under congruence modulo $3$, the integers $1$, $4$, and $-2$ all represent one class. The class itself is a subset, not a specially privileged member of that subset. (judsonbooks.org)

Quotient sets and functions

The quotient set of $X$ by $\sim$, written $X/{\sim}$, is the set of all equivalence classes:

The canonical projection $q:X\to X/{\sim}$, defined by $q(x)=[x]$, is a surjective function. It treats each class as a single element of a new set, while retaining the original relation through $x\sim y$ exactly when $q(x)=q(y)$. (sites.math.rutgers.edu)

Conversely, any function $f:X\to Y$ induces an equivalence relation by

Its classes are the nonempty fibers of $f$, meaning the sets of inputs with a particular output. Thus equivalence can be understood as indistinguishability under a chosen function. The assignment $[x]\mapsto f(x)$ gives a bijection from $X/{\sim_f}$ to $f(X)$. If $f$ is onto $Y$, the quotient therefore corresponds bijectively to $Y$. (terpconnect.umd.edu)

Numerical examples

In modular arithmetic, fix a positive integer $n$ and define

This means that $a$ and $b$ have the same remainder modulo $n$. For $n=3$, the three classes are

They partition the integers despite each containing infinitely many elements. (judsonbooks.org)

Equivalence classes also provide a construction of the rational numbers. On pairs $(a,b)$, where $a$ is an integer and $b$ is a positive integer, define

The class of $(a,b)$ represents the rational number $a/b$. Hence $(1,2)$ and $(2,4)$ represent the same number. This separates a number from its many possible fraction representations. Transitivity follows by combining $ad=bc$ and $cg=df$, then cancelling the nonzero factor $d$. (bookdown.org)

Examples in geometry and analysis

In geometry, points in the plane may be declared equivalent when they have the same Euclidean distance from the origin. Each positive-distance class is a circle centered at the origin; the zero-distance class contains only the origin. Equivalence classes therefore need not be finite or consist of discrete objects. (jiblm.org)

For real numbers, the relation $x\sim y$ defined by $x^2=y^2$ has classes $\{t,-t\}$, with the exceptional singleton $\{0\}$. This is an example of a relation induced by a function that loses information—in this case, the sign of a nonzero input. (sites.math.rutgers.edu)

In calculus, differentiable functions on $\mathbb R$ can be declared equivalent when their derivatives agree everywhere. Their classes consist of functions differing by an additive constant. In linear algebra, matrix similarity provides another example: square matrices $A$ and $B$ are related when $B=PAP^{-1}$ for some invertible matrix $P$. Inversion establishes symmetry, and multiplication of the change-of-basis matrices establishes transitivity. (judsonbooks.org)