HW 3 Answer Key

Section 1.6

4a. The domain is the set of nonnegative integers, and the range is the set of digits 0–9.

b. The domain is the set of positive integers, and the range is the set of integers greater than 1.

6a. This is one-to-one b. This is not one-to-one, since b is the image of both a and b

8 a. one-to-one b. no, example f(3) and f(−3) both equal 10 c. one-to-one d. no, example f(3) = f(4) = 2

There are many possible answers for question 10 10a. f(n) = n + 17 b. f(n) = ⌊n/2⌋ c. Let f(n) ≡ n − 1 for even values of n and f(n) = n + 1 for odd values of n. Thus we have f(1)=2, f(2)=1, f(3)=4, f(4)=3, and so on. (Note: this is just one function, even though its definition used two formulas, depending on the parity of n.) d. f(n) = 17

16. Yes For an example suppose that g : A → B and f : B → C, so that f ∘ g : A → C Suppose g were not one-to-one. By definition this means that there are distinct elements a_{1} and a_{2} in A such that g(a_{1}) = g(a_{2}). Then certainly f(g(a_{1})) = f(g(a_{2})), which is the same statment as (f ∘ g)(a_{1}) = (f ∘ g)(a_{2}). By definition this means that f ∘ g is not one-to-one, and our proof is complete.

28. Let n = ⌈x⌉, so that n − 1 < x ≤ n. Then multiplying through by −1 (and necessarily reversing the signs), we have −n + 1 > −x ≥ −n, which means that −n = ⌊−x⌋, as desired.

Section 1.7

2a. 2^{(8−1)} = 128 b. 7 c. 1 + (−1)^{8} = 2 d. −(−2)^{8} = −256

6a. 1+3+5+7 = 16 b. 1^{2} + 3^{2} + 5^{2} + 7^{2} = 84 c. (1/1)+(1/3) + (1/5) + (1/7) = 176/105 d. 1+1+1+1 = 4

16. n! = ∏_{i=1}^{n} i 20a. All that is needed is to show that the integers not divisible by 3 are a subset of a countable set.

Therefore 0 ↔ 1, 1 ↔ 2, 2 ↔ 4, 3 ↔ 5, 4 ↔ 7 etc. b. As in part (a) again, all that is needed is to show it is subset of a countable set. 0 ↔ 0, 1 ↔ 5, 2 ↔ 10, 3 ↔ 15, 4 ↔ 20, 5 ↔ 25, 6 ↔ 30, 7 ↔ 40, … c. This is countable but a little tricky. We can arrange the numbers in a 2-dimensional table as follows.

\begin{matrix}.¯1 & .¯1 & .1¯1 & .11¯1 & .111¯1 & .1111¯1 & … \\ 1.¯1 & ¯1 & 1.¯1 & 1.1¯1 & 1.11¯1 & 1.111¯1 & … \\ 11.¯1 & 1¯1 & 11.¯1 & 11.1¯1 & 11.11¯1 & 11.111¯1 & … \\ … & … & … & … & … & … & … \end{matrix} Thus we have shown that our set is the countable

union of countable sets (each countable set is one row of the table) Therefore the entire set is countable. d. This set is not countable. We can prove it by the same diagnolization argument as was used to prove the set of all real numbers is uncountable.

22. If a set A is countable then we can list its subsets a1, a2, a3, …, an, … (possibly ending after a finite no. of terms.) Any subset of A consists of some (or all) of the items in this sequence, and we can list them in the same order in which they appear in the sequence. This gives us a sequence (again finite or infinite) listing all the elements of the subset. Thus the subset is also countable.