Homework 2 Solution

Description

Question 1

Let f : A ! B and g : B ! C. Prove the following:

a) If C₀ C, show that (g f) ¹(C₀) = f ¹(g ¹(C₀)):

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 ¹.

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)

Show that f and g de ned above are bijections.

Question 4

a) x 2 R is algebraic if it satis es some polynomial equation of positive degree

xⁿ + a_{n 1}x^{n 1} + + a₁x + a₀ = 0

with rational coe cients a_i. 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 2^{p 1}(2^p 1) is a perfect number when 2^p 1 is prime.

Question 7

a) Given x c₁ (mod m) and x c₂ (mod n) where c₁; c₂; m; n are integers with m > 0; n > 0 show that the solution x exists if and only if gcd(m; n)jc₁ c₂.

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.

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