All Exercises, Problems, and page number refer to Eccles’ book.

1. (Compare with Exercise 6.1(iii),(iv) on p. 72.) Let a and b be real numbers.

(a) Prove that (a, b] = ∅ (the empty set) if and only if a ≥ b.
(b) Suppose that a < b. Prove that (a, b) ⊆ (c, d) ⇔ ( c ≤ a and b ≤ d ).
Hint for ⇒ (but this is not the only way to prove this): For a contradiction, suppose that
a < c. (To prove c ≤ a.)
Case 1. b ≤ c. Consider the average of a and b. It’s in one interval but not the other.
Case 2. b ≥ c. Now consider the average of a and c. Again, it’s in one interval but not
the other.

2. Do Exercise 6.6 on p. 73. This problem should be relatively straightforward. As

usual, don’t copy the answer in the back of the book. They’re too pedantic or too sketchy
(no pun intended) anyway. ,

3. Do Exercise 7.3 on p. 87. (The un-assigned Exercise 7.4 is perhaps more interesting.)

4.

(a) Do Exercise 7.5 on p. 87.
(b) Jumping ahead, state the Division Theorem 15.1.1 for the case where b = 2. What
does Exercise 7.5 say about the square of an odd integer? Give some detail.
(c) What is the contrapositive of your odd integer interpretation of Exercise 7.5? Hint:
It’s a statement about even integers.

5.

(a) Do Exercise 9.4 on p. 114.
(b) Using part (a) and induction, prove that for any integer n ≥ 2, if f1 : X0 → X1,
f2 : X1 → X2, …, fn : Xn−1 → Xn, are injections, then n-fold composition of functions
fn ◦ · · · ◦ f1 : X0 → Xn
is an injection.

6. Do Exercise 9.5 on p. 114.

7. Do Exercise 9.7 on p. 114.

8. Do #4 in Problems II on p. 115.

Math 109 SS2 2020 Homework 2 Lec A Prof. Chow

9. Do #10 in Problems II on p. 116.

10. Do #15 in Problems II on p. 117.

11.

(a) Do #18 in Problems II on p. 118.
(b) Using part (a) and induction, prove that for any integer n ≥ 2, if f1 : X0 → X1,
f2 : X1 → X2, …, fn : Xn−1 → Xn, are surjections, then n-fold composition of functions
fn ◦ · · · ◦ f1 : X0 → Xn
is an surjection.

12. Do #20 in Problems II on p. 118.

13. Let

P(x) = anx
n + · · · + a1x + a0
be a polynomial of a real variable x. Fact (do not prove): If an > 0 (i.e., the leading
coefficient is positive), then
limx→∞
P(x) = ∞.
By definition, this means that for any real number M there exists a real number N such
that
P(x) ≥ M for all x > N.
Universal and existential quantifiers with two free variables. The universal set
is the set of real numbers R.
(a) Prove: ∀y ∈ R, ∃x ∈ R, −3x
10 + 5x
6 + y
100 < −10. Hint: The leading coefficient of the polynomial in x is negative. What is the “flip side” of the “fact” above? (b) Let g : R → R be any function. Prove that for all real numbers y, there exists a real number x such that P(x) > g(y), where P is the polynomial above. Explain why part (a) is
a special case of this.

14.

(a) Prove: ∀y ∈ R, y
2 ≥ 1 or (∃x, y < x < 1).
(b) Let a be a positive real number.
Prove: ∀y ∈ R, (y
2 + 2y ≥ a
2 − 1) or (∃x, y + 1 − a < x < 0).
Math 109 SS2 2020 Homework 2 Lec A Prof. Chow

15. Let n be a positive integer. Define g : R → R by g(x) = x

2n
.
(a) Find ←
g ([0, 1]), where [0, 3] = {y ∈ R : 0 ≤ y ≤ 3}.
(b) For y ∈ R, define
←
g (y) = ←
g ({y}) = {x ∈ R : g(x) ∈ {y} } = {x ∈ R : g(x) = y}.
Describe ←
g (y) for each y ∈ R. Hint: You answer will depend on the relation of y to zero.

16. Power set.

(a) List all of the elements of the power set S = P({a, b, c, d}).
Define the function f : S × S → S by f(A, B) = A ∩ B for A, B ∈ S.
(b) Find all (A, B) ∈
←
f (∅) such that A ∪ B = {a, b, c, d}.
(c) Find
←
f ({a, b, c}).
(d) Find
←
f ({a, b}).
The following definition applies to problems #17–#18. Define g : Z → {0, 1, 2, 3} by:
For n ∈ Z,
g(n) =



0 if n = 4k for some k ∈ Z,
1 if n = 4k + 1 for some k ∈ Z,
2 if n = 4k + 2 for some k ∈ Z
3 if n = 4k + 3 for some k ∈ Z.
Fact that you may assume, which implies g is a well-defined function (consequence of the
Division Theorem of Chapter 15): For any integer n, exactly one of the four possibilities
above holds.

17. (a) Note that ←

g : P({0, 1, 2, 3}) → P(Z). Describe, for each r ∈ {0, 1, 2, 3},
←
g (r) := ←
g ({r}) (:= means “defined to be equal to”).
(b) What is ←
g (r) ∩
←
g (s) where r 6= s and 0 ≤ r, s ≤ 3? Hint: You may use the “Fact”
above.
(c) What is ←
g (0) ∪
←
g (1) ∪
←
g (2) ∪
←
g (3)? Explain why your answer is true.
(d) Prove that for any x ∈ Z, there exists a unique r ∈ Z such that 0 ≤ r ≤ 3 and
x ∈
←
g (r).

18. Let →

g : P(Z) → P({0, 1, 2, 3}) be the “image function” (see p. 111 of Eccles’ book
for the definition).
Math 109 SS2 2020 Homework 2 Lec A Prof. Chow
(a) Let 0 ≤ r ≤ 3. Find the “largest” subset A of Z such that →
g (A) = {r}. Hint: Does

17(a) ring a bell?

(b) Describe all “smallest” subsets A of Z such that →
g (A) = {r}. Hint: There are
infinitely many such subsets.
(c) Let A and B be subsets of Z satisfying A∪B = Z,
→
g (A) ⊆ {0, 1}, and →
g (B) ⊆ {2, 3}.
Prove that
A = {4j : j ∈ Z} ∪ {4k + 1 : k ∈ Z}
and
B = {4+ 2 : ∈ Z} ∪ {4m + 3 : m ∈ Z}.

Sample Solution