Sets and the like

2.5 Name sets having cardinality (a) 52, (b) 13, (c) 32, (d) 100, (e) 90, (f) 2,000,000.

(a) all cards in a deck; (b) all spades in a deck; (c) a deck of Swiss cards; (d) non- negative integers with at most two digits; (e) non-negative integers with exactly two digits; (f) inhabitants of Budapest, Hungary.

2.6 What are the elements of the following (admittedly peculiar) set: {Alice,{1}}?

Alice, and the set whose only element is the number 1.

2.7 We have not written up all subset relations between various sets of numbers; for example, Z ⊆ R is also true. How many such relations can you find between the sets ∅,N,Z+,Z,Q,R?

6·5/2 = 15.

2.8 Is an “element of a set” a special case of a “subset of a set”? no

2.9 List all subsets of {0,1,3}. How many do you get?

∅,{0},{1},{3},{0,1},{0,3},{1,3},{0,1,3}. 8 subsets.

2.10 Define at least three sets, of which {Alice, Diane, Eve} is a subset.

women; people at the party; students of Yale.

2.12 Define a set, of which both {1,3,4} and {0,3,5} are subsets. Find such a set with a smallest possible number of elements.

Z or Z+. The smallest is {0,1,3,4,5}.

2.13 (a) Which set would you call the union of {a,b,c}, {a,b,d} and {b,c,d,e}?

(a) {a,b,c,d,e}. (b) The union operation is associative. (c) The union of any set of sets consists of those elements which are lements of at least one of the sets.

2.15 We form the union of a set with 5 elements and a set with 9 elements. Which of the following numbers can we get as the cardinality of the union: 4, 6, 9, 10, 14, 20?

6,9,10,14.

2.16 We form the union of two sets. We know that one of them has n elements and the other has m elements. What can we infer for the cardinality of the union?

The cardinality of the union is at least the larger of n and m and at most n + m.

2.17 What is the intersection of
(a) the sets {0,1,3} and {1,2,3};
(b) the set of girls in this class and the set of boys in this class; (c) the set of prime numbers and the set of even numbers?

(a) {1,3}; (b) ∅; (c) {2}.

2.18 We form the intersection of two sets. We know that one of them has n elements and the other has m elements. What can we infer for the cardinality of the intersection?

The cardinality of the intersection is at most the minimum of n and m.

2.19 Prove that |A∪B|+|A∩B| = |A|+|B|.

The common elements of A and B are counted twice on both sides; the elements in either A or B but not both are counted once on both sides.


2.20 The symmetric difference of two sets A and B is the set of elements that belong to exectly one of A and B.

(a) What is the symmetric difference of the set Z+ of non-negative integers and the set E of even integers (E = {...−4,−2,0,2,4,... contains both negative and positive even integers).

(b) Form the symmetric difference of A ad B, to get a set C. Form the symmetric difference of A and C. What did you get? Give a proof of the answer.

a) The set of negative even integers and positive odd integers. (b) B.

The number of subsets

Theorem 2.1 A set with n elements has 2^n subsets.

2.21 Under the correspondence between numbers and subsets described above, which number correspond to subsets with 1 element?

Powers of 2.

2.22 What is the number of subsets of a set with n elements, containing a given element?

2^(n−1).

2.23 What is the number of integers with (a) at most n (decimal) digits; (b) exactly n

digits?


(a) 2·10^n −1; (b) 2·(10^n −10^n−1.

2.24 How many bits (binary digits) does 2100 have if written in base 2?

101.

Sequences

Theorem 2.2 The number of strings of length n composed of k given elements is k^n.

Theorem 2.3 Suppose that we want to form strings of length n so that we can use any of a given set of k1 symbols as the first element of the string, any of a given set of k2 symbols as the second element of the string, etc., any of a given set of kn symbols as the last element of the string. Then the total number of strings we can form is k1 ·k2 ·...·kn.

2.27 In a sport shop, there are T-shirts of 5 different colors, shorts of 4 different colors, and socks of 3 different colors. How many different uniforms can you compose from these items?

5·4·3 = 60.

2.28 On a ticket for a succer sweepstake, you have to guess 1, 2, or X for each of 13 games. How many different ways can you fill out the ticket?

3^13.

2.29 We roll a dice twice; how many different outcomes can we have (a 1 followed by a 4 is different from a 4 followed by a 1)?

6·6=36.

2.30 We have 20 different presents that we want to distribute to 12 children. It is not required that every child gets something; it could even happen that we give all the presents to the same child. In how many ways can we distribute the presents?

12^20.

2.31 We have 20 kinds of presents; this time, we have a large supply from each. We want to give presents to 12 children. Again, it is not required that every child gets something; but no child can get two copies of the same present. In how many ways can we give presents?

(2^20)^12.