$30
CS2214
Assignment #1
Submission: on the OWL web site of the course
Format of the submission. You must submit a single file which must
be in PDF format. All other formats (text or Miscrosoft word format) will
be ignored and considered as null. You are strongly encouraged to type
your solutions using a text editor. To this end, we suggest the following
options:
1. Miscrosoft word and convert your document to PDF
2. the typesetting system LATEX; see https://www.latex-project.org/
and https://en.wikipedia.org/wiki/LaTeX#Example to learn about
LATEX; see https://www.tug.org/begin.html to get started
3. using a software tool for typing mathematical symbols, for instance
http://math.typeit.org/
4. using a Handwriting recognition system such as those equipping tablet
PCs
Hand-writing and scanning your answers is allowed but not encouraged:
1. if you go this route please use a scanning printer and do not take a
picture of your answers with your phone,
2. if the quality of the obtained PDF is too poor, your submission will
be ignored and considered as null.
Problem 1 (Proving properties about the integers) [15 marks] Prove
or disprove the following properties:
1. For every integer n we have n ≤ n
2
.
2. For every integer n, the integer n
2 + n + 1 is odd.
If the statement is true, your proof should be in the style of the proofs done
in class, see Section 1.7 of the slides. If the statement is false, giving a
counter-example is sufficient.
Solution 1
1. We proceed by cases, considering n ≤ 0 and 1 ≤ n. If n is a nonpositive integer, we have n ≤ 0 and also 0 ≤ n
2
, thus we have n ≤ n
2
.
If n is a positive integer, we have 1 ≤ n and n ≤ n, which imply
n ≤ n
2
.
1
2. We proceed by cases, considering n even abd n odd. If n is even,
then there exists an integer k such that n = 2 k holds and we have
n
2 +n+ 1 = 4 k
2 + 2 k + 1, thus implying that n
2 +n+ 1 is odd. If n is
odd, then there exists an integer k such that n = 2 k + 1 holds and we
have n
2 + n + 1 = 4 k
2 + 6 k + 3, thus again implying that n
2 + n + 1
is odd.
Problem 2 (Proving properties about real numbers) [15 marks] Prove
or disprove the following properties:
1. For every real number x, if x ≤ 0 or 1 ≤ x holds, then x ≤ x
2 holds
as well.
2. For all real number x we have b2xc = 2bxc
If the statement is true, your proof should be in the style of the proofs done
in class, see Section 1.7 of the slides. If the statement is false, giving a
counter-example is sufficient.
Solution 2
1. One can prove the claim in the same way that we proved the first claim
of Problem 1, thus by considering the two cases x ≤ 0 and 1 ≤ x. Note
that when 0 < x < 1 holds we have x
2 < x; of course this configuration
cannot happen in the integer case. An alternative proof of
((x ≤ 0) ∨ (1 ≤ x)) −→ (x ≤ x
2
)
can be by solving the inequation
x ≤ x
2
the solution set of which being precisely:
(x ≤ 0) ∨ (1 ≤ x).
2. The claim is false. To show this, it is suffcient to exhibit a counterexample. Consider x = 1.6. We have 2bxc = 2 × 1 = 2 and b2xc =
b3.2c = 3. As an additional remark, consider a real number x of the
form n + ε where n is an integer and 1
2 < ε < 1 holds. Then we have
2bxc = 2n.
While we have
b2xc = b2(n + ε)c = b2 n + 1 + (2 ε − 1)c = 2 n + 1,
since 0 < 2 ε − 1 < 1 holds.
2
Problem 3 (Properties of preimage sets) [20 marks] Let f be a function from a set A to a set B. Let S and T be two subsets of B. Prove the
following properties:
1. f
−1
(S ∪ T) = f
−1
(S) ∪ f
−1
(T)
2. f
−1
(S ∩ T) = f
−1
(S) ∩ f
−1
(T)
Your proof should be in the style of the proofs done in class, see Section 1.7
of the slides.
Solution 3
1. By definition, the set f
−1
(S) is the set the elements x ∈ A such that
f(x) ∈ S holds. Similarly:
• the set f
−1
(T) is the set the elements x ∈ A such that f(x) ∈ T
holds.
• the set f
−1
(S ∪T) is the set the elements x ∈ A such that f(x) ∈
S ∪ T holds.
It follows that if an element x ∈ A belongs to f
−1
(S ∪ T), then either
f(x) ∈ S or f(x) ∈ T holds, that is, either x ∈ f
−1
(S) or x ∈ f(x) ∈ T
holds. Thus, we have proved the following implication for all x ∈ A:
x ∈ f
−1
(S ∪ T) −→ x ∈∈ f
−1
(S) ∪ f
−1
(T),
that is,
f
−1
(S ∪ T) ⊆ f
−1
(S) ∪ f
−1
(T).
The inclusion
f
−1
(S) ∪ f
−1
(T) ⊆ f
−1
(S ∪ T)
is proved in a similar way.
2. To prove the equality f
−1
(S ∩T) = f
−1
(S)∩f
−1
(T) we could proceed
as for f
−1
(S ∪ T) = f
−1
(S) ∪ f
−1
(T). For variety, we provide a more
compact proof avoiding the proof of the two inclusions. Consider an
arbitrary element x in A. Then, the following equivalences hold:
x ∈ f
−1
(S ∩ T) ⇐⇒ f(x) ∈ S ∩ T
⇐⇒ (f(x) ∈ S) ∧ (f(x) ∈ T)
⇐⇒ (x ∈ f
−1
(S)) ∧ (x ∈ f
−1
(T))
⇐⇒ x ∈ f
−1
(S) ∩ f
−1
(T).
Problem 4 (Properties of functions) [30 marks] Which of the functions
below is injective? surjective? When the function is bijective, determine its
inverse. Justify your answers.
3
1. f1 :
Z → Z
n 7−→ 2019n + 1
2. f2 :
Z → Z
n 7−→ bn/2c + dn/2e
3. f3 :
[1, 2) → [0, 1)
x 7−→ x − bxc
4. f4 :
[1, 2) → [0, 1)
x 7−→ (f3(x))2
Solution 4
1. f1 is injective. Indeed, if two integers n1 and n2 have the same image
by f1, then we have 2019n1 + 1 = 2019n2 + 1, which implies 2019n1 =
2019n2 and thus n1 = n2. However, f1 is not surjective. Indeed, the
integer m = 0 has no pre-images via f1 since 2019n + 1 = 0 yields
n = −
1
2019 which is not an integer.
2. Let us first understand what f2 computes. It is natural to distinguish
two cases: n even and n odd. If n is even, then there exists an integer
k such that we have n = 2k. In this case, we have
bn/2c + dn/2e = b(2k)/2c + d(2k)/2e = bkc + dke = k + k = n.
If n is odd, then there exists an integer k such that we have n = 2k+1.
In this case, we have
bn/2c+dn/2e = b(2k+1)/2c+d(2k+1)/2e = bk+1/2c+dk+1/2e = k+k+1 = n.
Therefore, for all integer n, we have f2(n) = n. It follows that if two
integers n1 and n2 have the same image by f2, then we have n1 = n2,
that is, f2 is injective. Similarly, every integer m has a pre-image by
f2, namely itself, thus f2 is surjective. Consequently, f2 is bijective
and f2 is its own inverse function.
3. Let us first understand what f3 computes. Observe that for all x ∈
[1, 2), we have 1 ≤ x < 2, thus bxc = 1, hence f3(x) = x − 1. It
follows that if two real numbers x1 and x2 have the same image by f3,
then we have x1 − 1 = x2 − 1, thus x1 = x2, that is, f3 is injective.
Similarly, every real number y ∈ [0, 1) has a pre-image by f3 in [1, 2),
namely y + 1, thus f3 is surjective. Consequently, f3 is bijective and
its inverse function is: f
−1
3
:
[0, 1) → [1, 2)
y 7−→ y + 1.
4
4. Let us first understand what f4 computes. From the previous question, we have: f4 :
[1, 2) → [0, 1)
x 7−→ (x − 1)2 The function f4 is injective.
Indeed, if x1 and x2 are real numbers in the interval [1, 2) with the
same image by f4 then we have (x1 − 1)2 = (x2 − 1)2
, which implies
(x1−1−x2+1)(x1−1+x2−1) = 0, that is, x1 = x2 or x1 = −x2. Since
x1 = −x2 cannot hold for x1 and x2 in [1, 2), we deduce x1 = x2, that
is f4 is injective. The function f4 is surjective. Indeed, if y ∈ [0, 1)
then x =
√y + 1 is a pre-image of y in [1, 2). Consequently, f4 is
bijective and its inverse function is: f
−1
4
:
[0, 1) → [1, 2)
y 7−→ √y + 1.
Problem 5 (Properties of functions) [20 marks] Let f be a surjective
function from a set A to a set B and g be a function from B to a set C.
Prove or disprove the following properties:
1. if g is surjective then so is gof.
2. if f and g are both injective, then so is gof.
If the statement is true, your proof should be in the style of the proofs done
in class, see Section 1.7 of the slides. If the statement is false, giving a
counter-example is sufficient.
Solution 5
1. Assume that g is surjective and let us prove that gof is surjective as
well. That is, let us prove that all z ∈ C there exists x ∈ A such
that g(f(x)) = z. Let z ∈ C. Since g is surjective there exists y ∈ B
such that g(y) = z. Since f is surjective there exists x ∈ A such that
f(x) = y. Hence, there exists x ∈ A such that we have gof(x) = z.
Therefore, we have proved that gof is surjective.
2. Assume that f and g are both injective and let us prove that gof is
injective as well. Let x1 and x2 be in A such that gof(x1) = gof(x2)
holds. Thus, we have g(f(x1)) = g(f(x2)). Since g is injective, we
deduce f(x1) = f(x2). Since f is injective, we deduce x1 = x2. Therefore, we have proved that gof is injective.
5