A relation on a set is called an equivalence relation if it is reflexive, symmetric, and transitive.
Two elements and that are related by an equivalence relation are called equivalent. The notation is often used to denote that and are equivalent elements with respect to a particular equivalence relation.
Let be an equivalence relation on a set The set of all elements that are related to an element of is called the equivalence class of . The equivalence class of with respect to is denoted by . When only one relation is under consideration, we can delete the subscript and write for this equivalence class.
In other words, if is an equivalence relation on a set , the equivalence class of the element is
If , then is called a representative of this equivalence class. Any element of a class can be used as a representative of this class. That is, there is nothing special about the particular element chosen as the representative of the class.
Cutting up a set into a bunch of different pieces is called partitioning the set.
A partition of a set, , is a collection, , of nonempty sets called the blocks of the partition such that
Shows that the equivalence classes of two elements of are either identical or disjoint.
Let be an equivalence relation on a set These statements for elements and of are equivalent:
(i)
(ii)
We first show that implies Assume that . We will prove that by showing and . Suppose . Then . Because and is symmetric, we know that . Furthermore, because is transitive and and , it follows that . Hence, . This shows that . The proof that is similar; it is left as an exercise for the reader.
Second, we will show that (ii) implies (iii). Assume that It follows that because is nonempty (because because is reflexive).
Next, we will show that (iii) implies ( ). Suppose that . Then there is an element with and In other words, and By the symmetric property, . Then by transitivity, because and , we have .
Because (i) implies (ii), (ii) implies (iii), and (iii) implies ( ), the three statements, (i), (ii)., and (iii), are equivalent.
Let be an equivalence relation on a set . The union of the equivalence classes of is all of , because an element of is in its own equivalence class, namely, . In other words,
In addition, from Theorem 1, it follows that these equivalence classes are either equal or disjoint,
So
when .
These two observations show that the equivalence classes form a partition of , because they split into disjoint subsets. More precisely, a partition of a set is a collection of disjoint nonempty subsets of that have as their union. In other words, the collection of subsets , (where is an index set) forms a partition of if and only if
for
when ,
and
(Here the notation represents the union of the sets for all .)
Let be an equivalence relation on a set . Then the equivalence classes of form a partition of . Conversely, given a partition of the set , there is an equivalence relation that has the sets , as its equivalence classes.