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