Some relations behave like "is the same as" in some respect: same remainder, same birthday, same number of letters. They have the three properties that sameness should have, and they always sort their set into neat groups.
Key idea
An equivalence relation is reflexive, symmetric and transitive; we often write $a \sim b$. The equivalence class of $a$ is $[a] = \{x \in A : x \sim a\}$. The classes form a partition of $A$: every element is in exactly one class, and two elements are related exactly when they share a class.
Why it works
Why can't classes overlap? Suppose some $c$ is in both $[a]$ and $[b]$. Then $c \sim a$ and $c \sim b$; symmetry gives $a \sim c$, and transitivity gives $a \sim b$. From there, anything related to $a$ is related to $b$ and the other way around, so $[a] = [b]$. Two classes are either identical or disjoint. Reflexivity puts each $a$ in its own class $[a]$, so the classes cover the whole set. Going the other way, any partition defines an equivalence relation: "in the same piece."
Worked examples
Worked example: Remainder classes
On $\{1, 2, \ldots, 12\}$, let $a \sim b$ mean $a$ and $b$ leave the same remainder when divided by $4$. List the classes.
- Remainder $1$: $[1] = \{1, 5, 9\}$. Remainder $2$: $[2] = \{2, 6, 10\}$.
- Remainder $3$: $[3] = \{3, 7, 11\}$. Remainder $0$: $[4] = \{4, 8, 12\}$.
- Four classes, disjoint, covering all $12$ numbers. Note $[5] = [1]$: a class can be named by any of its members.
Answer: $\{1, 5, 9\}, \{2, 6, 10\}, \{3, 7, 11\}, \{4, 8, 12\}$
Worked example: From a partition to a relation
A partition of $\{1, 2, 3, 4, 5\}$ has classes $\{1, 2, 3\}$ and $\{4, 5\}$. How many ordered pairs are in the corresponding equivalence relation?
- Inside a class, every element is related to every element, including itself.
- A class of size $s$ contributes $s^{2}$ pairs: $3^{2} + 2^{2} = 9 + 4 = 13$.
Answer: $13$
Worked example: A relation that fails
On $\{1, 2, 3\}$, is $$R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)\}$$ an equivalence relation?
- Reflexive: yes. Symmetric: every pair has its reverse. Yes.
- Transitive: $1 \sim 2$ and $2 \sim 3$, so we need $1 \sim 3$. But $(1, 3) \notin R$. No.
- So it is not an equivalence relation, and indeed it does not split $\{1, 2, 3\}$ into groups: $2$ would have to share a group with both $1$ and $3$, which are not related.
Answer: No (not transitive)
Common mistake
Forgetting transitivity, or putting an element in two classes. "Is within $1$ of" is reflexive and symmetric, so it feels like an equivalence relation, but $1 \sim 2$ and $2 \sim 3$ while $1 \not\sim 3$. And a proposed partition like $\{1, 2\}, \{2, 3\}$ is not a partition at all, because $2$ sits in two pieces. Check: every element must appear in exactly one class, and every two-step route must have its shortcut.
Counting equivalence relations means counting partitions. A $3$-element set $\{1, 2, 3\}$ has $5$: all together; $\{1, 2\}, \{3\}$; $\{1, 3\}, \{2\}$; $\{2, 3\}, \{1\}$; and all separate.