How to Prove an Equivalence Relation (With Step-by-Step Examples)
- Tyler Buffone
- Oct 6
- 5 min read
Updated: Oct 16
Why This Matters?
Relations are the language we use to compare mathematical objects. Two big families show up everywhere:
Equivalence relations: used for grouping things that are “the same in essence” even if they look different on the surface.
Order relations: used for arranging things from “smaller” to “larger” in a consistent, logical way.
This post gives you a clear, example-ready framework for understanding equivalence relations. Another post will go over order relations.
What is a Relation?
Let A be a set. A relation on A is any subset R ⊆ A × A. We write aRb when (a, b) ∈ R.
Core Properties of Relations
Suppose R is a relation on a set A (so R ⊆ A × A). To check whether R has certain properties, we always start with all elements of A, but the definition of the property (symmetry, antisymmetry, transitivity, etc.) is an implication, so you only need to check the cases where the premise holds.
Reflexive: every element relates to itself.
aRa for all a ∈ A.
Irreflexive: no element relates to itself.
never aRa for all a ∈ A.
Symmetric: whenever a is related to b, the reverse relation must also hold.
aRb ⇒ bRa.
Note: You don't check every pair blindly; you only check the ones where aRb is true.
Antisymmetric: if two elements relate in both directions, they must actually be the same element.
aRb and bRa ⇒ a = b.
Note: symmetric is not the opposite of antisymmetric; they talk about different implications.
Transitive: whenever a is related to b and b to c, it follows that a is related to c.
aRb and bRc ⇒ aRc.
Total (comparability): for any two elements, at least one relation holds.
For all a, b ∈ A, a = b, or aRb, or bRa.
Key Clarification
When you see "for all a, b, c ∈ A":
In reflexivity, irreflexivity, and totality, you must check all elements of A directly.
In symmetry, antisymmetry, and transitivity, you only check those cases where the premise is true.
Equivalence Relations
A relation ~ on A is an equivalence relation if it is:
Reflexive: a ~ a.
Symmetric: a ~ b ⇒ b ~ a.
Transitive: a ~ b and b ~ c ⇒ a ~ c.
~ captures "moral equality." It lets us treat different representatives as the same type of thing.
How to prove something is an equivalence relation
Use an "arbitrary elements + definition first" approach:
State the relation cleanly: "Define a ~ b if [insert condition here]."
Reflexive: Fix arbitrary a. Show the condition holds with a compared to itself.
Symmetric: Assume a ~ b. Manipulate the defining condition until you get the condition for b ~ a.
Transitive: Assume a ~ b and b ~ c. Combine the two conditions to reach the condition for a ~ c.
Conclude: All three properties hold, therefore ~ is an equivalence relation.
Avoid "example-checking" as a proof. You must argue for arbitrary a, b, c.
Equivalence Classes
Given an equivalence relation ~ on A, the equivalence class of a is
[a] = {x ∈ A : x ~ a}.
Here are some key facts you can cite quickly:
a ∈ [a].
a ~ b ⟺ [a] = [b]
a is not related to b ⟺ [a] ∩ [b] = ∅.
Partitions and the Quotient Set
The equivalence classes are pairwise disjoint and their union is all of A. So ~ partitions A. The collection of all classes is the quotient A/ ∼ = {[a] : a ∈ A}.
Note that this is not division. It's saying "we're grouping the set A according to the equivalence relation ~." So A/ ~ means "the set of all equivalence classes of A under ~."
An equivalence relation and a partition are two sides of the same coin:
Given a partition, you get an equivalence relation by saying "in the same block means equivalent."
Given an equivalence relation, you get a partition by grouping each element with all things equivalent to it.
Working Routine for Classes in Practice
Pick a representative a.
Describe all x that satisfy x ~ a.
If needed, choose a canonical representative for each class to talk about classes unambiguously.
Equivalence Relation Examples
Consider a relation on the real numbers defined by:
a ~ b if the difference b - a is a multiple of 2π
a) Show that this relation satisfies the conditions for an equivalence relation.
b) Describe what the elements of a single equivalence class represent.
Solution a)
Reflexivity
Take any real number x.
Compute x - x = 0. Since 0 = 2π ⋅ 0 with 0 ∈ ℤ, there exists an integer k (namely k = 0) such that:
x - x = 2πk
So x ~ x. Reflexivity is proven.
Symmetry
Take any x, y ∈ ℝ and assume x ~ y. By definition there exists an integer k such that:
y - x = 2πk
Multiply both sides by -1:
x - y = -2πk = 2π(-k)
Since -k is also an integer, there exists an integer k' (namely k' = -k) so that x - y = 2πk'.
So y ~ x. Symmetry is proven.
Transitivity
Take any x, y, z ∈ ℝ and assume x ~ y and y ~ z. There then exist integers k and k' such that:
y - x = 2πk and z - y = 2πk'.
Add the two equalities:
y - x + z - y = 2πk + 2πk'
z - x = 2π(k + k')
Since k + k' ∈ ℤ, there exists an integer k'' (namely k'' = k + k') with z - x = 2πk''.
So x ~ z. Transitivity is proven.
The relation is reflexive, symmetric, and transitive, so it is an equivalence relation.
Solution b)
For the relation:
a ~ b if b - a = 2πk for some k ∈ ℤ,
the equivalence class of a real number a is:
[a] = {x ∈ ℝ : x - a = 2πk for some k ∈ ℤ}.
Solve the defining condition for b: x - a = 2πk
x = a + 2πk
So every element in [a] looks like:
a + 2πk (k ∈ ℤ)
That is, every element in [a] is the arithmetic sequence:
..., a - 4π, a - 2π, a, a + 2π, a + 4π, ...
The intuition here is we are grouping angles that differ by full turns. All members of [a] land at the same spot on the unit circle (they're coterminal).
Remark: Why the equivalence class definition provided in this example matches the formal definition [a] = {x ∈ A : x ~ a}:
Take A = ℝ. For this relation, x ~ a if a - x = 2πk for some k ∈ ℤ. Because ~ is symmetric, x ~ a and a ~ x, and a ~ x means x - a = 2πk for some k ∈ ℤ. Hence, the display above is just the formal definition specialized to A = ℝ.
Need more help with Equivalence Relations? If you’re in Winnipeg and looking for a tutor, Tutor Advance provides expert one-on-one support!