Equivalence Relations and Partitions

Equivalence Relations

Definition

A relation $E$ on $A$ is an equivalence relation if it is:

1. Reflexive: $\forall a \in A. aEa$
2. Symmetric: $\forall a, b \in A. (aEb \Rightarrow bEa)$
3. Transitive: $\forall a, b, c \in A. (aEb \land bEc \Rightarrow aEc)$

Equivalence Classes

The equivalence class of $a$ under $E$ is:

$[a]_E = \{b \in A : aEb\}$

Examples

Relation	Equivalence Classes
$a = b$ on any set	Singletons $\{a\}$ for each $a$
Congruence mod $n$	$\{0, n, 2n, \ldots\}, \{1, n+1, \ldots\}, \ldots$
“Same parity” on $\mathbb{Z}$	{even integers}, {odd integers}
Universal relation $A \times A$	Single class containing all of $A$

Partitions

Definition

A partition $P$ of $A$ is a collection of non-empty, pairwise disjoint subsets whose union is $A$:

1. $\forall B \in P. B \neq \emptyset$
2. $\forall B_1, B_2 \in P. (B_1 \neq B_2 \Rightarrow B_1 \cap B_2 = \emptyset)$
3. $\bigcup_{B \in P} B = A$

The elements of a partition are called blocks.

Examples

• $\{\{1, 2\}, \{3\}, \{4, 5, 6\}\}$ is a partition of $\{1, 2, 3, 4, 5, 6\}$
• $\{\{1\}, \{2\}, \{3\}\}$ is a partition of $\{1, 2, 3\}$
• $\{\{\text{evens}\}, \{\text{odds}\}\}$ is a partition of $\mathbb{Z}$

Examinable Proof: Bijection between Equivalence Relations and Partitions

Theorem: There is a natural bijection $\Phi : \text{EqRel}(A) \cong \text{Part}(A)$.

From Equivalence Relation to Partition

Given an equivalence relation $E$, define:

$\Phi(E) = \{[a]_E : a \in A\}$

Well-defined: The equivalence classes form a partition.

• Non-empty: $a \in [a]_E$ by reflexivity
• Disjoint: If $b \in [a]_E \cap [a']_E$, then $aEb$ and $a'Eb$. By symmetry and transitivity, $aEa'$, so $[a]_E = [a']_E$.
• Covering: Every $a$ is in its own class

From Partition to Equivalence Relation

Given a partition $P$, define:

$\Phi^{-1}(P) = \{(a, b) : \exists B \in P. a \in B \land b \in B\}$

Well-defined: This is an equivalence relation.

• Reflexive: $a$ is in exactly one block $B$, so $(a, a) \in \Phi^{-1}(P)$
• Symmetric: If $a, b \in B$, then $b, a \in B$
• Transitive: If $a, b \in B$ and $b, c \in B'$, then $b \in B \cap B'$. Since blocks are disjoint, $B = B'$, so $a, c \in B$.

Inverses

$\Phi^{-1}(\Phi(E)) = E$: $a \Phi^{-1}(\Phi(E)) b$ iff $a, b$ are in the same equivalence class of $E$, iff $aEb$.

$\Phi(\Phi^{-1}(P)) = P$: The blocks of $\Phi(\Phi^{-1}(P))$ are the equivalence classes under “in same block of $P$”, which are the blocks themselves.

Key Step Explanation

The single crucial fact: every $a \in A$ lies in exactly one block of $P$.

• No fewer (blocks cover $A$)
• No more (blocks are disjoint)

This drives both directions of the proof.

Quotient Set

The quotient $A / E$ is the set of equivalence classes:

$A / E = \{[a]_E : a \in A\}$

Canonical Map

$\pi : A \to A/E$ sends $a$ to $[a]_E$.

This is the universal surjection associated with $E$.

---

Summary

• Equivalence relations: reflexive, symmetric, transitive
• Partitions: non-empty, disjoint blocks covering $A$
• Bijection: $E \mapsto \{[a]_E\}$ and $P \mapsto \{(a, b) : a, b \text{ in same block}\}$
• Quotient $A/E$ is the set of equivalence classes