Equivalence Relations and Partitions: Concepts and Examples

An equivalence relation is a relation that is reflexive, symmetric and transitive all at once — the mathematical way of saying "these things are the same in the sense we care about". Equality of numbers and congruence of triangles are classic examples.

It matters because an equivalence relation automatically sorts its set into neat, non-overlapping groups called equivalence classes, and each group can then be treated as a single object. Clock arithmetic, fractions and many classification systems run on this idea.

Key Concepts

• Equivalence relation: a relation R on a set A that is reflexive (aRa for all a), symmetric (aRb implies bRa) and transitive (aRb and bRc imply aRc).
• Equivalence class [a]: the set of all elements related to a, written [a] = {x in A such that xRa}.
• Partition: the collection of all distinct equivalence classes; they are pairwise disjoint and their union is the whole set A.
• Canonical example: congruence modulo n on integers: a is related to b when a minus b is a multiple of n.

How It Works

1. Verify the three properties: every element relates to itself, every link works both ways, every chain closes.
2. Pick an element a and collect everything related to it; that is the class [a].
3. Pick an element outside [a] and build its class; repeat until every element belongs to a class.
4. The classes never overlap: if two classes shared an element, symmetry and transitivity would force them to be the same class.

Worked Example

On A = {0, 1, 2, 3, 4, 5}, define aRb when a minus b is a multiple of 3. Find the equivalence classes.

1. Start with 0: numbers differing from 0 by a multiple of 3 are 0 and 3, so [0] = {0, 3}.
2. Take 1, not yet classified: 1 and 4 differ by 3, so [1] = {1, 4}.
3. Take 2: 2 and 5 differ by 3, so [2] = {2, 5}.
4. The three classes {0, 3}, {1, 4}, {2, 5} are disjoint and cover all of A — a perfect partition.

Common Misconceptions

• "Equivalence just means equals." Equality is one equivalence relation, but "has the same remainder on division by 3" is another, grouping different numbers together.
• "Equivalence classes can overlap partially." They cannot: distinct classes are always disjoint; an element belongs to exactly one class.
• "All classes must have the same size." Not in general. Congruence modulo 3 on {0, 1, 2, 3, 4} gives classes of sizes 2, 2 and 1.

Real-World Applications

• Clock arithmetic: 14:00 and 2 PM are the same time because 14 and 2 differ by a multiple of 12.
• Fractions: 1/2, 2/4 and 3/6 are grouped as one rational number by an equivalence relation on pairs.
• Data grouping: clustering records that "match on the key fields" partitions a dataset into duplicate groups.

An equivalence relation — reflexive, symmetric, transitive — chops its set into disjoint equivalence classes that fit together like puzzle pieces. Once you see the classes, you can reason about whole groups instead of individual elements.