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
