Equivalence Relations and Equivalence Classes

An equivalence relation $\sim$ on a set $A$ is a relation that is

• reflexive: $a \sim a$ for all $a \in A$,
• symmetric: $a \sim b \implies b \sim a$,
• transitive: $a \sim b$ and $b \sim c \implies a \sim c$.

These three axioms are exactly what is needed to group elements into clusters of “the same kind.”

Equivalence classes

The equivalence class of $a$ is the set of everything related to it:

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

Any member of a class is a valid representative: $a \sim b \iff [a] = [b]$. So $[0]$, $[3]$, $[6]$ can all name the same class — listing them separately does not create new classes.

The partition theorem

The classes of an equivalence relation partition $A$:

1. every $a$ lies in some class (its own, by reflexivity), so the classes cover $A$;
2. two classes are either identical or disjoint — if they share even one element they are equal.

Conversely, every partition of $A$ comes from a unique equivalence relation (relate $a \sim b$ iff they sit in the same block). “Equivalence relation” and “partition” are two views of the same object.

How to find the classes

When $a \sim b$ means “$f(a) = f(b)$” for some function $f$ (a very common konkur setup), the classes are exactly the fibers of $f$ — group together all inputs sharing the same output value. Then count the distinct output values: that count is the number of classes.

Mini-example

Define $\sim$ on $\mathbb{Z}_6 = \{0,1,2,3,4,5\}$ by $a \sim b \iff a \equiv b \pmod 3$ (same remainder mod $3$). Tabulating $a \bmod 3$:

Grouping equal values gives the classes

$\{0,3\},\quad \{1,4\},\quad \{2,5\},$

so there are exactly 3 classes, and $\{0,3\}\cup\{1,4\}\cup\{2,5\} = \mathbb{Z}_6$ — they partition the set.

Exam trick: the number of equivalence classes equals the number of distinct values, not the number of representatives a choice happens to list. A class written as $[0]=[3]=[6]$ is one class shown three times; counting it three times (or trusting an option that pads the list with duplicate representatives) is the classic trap.