Equivalence relations and equivalence classes

An equivalence relation is the mathematician's tool for declaring that certain elements should be regarded as "the same". Once you have one, the underlying set splits cleanly into bundles called equivalence classes, and you can work with bundles instead of individual elements. This is how integers split into residue classes modulo $n$, how triangles split into similarity types, and how rational numbers like $\tfrac{1}{2}$ and $\tfrac{2}{4}$ are recognised as equal.

Definition

A relation $R$ on $A$ is an equivalence relation if it is

1. reflexive,
2. symmetric, and
3. transitive.

For an equivalence relation $R$ we usually write $a \sim b$ instead of $(a, b) \in R$.

For each $a \in A$ the equivalence class of $a$ is

$[a] = \{x \in A : x \sim a\}.$

The set of all equivalence classes is denoted $A / \sim$.

The partition theorem

Theorem. If $\sim$ is an equivalence relation on $A$, then the equivalence classes $\{[a] : a \in A\}$ form a partition of $A$. That is

1. each $[a]$ is non-empty,
2. distinct equivalence classes are disjoint,
3. the union of all classes equals $A$.

Conversely, every partition of $A$ arises from a unique equivalence relation.

Proof. Non-emptiness is immediate because $a \in [a]$ by reflexivity. For (3), each $a \in A$ lies in its own class, so the union covers $A$.

For (2), suppose $[a] \cap [b] \neq \varnothing$ and let $x$ be common. Then $x \sim a$ and $x \sim b$. By symmetry $a \sim x$, and by transitivity $a \sim b$. We now show $[a] = [b]$. Take $y \in [a]$, so $y \sim a$; by transitivity with $a \sim b$ we get $y \sim b$, hence $y \in [b]$. The reverse inclusion is identical, so $[a] = [b]$.

For the converse, given a partition $\mathcal{P}$ of $A$, define $a \sim b$ iff $a$ and $b$ belong to the same block. This is plainly reflexive, symmetric and transitive, and its equivalence classes are the blocks of $\mathcal{P}$. $\blacksquare$

The partition theorem is the single most useful fact in this chapter. It lets you reason at the level of classes rather than individual elements.

The classical example: integers modulo $n$

Fix a positive integer $n$. Define $a \sim b$ on $\mathbb{Z}$ iff $n \mid (a - b)$. We have already verified, in the previous subtopic for $n = 2$, that this is an equivalence relation.

The equivalence classes are

$[0], [1], [2], \dots, [n - 1]$

and they correspond to the possible remainders on dividing by $n$. The set of classes is denoted $\mathbb{Z}_n$ or $\mathbb{Z} / n\mathbb{Z}$.

For $n = 3$ the classes are $\{\dots, -6, -3, 0, 3, 6, \dots\}$, $\{\dots, -5, -2, 1, 4, 7, \dots\}$, $\{\dots, -4, -1, 2, 5, 8, \dots\}$. Each integer belongs to exactly one of these three sets, and the union is all of $\mathbb{Z}$.

Why the proof matters

Students often skim the partition theorem and rush to compute classes. But the idea in the proof , that overlapping classes are forced to coincide , is the trick used in nearly every JEE problem on this topic. If you can sketch the argument from memory, you can solve any problem of the form "show that the following sets are either equal or disjoint".

Worked examples

Example 1. On $\mathbb{R}$, let $a \sim b \iff a - b \in \mathbb{Z}$. Show $\sim$ is an equivalence relation and describe the class of $\tfrac{1}{3}$.

• Reflexive: $a - a = 0 \in \mathbb{Z}$.
• Symmetric: if $a - b \in \mathbb{Z}$ then $b - a = -(a - b) \in \mathbb{Z}$.
• Transitive: $(a - b) + (b - c) = a - c$ is a sum of integers, hence an integer.

The class $[\tfrac{1}{3}]$ consists of all $x$ with $x - \tfrac{1}{3} \in \mathbb{Z}$, i.e., $x = \tfrac{1}{3} + n$ for some $n \in \mathbb{Z}$. The quotient $\mathbb{R} / \mathbb{Z}$ can be thought of as the circle.

Example 2. On $A = \{1, 2, 3, 4, 5\}$, $R = \{(a, b) : a, b \in A, |a - b| \text{ is even}\}$. List the equivalence classes.

$|a - b|$ even means $a$ and $b$ have the same parity. The classes are

$[1] = \{1, 3, 5\}, \quad [2] = \{2, 4\}.$

There are exactly two classes, $\{1, 3, 5\}$ and $\{2, 4\}$.

Example 3. On the set of integers, let $a R b \iff a + b$ is even. Show $R$ is an equivalence relation. Find the classes.

$a + b$ even means $a$ and $b$ have the same parity. Reflexive: $2a$ is even. Symmetric: obvious. Transitive: if $a + b$ and $b + c$ are both even, $(a + b) + (b + c) = a + c + 2b$ is even, so $a + c$ is even.

Classes: evens and odds.

Example 4. On $\mathbb{R}^2 \setminus \{(0, 0)\}$, define $(x_1, y_1) \sim (x_2, y_2)$ iff there is $\lambda > 0$ with $(x_2, y_2) = \lambda (x_1, y_1)$. Show this is an equivalence relation.

Reflexive ($\lambda = 1$), symmetric ($\lambda \mapsto 1/\lambda$), transitive (product of positives is positive). The equivalence classes are open half-lines through the origin.

Example 5. On the set of all triangles, $T_1 \sim T_2$ iff $T_1$ is congruent to $T_2$. Equivalence relation? What is an equivalence class?

Yes, by reflexivity of identity, symmetry of swapping, and transitivity of composing congruences. A class consists of all triangles with the same three side lengths (and orientation if you choose).

Example 6. Let $A = \mathbb{R}^\times$ (nonzero reals) and define $a \sim b \iff a/b > 0$. Show this is an equivalence relation. Find the classes.

$a / a = 1 > 0$, reflexive. If $a/b > 0$ then $b/a > 0$, symmetric. If $a/b > 0$ and $b/c > 0$, then $a/c = (a/b)(b/c) > 0$, transitive.

The classes are the positive reals and the negative reals. So $\mathbb{R}^\times / \sim$ has two elements.

Try it yourself

1. On $\mathbb{Z}$, $a \sim b \iff 5 \mid (a^2 - b^2)$. Is this an equivalence relation? If so, list classes.
2. On $\mathbb{R}$, $a \sim b \iff \cos a = \cos b$. Show it is an equivalence relation. Describe $[0]$.
3. On $\mathbb{Z}$, $a R b \iff a + b$ is divisible by $3$. Is $R$ transitive? (Check carefully.)
4. List all equivalence relations on $\{a, b, c\}$.
5. On the set of straight lines in the plane, $\ell_1 \sim \ell_2 \iff \ell_1 \parallel \ell_2$ (including equal). Is this an equivalence relation? Describe a class.
6. Show: on $\mathbb{N}$, $a \sim b \iff a + b$ is even is an equivalence relation. How many classes are there?
7. On $\mathbb{Z}$, define $a \sim b \iff a - b$ is a multiple of $4$. Find the class of $5$.
8. On $\mathbb{R} \setminus \{0\}$, define $a \sim b \iff a \cdot b > 0$. Equivalence relation? Classes?
9. Construct an equivalence relation on $\{1, 2, 3, 4, 5\}$ with exactly two classes of size $3$ and $2$.
10. Prove: every equivalence class is non-empty.
11. Show that two equivalence classes are either disjoint or equal.
12. How many equivalence relations are there on a set of size $4$? (Hint: this is the Bell number $B_4 = 15$.)
13. On $\mathbb{Z}_+$, $a \sim b \iff$ the number of prime factors of $a$ counted with multiplicity equals that of $b$. Verify $\sim$ is an equivalence relation.
14. Show: every partition of $A$ gives rise to an equivalence relation by setting $a \sim b$ iff $a, b$ lie in the same block.

Pitfalls / Tricks

• The biggest trap: forgetting reflexivity. A symmetric and transitive relation may appear equivalence-like but can fail at elements with no incident pair.
• When listing classes, always check the union equals $A$ and the classes are pairwise disjoint , that is your sanity check.
• Two classes $[a]$ and $[b]$ are equal iff $a \sim b$; they are disjoint iff $a \not\sim b$. There is no middle ground.
• The number of equivalence relations on an $n$-element set equals the Bell number $B_n$: $B_1 = 1, B_2 = 2, B_3 = 5, B_4 = 15, B_5 = 52$. Useful for fast counting in objective questions.

Carry the partition theorem with you everywhere in this chapter: it is the cleanest way to organise messy verification problems.