How to prove that a relation is an equivalence relation and find its equivalence classes?

**Proof that $a \sim b \iff a - b$ is even is an equivalence relation on $\mathbb{Z}$:** **Reflexive:** $a - a = 0$, which is even, so $a \sim a$ ✓ **Symmetric:** If $a \sim b$, then $a - b = 2k$ for some $k \in \mathbb{Z}$. Then $b - a = -2k = 2(-k)$, which is even, so $b \sim a$ ✓ **Transitive:** If $a \sim b$ and $b \sim c$, then $a - b = 2k$ and $b - c = 2\ell$. Then $a - c = (a - b) + (b - c) = 2k + 2\ell = 2(k + \ell)$, which is even, so $a \sim c$ ✓ **Equivalence Classes:** The equivalence class of $a$ is $[a] = \{b \in S : a \sim b\}$. For this relation: $[a] = \{a + 2k : k \in \mathbb{Z}\}$ — all numbers with the same parity as $a$. There are exactly two equivalence classes: - $[0] = \{\ldots, -4, -2, 0, 2, 4, \ldots\}$ (even numbers) - $[1] = \{\ldots, -3, -1, 1, 3, 5, \ldots\}$ (odd numbers) **Partition:** These two classes are disjoint and their union is $\mathbb{Z}$. This is always true: equivalence relations partition the set, and every partition defines an equivalence relation. **Connection to $\mathbb{Z}_n$:** The relation $a \equiv b \pmod{n}$ (i.e., $a - b$ is divisible by $n$) is an equivalence relation on $\mathbb{Z}$ with $n$ equivalence classes: $[0], [1], \ldots, [n-1]$. These are exactly the elements of $\mathbb{Z}_n$, showing that quotient sets arise naturally from equivalence relations. **Equivalence Relations and Functions:** Every function $f: X \to Y$ defines an equivalence relation on $X$: $x_1 \sim x_2 \iff f(x_1) = f(x_2)$. The equivalence classes are the fibers (level sets) of $f$. This is the fundamental connection between functions and equivalence relations.