Problem Set 6 (week 7)Solutions

1
.
Consider the function f:{1,2,3,4}→{1,2,3,4} represented in the graph above
1
.
1
.
f is not injective: f(1) = f(4)= 3 so f is not injective
1
.
2
.
f is not surjective: There is no x∈{1,2,3,4} such that f(x) = 2, as shown by f(1) = f(4) = 3, f(2) = 4, and f(3) = 1, so f is not surjective
2
.
It is a function with domain equal to the set of Students and Codomain equal to the set of grades. It is a function because every student gets just one unique final grade.
3
.
Yes:
3
.
1
.
Reflexivity: Let p, q∈ with q≠0. note that pq = qp so
p
q
R
p
q
3
.
2
.
Symmetry: let
a
b
R
p
q
so
aq=pb
but that means ​
pb=aq
, so
p
q
R
a
b
3
.
3
.
Transitivity: Let
a
b
R
c
d
and
c
d
R
p
q
then ​
ad=cb
. Thus​
adpq=cbpq
, so​
aqdp=pbcq=pbdp
. Since d ≠0 then​
aqp=pbp
. We then have two cases: p =0 or p ≠0. If p = 0, then c = 0, then
a
= 0 so
aq=pb=0
. If p ≠ 0, then we can cancel p out. so
aq=pb
.By considering both cases, then we get ​
a
b
R
p
q
4
.
Consider the following function: f:N→N described as f(n+1)={f(n)2iff(n)is even3f(n)+1iff(n)is odd}
Notice that if f(0) = 1, we get that: f(1) = 4, f(2) = 2, f(3) = 1, f(4) = 4, etc. So we have a cycle.
4
.
1
.
NO
If f(0) = 5, then f(1) = 16, so f(2) = 8, so f(3) = 4, so f(4) = 2, so f(5) = 1, so f(6) = 4.
Thus f(3) = f(6) and 3≠6
Thus f cannot be injective if f(0) = 5
4
.
2
.
If f(0) = 3, then f(1) = 10, so f(2) = 5, so then f(3) = 16, so f(4) = 8, so f(5) = 4, so f(6) = 2, so f(7) = 1, so f(8) = 4.
Thus f(5) = f(8) and 5≠8
Thus f cannot be injective if f(0) = 3
4
.
3
.
Assume for the sake of contradiction that f is surjective. Then there is n∈ such that f(n) = 4so f(n+1) = 2, so f(n+2) = 1, so f(n+3) = 4In general: f(n+3k+1) = 2 for any k∈ f(n+3k+2) = 1 for any k∈, and f(n+3k) = 4 for any k∈. Thus f() has at most n+2 different values and thus cannot be surjective, since  has infinite cardinality.