Equivalence Relations

Definition

A relation $R$ on a set $A$ is an equivalence relation if it is:

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

Equivalence Classes

For an equivalence relation $R$ on $A$, the equivalence class of $a \in A$ is: $[a] = [a]_R = \{b \in A \mid aRb\}$

All elements equivalent to $a$ form its equivalence class.

Properties

• Every element belongs to exactly one equivalence class
• $[a] = [b]$ if and only if $aRb$
• $[a] \cap [b] = \emptyset$ or $[a] = [b]$

Partitions

A partition of a set $A$ is a collection of non-empty subsets $\{A_1, A_2, \ldots\}$ such that:

1. $A_i \cap A_j = \emptyset$ for $i \neq j$ (pairwise disjoint)
2. $\bigcup_i A_i = A$ (cover all of $A$)

Fundamental Theorem

Theorem: The equivalence classes of an equivalence relation form a partition. Conversely, every partition defines an equivalence relation.

Quotient Set

The quotient set of $A$ by $R$ is the set of all equivalence classes: $A/R = \{[a] \mid a \in A\}$

Examples

Equality

The simplest equivalence relation: $aRb \iff a = b$

Each equivalence class is a singleton: $[a] = \{a\}$

Congruence Modulo n

For integers and positive integer $n$: $a \equiv b \pmod{n} \iff n \mid (a - b)$

Verification:

• Reflexive: $a - a = 0 = n \cdot 0$, so $n \mid 0$ ✓
• Symmetric: If $n \mid (a-b)$, then $n \mid (-(a-b)) = (b-a)$ ✓
• Transitive: If $n \mid (a-b)$ and $n \mid (b-c)$, then $n \mid ((a-b)+(b-c)) = (a-c)$ ✓

Equivalence Classes (mod 3): $[0] = \{\ldots, -6, -3, 0, 3, 6, \ldots\}$ $[1] = \{\ldots, -5, -2, 1, 4, 7, \ldots\}$ $[2] = \{\ldots, -4, -1, 2, 5, 8, \ldots\}$

Quotient set: $\mathbb{Z}/\equiv_n = \{[0], [1], \ldots, [n-1]\} = \mathbb{Z}_n$

Same Parity

$aRb \iff a$ and $b$ are both even or both odd

Two equivalence classes: even integers and odd integers

Same Length (for strings)

$sRt \iff |s| = |t|$

Equivalence classes: all strings of length 0, length 1, length 2, etc.

Counting Equivalence Relations

The number of equivalence relations on a set of $n$ elements equals the Bell number $B_n$.

$n$	$B_n$
0	1
1	1
2	2
3	5
4	15
5	52

Equivalence Relations and Functions

Kernel of a Function

For function $f: A \to B$, the kernel is: $\ker(f) = \{(a_1, a_2) \in A \times A \mid f(a_1) = f(a_2)\}$

The kernel is always an equivalence relation.

Example: For $f(x) = x^2$ on $\mathbb{R}$: $\ker(f) = \{(a, b) \mid a^2 = b^2\} = \{(a, b) \mid a = b \text{ or } a = -b\}$

Equivalence classes: $[a] = \{a, -a\}$

Canonical Map

The canonical map $\pi: A \to A/R$ sends each element to its class: $\pi(a) = [a]$

This is always surjective.

Operations on Equivalence Classes

For congruence mod $n$, we can define: $[a] + [b] = [a + b]$ $[a] \cdot [b] = [a \cdot b]$

These are well-defined because:

• If $a \equiv a' \pmod{n}$ and $b \equiv b' \pmod{n}$
• Then $a + b \equiv a' + b' \pmod{n}$ and $ab \equiv a'b' \pmod{n}$

This gives $\mathbb{Z}_n$ the structure of a ring.