50 CHAPTER 3. SET THEORY

not hypothetical. Tyrants usually seek to deprive others of their agency to do whatthey want. Do they have a right to do this if they want to?)

3. Only the good die young. It says so in a song. Which is the correct diagram tocorrespond to this statement? Sometimes such pictures are helpful.

die youngthe good

the gooddie young

4. DeMorgan’s laws are very useful in mathematics. Let S be a set of sets each ofwhich is contained in some universal set, U . Show

∪{

AC : A ∈S}= (∩{A : A ∈S })C

and∩{

AC : A ∈S}= (∪{A : A ∈S })C .

5. Let S be a set of sets show B∪∪{A : A ∈S }= ∪{B∪A : A ∈S } .

6. Let S be a set of sets show B∩∪{A : A ∈S }= ∪{B∩A : A ∈S } .

7. Show the rational numbers are countable, this is in spite of the fact that between anytwo integers there are infinitely many rational numbers. What does this show aboutthe usefulness of common sense and instinct in mathematics?

8. From Problem 7 the rational numbers can be listed as {ri}∞

i=1 . Let j ∈ N. Show that

Q= ∪∞i=1∩∞

j=1

(ri−

1j,ri +

1j

), R= ∩∞

j=1∪∞i=1

(ri−

1j,ri +

1j

)Thus you can’t switch intersections and unions in general.

9. Show the set of all subsets of N, the natural numbers, which have 3 elements, iscountable. Is the set of all subsets ofNwhich have finitely many elements countable?How about the set of all subsets of N?

10. We say a number is an algebraic number if it is the solution of an equation of theform anxn + · · ·+ a1x+ a0 = 0 where all the a j are integers and all exponents arealso integers. Thus

√2 is an algebraic number because it is a solution of the equation

x2− 2 = 0. Using the observation that any such equation has at most n solutions,show the set of all algebraic numbers is countable.

11. Let A be a nonempty set and let P (A) be its power set, the set of all subsets of A.Show there does not exist any function f , which maps A onto P (A). Thus the powerset is always strictly larger than the set from which it came. Hint: Suppose f is onto.Consider S ≡ {x ∈ A : x /∈ f (x)}. If f is onto, then f (y) = S for some y ∈ A. Isy ∈ f (y)? Note this argument holds for sets of any size.

12. The empty set is said to be a subset of every set. Why? Consider the statement: Ifpigs had wings, then they could fly. Is this statement true or false?