Let be a set. A relation on is a subset of .
consists of ordered pairs with . For those ordered pairs , we write or and say is related to .
Example: Let and define . Here:
Example: Let and let be a positive integer. Define , then:
Let be a set, and let be a relation on . Then is an equivalence relation if the following three properties hold :
Consider the two examples of relations in the previous section:
- Reflexivity: If , then for reflexivity we need . However, this is clearly not the case, so this relation is not reflexive.
- Symmetry: If , then for symmetry we need . Again, this is clearly not the case, so this relation is not symmetric.
- Transitivity: If , then for transitivity we need . This is clearly the case, as , so this relation is transitive.
- The relation is not an equivalence relation because not all three properties hold.
- Reflexivity: If , then for reflexivity, we need , which is clearly the case, so this relation is reflexive.
- Symmetry: If , then for symmetry, we need . Note that , so this relation is symmetric.
- Transitivity: If , then for transitivity we need . We have and . Therefore, , giving us , so this relation is transitive.
- The relation is an equivalence relation because all three properties hold.
Let be a set and an equivalence relation on . For , define
Thus, is the set of things that are related to . The subset of is called an equivalence class of . The equivalence classes of are the subsets as ranges over the elements of .
Example: Consider the equivalence relation
Some various equivalence classes are:
We claim that these are all the equivalence classes. For if is any integer, then with . Then , so , which is one of the classes listed above.