252 16. Answers to Exercises
1.2.8. {a},{a, c},{a, d},{a, e},{a, c, d},{a, c, e},{a, d, e},{a, c, d, e}.
1.2.9. ZorZ+. The smallest is{ 0 , 1 , 3 , 4 , 5 }.
1.2.10. (a){a, b, c, d, e}. (b) The union operation is associative. (c) The
union of any set of sets consists of those elements that are elements of at
least one of the sets.
1.2.11. The union of a set of sets{A 1 ,A 2 ,...,Ak}is the smallest set
containing eachAias a subset.
1.2.12. 6 , 9 , 10 ,14.
1.2.13. The cardinality of the union is at least the larger ofnandmand
at mostn+m.
1.2.14. (a){ 1 , 3 }; (b)∅; (c){ 2 }.
1.2.15. The cardinality of the intersection is at most the minimum ofn
andm.
1.2.16. Commutativity (1.2) is obvious. To show that (A∩B)∩C =
A∩(B∩C), it suffices to check that both sides consist of those elements
that belong to all three ofA, B, andC. The proof of the other identity in
(1.3) is similar. Finally, one can prove (1.4) completely analogously to the
proof of (1.1).
1.2.17. The common elements ofAandBare counted twice on both sides;
the elements in eitherAorBbut not both are counted once on both sides.
1.2.18. (a) The set of negative even integers and positive odd integers.
(b)B.
1.3 The Number of Subsets
1.3.1. (a) Powers of 2. (b) 2n−1. (c) sets not containing the last element.
1.3.2. 2 n−^1.
1.3.3. Divide all subsets into pairs such that each pair differs only in
their first element. Each pair contains an even and an odd subset, so their
numbers are the same.
1.3.4. (a) 2· 10 n−1; (b) 2·(10n− 10 n−^1 ).
1.4.1. 101.
1.4.2. 1+ nlg 2.
1.5 Sequences
1.5.1. The trees have 9 and 12 leaves, respectively.
1.5.2. 5 · 4 ·3 = 60.