Mathwords: Equivalence Relation

Key Formula

\text{A relation } \sim \text{ on a set } S \text{ is an equivalence relation if:}

\begin{aligned} &1.\ \forall\, a \in S,\; a \sim a \quad (\text{reflexive}) \\ &2.\ \forall\, a, b \in S,\; a \sim b \Rightarrow b \sim a \quad (\text{symmetric}) \\ &3.\ \forall\, a, b, c \in S,\; (a \sim b \text{ and } b \sim c) \Rightarrow a \sim c \quad (\text{transitive}) \end{aligned}

Where:

$\sim$ = The relation being tested
$S$ = The set on which the relation is defined
$a, b, c$ = Arbitrary elements of S

Worked Example

Problem: Define the relation ~ on the set of integers by: a ~ b if and only if a and b give the same remainder when divided by 3 (i.e., a ≡ b mod 3). Show that ~ is an equivalence relation and identify the equivalence classes.

Step 1 — Reflexive: Take any integer a. When you subtract a from itself you get 0, and 3 divides 0. So a ≡ a (mod 3), meaning a ~ a.

a - a = 0 = 3 \cdot 0 \quad \Rightarrow \quad a \sim a \; \checkmark

Step 2 — Symmetric: Suppose a ~ b, so 3 divides (a − b). Then 3 also divides −(a − b) = b − a, which means b ~ a.

3 \mid (a - b) \;\Rightarrow\; 3 \mid (b - a) \;\Rightarrow\; b \sim a \; \checkmark

Step 3 — Transitive: Suppose a ~ b and b ~ c, so 3 divides (a − b) and 3 divides (b − c). Adding these two differences gives (a − c), which is also divisible by 3. Therefore a ~ c.

3 \mid (a - b) \text{ and } 3 \mid (b - c) \;\Rightarrow\; 3 \mid \big((a - b) + (b - c)\big) = (a - c) \;\Rightarrow\; a \sim c \; \checkmark

Step 4 — Equivalence classes: Every integer has remainder 0, 1, or 2 when divided by 3. The relation partitions the integers into three equivalence classes based on that remainder.

[0] = \{\ldots, -6, -3, 0, 3, 6, \ldots\}, \quad [1] = \{\ldots, -5, -2, 1, 4, 7, \ldots\}, \quad [2] = \{\ldots, -4, -1, 2, 5, 8, \ldots\}

Answer: Since the relation is reflexive, symmetric, and transitive, congruence modulo 3 is an equivalence relation. It partitions the integers into three equivalence classes: [0], [1], and [2].

Frequently Asked Questions

What is the difference between an equivalence relation and equality?

Equality is one specific equivalence relation — two things are related only if they are literally the same. An equivalence relation is more general: it groups elements that are 'alike' in some defined way. For instance, two integers can be different yet equivalent under mod 3 (like 2 and 8). Every equivalence relation behaves like equality within its own equivalence classes.

What are equivalence classes and how do they relate to equivalence relations?

An equivalence class is the set of all elements that are related to a given element. If ~ is an equivalence relation on a set S, the equivalence class of element a is

[a] = \{x \in S : x \sim a\}

. A key theorem states that the equivalence classes of any equivalence relation form a partition of S — they are non-empty, pairwise disjoint, and their union is all of S.

Equivalence Relation vs. Partial Order

Both are relations that are reflexive and transitive. The key difference is the second property: an equivalence relation is symmetric (if a ~ b then b ~ a), while a partial order is antisymmetric (if a ≤ b and b ≤ a, then a = b). Equivalence relations group elements into interchangeable classes; partial orders rank elements into a hierarchy.

Why It Matters

Equivalence relations appear throughout mathematics whenever you want to treat different objects as 'the same' for a particular purpose. Fractions are a familiar example:

\frac{1}{2}

and

\frac{2}{4}

are different pairs of numbers, but the equivalence relation on ordered pairs

(a,b) \sim (c,d)

iff

ad = bc

lets us treat them as the same rational number. In more advanced work, equivalence relations underpin constructions like modular arithmetic, quotient groups, and equivalence classes in geometry and topology.

Common Mistakes

Mistake: Checking only one or two properties and assuming the relation is an equivalence relation.

Correction: All three properties — reflexive, symmetric, and transitive — must hold. A relation can satisfy any two without satisfying the third. For example, 'is a sibling of' is symmetric and transitive but not reflexive (you are not your own sibling), so it is not an equivalence relation.

Mistake: Assuming that if a relation is not reflexive for some specific element, it might still be an equivalence relation.

Correction: Reflexivity must hold for every element in the set. Even one element failing a ~ a disqualifies the relation. Always verify the property universally, not just on a few test cases.

Related Terms

Relation — General concept that equivalence relations specialize
Reflexive Property of Equality — First required property of equivalence relations
Symmetric Property of Equality — Second required property of equivalence relations
Transitive Property of Equality — Third required property of equivalence relations
Modular Equivalence — Classic example of an equivalence relation
Cardinality — Equal cardinality defines an equivalence relation on sets