Equivalence Class

An equivalence class is a collection of elements of a set that are equivalent to one another under a specified equivalence relation. It treats objects that may differ individually as instances of the same object for a particular purpose. Equivalence classes provide a precise way to organize a set into nonoverlapping groups and to construct new mathematical objects from existing ones. They occur throughout set theory, algebra, analysis, and computer science. (cs.cornell.edu)

Definition and notation

Let $X$ be a set and let $\sim$ be an equivalence relation on $X$. This is a binary relation satisfying three conditions: reflexivity, $x\sim x$; symmetry, $x\sim y\Rightarrow y\sim x$; and transitivity, $x\sim y$ and $y\sim z\Rightarrow x\sim z$. For $a\in X$, its equivalence class is the subset

The subscript is usually omitted when the relation is understood. Any member of a class is called a representative of that class. (pi.math.cornell.edu)

A representative is not the class itself: $a$ is an element of $X$, whereas $[a]$ is a subset of $X$. Different representatives can name the same class. Consequently, equivalence of elements and equality of classes are related by

The underlying set and relation are essential: changing either can change the class denoted by the same symbol. (jirka.org)

Relationship with partitions

The equivalence classes of a relation form a partition of $X$. Each class is nonempty because $a\in[a]$, every element belongs to a class, and two classes are either identical or disjoint. Thus every element belongs to exactly one distinct class. Conversely, any partition determines an equivalence relation by declaring two elements equivalent precisely when they belong to the same block. (pi.math.cornell.edu)

The disjointness assertion has a short proof. Suppose $c\in[a]\cap[b]$. Then $c\sim a$ and $c\sim b$, so symmetry and transitivity imply $a\sim b$. If $x\in[a]$, transitivity gives $x\sim b$, hence $[a]\subseteq[b]$. Reversing the argument gives the opposite inclusion. Therefore classes cannot partially overlap. Their sizes, however, need not be equal. (pi.math.cornell.edu)

Quotient sets and induced functions

The quotient set is the set whose elements are the distinct equivalence classes:

The canonical projection

is a surjective function. Its fibers are exactly the equivalence classes: $\pi(x)=\pi(y)$ precisely when $x\sim y$. Passing to the quotient therefore identifies equivalent elements without choosing a preferred representative. (pi.math.cornell.edu)

A rule defined using representatives must be independent of their choice. Given a function $f:X\to Y$, the formula

defines a well-defined function exactly when $x\sim y$ implies $f(x)=f(y)$. When this condition holds, $\bar f$ is unique and $f=\bar f\circ\pi$. This factorization expresses a universal property of the quotient set. It is also the basic test used when defining operations on classes. (pi.math.cornell.edu)

Numerical examples

In modular arithmetic, two integers are equivalent modulo a positive integer $n$ when their difference is divisible by $n$. The class of $a$ is

Modulo $3$, for example, $[1]$ contains $\ldots,-5,-2,1,4,7,\ldots$. There are exactly three classes, represented by $0,1,2$. More generally, $0,\ldots,n-1$ provide one representative per class. Addition and multiplication of representatives induce operations on these classes. (pi.math.cornell.edu)

Rational numbers can be constructed from ordered pairs of integers $(a,b)$, with $b\ne0$, by defining

Thus $(1,2)$, $(2,4)$, and $(-3,-6)$ belong to one class. The rational number is the class, while the different fractions are representations of it. This construction separates a numerical value from the notation used to express it. (pi.math.cornell.edu)

One construction of the real numbers uses classes of rational Cauchy sequences. Two such sequences $(a_k)$ and $(b_k)$ are equivalent when their difference has limit zero:

Each class becomes a real number. Termwise addition and multiplication define operations on classes because replacing either sequence by an equivalent one leaves the resulting class unchanged. (pi.math.cornell.edu)

Vector spaces and counting

For a vector space $V$ and a linear subspace $W$, define $v\sim u$ when $v-u\in W$. The class of $v$ is the coset

These classes form the quotient vector space $V/W$, with addition $(v+W)+(u+W)=(v+u)+W$. Its zero element is the entire class $W$. For finite-dimensional $V$, its dimension is $\dim V-\dim W$. (math.stanford.edu)

In combinatorics, equivalence classes prevent multiple representations from being counted as different objects. Ordered lists of $k$ distinct elements can be declared equivalent when they contain the same elements, regardless of order. Every class then has $k!$ members, and the classes correspond to $k$-element subsets. For a finite set $X$ partitioned into classes of a common size $m$, the number of classes is $|X|/m$. This division rule does not apply unchanged when class sizes differ. (discrete.openmathbooks.org)