Handout 7 Math 255
Relations
Winter 2002
Dr. M. P. M. M. McLoughlin
Definition
1: Let U1
and U2 be well defined universes.
Let us consider the product universe,
U1 ´ U2.
Let A Í
U1 and B ÍU2
. Let R Í
A ´ B. R is called a relation from A to B.
Definition
2: Let U1
and U2 be well defined universes.
Let us consider the product universe,
U1 ´ U2.
Let A Í
U1 and B ÍU2. Let R Í
A ´ B.
Let D = { x | there exists an ordered pair (x,
y) Î R}. D is called the domain of R.
Definition
3: Let U1
and U2 be well defined universes.
Let us consider the product universe,
U1 ´ U2.
Let A Í
U1 and B ÍU2. Let R Í
A ´ B.
Let C = { x | there exists an ordered pair (a,
x) Î R}. C is called the range of R.
Definition
4: Let U1
and U2 be well defined universes.
Let us consider the product universe,
U1 ´ U2.
Let A Í
U1 and B ÍU2. Let R Í
A ´ B. B is called the codomain of R.
Note
R can be empty, but then it is called the trivial relation and is not of
interest to us. So, let R ¹
Æ. This kind of relation is more interesting.
Claim
1: Let U1 and U2 be well
defined universes. Let us consider the
product universe,
U1 ´ U2. Let A Í
U1 and B ÍU2. Let R be a relation from A to B. It is the case that A ¹ Æ and
B ¹
Æ.
Homework:
prove or disprove the claim.
Definition
5: Let U
be a well defined universe Let us consider the product universe,
U ´ U. Let A Í
U. Let R Í A ´ A. R is called a relation from A to A or R is called a relation on A.
There are 4 properties of R (relations on a set
in general) we will investigate:
For
definitions 6 - 11 and claims 2 and 3 assume the premises:
Let U be a well defined universes.
Let us consider the product universe, U ´ U.
Let A Í
U.
Let R Í
A ´ A.
Definition
6 (reflexive):
R is said to be reflexive
if "
x Î A, (x ,x) Î
R and $
a Î A '
(a, a) Î
R. Note the existential part of the definition, this is to ensure that
reflexivity does not vacuously hold.
Definition
7 (symmetric):
R is said to be symmetric
if (x ,y) Î R Þ (y, x) Î
R.
Note
this definition is a conditional. It
does not mean that every ordered pair must be in the relation.
Definition
8 (antisymmetric):
R is said to be antisymmetric
if (x ,y) Î R Þ (y, x) Ï
R.
Note
this definition is a conditional. It
does not mean that every ordered pair must be in the relation.
Alternate
Definition 8 (antisymmetric): R is said to be antisymmetric if (x ,y) Î
R Ù (y, x) Î R
Þ x = y.
Claim
2: Definition 5 and alternate definition 5 are
logically equivalent.
Homework:
prove or disprove the claim.
Definition
9 (transitive):
R is said to be transitive if
(x ,y) Î
R Ù (y, z) Î R Þ (x, z) Î
R.
Note
this definition is a conditional. It
does not mean that every ordered pair must be in the relation and its symmetric
reflection must not be in the relation.
Definition
10: R is
said to be an equivalence relation if
R is reflexive, symmetric, and transitive.
Definition
11: R is
said to be a partial order if R is
reflexive, antisymmetric, and transitive.
Claim
3: There exist a relation on a set such that it
is both a partial order and an equivalence relation.
Homework:
prove or disprove the claim.
Definition
12: Let U1
, and U2 be well defined universes.
Let us consider the product universe,
U1 ´
U2. Let A Í U1 and B ÍU2. Let R Í
A ´ B. T = R-1 is called an inverse relation from
B to A, and it is a subset of B ´ A. Note also
that T Í
U2 ´
U1.
Definition
13: Let U1,
U2, and U3 be
well defined universes. Let us consider
the product universes, U1 ´
U2 and U2 ´ U3. Let A Í
U1, B ÍU2, D Í
U2, and C ÍU3. Let R Í
A ´ B.
Let S Í
D ´ C. T = 
is
called a composition relation from A
to C, and it is called the composition of S and R.
Note
the order matters since 
is not
well defined. The codomain of the first
relation must exist within the same universe as the domain of the second
relation. Now, it is most useful if the
domain of the second relation is a superset of the codomain of the first
relation. Many useful relations have this property.
Also,
note that the three universes are not really that intriguing since we can
create a new universe U4 = U1
È U2 È
U3 . This is nice since
having a common universe to work with allows for more interesting examples;
but, it is not necessary to have a common universe. Hence, always note the premises of a claim or problem!!!!
Definition
14: Let U
be a well defined universe. Let us
consider the product universe, U ´
U.
Let A Í
U, B ÍU, and C ÍU. Let R Í
A ´ B. Let S Í
B ´ C. T = 
is called a composition
relation from A to C, and it is called the composition of S and R.
Definition
15: Let U be a well defined universe. Let us consider the product universe, U ´ U.
Let A Í
U. Let R Í
A ´ A. Let R be an equivalence relation. Let a be an element of A.
The set B = {x | x Î A such that
(a, x) Î
R} is called the equivalence class of a
under R and is usually denoted as [a]R.
Claim
4: Let U be a well defined universe. Let us consider the product universe, U ´ U.
Let A Í
U. Let R Í A ´ A. Let R be an equivalence relation. Let a and b be elements of A.
[a]R = [b]R iff a Î [b]R.
Homework:
prove or disprove the claim.
Definition
16: Let U be a well defined universe. Let A Í U. Let W
ÍÃ(U).
W
is called an exhaustive collection over A if
ÈW = A
Definition
17: Let U be a well defined universe. Let F ÍÃ(U).
F
is called an collection of mutually
exclusive sets if "
X Î
F and "
Y Î F
it is the case that X Ç Y = Æ. Note that this means that each pair of sets
in the collection is disjoint.
Definition
18: Let U be a well defined universe Let A Í U. Let P
ÍÃ(U).
P
is called a partition of A
if 1) Æ
Ï P,
2) P
is an exhaustive collection, and
3)
P is a
collection of mutually exclusive sets.
Definition
19: Let U be a well defined universe. Let us consider the product universe, U ´ U.
Let A Í
U. Let R Í A ´ A. Let R be an equivalence relation. Let a be an element of A.
Consider Y
= {[a]R | a Î
A}. Y
is called the collection of equivalence
classes of A under R.
Y
is often written as A/R.
Claim
5: Let U be a well defined universe. Let us consider the product universe, U ´ U.
Let A Í
U. Let R Í A ´ A. Let R be an
equivalence relation. Let a be an
element of A.
Consider G
= {[a]R | a ( A}. G is a partition
of A.
Homework:
prove or disprove the claim.
Claim
6: Let U be a well defined universe. Let A Í U. Let
L
be a partition of A.
The relation
A/L
is an equivalence relation of A.
Homework:
prove or disprove the claim.
Definition
20: Let U be a well defined universe. Let A Í U. Let R Í
A ´ A. Let R
be a partial order on A. Let x Î
A and y Î
A. x and y are said to be comparable iff (x, y) Î
R or (y, x) Î
R.
Definition
21: Let U be a well defined universe. Let A Í U. Let R Í
A ´ A. Let R
be a partial order on A. R is said to be a total order or linear order
iff for every x Î A and y Î A, x and y
are comparable.
Claim
7: Let U = Q.
Consider the relation “£”
to be the usual (the defined less than or equal) on R. The relation, R Í Q
´ Q,
defined by R = {(x,y) | x £
y } is an equivalence relation on Q.
Homework:
prove or disprove the claim.
Claim
8: Let U = Q.
Consider the relation “<” to be the usual (the defined less than) on R. The relation, S Í Q
´ Q,
defined by S = {(x,y) | x < y } is a partial order on Q.
Homework:
prove or disprove the claim.
Claim
9: Let U = Z.
Consider the relation “£”
to be the usual (the defined less than or equal) on R. The relation, T Í Z´ Z,
defined by T = {(x,y) | x £
y } is an equivalence relation on Z.
Homework:
prove or disprove the claim.
Claim
10: Let U = Z.
Consider the relation “<” to be the usual (the defined less than) on R. The relation, W Í Z
´ Z,
defined by W = {(x,y) | x < y } is a partial order on Z.
Homework:
prove or disprove the claim.
Claim
11: Let U = N.
Let A = {1, 2, 3, 4}. Consider the
relation “Í”
to be the usual (the defined subset) on Ã(A). The relation, X Í Ã(A) ´ Ã(A), defined by
X = {(M, N) | M Í
N } is an equivalence relation on Ã(A).
Homework:
prove or disprove the claim.
Claim
12: Let U = N.
Let A = {1, 2, 3, 4}. Consider the
relation “Í”
to be the usual (the defined subset) on Ã(A). The relation, X Í Ã(A) ´ Ã(A), defined by
X = {(M, N) | M Í
N } is a partial order on Ã(A).
Homework:
prove or disprove the claim.