Question 1
Let f : A ! B and g : B ! C. Prove the following:
a) If C0 C, show that (g f) 1(C0) = f 1(g 1(C0)):
b) If g f is injective, what can be said about the injectivity of f and g?
c) If g f is surjective, what can be said about the surjectivity of f and g?
Question 2
Let C : C ! C such that C(x) = x; 8x 2 C for a set C. Given f : A ! B, we say that a function
g : B ! A is a left inverse for f if g f = A, and a function h : B ! A is a right inverse for f if
• h = B.
a) Show that if f has a left inverse, f is injective; and if f has a right inverse, f is surjective. b) Can a function have more than one left inverse? What about right inverses?
c) Show that if f has both a left inverse g and a right inverse h, then f is bijective and g = h = f 1.
Question 3
The product Z+ Z+ is countably in nite.
We can de ne a function f : Z+ Z+ ! A, where A = f(x; y)jy x ^ x; y 2 Z+g, by the equation
f(x; y) = (x + y 1; y)
Then we can construct a function g : A ! Z+ by
g(x; y) =
1
(x 1)x + y:
2
Show that f and g de ned above are bijections.
1
Question 4
a) x 2 R is algebraic if it satis es some polynomial equation of positive degree
xn + an 1xn 1 + + a1x + a0 = 0
with rational coe cients ai. Assuming that each polynomial equation has only nitely many roots, show that the set of algebraic numbers is countable.
b) A real number is said to be transcendental if it is not algebraic. Assuming the reals are uncount-able, show that the transcendental numbers are uncountable.
Question 5
If n ln n = (k), show that
k
n = ln k :
Question 6
We call a positive integer perfect if it equals the sum of its positive divisors other than itself.
a) Show that 6 and 28 are perfect.
b) Show that 2p 1(2p 1) is a perfect number when 2p 1 is prime.
Question 7
a) Given x c1 (mod m) and x c2 (mod n) where c1; c2; m; n are integers with m > 0; n > 0 show that the solution x exists if and only if gcd(m; n)jc1 c2.
b) If the solution exists to the above system, show that it is unique in the interval [ 0; lcm(m; n) )
Regulations
1. You have to write your answers to the provided sections of the template answer le given.
2. Late Submission: Not allowed.
3. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
4. Updates & Announces: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates.
5. Evaluation:Your latex le will be converted to pdf and evaluated by course assistants. The .tex le will be checked for plagiarism automatically using \black-box" technique and manually by assistants, so make sure to obey the speci cations.
2
Submission
Submission will be done via COW. Download the given template answer le \hw2.tex". When you nish your exam upload the .tex le with the same name to COW.
Note: You cannot submit any other les. Don’t forget to make sure your .tex le is successfully compiled in Inek machines using the command below.
$ pdflatex hw2.tex
3
