Next: Isomorphism
Up: Relations and Functions
Previous: The Pigeonhole Principle
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:
- Reflexive Property: for every .
- Symmetric Property: If then .
- Transitive Property: If and then .
Which of the following are equivalence relations? Why or why not?
- X is the set of real numbers, and if and only if x
actually equals y.
- X is the set of all real numbers, and if and only if x<y.
- X is the set of integers, and n is a fixed positive integer.
if and only if n is a divisor of y-x.
- 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.
- X is the set of all natural numbers, and if and only
if x and y have no common divisor greater than 1.
- X is the set of ordered pairs of integers, and
if and only if and .
- X is the set of all ordered pairs (a,b) of integers, and
if and only if .
- X is the set of all ordered pairs (a,b) of integers for
which , and
if and only if .
- 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 .
- 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