MODULE
FIVE
PROBLEM
SET
1
Directions:
Type
your
solutions
into
this
document
and
be
sure
to
show
all
steps
for
arriving
at
your
solution.
Just
giving
a
final
number
may
not
receive
full
credit.
P
ROBLEM
1
Indicate
whether
the
two
functions
are
equal.
If
the
two
functions
are
not
equal,
then give an element of the domain on which the two functions have
different values.
(a)
f
:
Z
→
Z
,
where
f
(x)
=
x
2
.
g
:
Z
→
Z
,
where
g(x)
=
|
x
|
2
.
(b)
•
Both
functions
are
a
positive
value.x
2
is
positive
and
x
|
2
|
can
never
be
negative.
f
:
Z
×
Z
→
Z
,
where
f
(x,
y)
=
|
x
+
y
|
.
g : Z × Z → Z, where g(x, y) =
|x| + |y|.
•
These
two
functions
are
not
equal.
•
Proof:
Let
x
=
-2
and
y
=
2
f
(x,
y)
d
=
d d
|
2
−
2
|
d
=
d
0
g(x,
y)
=
|
2
|
+
|
2
−
2
|
=
2
as:
P
ROBLEM
2
The
domain
and
target
set
of
functions
f
and
g
is
R
.
The
functions
are
defined
•
f
(x)
=
2x
+
3
•
g(x)
=
5x
+
7
(a)
f ◦ g?
f
(g(x))
=
f
(5x
+
7)
=
2(5x
+
7)
+
3
=
10x
+
14
+
3
f
◦
g
=
10x
+
17
(b)
g ◦ f ?
g(f
(x))
=
g(2x
+
3)
=
5(2x
+
3)
+
7
=
10x
+
15
+
7
g
◦
f
=
10x
+
22
(c)
(f
◦
g)
−
1
?
y
=
10x
+
17
⇒
x
=
10y
−
17
Thus
x
=
(f
◦
g)
−
1(y)
=
10y
−
17
(f
◦
g)
−
1(x)
=
10x
−
17
(d)
f
−
1
◦
g
−
1
?
(f
−
1
◦
g
−
1)(x)
=
−
1(g
−
1(x))
=
f
−
1(5x
7)
=
25x
7
3
= 25x − 7 − 15 = 10x − 22
(e)
g
−
1
◦
f
−
1
?
(g
−
1
◦
f
−
1)(x)
=
g
−
1(f
−
1)(x))
= g − 1(2x − 3) = 52x − 3 − 7
= 52x − 3 − 14 = 10x − 17
Are
any
of
the
above
equal?
(f ◦ g)-1 = g-1 ◦ f-1
are
equal
P
ROBLEM
3
(a)
Give
the
matrix
representation
for
the
relation
depicted
in
the
arrow
dia-
gram.
Then,
express
the
relation
as
a
set
of
ordered
pairs.
The
arrow
diagram
below
represents
a
relation.
Figure
1:
An
arrow
diagram
shows
three
vertices,
1,
2,
and
3.
An
arrow
from
vertex
1
points
to
vertex
3,
and
another
arrow
from
vertex
2
points
to
vertex
3.
Two
self
loops
are
formed,
one
at
vertex
1
and
another
at
vertex
2.
•
R
=
(1,
1);
(1,
3);
(2,
2);
(2,
3)
1 d 0
0 1 1
0 d 0 d d 0
(b)
Draw
the
arrow
diagram
for
the
relation.
The
domain
for
the
relation
A
is
the
set
{
2,
5,
7,
8,
11
}
.
For
x,
y
in
the
domain, xAy if |x − y| is less than 2.
1
P
ROBLEM
4
For
each
relation,
indicate
whether
the
relation
is:
•
Reflexive,
anti-reflexive,
or
neither
•
Symmetric,
anti-symmetric,
or
neither
•
Transitive
or
not
transitive
Justify
your
answer.
(a)
The
domain
of
the
relation
L
is
the
set
of
all
real
numbers.
For
x,
y
∈
R
,
xLy
if
x
<
y.
•
For x ∈ R x ¡ x will be d false because (x,x) do not belong to L
•
Because
of
this,
L
is
anti-reflective
(b)
The
domain
of
the
relation
A
is
the
set
of
all
real
numbers.
xAy
if
|
x
−
y
|
≤
2
•
For
every
x
∈
R
it
is
true
that
—x
-
x—
=
0
≤
2
•
This
would
mean
that
(x,x)
does
belong
to
A,
also
meaning
that
A
isreflective
and
not
anti-reflective.
(c)
The
domain
of
the
relation
Z
is
the
set
of
all
real
numbers.
xZy
if
y
=
2x
•
For
every
x
∈
R
x
=
2x
is
false
and
(x,x)
does
not
belong
to
Z.
•
This
means
that
Z
is
anti-reflective
P
ROBLEM
5
The number of watermelons in a truck are all weighed on a scale. The
scale rounds the weight of every watermelon to the nearest pound. The
number of pounds read off the scale for each watermelon is called its measured
weight. The domain for each of the following relations below is the set of
watermelons on the truck. For each relation, indicate whether the relation is:
•
Reflexive,
anti-reflexive,
or
neither
•
Symmetric,
anti-symmetric,
or
neither
•
Transitive
or
not
transitive
Justify
your
answer.
(a)
Watermelon
x
is
related
to
watermelon
y
if
the
measured
weight
of
water-
melon
x
is
at
least
the
measured
weight
of
watermelon
y.
No
two
water-
melons
have
the
same
measured
weight.
•
This
relation
is
viewed
as
reflective
since
x
is
related
to
x
for
all
wa-termelons(x).
•
If
x
has
a
weight
of
z
pounds,
then
x
is
atleast
z
pounds.
This
wouldmean
that
the
relation
is
reflective.
•
Let:
x
have
20lbs
and
let
y
have
30lbs.
•
y
is
related
to
x,
but
x
is
not
related
to
y.
Because
no
watermelon
weighs
the
same,
it
is
anti-symmetric.
•
if
x
is
related
to
y,
and
y
related
to
z:
weight
of
x
¿
weight
of
y
¿weight
of
z
This
relation
is
transitive
(b)
Watermelon
x
is
related
to
watermelon
y
if
the
measured
weight
of
water-
melon
x
is
at
least
the
measured
weight
of
watermelon
y.
All
watermelons
have
exactly
the
same
measured
weight.
•
For this we need to imagine that all watermelons have the same
weight. Because every watermelon has the same value, this makes
it reflexive,
symmetric and transitive.
P
ROBLEM
6
Part
1.
Give
the
adjacency
matrix
for
the
graph
G
as
pictured
below:
Figure
2:
A
graph
shows
6
vertices
and
9
edges.
The
vertices
are
1,
2,
3,
4,
5,
and
6,
represented
by
circles.
The
edges
between
the
vertices
are
represented
by
arrows,
as
follows:
4
to
3;
3
to
2;
2
to
1;
1
to
6;
6
to
2;
3
to
4;
4
to
5;
5
to
6;
and
a
self
loop
on
vertex
5.
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
Part
2.
A
directed
graph
G
has
5
vertices,
numbered
1
through
5.
The
5
×
5
matrix
A
is
the
adjacency
matrix
for
G.
The
matrices
A
2
and
A
3
are
given
below.
A
2
=
A
2
A
3
=
Use
the
information
given
to
answer
the
questions
about
the
graph
G.
(a)
Which
vertices
can
reach
vertex
2
by
a
walk
of
length
3?
•
To
find
the
vertices
that
can
reach
vertex
2
by
a
walk
of
3
lengths
(vertex
x
to
vertex
y):
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
0
1
1
1
0
1
0
We
can
use:
[A
3
]xy
•
Find
for
x:
[A
3
]xy
≠
0
[A
3
]
22
=
1
≠
0
•
Vertex
2
is
the
only
vertex
able
to
reach
vertex
2
by
a
walk
of
3
lengths.
(b)
Is
there
a
walk
of
length
4
from
vertex
4
to
vertex
5
in
G?
(Hint:
A
4
=
A2 · A2.)
•
Using
the
given
adjacency
matrices.
A
4
=
A
2
∗
A
2
•
To
achieve
the
requested
walk,
you
would
need
[A
4
]
54
=
0
which
such
a
walk
does
not
exist.
P
ROBLEM
7
Part
1.
The
drawing
below
shows
a
Hasse
diagram
for
a
partial
order
on
the
set
{
A,
B,
C,
D,
E,
F,
G,
H,
I,
J
}
Figure
3:
A
Hasse
diagram
shows
10
vertices
and
8
edges.
The
vertices,
rep-
resented
by
dots,
are
as
follows:
vertex
J;
vertices
H
and
I
are
aligned
vertically
to
the
right
of
vertex
J;
vertices
A,
B,
C,
D,
and
E
forms
a
closed
loop,
which
is
to
the
right
of
vertices
H
and
I;
vertex
G
is
inclined
upward
to
the
right
of
vertex
E;
and
vertex
F
is
inclined
downward
to
the
right
of
vertex
E.
The
edges,
represented
by
line
segments,
between
the
vertices
are
as
follows:
Vertex
J
is
connected
to
no
vertex;
a
vertical
edge
connects
vertices
H
and
I;
a
vertical
edge
connects
vertices
B
and
C;
and
6
inclined
edges
connect
the
following
vertices,
A
and
B,
C
and
D,
D
and
E,
A
and
E,
E
and
G,
and
E
and
F.
(a)
What are the d minimal elements of the partial order?
•
Since minimal elements are elements that are not proceeded by
otherelements, you can order the elements like so:
{
J,I,A,F
}
(b)
What are the maximal elements of the partial order?
•
Since maximal elements are elements that are not succeeded by
the same element:
{
J,
H,
D,
G
}
(c)
Which
of
the
d
following
pairs
are
comparable?
(A,
D),
(J,
F),
(B,
E),
(G,
F),
(D,
B),
(C,
F),
(H,
I),
(C,
E)
•
Comparable
Pairs:
(A,D),(G,F),(D,B),(H,I)
•
Comparable
for
given
partial
order:
(D
d
≤
A),
(F
d d
≤
G),
(B
d
≤
D),
(I
d
≤
H)
Part
2.
Each
relation
given
below
is
a
partial
order.
Draw
the
Hasse
diagram
for
the
partial
order.
(a)
The
domain
is
{
3,
5,
6,
7,
10,
14,
20,
30,
60
}
.
x
≤
y
if
x
evenly
divides
y.
(b)
The domain is {a, b, c, d, e, f }. The relation is the set:
{
(b,
e),
(b,
d),
(c,
a),
(c,
f
),
(a,
f
),
(a,
a),
(b,
b),
(c,
c),
(d,
d),
(e,
e),
(f,
f
)
}
P
ROBLEM
8
Determine
whether
each
relation
is
an
equivalence
relation.
Justify
your
answer.
If
the
relation
is
an
equivalence
relation,
then
describe
the
partition
defined
by
the
equivalence
classes.
(a)
The
domain
is
a
group
of
people.
Person
x
is
related
to
person
y
under
relation
M
if
x
and
y
have
the
same
favorite
color.
You
can
assume
that
there
is
at
least
one
pair
in
the
group,
x
and
y,
such
that
xMy.
Consider
the
given
relation
M.
A
person
has
the
same
favorite
color
as
themselves.
•
Relation
M
is
Reflexive.
If
person
•
x
has
the
same
favorite
color
as
person
y,
then
y
has
the
same
favorite
color
as
person
x.
•
Relation
M
is
Symmetric.
If
person
x
has
the
same
favorite
color
as
person
y.
and
y
has
the
same
favorite
color
as
person
z.
then
person
x
has
the
same
favorite
color
as
person
z.
•
•
M
is
transitive.
Therefore,
the
given
relation
M
is
an
equivalence
relation.
All
person
•
s
having
one
favorite
color
is
considered
as
one
equivalence
class.
(b)
The
domain
is
the
set
of
all
integers.
xEy
if
x
+
y
is
even.
An
integer
z
is
even
if
z
=
2k
for
some
integer
k.
•
The
relation
is
reflexive:
if
x
is
an
integer,
that
also
means
x
+
x
=
2x
is
also
an
•
integer.We
can
find
if
the
relation
is
symmetric
by:
if
x
+
y
is
even,
y
+
x
will
also
be
even.
This
is
•
true.Since
x,
y,
and
z
are
integers
•
We
can
assume
that
x
+
y
is
•
even.for
integer
a:
x
+
y
=
2a
•
for
integer
k:
y
+
z
=
2k
•
x
+
z
=
2a
-
y
+
2k
-
y
=
2(a
+
k
-
y)
•
Both
(a
+
k
-
y)
and
x
+
z
are
integers,
therefore
this
relation
is
anequivalence
relation.
