Math 220
Final exam
Recall that the set of irrational numbers is R \ Q.
1. Are the statements (a) to (j) below True or False? Write T or F in the box.
(a) ∅ ∈ {N, {∅}} and N ∈ P(N).
(b) P(N) ∪ P(Z) = P(Z).
(c) (R × Q) ∩ (Q × R) = Q × Q.
(d)
(e) {x ∈ R, s.t. (∃n ∈ Z s.t. x = (n+1)(n+2)(n+3))} ⊆ {x ∈ Z, s.t. (∃k ∈ Z s.t. x = 3k))}.
(f) {x ∈ Z, s.t. (∃k ∈ Z s.t. x = 3k)} ⊆ {x ∈ R, s.t. (∃n ∈ Z s.t. x = (n+ 1)(n+ 2)(n+ 3))}
(g) There exists an injective function R → P(R).
(h) The product of two irrational numbers is irrational.
(i) For a function f : A → B, recall the definition of Range(f).
(j) Given a function f : A → B and Y ⊂ B, recall the definition of f−1 (Y ).
(k) Give the Euclidean division of −142 by 9.
2. Prove or disprove the following statements:
(a)
(b) There exists x ∈ Z such that x2 ≡ 142 mod 9.
(c) There exists x ∈ Z such that x
2 ≡ −142 mod 9.
(d) For any function f : Z → Z and any X ⊆ Z we have f−1 (f(X)) ⊆ X.
3. This question is on two pages. Parts (a), (b) and (c) are related. You may admit the result in (b) to prove (c).
We admit that for any real number x ∈ R, there exists a unique integer c(x) ∈ Z such that
x ∈ (c(x) − 1, c(x)] .
(a) Write the required values in the boxes:
c(0.2)= c(-5.3)=
(b) Prove, for x ∈ R:
x > 0 =⇒ c(x) ≥ 1.
(c) Prove
4. Find (with proof) a ∈ {0, . . . , 6} such that 6354235a ≡ 1 mod 7.
5. In this question, Parts (a) and (b) are connected. You may admit the result of Part (a) to prove Part (b).
(a) Prove that
(b) Prove that
6. The Fibonacci numbers are defined by the recurrence
F1 = 1 F2 = 1 and Fn = Fn−1 + Fn−2 for n > 2.
Show that for every k ∈ N:
F4k is a multiple of 3.
7. This question has several parts from page 9 to page 12.
We consider the function
(a) Compute f−1 ({1}) and f−1 ({6}).
(b) Is f injective? Justify your answer.
(c) Is f surjective? Justify your answer.
(d) Let
(d)-1) Show that Range(g) = R \ {1}.
(d)-2) Show that g([0, 4)) = [ 4/9
, +∞).
(d)-3) Compute f(] − 2, 0]) where f is the function defined at the beginning of Question 7.
Hint: there is a link between functions f, g and h.
8. This question has 3 parts on two pages.
Consider a function f : A → B between sets A and B. Define the function
(a) When f is the function
describe the function F explicitly by giving all its values.
(b) With the same example of function f as in part (b), is F injective? Justify your answer.
(c) Now f is general again like at the beginning of Question 8, before Part (a).
Prove:
if f is injective, then F is injective.
9. For each of the following relations:
• If it is not an an equivalence relation, explain why.
• If it is an equivalence relation, no need to prove it but give (without proof) a description or list of the equivalence classes.
a) On the set {1, . . . 20}, the relation R given by:
xRy when (2|(x − y) or 5|(x − y)).
b) On the set F of functions R → R, the relation S given by:
fSg when there is x ∈ R such that f(x) = g(x).
c) On the set R × R, the relation given by:
(x, y)T(x
0 , y0 ) when y − 3x = y
0 − 3x
0 .
d) On the set F of functions R → R, the relation U given by:
fUg when there is x ∈ R such that |f(x) − 1| = |g(x) + 1|.
e) Let X be a non empty set. On P(X), the relation V given by:
AVB when A ⊆ B.