# ICS 1F, Homework 2 Solutions

1. (a) Below is a partially completed table giving A u B, A n B, |A u B|, and |A n B| for various sets A and B. (Assume that a,b,c,... refer to distinct objects. Note that I am using n and u as a rough approximation to the union and intersection symbols due to limitations in web browser technology. Complete the table.
 A B A u B A n B |A u B| |A n B| {a,b,c,d,e} {b,c,d,e,f} {a,b,c,d,e,f} {b,c,d,e} 6 4 {a,b} {d} {a,b,d} Ø 3 0 {a,c,e} {c,d,e} {a,c,d,e} {c,e} 4 2 {a,b,f} {a,b,c,d,e,f} {a,b,c,d,e,f} {a,b,f} 6 3 {b,c,d,e} {c,f,g} {b,c,d,e,f,g} {c} 6 1
(b) Can you give a formula for |A u B| in terms of |A|, |B|, and |A n B|? If so, explain why it is true.
Answer: |A u B| = |A| + |B| - |A n B|.

If you add |A| + |B|, everything in A u B gets counted at least once, but some members get counted twice. The elements counted twice are the ones in both A and B, so subtracting |A n B| makes up for this overcounting and counts everything in A u B exactly once.

2. We discussed the power set P(S) of a set S in class. An example of a power set is
P({black,white}) = { Ø, {black}, {white}, {black,white} }.
(a) List the elements of the power set of {blue,red,yellow}.
Answer: Ø, {blue}, {red}, {yellow}, {red,yellow}, {blue,yellow}, {blue,red}, {blue,red,yellow}
(b) What is the size of the power set of {puce,turquoise,taupe,khaki,lime,cyan,emerald}? (You do not have to list all the elements of the power set, just give its size.)
Answer: the set has 7 members, so its power set has 27 = 128 members.

3. Write out the mathematical notation used as shorthand for the following phrases.
(a) x is not a member of the empty set.
(b) The empty set is a subset of the powerset of U.
(c) The intersection of A and B is equal to the union of C and D.
(d) The complement of X is a superset of Y.
(e) X is the set of ordered pairs in which the first item in the pair is taken from set Y and the second item is taken from set Z.