Ch 4. Relations
4.6 Partitions and Equivalent Classes and Closure of Relations
Let [latex]\mathcal{A}[/latex] be a collection of sets. The union of all sets in [latex]\mathcal{A}[/latex], denoted by [latex]\bigcup_{A \in \mathcal{A}}A[/latex], is the set of all elements that belong to at least one set in [latex]\mathcal{A}[/latex]. Formally,
[latex]\bigcup_{A \in \mathcal{A}}A = \{x \mid \exists A \in \mathcal{A}[/latex] such that [latex]x \in A \}[/latex]
Example 4.100
Let [latex]\mathcal{A} = \{ \{ 1, 2 \} , \{ 2, 3 \} , \{ 4 \} \}[/latex]. Then [latex]\bigcup_{A \in \mathcal{A}}A = \{1, 2, 3, 4 \}[/latex].
The intersection of all sets in [latex]\mathcal{A}[/latex], denoted by [latex]\bigcap_{A \in \mathcal{A}}A[/latex]is the set of all elements that belong to every set in [latex]\mathcal{A}[/latex]. Formally,
[latex]\bigcap_{A \in \mathcal{A}}A = \{x \mid \forall A \in \mathcal{A}[/latex] such that [latex]x \in A \}[/latex]
Example 4.101
Let [latex]\mathcal{A} = \{ \{ 1, 2, 3 \} , \{ 2, 3, 4 \} , \{ 2, 3 \} \}[/latex]. Then [latex]\bigcap_{A \in \mathcal{A}}A = \{2, 3 \}[/latex].
When using notation for unions and intersections, the union [latex]\bigcup_{i \in I} A_{i}[/latex] means the union of all sets [latex]A_{i}[/latex] indexed by [latex]i \in I[/latex]. The intersection [latex]\bigcap_{i \in I} A_{i}[/latex] means the intersection of all sets [latex]A_{i}[/latex] indexed by [latex]i \in I[/latex].
Example 4.102
Let [latex]A_{i} = \{ i, i + 1, i + 2 \}[/latex] for [latex]i = 1, 2, 3[/latex]. Then [latex]\bigcup^{3}_{i=1} A_{i} = \{ 1, 2, 3, 4, 5 \}[/latex] and [latex]\bigcap^{3}_{i=1} A_{i} = \{ 3 \}[/latex].
A collection of subsets of a set is pairwise disjoint if every pair of different subsets in the collection has an empty intersection. That is, for a collection of subsets [latex]\{ A_{1}, A_{2}, \dots, A_{n} \}[/latex] of a set [latex]X[/latex],
[latex]\forall i \neq j, A_{i} \cap A_{j} = \emptyset[/latex]
Example 4.103
Let [latex]X = \{ 1, 2, 3, 4, 5, 6 \}[/latex] and consider the subsets [latex]A_{1} = \{ 1, 2 \}[/latex], [latex]A_{2} = \{ 3, 4 \}[/latex], [latex]A_{3} = \{ 5, 6 \}[/latex]. Then [latex]\{ A_{1}, A_{2}, A_{3} \}[/latex] is a pairwise disjoint collection because [latex]A_{1} \cap A_{2} = \emptyset[/latex], [latex]A_{1} \cap A_{3} = \emptyset[/latex], and [latex]A_{2} \cap A_{3} = \emptyset[/latex].
A partition divides a set into distinct, non-overlapping parts that together include every element exactly once. Formally, we let [latex]X[/latex] be a non-empty set. Then a partition of [latex]X[/latex] is a collection of non-empty subsets [latex]\{ A_{i} \}_{i \in I}[/latex] such that
- [latex]A_{i} \neq \emptyset[/latex] for all [latex]i \in I[/latex] (no subset is empty)
- [latex]\bigcup_{i \in I} A_{i} = X[/latex] (the union of all subsets covers the entire set)
- [latex]A_{i} \cap A_{j} = \emptyset[/latex] for all [latex]i \neq j[/latex] (the subsets are pairwise disjoint)
Example 4.104
Let [latex]X = \{ 1, 2, 3, 4, 5, 6 \}[/latex]. Then [latex]\mathcal{P} = \{ \{1, 2 \}, \{ 3, 4 \}, \{ 5, 6 \} \}[/latex] is a partition of X.
The following theorem (a partition induces an equivalence relation) is important because it shows that every partition of a set defines an equivalence relation, and vice versa. This connection allows us to rigorously group elements that are “equivalent” in some way, which is fundamental in mathematics, computer science, and data organization.
Theorem 4.4: Partition Induces an Equivalence Relation
Let [latex]\mathcal{P}[/latex] be a partition of a set [latex]X[/latex]. Define a relation [latex]R[/latex] on [latex]X[/latex] by
[latex]x \; R \; y[/latex] if and only if [latex]\exists P \in \mathcal{P}[/latex] such that [latex]x \in P[/latex] and [/latex]y \in P[/latex]
Then [latex]R[/latex] is an equivalence relation.
Proof
Recall from Section 4.5 that a relation [latex]R[/latex] on a set [latex]X[/latex] is an equivalence relation if it is reflexive, symmetric, and transitive.
For any [latex]x \in X[/latex], since [latex]\mathcal{P}[/latex] is a partition, [latex]x \in P[/latex] for some [latex]P \in \mathcal{P}[/latex]. So, [latex]x \; R \; x[/latex] and hence [latex]R[/latex] is reflexive.
Suppose [latex]x \; R \; y[/latex]. Then [latex]x, y \in P[/latex] for some [latex]P \in \mathcal{P}[/latex]. So, [latex]y, x \in P[/latex], hence [latex]y \; R \; x[/latex]. So, [latex]R[/latex] is symmetric.
Suppose [latex]x \; R \; y[/latex] and [latex]y \; R \; z[/latex]. Then [latex]x, y \in P_{1}[/latex] and [latex]y, z \in P_{2}[/latex] for some [latex]P_{1}, P_{2} \in \mathcal{P}[/latex]. Since [latex]y \in P_{1} \cap P_{2}[/latex] and the sets in [latex]\mathcal{P}[/latex] are disjoint, [latex]P_{1} = P_{2}[/latex]. So, [latex]x, z \in P_{1}[/latex], hence [latex]x \; R \; z[/latex]. So, [latex]R[/latex] is transitive.
[latex]\square[/latex]
Example 4.105
Let [latex]X = \{ 1, 2, 3, 4, 5, 6 \}[/latex] and define a partition [latex]\mathcal{P} = \{ \{1, 2 \}, \{ 3, 4 \}, \{ 5, 6 \} \}[/latex].
Define a relation [latex]R[/latex] on [latex]X[/latex] such that [latex]x \; R \; y[/latex] if and only if [latex]x[/latex] and [latex]y[/latex] are in the same subset of [latex]\mathcal{P}[/latex].
Then [latex]R = \{ (1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4), (5, 5), (5, 6), (6, 5), (6, 6) \}[/latex], which is reflexive, symmetric, and transitive, and hence an equivalence relation.
We often need to divide a set into distinct, non-overlapping groups of related elements. The next theorem is important because it guarantees that any equivalence relation can achieve this.
Theorem 4.5: Equivalence Relation Induces a Partition
Let [latex]R[/latex] be an equivalence relation on a set [latex]X[/latex]. For each [latex]a \in X[/latex], define the equivalence class
[latex][a] = \{ x \in X \mid x \; R \; a \}[/latex]
Then the set [latex]\mathcal{P} = \{ [a] \mid a \in X \}[/latex] is a partition of [latex]X[/latex].
Proof
To prove that [latex]\mathcal{P}[/latex] is a partition of [latex]X[/latex], we break the proof into the following steps:
- Each equivalence class is non-empty.
- The union of all equivalence classes is [latex]X[/latex].
- The equivalence classes are pairwise disjoint.
Step 1: Let [latex]a \in X[/latex]. Since [latex]R[/latex] is reflexive, [latex]a \; R \; a[/latex]. Therefore, [latex]a \in [a][/latex], so each equivalence class contains at least one element.
Step 2: Let [latex]x \in X[/latex]. Since [latex]R[/latex] is reflexive, [latex]x \; R \; x[/latex], so [latex]x \in [x][/latex]. Thus, every element of [latex]X[/latex] belongs to at least one equivalence class. Hence, [latex]\bigcup_{a \in X}[a] = X[/latex].
Step 3: Suppose [latex][a] \cap [b] \neq \emptyset[/latex]. Then there exists some [latex]x \in X[/latex] such that [latex]x \in [a][/latex] and [latex]x \in [b][/latex]. So, [latex]x \; R \; a[/latex] and [latex]x \; R \; b[/latex].
Since [latex]R[/latex] is symmetric, [latex]a \; R \; x[/latex] and since [latex]R[/latex] is transitive, [latex]a \; R \; b[/latex]. Now take any [latex]y \in [a][/latex]. Then [latex]y \; R \; a[/latex], and since [latex]a \; R \; b[/latex], by transitivity, [latex]y \; R \; b[/latex], so [latex]y \in [b][/latex]. Thus, [latex][a] \subseteq [b][/latex].
Similarly, any [latex]z \in [b][/latex] satisfies [latex]z \; R \; b[/latex], and since [latex]b \; R \; a[/latex], [latex]z\; R \; a[/latex], so [latex]z \in [a][/latex]. Thus, [latex][b] \subseteq [a][/latex].
Therefore, [latex][a] = [b][/latex]. So, if two equivalence classes intersect, they are equal. Hence, all equivalence classes are either disjoint or identical.
[latex]\square[/latex]
Given an equivalence relation [latex]R[/latex] on a set [latex]X[/latex], the equivalence class of an element [latex]a \in X[/latex] is
[latex][a] = \{ x \in X \mid x \; R \; a \}[/latex]
Example 4.106
Let [latex]x = \{ 1, 2, 3, 4, 5, 6 \}[/latex] and define [latex]x \; R \; y[/latex] if and only if [latex]x \equiv y \text{ mod } 3[/latex].
Then the equivalence classes are [latex][0] = \{ 3, 6 \}[/latex], [latex][1] = \{ 1, 4 \}[/latex], and [latex][2] = \{ 2, 5 \}[/latex].
We sometimes need to calculate how many distinct groups a set is divided into when each group has the same number of elements. This requires finding the number of equivalence classes as outlined by the next theorem.
Theorem 4.6: Number of Equivalence Classes
Let [latex]R[/latex] be an equivalence relation on a finite set [latex]X[/latex]. If each equivalence class has exactly [latex]r[/latex] elements, then the number of equivalence classes is [latex]\frac{|X|}{r}[/latex].
Proof
Since [latex]R[/latex] partitions [latex]X[/latex] into disjoint equivalence classes, and each class has [latex]r[/latex] elements, the total number of elements in [latex]X[/latex] is the sum of the sizes of the classes. Let [latex]n[/latex] be the number of equivalence classes. Then
[latex]|X| = n \cdot r \rightarrow n = \frac{|X|}{r} \quad[/latex]
[latex]\square[/latex]
Example 4.107
The equivalence classes in Example 4.106 each have exactly [latex]r = 2[/latex] elements, and the total number of elements in [latex]X[/latex] is [latex]|X| = 6[/latex]. By Theorem 4.6, the number of equivalence classes is
[latex]\frac{|X|}{r} = \frac{6}{2} = 3[/latex]
So, there are three equivalence classes, which match our result.
A relation may not initially have certain properties (reflexivity, symmetry, transitivity), but we can extend it to the smallest relation that does; this process is called closure. This enables work with incomplete or partial data while preserving logical consistency and facilitating further analysis or computation.
The reflexive closure of a relation [latex]R[/latex] is the smallest reflexive relation containing [latex]R[/latex]. We write the reflexive closure as [latex]R^{+} \supseteq R[/latex], where [latex]R^{+}[/latex] is reflexive and construct it by adding all missing pairs [latex](a, a)[/latex] for [latex]a \in A[/latex] to [latex]R[/latex].
Example 4.108
Let [latex]R = \{ (1, 2), (2, 3) \}[/latex] on [latex]A = \{ 1, 2, 3 \}[/latex]. The reflexive closure is [latex]R^{+} = R \cup \{ (1, 1), (2, 2), (3, 3) \}[/latex]
The symmetric closure of a relation [latex]R[/latex] is the smallest symmetric relation containing [latex]R[/latex]. It is constructed by looking at every [latex](a, b) \in R[/latex] and adding [latex](b, a)[/latex] if not already present.
Example 4.109
Let [latex]R = \{ (1, 2), (2, 3) \}[/latex]. The symmetric closure is [latex]R^{+} = \{ (1, 2), (2, 1), (2, 3), (3, 2) \}[/latex].
The transitive closure of a relation [latex]R[/latex] is the smallest transitive relation containing [latex]R[/latex]. It is constructed by adding [latex](a, c)[/latex] whenever [latex](a, b) \in R[/latex] and [latex](b, c) \in R[/latex].
Example 4.110
Let [latex]R = \{ (1, 2), (2, 3) \}[/latex]. The transitive closure is [latex]R^{+} = \{ (1, 2), (2, 3), (1, 3) \}[/latex].
In practice, closures are computed using iterative or matrix-based algorithms. Warshall’s Algorithm is commonly used to compute the transitive closure of a relation represented as a matrix.
Programming Example 4.1 (Pseudocode)
Input: Matrix M of size n x n
for k from 1 to n:
for i from 1 to n:
for j from 1 to n:
M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])
This algorithm ensures that if there is a path from [latex]i[/latex] to [latex]j[/latex] through [latex]k[/latex], then [latex](i, j)[/latex] is added to the relation.
To show that a closure of a relation is both minimal and unique, we rely on formal definitions and logical reasoning. A closure of a relation [latex]R[/latex] is minimal if it is the smallest relation that satisfies the desired property (reflexivity, symmetry, or transitivity).
Example 4.111
If we remove [latex](1, 3)[/latex] from the transitive closure in Example 4.110, the relation is no longer transitive. Therefore, the closure is minimal.
A closure of a relation [latex]R[/latex] is unique if there is only one minimal relation that contains [latex]R[/latex] and satisfies the desired property (reflexivity, symmetry, or transitivity).
Example 4.112
Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]R = \{ (1, 2) \}[/latex]. The reflexive closure must include
[latex]R^{+} = \{ (1, 2), (1, 1), (2, 2), (3, 3) \}[/latex]
Any reflexive relation on [latex]A[/latex] must include all [latex](a, a)[/latex] for [latex]a \in A[/latex]. No other minimal reflexive relation containing [latex]R[/latex] can exist. Hence, the reflexive closure is unique.
Real-World Example 4.6: University Course Enrollment System
The postsecondary institution you study at needs to track which students are enrolled in the same course. This is done by letting the set [latex]X[/latex] be all students, and defining a relation [latex]R[/latex] such that
[latex]x \; R \; y[/latex] if and only if student [latex]x[/latex] and student [latex]y[/latex] are enrolled in the same course
The relation [latex]R[/latex] is reflexive, since every student is in the same course as themselves. It is symmetric, since if [latex]x[/latex] is in the same course as [latex]y[/latex], then [latex]y[/latex] is in the same course as [latex]x[/latex]. It is transitive, since if [latex]x[/latex] is in the same course as [latex]y[/latex], and [latex]y[/latex] is in the same course as [latex]z[/latex], then [latex]x[/latex] is with [latex]z[/latex]. Therefore, [latex]R[/latex] is an equivalence relation.
Each equivalence class corresponds to a group of students enrolled in the same course. If we look at the set of all such equivalence classes, they form a partition of the student population, with each subset representing a course group.
When the data is collected, it may initially be incomplete, with only some student pairs known. Computing the transitive closure ensures that all indirect relationships are captured, that is, students in the same courses are captured via others.
