RelationsRelationsEquivalence relationsEquivalence classes

Relations

Relations

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:

Equivalence relations

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:

Equivalence classes

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.