Quotient Sets and Partitions
The quotient set A/ρ consists of all equivalence classes of the set A under the relation ρ.
That is, all elements of A that belong to the same equivalence class [a] are represented collectively by the single element [a] in A/ρ.
The equivalence classes of A under ρ form what is known as a partition of the set.
What is a partition? A partition is a collection of non-empty subsets (called parts) of a set such that:
[1] The union of all the parts equals the original set: $$ \bigcup A_n = A $$
[2] The parts are pairwise disjoint: $$ A_a \cap A_b = \emptyset $$
Examples
Example 1
Let A = {1, 2, 3, 4}
Let F be a collection of subsets of A:
$$ F = \{ \{1\}, \{3,4\} \} $$
F is not a partition because it satisfies only two of the required three properties:
- F is non-empty
- The subsets in F are mutually disjoint
However, the union of these subsets does not cover the entire set A - the element 2 is missing.
Example 2
Again, let A = {1, 2, 3, 4}
And let F consist of the subsets:
$$ F = \{ \{1\}, \{3,4\}, \{2\} \} $$
This time, F is a valid partition because it satisfies all three conditions.
We can now state the fundamental theorem of equivalence relations:
- Given an equivalence relation ρ on a set A, the corresponding equivalence classes (i.e., the quotient set A/ρ) define a partition of A.
- Conversely, every partition of A determines an equivalence relation ρ, where each subset in the partition corresponds to a distinct equivalence class.
Proof
An equivalence relation always relates each element to itself: aρa.
Therefore, the equivalence class [a] always contains at least the element a.
This applies to every element x = b, c, d, … in A.
As a result, equivalence classes are either completely disjoint or identical.
If an element x belongs to both [a] and [b], then x is related to both a and b:
$$ x \rho a \\ x \rho b $$
By symmetry and transitivity, it follows that a is also related to b:
$$ a \rho x \land x \rho b \Rightarrow a \rho b $$
In the context of equivalence relations, this implies that [a] and [b] are the same class:
$$ a \rho b \Rightarrow [a] = [b] $$
So, whenever two classes have a non-empty intersection, they must be equal: [a] ⋂ [b] ≠ ∅ ⇒ [a] = [b]
- If [a] and [b] are disjoint, then [a] ⋂ [b] = ∅ ⇒ [a] ≠ [b]
- If [a] and [b] are not disjoint, then [a] ⋂ [b] ≠ ∅ ⇒ [a] = [b]
This shows that the equivalence classes defined by ρ on A satisfy all the defining properties of a partition:
- Each class is non-empty: by definition, it contains at least its own representative.
- The union of all classes in A/ρ equals A: combining all elements from every class reconstructs the full set A.
- The intersection of any two distinct classes is empty: if [a] ⋂ [b] ≠ ∅, then the two classes are actually the same.
Example
Let A be the set {1, 2, 3, 4}
$$ A = \{1, 2, 3, 4\} $$
Let F be the collection of subsets {1}, {2}, {3,4}:
$$ F = \{ \{1\}, \{3,4\}, \{2\} \} $$
We define an equivalence relation ρ on A such that:
$$ a \rho b $$
This means that a and b belong to the same subset of F:
$$ \forall a, b \in A,\quad a \rho b \Leftrightarrow \exists X \in F \text{ such that } \{a,b\} \subseteq X $$
The pairs of elements that satisfy this relation are:
$$ \rho_F = \{ (1,1), (2,2), (3,3), (4,4), (3,4), (4,3) \} $$
The quotient set A/ρ is made up of the following equivalence classes:
$$ A/\rho = \{ [1], [2], [3], [4] \} $$
Each class [x] includes all elements related to x:
$$ [1] = \{1\} \\ [2] = \{2\} \\ [3] = \{3, 4\} \\ [4] = \{3, 4\} $$
Note. Element 1 is only related to itself. The same is true for 2. Element 3 is related to both itself and 4 - and vice versa.
If we now express the quotient set in terms of sets of elements:
$$ A/\rho = \{ \{1\}, \{2\}, \{3,4\} \} $$
This quotient set A/ρ is identical to the partition F.
And so on.
