Page 209 - Discrete Mathematics and Its Applications

188 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

15. Suppose that f is a function from A to B where A and B ∗ 28. We define the Ulam numbers by setting u 1 = 1 and
are finite sets. Explain why |f(S)|=|S| for all subsets S u 2 = 2. Furthermore, after determining whether the in-
of A if and only if f is one-to-one. tegers less than n are Ulam numbers, we set n equal to
Suppose that f is a function from A to B. We define the func- the next Ulam number if it can be written uniquely as the
tion S f from P(A) to P(B) by the rule S f (X) = f(X) for sum of two different Ulam numbers. Note that u 3 = 3,
u 4 = 4, u 5 = 6, and u 6 = 8.
each subset X of A. Similarly, we define the function S −1
f
from P(B) to P(A) by the rule S −1(Y) = f −1 (Y) for each a) Find the first 20 Ulam numbers.
f
subset Y of B. Here, we are using Definition 4, and the defi- b) Prove that there are infinitely many Ulam numbers.
nition of the inverse image of a set found in the preamble to 29. Determine the value of 100 k+1 . (The notation used
k
k=1
Exercise 42, both in Section 2.3. here for products is defined in the preamble to Exercise
∗ 16. Suppose that f is a function from the set A to the set B. 43 in Section 2.4.)
Prove that ∗ 30. Determine a rule for generating the terms of the sequence
a) if f is one-to-one, then S f is a one-to-one function that begins 1, 3, 4, 8, 15, 27, 50, 92,..., and find the next
from P(A) to P(B). four terms of the sequence.
b) if f is onto function, then S f is an onto function from ∗ 31. Determine a rule for generating the terms of the sequence
P(A) to P(B).
that begins 2, 3, 3, 5, 10, 13, 39, 43, 172, 177, 885,
c) if f is onto function, then S −1 is a one-to-one func-
f 891,..., and find the next four terms of the sequence.
tion from P(B) to P(A).
32. Show that the set of irrational numbers is an uncountable
d) if f is one-to-one, then S −1 is an onto function from
f
P(B) to P(A). set.
e) if f is a one-to-one correspondence, then S f is a one- 33. Show that the set S is a countable set if there is a func-
tion f from S to the positive integers such that f −1 (j) is
to-one correspondence from P(A) to P(B) and S −1
f
is a one-to-one correspondence from P(B) to P(A). countable whenever j is a positive integer.
[Hint: Use parts (a)-(d).] 34. Show that the set of all finite subsets of the set of positive
17. Prove that if f and g are functions from A to B and integers is a countable set.
S f = S g (using the definition in the preamble to Exercise ∗∗ 35. Show that |R × R|=|R|.[Hint: Use the Schröder-
16), then f(x) = g(x) for all x ∈ A.
Bernstein theorem to show that |(0, 1) × (0, 1)|=
18. Show that if n is an integer, then n = n/2 + n/2 . |(0, 1)|. To construct an injection from (0, 1) × (0, 1) to
19. For which real numbers x and y is it true that x + y = (0, 1), suppose that (x, y) ∈ (0, 1) × (0, 1). Map (x, y)
x + y ? to the number with decimal expansion formed by alter-
nating between the digits in the decimal expansions of x
20. For which real numbers x and y is it true that x + y =
x + y ? and y, which do not end with an infinite string of 9s.]
∗∗ 36. Show that C, the set of complex numbers has the same
21. For which real numbers x and y is it true that x + y =
x + y ? cardinality as R, the set of real numbers.
n
2
22. Prove that n/2 n/2 = n /4 for all integers n. 37. Find A if A is
23. Prove that if m is an integer, then x + m − x =
m − 1, unless x is an integer, in which case, it equals m. 0 1 .
−10
24. Prove that if x is a real number, then x/2 /2 = x/4 .
2
25. Prove that if n is an odd integer, then n /4 =
2
(n + 3)/4. 38. Show that if A = cI, where c is a real number and I is the
26. Prove that if m and n are positive integers and x is a real n × n identity matrix, then AB = BA whenever B is an
number, then n × n matrix.
39. ShowthatifAisa2 × 2 matrixsuchthatAB = BAwhen-

x + n x + n
= . ever B isa2 × 2 matrix, then A = cI, where c is a real
m m number and I is the 2 × 2 identity matrix.
∗ 27. Prove that if m is a positive integer and x is a real number, 40. Show that if A and B are invertible matrices and AB exists,
then then (AB) −1 = B −1 A −1 .

41. Let A be an n × n matrix and let 0 be the n × n matrix
1 2
mx = x + x + + x + + ··· all of whose entries are zero. Show that the following are
m m
true.
m − 1

a) A 0 = 0 A = 0
+ x + . b) A ∨ 0 = 0 ∨ A = A
m
c) A ∧ 0 = 0 ∧ A = 0