Next: Isomorphism Up: Relations and Functions Previous: The Pigeonhole Principle

Equivalence Relations

Now back to relations. Sometimes, to make notation easier, we may write instead of for a relation S.

Suppose S is a relation between X and itself; i.e., a subset of . S is called an equivalence relation if the following three properties hold:

1. Reflexive Property: for every .
2. Symmetric Property: If then .
3. Transitive Property: If and then .

Which of the following are equivalence relations? Why or why not?

1. X is the set of real numbers, and if and only if x actually equals y.
2. X is the set of all real numbers, and if and only if x<y.
3. X is the set of integers, and n is a fixed positive integer. if and only if n is a divisor of y-x.
4. X is the set of all natural numbers, and if and only if the fraction x/y, when ``reduced'' becomes a fraction a/b in which both the numerator and the denominator are odd.
5. X is the set of all natural numbers, and if and only if x and y have no common divisor greater than 1.
6. X is the set of ordered pairs of integers, and if and only if and .
7. X is the set of all ordered pairs (a,b) of integers, and if and only if .
8. X is the set of all ordered pairs (a,b) of integers for which , and if and only if .
9. X is the set of all ordered pairs (a,b) of real numbers, excluding the ordered pair (0,0), and if and only if there is a nonzero real number k such that .
10. X is the set of all ordered pairs (a,b) of real numbers, and if and only if there is a real number k such that .

Whenever you have an equivalence relation on a set X, you can partition the elements of X into subsets, such that a is in subset T if and only if T consists of all elements of X equivalent to a. These subsets are called the equivalence classes of the equivalence relation. Conversely, whenever you have a partition of a set X into the union of mutually disjoint subsets, then you can define a equivalence relation on X by declaring if and only if a and b belong to the same subset of the partition. (Try to prove these statements.)

Next: Isomorphism Up: Relations and Functions Previous: The Pigeonhole Principle

Carl Lee
Wed Sep 30 08:36:10 EDT 1998