Graphics Reference
In-Depth Information
B.2
Set Theoretic Basics
Definition.
A
(binary) relation between sets
X
and
Y
is a subset
S
of the Cartesian
product
X
¥
Y
. If
X
=
Y
, then we call
S
a
relation on
X
. The notation x
S
y is often used
to denote the fact that (x,y) Œ
S
.
Definition.
Let
S
be a relation between sets
X
and
Y
. Define subsets dom(
S
) and
range(
S
), called the
domain
and
range
of
S
, respectively, by
()
=
{
}
dom
S
x
x y for some y in
S
Y
and
()
=
{
}
.
range
S
y
x y for some x in
S
X
The relation
S
is said to be
one-to-one
if x
1
S
y and x
2
S
y imply that x
1
= x
2
. The rela-
tion
S
is said to be
onto
Y
if for all y in
Y
there is an x in
X
so that x
S
y.
S
is said to
be
well defined
if x
S
y
1
and x
S
y
2
imply that y
1
= y
2
.
Definition.
Let
S
be a relation on a set
X
. Below are names and definitions of some
common properties such a relation may possess:
Reflexive
:
For all x Œ
X
, x
S
x
Symmetric
:
For all x, y Œ
X
, if x
S
y, then y
S
x
Antisymmetric
:
For all x, y Œ
X
, if x
S
y and y
S
x, then x = y
Transitive
:
For all x, y, z Œ
X
, if x
S
y and y
S
z, then x
S
z
Definition.
An
equivalence relation
on a set
X
is a reflexive, symmetric, and transi-
tive relation on
X
.
B.2.1. Example.
It is easy to show that the congruence relation ∫ on the set of inte-
gers is an equivalence relation.
The reason that equivalence relations play such an important role in mathemat-
ics is that they capture a fundamental concept.
B.2.2. Theorem.
Let
X
be a nonempty set.
(1) Given a relation
S
on
X
and x Œ
X
, define
{
}
.
S
=Œ
y
X
x y
S
x
If S is an equivalence relation, then each
S
x
is nonempty and
X
is the disjoint
union of these sets.
(2) Conversely, assume that
X
is the disjoint union of nonempty sets
A
a
. Define a
relation
S
on
X
by the condition that (x,y) Œ
S
if and only if both x and y
belong to
A
a
for some a. Then
S
is an equivalence relation.
