Problem Set 6 (week 7)Solutions
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 R
p
q
p
q
3
.2
.Symmetry: let R so but that means , so R
a
b
p
q
aq=pb
pb=aq
p
q
a
b
3
.3
.Transitivity: Let R and R then . Thus, so. Since d ≠0 then. We then have two cases: p =0 or p ≠0. If p = 0, then c = 0, then = 0 so . If p ≠ 0, then we can cancel p out. so .By considering both cases, then we get R
a
b
c
d
c
d
p
q
ad=cb
adpq=cbpq
aqdp=pbcq=pbdp
aqp=pbp
a
aq=pb=0
aq=pb
a
b
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.
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
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
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.