Equivalence Relations and Partitions

Equivalence relations are among the most important structures in mathematics, providing a way to identify objects that share essential properties. They formalize the notion of "sameness" and lead naturally to quotient structures.

DefinitionEquivalence Relation

A binary relation $R$ on a set $A$ (i.e., $R \subseteq A \times A$ ) is an equivalence relation if it satisfies three properties:

Reflexive: $\forall a \in A(aRa)$
Symmetric: $\forall a, b \in A(aRb \rightarrow bRa)$
Transitive: $\forall a, b, c \in A(aRb \land bRc \rightarrow aRc)$

We often write $a \sim b$ instead of $aRb$ for equivalence relations.

Equivalence relations capture the idea of objects being "the same" in some sense, even if they are not literally equal. The three axioms ensure that this notion of sameness behaves as expected.

ExampleStandard Equivalence Relations

Equality: The relation $=$ on any set is an equivalence relation (the finest equivalence)
Congruence modulo n: On $\mathbb{Z}$ , define $a \sim b$ iff $n | (a - b)$ . This is an equivalence relation
Similarity: On the set of matrices, $A \sim B$ iff there exists an invertible $P$ with $B = P^{-1}AP$
Cardinality: On the class of all sets, $A \sim B$ iff $|A| = |B|$ (i.e., there exists a bijection)
Parallel lines: In Euclidean geometry, lines are equivalent if they are parallel (including the case where a line is parallel to itself)

DefinitionEquivalence Class

Let $\sim$ be an equivalence relation on $A$ . For $a \in A$ , the equivalence class of $a$ is:

[a] = \{b \in A : a \sim b\}

The set of all equivalence classes is called the quotient set and denoted $A/\sim$ or $A/R$ :

A/\sim = \{[a] : a \in A\}

Equivalence classes partition the set: every element belongs to exactly one equivalence class, and two equivalence classes are either identical or disjoint.

TheoremFundamental Theorem of Equivalence Relations

Let $\sim$ be an equivalence relation on $A$ . Then:

Every element $a \in A$ belongs to some equivalence class (its own): $a \in [a]$
If $a \sim b$ , then $[a] = [b]$
If $a \not\sim b$ , then $[a] \cap [b] = \emptyset$
$A = \bigcup_{a \in A} [a]$ , i.e., the equivalence classes cover $A$

Therefore, the equivalence classes form a partition of $A$ .

Proof

(1) follows from reflexivity: $a \sim a$ , so $a \in [a]$ .

(2) Suppose $a \sim b$ . We show $[a] = [b]$ by double inclusion.

Let $c \in [a]$ , so $a \sim c$ . By symmetry, $b \sim a$ . By transitivity, $b \sim c$ , so $c \in [b]$ . Thus $[a] \subseteq [b]$ .
Similarly, $[b] \subseteq [a]$ . Therefore $[a] = [b]$ .

(3) Suppose $[a] \cap [b] \neq \emptyset$ , so there exists $c \in [a] \cap [b]$ . Then $a \sim c$ and $b \sim c$ . By symmetry, $c \sim b$ . By transitivity, $a \sim b$ . This contradicts $a \not\sim b$ .

(4) is immediate from (1).

■

DefinitionPartition

A partition of a set $A$ is a collection $\mathcal{P} = \{A_i : i \in I\}$ of non-empty subsets of $A$ such that:

$\bigcup_{i \in I} A_i = A$ (the sets cover $A$ )
If $i \neq j$ , then $A_i \cap A_j = \emptyset$ (the sets are pairwise disjoint)

The sets $A_i$ are called the blocks or parts of the partition.

TheoremCorrespondence Between Equivalence Relations and Partitions

There is a bijective correspondence between equivalence relations on $A$ and partitions of $A$ :

Given an equivalence relation $\sim$ , the equivalence classes $\{[a] : a \in A\}$ form a partition
Given a partition $\mathcal{P}$ , define $a \sim b$ iff $a$ and $b$ belong to the same block. This is an equivalence relation

These constructions are inverse to each other.

ExampleQuotient Structures

Integers modulo n: The quotient $\mathbb{Z}/n\mathbb{Z}$ consists of $n$ equivalence classes: $[0], [1], \ldots, [n-1]$ . We can define addition: $[a] + [b] = [a+b]$ , giving the ring $\mathbb{Z}_n$
Rational numbers: We construct $\mathbb{Q}$ from $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ by the equivalence $(a, b) \sim (c, d)$ iff $ad = bc$ . The equivalence class of $(a, b)$ is denoted $a/b$
Projective space: In projective geometry, points in $\mathbb{P}^n$ are equivalence classes of $(n+1)$ -tuples under the relation $(x_0, \ldots, x_n) \sim (\lambda x_0, \ldots, \lambda x_n)$ for $\lambda \neq 0$
Homeomorphism: In topology, we often study spaces "up to homeomorphism," treating homeomorphic spaces as equivalent

DefinitionCanonical Projection

Given an equivalence relation $\sim$ on $A$ , the canonical projection (or quotient map) is the function:

\pi: A \to A/\sim, \quad a \mapsto [a]

This function is always surjective. It "collapses" equivalent elements to a single representative.

TheoremUniversal Property of Quotients

Let $\sim$ be an equivalence relation on $A$ , and let $f: A \to B$ be a function that is compatible with $\sim$ (meaning $a \sim a'$ implies $f(a) = f(a')$ ). Then there exists a unique function $\bar{f}: A/\sim \to B$ such that $f = \bar{f} \circ \pi$ :

\begin{array}{ccc} A & \xrightarrow{f} & B \\ \downarrow{\pi} & \nearrow{\bar{f}} & \\ A/\sim & & \end{array}

The function $\bar{f}$ is defined by $\bar{f}([a]) = f(a)$ , and compatibility ensures this is well-defined.

Remark

This universal property is fundamental in category theory and abstract algebra. It says that compatible functions through $A$ can be "factored" through the quotient $A/\sim$ . This construction is ubiquitous: group homomorphisms factor through normal subgroups, continuous maps factor through quotient topologies, etc.

ExampleFirst Isomorphism Theorem

In group theory, if $\varphi: G \to H$ is a homomorphism, we can define an equivalence relation on $G$ by $g_1 \sim g_2$ iff $\varphi(g_1) = \varphi(g_2)$ . The equivalence classes are the cosets of $\ker(\varphi)$ , and the quotient $G/\ker(\varphi)$ is isomorphic to $\text{im}(\varphi)$ via the map $\bar{\varphi}([g]) = \varphi(g)$ .

This is the first isomorphism theorem, which holds analogously for rings, modules, vector spaces, and many other algebraic structures. The underlying set-theoretic machinery is the universal property of quotients.

Equivalence relations and quotients are among the most powerful tools in mathematics, allowing us to study structure by ignoring irrelevant distinctions. They appear everywhere from number theory to topology to category theory, providing a uniform language for discussing "identification" and "modding out."