## Description

## Question 1 (20 pts)

For each of the following functions, show whether they are a) surjective or not b) injective or not.

• f1 : R → R, f(x) = x

2

• f2 : R¯ + → R, f(x) = x

2

• f3 : R → R¯ +, f(x) = x

2

• f4 : R¯ + → R¯ +, f(x) = x

2

Note: R¯ + denotes the set of nonnegative real numbers.

## Question 2 (20 pts)

A function f : A ⊂ R

n → R

m is said to be continuous at x0 ∈ A if

∀ ε ∈ R

+ ∃ δ ∈ R

+ ∀ x ∈ A (∥x − x0∥ < δ → ∥f(x) − f(x0)∥ < ε)

where ∥x∥ represents the Euclidean norm, i.e. for x = (x1, x2, . . . , xn) ∈ R

n

, the norm is given as

∥x∥ =

qPn

i=1 x

2

i

. If f is continuous at every x ∈ A, f is continuous. Use this definition to

a) show that every function f : A ⊂ Z → R is continuous.

b) show that a necessary and sufficient condition for a function f : R → Z to be continuous is that f is

a constant function.

## Question 3 (20 pts)

a) Show that a finite Cartesian product of countable sets, i.e. Xn = A1 × A2 × . . . × An for all n ≥ 2,

is countable.

1

b) Show that an infinite countable product of the set X = {0, 1} with itself is uncountable.

Note: You can use the following without proving them: i) the set of positive integers Z

+, Z and Z × Z

have the same cardinality, ii) a set A is countable if and only if there exists some f : Z → A that is

surjective.

## Question 4 (25 pts)

Arrange the following functions so that each function is big-O of the next function. Show your work.

2

n

, n50

, (log n)

2

,

√

n log n, 5

n

, (n!)2

, n51 + n

49

Note: You can use calculus in this question.

## Question 5 (15 pts)

a) Use the Euclidean algorithm to find gcd(94, 134).

b) Goldbach’s conjecture states that every even integer greater than 2 is the sum of two primes. Show

that this statement is equivalent to the statement that every integer greater than 5 is the sum of three

primes.

## Question 6 (ungraded)

Let f : A → B be a function, A0 ⊂ A, B0 ⊂ B and f

−1 denote the preimage of B0 under f defined by

f

−1

(B0) = {a | f(a) ∈ B0}

a) Show that A0 ⊆ f

−1

(f(A0)) and that equality holds if f is injective.

b) Show that f(f

−1

(B0)) ⊆ B0 and that equality holds if f is surjective.

## Question 7 (ungraded)

a) A real number is said to be algebraic over the rationals if it satisfies some polynomial equation of

positive degree

x

n + an−1x

n−1 + . . . + a1x + a0 = 0

where ai ∈ Q. Assuming that each polynomial has only finitely 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. Show that the set of transcendental

numbers are uncountable.

2

## Regulations

1. Your submission should be a single vector-based PDF document with the name the2.pdf.

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 odtuclass for discussions and possible updates. You

can ask your questions in the Student Forum on the course page in odtuclass.

5. Evaluation: Your .pdf file will be checked for plagiarism automatically using “black-box” technique and manually by assistants, so make sure to obey the specifications.

## Submission

Submission will be done via odtuclass. For those who prefer to use LATEX to generate the vector-based

PDF file, a template answer file the2.tex is provided in odtuclass. You need to compile the filled template

yourselves and submit the generated .pdf file only.

3