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 :

Reflexivity:

Symmetry:

Transitivity:

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.

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.