Page 208 - Discrete Mathematics and Its Applications

Supplementary Exercises 187

7. Explain the relationship between logical equivalences and 10. a) Define the inverse of a function.
set identities. b) When does a function have an inverse?
8. a) Define the domain, codomain, and range of a function. c) Does the function f (n) = 10 − n from the set of inte-
b) Let f (n) be the function from the set of integers to the gers to the set of integers have an inverse? If so, what
2
set of integers such that f (n) = n + 1. What are the is it?
domain, codomain, and range of this function?
11. a) Define the floor and ceiling functions from the set of
9. a) Define what it means for a function from the set of
positive integers to the set of positive integers to be real numbers to the set of integers.
one-to-one. b) For which real numbers x is it true that x = x ?
b) Define what it means for a function from the set of 12. Conjecture a formula for the terms of the sequence that
positive integers to the set of positive integers to be begins 8, 14, 32, 86, 248 and find the next three terms of
onto. your sequence.
c) Give an example of a function from the set of posi-
tive integers to the set of positive integers that is both 13. Suppose that a n = a n−1 − 5 for n = 1, 2,.... Find a for-
one-to-one and onto. mula for a n .
d) Give an example of a function from the set of positive 14. What is the sum of the terms of the geometric progression
integers to the set of positive integers that is one-to-one a + ar + ··· + ar when r = 1?
n
but not onto.
15. Show that the set of odd integers is countable.
e) Give an example of a function from the set of posi-
tive integers to the set of positive integers that is not 16. Give an example of an uncountable set.
one-to-one but is onto.
17. Define the product of two matrices A and B. When is this
f) Give an example of a function from the set of positive
product defined?
integers to the set of positive integers that is neither
one-to-one nor onto. 18. Show that matrix multiplication is not commutative.

Supplementary Exercises

1. Let A be the set of English words that contain the letter 7. Let A, B, and C be sets. Show that (A − B) − C is not
x, and let B be the set of English words that contain the necessarily equal to A − (B − C).
letter q. Express each of these sets as a combination of A 8. Suppose that A, B, and C are sets. Prove or disprove that
and B.
(A − B) − C = (A − C) − B.
a) The set of English words that do not contain the letter 9. Suppose that A, B, C, and D are sets. Prove or disprove
x.
that (A − B) − (C − D) = (A − C) − (B − D).
b) The set of English words that contain both an x and a
q. 10. Show that if A and B are finite sets, then |A ∩ B|≤
c) The set of English words that contain an x but not a q. |A ∪ B|. Determine when this relationship is an equality.
d) The set of English words that do not contain either an 11. Let A and B be sets in a finite universal set U. List the
x or a q. following in order of increasing size.
e) The set of English words that contain an x or a q,but a) |A|, |A ∪ B|, |A ∩ B|, |U|, |∅|
not both.
b) |A − B|, |A ⊕ B|, |A|+|B|, |A ∪ B|, |∅|
2. Show that if A is a subset of B, then the power set of A 12. Let A and B be subsets of the finite universal set U. Show
is a subset of the power set of B.
that |A ∩ B|=|U|−|A|−|B|+|A ∩ B|.
3. Suppose that A and B are sets such that the power set of
13. Let f and g be functions from {1, 2, 3, 4} to {a, b, c, d}
A is a subset of the power set of B. Does it follow that A
and from {a, b, c, d} to {1, 2, 3, 4}, respectively, with
is a subset of B?
f(1) = d, f(2) = c, f(3) = a, and f(4) = b, and
4. Let E denote the set of even integers and O denote the g(a) = 2, g(b) = 1, g(c) = 3, and g(d) = 2.
set of odd integers. As usual, let Z denote the set of all a) Is f one-to-one? Is g one-to-one?
integers. Determine each of these sets.
b) Is f onto? Is g onto?
a) E ∪ O b) E ∩ O c) Z − E d) Z − O c) Does either f or g have an inverse? If so, find this
5. Show that if A and B are sets, then A − (A − B) = inverse.
A ∩ B. 14. Suppose that f is a function from A to B where A and B
6. Let A and B be sets. Show that A ⊆ B if and only if are finite sets. Explain why |f(S)|≤|S| for all subsets S
A ∩ B = A. of A.