In the previous post we studied binary relations, their fundamental properties, and classified them into 8 types. Of all of these, the equivalence relation holds a special place: it is the mathematical tool for grouping elements that share a common characteristic, treating them as “equal” under some chosen criterion.
In this post we will go deeper into equivalence relations, discover how they generate equivalence classes and quotient sets, and prove the powerful Fundamental Theorem that ties these relations to partitions of a set. We will also see how this seemingly abstract concept has direct applications in computing, artificial intelligence, engineering, and everyday life.
Quick recap: equivalence relations
In the previous post we defined a relation \( R \) on a set \( A \) to be an equivalence relation when it satisfies three properties simultaneously:
| Property | Formal definition | What it means |
|---|---|---|
| Reflexive | \( \forall a \in A: (a,a) \in R \) | Every element is related to itself |
| Symmetric | \( (a,b) \in R \implies (b,a) \in R \) | If \( a \) is related to \( b \), then \( b \) is related to \( a \) |
| Transitive | \( (a,b) \in R \wedge (b,c) \in R \implies (a,c) \in R \) | If \( a \) relates to \( b \) and \( b \) to \( c \), then \( a \) relates to \( c \) |
Intuition. An equivalence relation generalizes the idea of equality: it groups elements that, under some criterion, are considered “the same thing.” Equality \( = \) is the most basic equivalence relation, but there are many others.
What goes wrong if a property is missing?
If a relation satisfies only two of the three properties, it is not an equivalence relation and cannot group elements cleanly:
| Properties present | Class | Example |
|---|---|---|
| Reflexive + Symmetric | Dependency | “know each other” — if Ana knows Bruno and Bruno knows Carlos, that doesn’t mean Ana knows Carlos; without transitivity, groups can overlap |
| Reflexive + Transitive | Preorder | \( \leq \) — without symmetry, there is hierarchy instead of equality |
| Symmetric + Transitive | — | Without reflexivity, some elements may belong to no group at all |
In short: An equivalence relation rules out three failure modes: groups with elements in common (overlap), groups nested inside other groups (hierarchy), and elements left out of every group (gaps).
Only the full combination of all three properties guarantees a perfect grouping — separate blocks, no gaps, each element falling into exactly one block under a shared criterion.
Examples of equivalence relations
In the examples below we use a relation matrix to display the ordered pairs. The rows and columns represent the elements of the set, and each cell contains:
- 1 if the pair \( (\text{row},\ \text{column}) \) belongs to the relation (true)
- 0 if it does not (false)
For example, for the set \( \{a, b\} \) with the relation \( R = \{(a, a),\ (a, b),\ (b, b)\} \):
| a | b | |
|---|---|---|
| a | 1 | 1 |
| b | 0 | 1 |
The cell in row \( a \), column \( b \) holds 1 because \( (a, b) \in R \), while the cell in row \( b \), column \( a \) holds 0 because \( (b, a) \notin R \).
With that in mind, here are the examples:
Example 1: an explicit relation on a finite set
Let \( S = \{1, 2, 3\} \) and the relation:
\[ R = \{(1, 1),\ (1, 2),\ (2, 1),\ (2, 2),\ (3, 3)\} \]
Checking the three properties:
- Reflexive: \( (1,1),\ (2,2),\ (3,3) \in R \) ✓
- Symmetric: \( (1,2) \in R \) and \( (2,1) \in R \) ✓; diagonal pairs are their own mirrors ✓
- Transitive: \( (1,2) \wedge (2,1) \implies (1,1) \in R \) ✓; \( (2,1) \wedge (1,2) \implies (2,2) \in R \) ✓
\( R \) is an equivalence relation. ✓
Its relation matrix:
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 0 | 0 | 1 |
Notice how the matrix forms square blocks of 1s along the diagonal. This visual pattern is characteristic of equivalence relations.
Example 2: equality
The relation \( = \) on any set is an equivalence relation:
- \( a = a \) ✓ (reflexive)
- \( a = b \implies b = a \) ✓ (symmetric)
- \( a = b \wedge b = c \implies a = c \) ✓ (transitive)
It is the finest possible equivalence relation: each element is equivalent only to itself.
Example 3: same parity
Let \( R \) be the relation on \( \mathbb{Z} \) defined by: \( aRb \) if \( a \) and \( b \) have the same parity (both even or both odd).
- Reflexive: Every number has the same parity as itself ✓
- Symmetric: If \( a \) has the same parity as \( b \), then \( b \) has the same parity as \( a \) ✓
- Transitive: If \( a \) and \( b \) are both even, and \( b \) and \( c \) are both even, then \( a \) and \( c \) are both even ✓ (same argument applies for odd)
\( R \) is an equivalence relation that splits \( \mathbb{Z} \) into exactly two groups: the even integers and the odd integers.
Numerical examples:
- \( 4R6 \) ✓ (both even)
- \( 3R7 \) ✓ (both odd)
- \( 4 \not{R} 3 \) ✗ (one even, one odd)
Example 4: difference is an integer
Let \( R \) be the relation on \( \mathbb{R} \) defined by \( aRb \) if and only if \( a – b \in \mathbb{Z} \).
- Reflexive: \( a – a = 0 \in \mathbb{Z} \) ✓
- Symmetric: If \( a – b \in \mathbb{Z} \), then \( b – a = -(a – b) \in \mathbb{Z} \) ✓
- Transitive: If \( a – b \in \mathbb{Z} \) and \( b – c \in \mathbb{Z} \), then \( a – c = (a – b) + (b – c) \in \mathbb{Z} \) ✓
What does this relation group together? Real numbers that differ by an integer: for instance, \( 3.7 R 0.7 R (-2.3) \), since all three share the same fractional part \( 0.7 \).
Example 5: geometric relations
| Relation | Set | Equivalence? | Criterion for “sameness” |
|---|---|---|---|
| Parallelism (\( \parallel \)) | Lines in the plane | ✓ | Same direction |
| Congruence (\( \cong \)) | Geometric figures | ✓ | Same shape and size |
| Similarity (\( \sim \)) | Geometric figures | ✓ | Same shape (size may differ) |
Example 6: a relation that is NOT an equivalence
Let \( R \) on \( \mathbb{R} \) be defined by \( xRy \) if \( |x – y| < 1 \).
- Reflexive: \( |x – x| = 0 < 1 \) ✓
- Symmetric: \( |x – y| = |y – x| \), so if \( |x – y| < 1 \) then \( |y – x| < 1 \) ✓
- Transitive: Take \( x = 2.8 \), \( y = 1.9 \), \( z = 1.1 \). Then \( |2.8 – 1.9| = 0.9 < 1 \) ✓ and \( |1.9 – 1.1| = 0.8 < 1 \) ✓, but \( |2.8 – 1.1| = 1.7 > 1 \) ✗
Not an equivalence relation because transitivity fails. Without it, groupings overlap with no clear boundaries.
Equivalent elements and notation
After working through several examples, we can formalize what it means for two elements to be “equivalent.”
Given two elements \( a \) and \( b \) of a set \( A \), we say \( a \) and \( b \) are equivalent under an equivalence relation \( R \) if \( (a, b) \in R \) — that is, if the relation connects them.
This is written formally as:
\[ a \sim b \]
read as “\( a \) is equivalent to \( b \)” or “\( a \) is related to \( b \).”
Notation. The symbol \( \sim \) is used in place of \( R \) when working with equivalence relations. So \( a \sim b \) is just another way to write \( (a, b) \in R \) or \( aRb \). We will use this notation from here on.
Applying this notation to the previous examples:
| Example | Equivalence | Meaning |
|---|---|---|
| Ex. 1 (finite set) | \( 1 \sim 2 \) | 1 and 2 belong to the same class in \( R \) |
| Ex. 2 (equality) | \( 7 \sim 7 \) | 7 equals itself |
| Ex. 3 (parity) | \( 4 \sim 6 \) | 4 and 6 are both even |
| Ex. 4 (integer difference) | \( 3.7 \sim 0.7 \) | \( 3.7 – 0.7 = 3 \in \mathbb{Z} \) |
| Ex. 5 (parallelism) | \( L_1 \sim L_2 \) | Lines \( L_1 \) and \( L_2 \) are parallel |
| Ex. 6 (not an equivalence) | \( 2.8 \not\sim 1.1 \) | \( R \) is not an equivalence — \( \sim \) cannot be used |
Take Example 3 (parity): we know \( 4 \sim 6 \) because both are even. But 4 is also related to 8, to 10, to 2, to 0… In fact, all even numbers are equivalent to each other. This means there is a complete set of numbers related to 4 — namely, all even integers. That set has a formal name, which is exactly what we study next.
Equivalence classes
As the parity example showed, an equivalence relation groups the elements of a set into subsets — all the even numbers on one side, all the odd numbers on the other. Each such subset is called an equivalence class. Here is the general definition:
Definition
Let \( \sim \) be an equivalence relation on a set \( A \). The equivalence class of an element \( a \in A \) is the set of all elements of \( A \) that are related to \( a \):
\[ [a] = \{x \in A \mid x \sim a\} \]
In plain terms: The class \( [a] \) contains every element that is “equivalent” to \( a \) — including \( a \) itself.
Any element \( b \in [a] \) is called a representative of the class. As we will see, any element of a class can serve as its representative — there is nothing special about the choice of \( a \).
Example 1: classes on a finite set
Going back to \( S = \{1, 2, 3\} \) with \( R = \{(1,1),\ (1,2),\ (2,1),\ (2,2),\ (3,3)\} \).
To find the class of each element, we look at which elements it is paired with in \( R \):
- Class of 1: Pairs involving 1: \( (1,1) \) and \( (1,2) \). So 1 is related to 1 and to 2. Therefore: \( [1] = \{1, 2\} \)
- Class of 2: Pairs involving 2: \( (2,1) \) and \( (2,2) \). So 2 is related to 1 and to itself. Therefore: \( [2] = \{1, 2\} \)
- Class of 3: Pairs involving 3: only \( (3,3) \). So 3 is only related to itself. Therefore: \( [3] = \{3\} \)
Notice that \( [1] = [2] = \{1, 2\} \) — since 1 and 2 are equivalent, they generate the same class. Meanwhile \( [3] = \{3\} \) forms its own class.
The distinct classes are \( \{1, 2\} \) and \( \{3\} \). Together they cover all of \( S \) without overlapping.
Note. Intuitively, “cover” means that uniting all the classes gives back the original set: \( \{1, 2\} \cup \{3\} = \{1, 2, 3\} = S \). For a deeper look at the concepts of covers and partitions, see the post on families of sets, where we develop these ideas in full.
Example 2: the parity classes
Returning to the parity relation from Example 3 above: \( aRb \) if \( a \) and \( b \) have the same parity. The classes are:
\[ [0] = \{\ldots, -4, -2, 0, 2, 4, \ldots\} = \text{even integers} \] \[ [1] = \{\ldots, -3, -1, 1, 3, 5, \ldots\} = \text{odd integers} \]
Every integer belongs to exactly one of these 2 classes. For instance:
- \( 8 \in [0] \) because 8 is even
- \( -7 \in [1] \) because \( -7 \) is odd
- \( [4] = [0] = [2] = [-6] \) — all even numbers generate the same class
Notice that the infinite set \( \mathbb{Z} \) is divided into just 2 classes.
Example 3: classes on a four-element set
Let \( A = \{a, b, c, d\} \) and the relation:
\[ R = \{(a,a),\ (b,b),\ (c,c),\ (d,d),\ (a,c),\ (c,a),\ (b,d),\ (d,b)\} \]
We verify that \( R \) is an equivalence relation (reflexive ✓, symmetric ✓, transitive ✓). The classes are:
\[ [a] = \{a, c\}, \quad [b] = \{b, d\}, \quad [c] = \{c, a\} = [a], \quad [d] = \{d, b\} = [b] \]
There are only two distinct classes: \( \{a, c\} \) and \( \{b, d\} \).
Fundamental properties of equivalence classes
Equivalence classes satisfy three properties that follow directly from the axioms of the relation:
Property 1. Every element belongs to its own class.
\[ \forall a \in A: a \in [a] \]
Proof: Since \( \sim \) is reflexive, \( a \sim a \), which by definition means \( a \in [a] \). In particular, no equivalence class can be empty. ∎
Property 2. Equivalent elements generate the same class.
\[ a \sim b \implies [a] = [b] \]
Proof: Suppose \( a \sim b \). We show \( [a] \subseteq [b] \) and \( [b] \subseteq [a] \).
Let \( x \in [a] \), so \( x \sim a \). Since \( a \sim b \) (hypothesis), transitivity gives \( x \sim b \), so \( x \in [b] \). This gives \( [a] \subseteq [b] \).
By the same argument with \( b \sim a \) (from symmetry), we get \( [b] \subseteq [a] \).
Therefore \( [a] = [b] \). ∎
Property 3. Two distinct classes are completely disjoint.
\[ [a] \neq [b] \implies [a] \cap [b] = \emptyset \]
Proof: We proceed by contradiction. Suppose \( [a] \cap [b] \neq \emptyset \). Then there exists \( y \in [a] \cap [b] \), meaning \( y \sim a \) and \( y \sim b \). By symmetry, \( a \sim y \). Applying transitivity with \( y \sim b \) gives \( a \sim b \). But by Property 2, this implies \( [a] = [b] \), contradicting the assumption that the classes are distinct. ∎
Visual summary. The three properties tell us that equivalence classes tile \( A \) perfectly: every element belongs to exactly one class, and the classes neither overlap nor leave gaps. This behavior has a name: partition.
Quotient set
Definition
Let \( \sim \) be an equivalence relation on \( A \). The collection of all distinct equivalence classes is called the quotient set of \( A \) by \( \sim \), denoted:
\[ A/ \negthinspace \sim \ = \{[a] \mid a \in A\} \]
In plain terms: The quotient set is a “new set” whose elements are not the original elements of \( A \), but rather the classes (the “groups”) that the equivalence forms. It is like shifting focus from individuals to families.
Example 1
With \( S = \{1, 2, 3\} \) and the relation above:
\[ S/ \negthinspace \sim \ = \{[1], [3]\} = \{\{1, 2\},\ \{3\}\} \]
The set \( S \) had 3 elements; the quotient \( S/ \negthinspace \sim \) has 2 elements (two classes). Valid sets of representatives include \( \{1, 3\} \) or \( \{2, 3\} \) — either choice works.
What are representatives? A representative is any element we choose to name a class. Since \( [1] = [2] = \{1, 2\} \), we can call this class “[1]” or “[2]” — both names refer to the same set. For the class \( \{3\} \), the only possible representative is 3. So one valid set of representatives is \( \{1, 3\} \), but \( \{2, 3\} \) works equally well.
Example 2
With \( A = \{a, b, c, d\} \) and the relation above:
\[ A/ \negthinspace \sim \ = \{[a], [b]\} = \{\{a, c\},\ \{b, d\}\} \]
Example 3: the quotient of the integers by parity
The parity relation on \( \mathbb{Z} \) produces the quotient set:
\[ \mathbb{Z}/ \negthinspace \sim \ = \{[0],\ [1]\} = \{\text{even integers},\ \text{odd integers}\} \]
The infinite set \( \mathbb{Z} \) is compressed down to a quotient with just 2 elements. Any even number works as a representative of the first class (\( [0] = [2] = [-4] \)), and any odd number for the second (\( [1] = [3] = [-7] \)).
Counting pairs in an equivalence relation
There is a useful formula for counting the total number of ordered pairs in an equivalence relation. If \( \sim \) divides a set of \( N \) elements into classes of sizes \( k_1, k_2, \ldots, k_m \), then:
\[ \text{Total number of pairs} = \sum_{i=1}^{m} k_i^2 \]
Why? Within each class of size \( k_i \), every element is related to every other (reflexively and symmetrically), generating a full grid of \( k_i \times k_i = k_i^2 \) pairs.
Example. In \( A = \{a, b, c, d\} \) with classes \( \{a, c\} \) and \( \{b, d\} \):
\[ k_1 = 2,\quad k_2 = 2 \implies \text{pairs} = 2^2 + 2^2 = 4 + 4 = 8 \]
Verification: \( R = \{(a,a), (c,c), (a,c), (c,a), (b,b), (d,d), (b,d), (d,b)\} \) has exactly 8 pairs. ✓
Note. It always holds that \( \sum_{i=1}^{m} k_i = N \) — the class sizes add up to the total number of elements.
Partitions
Imagine you have a group of 6 students and need to divide them into project teams. If you split them into three teams — \( \{\text{Ana, Luis}\} \), \( \{\text{Carlos, María}\} \), and \( \{\text{Pedro, Sofía}\} \) — you have created a partition: each student is in exactly one team, no team is empty, and together all teams account for every student. If any student ended up on two teams at once, or if any student was left out, it would no longer be a partition.
Note. For a deeper look at partitions and other types of families of sets (covers, chains, antichains), see the post on families of sets.
The concept of partition is closely tied to equivalence relations, which is why we revisit it formally below.
Definition
Let \( A \) be a nonempty set. A partition of \( A \) is a family of subsets \( \{A_i\}_{i \in I} \) satisfying three conditions:
| Condition | Name | Statement | What it means |
|---|---|---|---|
| P₁ | Non-emptiness | \( A_i \neq \emptyset \) for all \( i \in I \) | No subset in the family is empty |
| P₂ | Disjointness | \( A_i \cap A_j = \emptyset \) for all \( i \neq j \) | The subsets are pairwise disjoint |
| P₃ | Coverage | \( \bigcup_{i \in I} A_i = A \) | The union of all subsets reconstructs \( A \) |
In plain terms: A partition “cuts” \( A \) into non-overlapping pieces that together make the whole. Every element of \( A \) falls into exactly one piece.
Example 1: partition of a finite set
Let \( S = \{1, 2, 3, 4, 5, 6\} \). The family \( \{A_1, A_2, A_3\} \) with:
\[ A_1 = \{1, 2, 3\}, \quad A_2 = \{4, 5\}, \quad A_3 = \{6\} \]
is a partition of \( S \):
- P₁: \( A_1 \neq \emptyset \), \( A_2 \neq \emptyset \), \( A_3 \neq \emptyset \) ✓
- P₂: \( A_1 \cap A_2 = \emptyset \), \( A_1 \cap A_3 = \emptyset \), \( A_2 \cap A_3 = \emptyset \) ✓
- P₃: \( A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6\} = S \) ✓
Example 2: all partitions of a small set
Let \( A = \{a, b, c\} \). The possible partitions are:
| Partition | Blocks |
|---|---|
| \( P_1 \) | \( \{\{a\}, \{b\}, \{c\}\} \) — each element in its own block |
| \( P_2 \) | \( \{\{a, b\}, \{c\}\} \) |
| \( P_3 \) | \( \{\{a, c\}, \{b\}\} \) |
| \( P_4 \) | \( \{\{b, c\}, \{a\}\} \) |
| \( P_5 \) | \( \{\{a, b, c\}\} \) — the whole set as a single block |
There are exactly 5 partitions. This count is the third Bell number (\( B_3 = 5 \)). (See the post on families of sets for this concept.)
Note. Families such as \( \{\{a, b\}, \{b, c\}\} \) are not partitions because \( b \) appears in two subsets (violates P₂). Similarly, \( \{\{a\}, \{c\}\} \) is not a partition because \( b \) is missing (violates P₃).
Example 3: partitioning the universal set
Let \( A \) be a subset of a universe \( U \). The family \( \{A, A^c\} \) (where \( A^c \) is the complement of \( A \)) is a partition of \( U \), provided both \( A \) and \( A^c \) are nonempty:
- P₁: \( A \neq \emptyset \) and \( A^c \neq \emptyset \) ✓ (assuming \( A \neq \emptyset \) and \( A \neq U \))
- P₂: \( A \cap A^c = \emptyset \) ✓ (by definition of complement)
- P₃: \( A \cup A^c = U \) ✓
Example 4: partitioning an interval
Let \( I = [1, 3) \). We divide it into 5 equal subintervals of length \( \frac{3-1}{5} = \frac{2}{5} \):
\[ I_k = \left[1 + \frac{2}{5}(k-1),\ 1 + \frac{2}{5}k\right), \quad k = 1, 2, 3, 4, 5 \]
The family \( \{I_1, I_2, I_3, I_4, I_5\} \) is a partition of \( I \):
- Each \( I_k \neq \emptyset \) ✓
- The subintervals are pairwise disjoint (they don’t overlap) ✓
- Their union is \( [1, 3) = I \) ✓
The Fundamental Theorem
The most important result in this post establishes a perfect correspondence between two apparently different concepts.
Statement
Let \( A \) be a nonempty set.
(a) Every equivalence relation \( \sim \) on \( A \) induces a partition of \( A \), where the blocks are the equivalence classes.
(b) Every partition \( \{A_i\}_{i \in I} \) of \( A \) induces an equivalence relation on \( A \), where two elements are equivalent if and only if they belong to the same block.
In other words: equivalence relations and partitions are two sides of the same coin. Each one determines the other uniquely.
Proof of (a): from equivalence to partition
Let \( \sim \) be an equivalence relation on \( A \). We verify that the family of equivalence classes \( A/ \negthinspace \sim \) satisfies the three partition conditions:
P₁ (non-emptiness). For every \( a \in A \), the class \( [a] \neq \emptyset \) because \( a \in [a] \) (by Property 1 of equivalence classes). ✓
P₃ (coverage). Every element \( a \in A \) belongs to its class \( [a] \), so:
\[ \bigcup_{a \in A} [a] = A \]
That is, taking all equivalence classes and uniting them (\( [a_1] \cup [a_2] \cup \ldots \)) gives back the complete set \( A \). No element is left out. ✓
P₂ (disjointness). If \( [a] \neq [b] \), then \( [a] \cap [b] = \emptyset \) (by Property 3 of equivalence classes). ✓
Therefore \( A/ \negthinspace \sim \) is a partition of \( A \). ∎
Proof of (b): from partition to equivalence
Let \( \{A_i\}_{i \in I} \) be a partition of \( A \). Define the relation \( R \) on \( A \) by:
\[ x R y \iff \text{there exists } A_i \text{ such that } x \in A_i \text{ and } y \in A_i \]
That is, two elements are related if and only if they belong to the same block of the partition. We verify the three axioms:
Reflexive. Every \( a \in A \) belongs to some block \( A_i \) (by P₃), so \( a \) and \( a \) are in the same block. Therefore \( aRa \). ✓
Symmetric. If \( aRb \), then \( a \) and \( b \) are in the same block \( A_i \). But then \( b \) and \( a \) are also in the same block, so \( bRa \). ✓
Transitive. If \( aRb \) and \( bRc \), then \( a, b \in A_i \) for some block \( A_i \), and \( b, c \in A_j \) for some block \( A_j \). Since \( b \) belongs to both \( A_i \) and \( A_j \), and the blocks of a partition are pairwise disjoint (P₂), an element cannot belong to two distinct blocks. Therefore \( A_i = A_j \), and since \( a \) and \( c \) both lie in that same block, we conclude \( aRc \). ✓
Therefore \( R \) is an equivalence relation, and its equivalence classes are exactly the blocks \( A_i \). ∎
Example: building a relation from a partition
Given the partition \( A_1 = \{1, 2, 3\} \), \( A_2 = \{4, 5\} \), \( A_3 = \{6\} \) of \( S = \{1, 2, 3, 4, 5, 6\} \):
The induced equivalence relation contains the pairs \( (x, y) \) where \( x \) and \( y \) lie in the same block:
- From block \( \{1, 2, 3\} \): \( (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) \) — 9 pairs
- From block \( \{4, 5\} \): \( (4,4), (4,5), (5,4), (5,5) \) — 4 pairs
- From block \( \{6\} \): \( (6,6) \) — 1 pair
Total: \( 3^2 + 2^2 + 1^2 = 9 + 4 + 1 = 14 \) pairs. ✓
Its relation matrix:
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 1 | 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 1 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 |
Notice the square blocks of 1s along the diagonal — a 3×3, a 2×2, and a 1×1. Each block corresponds to one equivalence class (and to one block of the partition).
Example: the partition induced by parity
The parity relation splits \( \mathbb{Z} \) into 2 classes: even and odd. They form a partition:
- P₁ (non-emptiness): Both classes have infinitely many elements ✓
- P₂ (disjointness): No number is both even and odd ✓
- P₃ (coverage): Every integer is even or odd, so it belongs to one of the classes ✓
Takeaway from the Fundamental Theorem. This result gives us the freedom to think in terms of equivalences or partitions, whichever is more convenient. To verify a relation, check reflexivity, symmetry, and transitivity. To construct one, just define a partition — the equivalence relation comes along for free.
Applications of equivalence relations
Equivalence relations and partitions are far from purely theoretical — they appear across many disciplines. Here are some of their most practical and common applications:
1. Computing and programming
- Disjoint Set Union (DSU) data structure: Used to group elements and quickly determine whether two belong to the same set. It is central to algorithms like Kruskal’s, which finds the minimum spanning tree of a network.
- Database normalization: The normalization process partitions information to avoid redundancy, ensuring each piece of data sits in the “class” it belongs to based on its logical dependencies.
2. Mathematics and arithmetic
- Modular arithmetic: The foundation of modern cryptography. Two numbers are equivalent if they give the same remainder when divided by a modulus (like 12 on a clock face). This partitions all integers into a finite group of classes.
- Rational numbers: One half (\( \frac{1}{2} \)) and two quarters (\( \frac{2}{4} \)) are different representations of the same value. An equivalence relation lets us treat them as a single “number” even though they are written differently.
3. Artificial intelligence and data science
- Clustering (unsupervised learning): The goal is to produce a partition of a dataset where elements in the same group are “similar” to each other and different from elements in other groups.
- Natural language processing: Grouping words by their root (lemmatization) or grammatical role is, at its core, defining an equivalence relation.
4. Engineering and physics
- Dimensional analysis: Physical quantities that measure the same thing (such as all units of energy) can be grouped into equivalence classes, making it easier to simplify complex equations.
- Logic circuits: In hardware design, equivalent states in a finite state machine are grouped together to reduce the number of required components (automaton minimization).
5. Everyday life
- Classification systems: From biological taxonomy (species, genera) to organizing files on a computer — whenever you classify objects so that no object falls into two categories at once, you are creating a partition.
Solved exercises
Exercise 1: congruence modulo \( m \)
Let \( m \) be a fixed positive integer and \( a, b \in \mathbb{Z} \). We say \( a \) is congruent to \( b \) modulo \( m \), written:
\[ a \equiv b \pmod{m} \]
if \( m \) divides the difference \( a – b \), that is, \( m \mid (a – b) \).
Reminder. \( a \mid b \) (read “\( a \) divides \( b \)”) means that \( \frac{b}{a} \) is an exact integer with no remainder. For example: \( 4 \mid 12 \) because \( \frac{12}{4} = 3 \in \mathbb{Z} \), but \( 4 \nmid 10 \) because \( \frac{10}{4} = 2.5 \notin \mathbb{Z} \).
In plain terms: Two integers are congruent modulo \( m \) when they leave the same remainder upon division by \( m \).
What does “same remainder” mean? When we divide a number by \( m \), we use the formula \( a = mq + r \) (where \( 0 \leq r < m \)). If two numbers yield the same \( r \), they are congruent. For example, with \( m = 4 \):
| Number | Division | Quotient (\( q \)) | Remainder (\( r \)) |
|---|---|---|---|
| 11 | \( 11 = 4 \cdot 2 + 3 \) | 2 | 3 |
| 3 | \( 3 = 4 \cdot 0 + 3 \) | 0 | 3 |
Both leave remainder 3, so \( 11 \equiv 3 \pmod{4} \). Their difference \( 11 – 3 = 8 \) is divisible by 4 (\( 4 \mid 8 \)) — the two definitions are equivalent.
a) Prove that congruence modulo \( m \) is an equivalence relation.
Solution:
- Reflexive: \( a – a = 0 \) and \( m \mid 0 \) (because \( 0 = 0 \cdot m \)) ✓
- Symmetric: If \( m \mid (a – b) \), then \( a – b = km \) for some integer \( k \). Then \( b – a = (-k)m \), so \( m \mid (b – a) \) ✓
- Transitive: If \( m \mid (a – b) \) and \( m \mid (b – c) \), then \( a – b = km \) and \( b – c = lm \). Adding: \( a – c = (k + l)m \), so \( m \mid (a – c) \) ✓
Therefore congruence modulo \( m \) is an equivalence relation. ∎
b) Find the equivalence classes and the quotient set for \( m = 4 \).
Solution: There are exactly 4 possible remainders (0, 1, 2, 3), so there are 4 classes:
\[ [0]_4 = \{\ldots, -8, -4, 0, 4, 8, \ldots\} \] \[ [1]_4 = \{\ldots, -7, -3, 1, 5, 9, \ldots\} \] \[ [2]_4 = \{\ldots, -6, -2, 2, 6, 10, \ldots\} \] \[ [3]_4 = \{\ldots, -5, -1, 3, 7, 11, \ldots\} \]
The quotient set is \( \mathbb{Z}/ \negthinspace \sim \ = \{[0]_4, [1]_4, [2]_4, [3]_4\} \) — the infinite set \( \mathbb{Z} \) is compressed down to just 4 classes.
These classes form a partition of \( \mathbb{Z} \):
- P₁: Each class has infinitely many elements ✓
- P₂: The classes are disjoint (no integer has two distinct remainders when divided by 4) ✓
- P₃: Every integer has a remainder when divided by 4, so it belongs to some class ✓
Generalization. For any modulus \( m \), congruence modulo \( m \) produces exactly \( m \) equivalence classes: \( [0]_m, [1]_m, \ldots, [m-1]_m \). The parity example (Example 3 above) is the special case \( m = 2 \).
Exercise 2: quotient set modulo 5
Congruence modulo 5 on \( \mathbb{Z} \) (defined by \( a \sim b \) if \( 5 \mid (a – b) \)) is an equivalence relation (the proof is identical to Exercise 1).
Find the equivalence classes and the quotient set.
Solution: There are exactly 5 possible remainders (0, 1, 2, 3, 4), so there are 5 classes:
\[ [0]_5 = \{\ldots, -10, -5, 0, 5, 10, \ldots\} \] \[ [1]_5 = \{\ldots, -9, -4, 1, 6, 11, \ldots\} \] \[ [2]_5 = \{\ldots, -8, -3, 2, 7, 12, \ldots\} \] \[ [3]_5 = \{\ldots, -7, -2, 3, 8, 13, \ldots\} \] \[ [4]_5 = \{\ldots, -6, -1, 4, 9, 14, \ldots\} \]
The quotient set is \( \mathbb{Z}/ \negthinspace \sim \ = \{[0]_5, [1]_5, [2]_5, [3]_5, [4]_5\} \) — the infinite set \( \mathbb{Z} \) is compressed to just 5 classes.
Connection to modular arithmetic. The quotient set \( \mathbb{Z}/ \negthinspace \sim \) is the foundation of modular arithmetic: addition and multiplication can be performed on classes, and the result is independent of which representative you choose. For example, modulo 5: \( [3]_5 + [4]_5 = [7]_5 = [2]_5 \).
Exercise 3: building an equivalence relation from a partition
Given the partition \( \{\{1, 3, 5\},\ \{2, 4, 6\}\} \) of the set \( S = \{1, 2, 3, 4, 5, 6\} \), construct the induced equivalence relation and verify that it is indeed an equivalence relation.
Solution: By the Fundamental Theorem (direction b), two elements are related if and only if they belong to the same block. The blocks are:
- \( B_1 = \{1, 3, 5\} \) — the odd numbers
- \( B_2 = \{2, 4, 6\} \) — the even numbers
Building all ordered pairs within each block:
- From \( B_1 \): \( (1,1), (1,3), (1,5), (3,1), (3,3), (3,5), (5,1), (5,3), (5,5) \) — 9 pairs
- From \( B_2 \): \( (2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6) \) — 9 pairs
Total: \( 3^2 + 3^2 = 18 \) pairs.
Verification:
- Reflexive: \( (1,1), (2,2), (3,3), (4,4), (5,5), (6,6) \in R \) ✓
- Symmetric: For every \( (a,b) \) within a block, \( (b,a) \) is also there (both belong to the same block) ✓
- Transitive: If \( (a,b) \) and \( (b,c) \) are in \( R \), all three lie in the same block, so \( (a,c) \in R \) ✓
The result is an equivalence relation. The quotient set is \( S/ \negthinspace \sim \ = \{[1],\ [2]\} = \{\{1, 3, 5\},\ \{2, 4, 6\}\} \), which coincides with the original partition. ∎
Chapter summary
We started from the equivalence relation — a reflexive, symmetric, and transitive relation — and traced the structures it gives rise to. Throughout this post:
- We recalled the definition of an equivalence relation and examined what breaks when a property is missing
- We worked through 6 detailed examples, including parity, geometric relations, and a counterexample
- We defined equivalence classes \( [a] \) and proved their 3 fundamental properties: membership, class identity, and disjointness
- We built the quotient set \( A/!\sim \) as the collection of all distinct classes
- We defined partitions with their 3 conditions (non-emptiness, disjointness, coverage)
- We proved the Fundamental Theorem: equivalence relations and partitions are two sides of the same coin
- We explored applications in computing, mathematics, AI, engineering, and everyday life
- We worked through exercises on congruence modulo \( m \) and quotient sets
With these tools, we understand how equivalence relations organize any set into perfectly disjoint blocks, and how any such block decomposition generates an equivalence.
What’s coming next
With equivalence relations and partitions in hand, we are ready for the following topics in upcoming posts:
- Mathematical correspondences — We will develop in full the four conditions (existence/uniqueness of image and origin), with complete examples and arrow diagrams for each type of correspondence.
- Functions — We will study functions as a special type of correspondence, with their complete classification (injective, surjective, bijective), composition, inverses, and applications.
See you in the next post!