Equivalence Relations and Equivalence Classes, with Partitions You Can Draw

Mathematics is full of things that are "the same" without being identical. The fractions 1/2 and 2/4 are different expressions for one number. 7 and 19 leave the same remainder when divided by 12, so they are the same hour on a clock. Two graphs drawn differently can have the same structure. An equivalence relation is the precise version of "the same in the respect we care about", and its equivalence classes are the groups of things that count as the same.

Reflexive, symmetric and transitive

A relation ~ on a set A is an equivalence relation when it is

• reflexive: a ~ a for every a,
• symmetric: a ~ b implies b ~ a, and
• transitive: a ~ b and b ~ c imply a ~ c.

Applied Discrete Structures calls equality the classic example and explains the name: relations that satisfy these three conditions behave very much like equality. The three properties are covered one at a time, with ways to test them, in checking a relation's properties.

Examples and non-examples

The fraction example is the one Applied Discrete Structures uses to motivate equivalence classes: every fraction belongs to a set of equivalent fractions, any of which can stand in for the others when doing arithmetic.

Equivalence classes

For an element a, its equivalence class is

[a] = {x ∈ A : x ~ a},

everything equivalent to a. Any member of the class can represent it.

Congruence mod 3 on the integers gives three classes:

• [0] = {…, −6, −3, 0, 3, 6, …}
• [1] = {…, −5, −2, 1, 4, 7, …}
• [2] = {…, −4, −1, 2, 5, 8, …}

So [1] = [4] = [−2]: they are three names for one class. These three classes are the "integers mod 3", the setting for modular arithmetic. Applied Discrete Structures defines congruence modulo n by a ≡ b exactly when n divides a − b, and checks each property directly from that definition.

Partitions: the picture behind the classes

A partition of A is a collection of non-empty subsets that cover A and do not overlap. Draw A as a region and the partition as lines dividing it into pieces; every element lies in exactly one piece.

The central theorem of the topic says equivalence relations and partitions are two descriptions of the same thing:

1. The distinct equivalence classes of an equivalence relation on A form a partition of A.
2. Every partition of A comes from exactly one equivalence relation: "is in the same piece as".

Applied Discrete Structures states the first direction as a theorem and notes that all three properties are used in its proof. Here is why. Reflexivity puts each a in its own class [a], so the classes cover A. Now suppose [a] and [b] share an element c. Then c ~ a and c ~ b, so by symmetry a ~ c, and by transitivity a ~ b. From there, anything equivalent to a is equivalent to b and vice versa, so [a] = [b]. Two classes are therefore either identical or disjoint.