Equivalence Classes and Partitions

Set Theory · Axiom Academy

The building blocks of quotient structures 1. Definition of Equivalence Class Let R be an equivalence relation on set A. For any element a  A, the equivalence class of a is: This is the set of all elements related to a. We call a a representative of the class [a]. Notation: [a],
, or [a] R all denote the equivalence class of a. 2. Key Property: [a] = [b] aRb Two equivalence classes are either identical or disjoint : This means every element belongs to exactly one equivalence class, and any element in a class can serve as its representative. Example: In congruence mod 5, [2] = [7] = [12] = ... since 2 a 7 a 12 (mod 5). 3. Equivalence Classes are Disjoint For any two elements a and b in A, either: 1. [a] = [b] (the classes are identical), or 2. [a] ) [b] =  (the classes share no elements) Proof sketch: Suppose x  [a] ) [b]. Then xRa and xRb. By symmetry and transitivity, aRb, so [a] = [b]. This is why equivalence classes form a partition: they cover all of A without overlapping. The quotient set (or factor set) A/R is the set of all equivalence classes: This is a set whose elements are themselves sets (the equivalence classes). A/R represents the original set A "viewed through the lens" of the equivalence relation R. Example: For congruence mod n, the quotient set /a n has exactly n elements: [0], [1], ..., [n-1]. 5. Example: /a Has Three Classes For congruence modulo 3 on the integers: The quotient set is /a = [0], [1], [2] . We often write this as or /3 .

This is the written version of the interactive lesson above. See the full Set Theory course.