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.

4. Let R be the relation between people and the cars they own; that is, the pair (x,y) is in R if x is a person, y is a car, and x owns y. Does R represent a function? Why or why not?
Answer: No, because a relation on two sets X and Y is only a function when each member of X is on the left hand side of exactly one pair. But in this example, some people are not in any pairs (they don't own any cars), or are in more than one pair (they own more than one car).