274 CHAPTER 4 Functions
- (a) Prove that if X and Y are countable sets, so are X U Y, X fl Y, X - Y, and X x Y,
(Caution: Countable means either finite or countably infinite, so there may be
separate cases to consider.)
(b) If X and Y are countably infinite, which of the following sets must be countably
infinite: X U Y, X n Y, X - Y, and X x Y? - Prove that every subset of N is countable.
- Prove that the function F : (0, 1) --* R defined as F(x) = (1/2 - x)/(x (1 - x)) is a
bijection. - Find 1-1 and onto functions from R to the following sets:
(a) (0, 1)
(b) [0, 1]
(c) (0, 1)- {1/2}
(d) JR - Q, the irrationals- Prove Theorem 1.
- Prove Corollary 2 to Theorem 9.
- A chain-letter scheme is a famous (and usually illegal) get-rich-quick scheme. A per-
son X receives a letter with, say, five names on it. X sends $10 to the person whose
name is at the top of the list. X then deletes that name from the top of the list, adds
his or her own name to the bottom of the list, and sends the letter to five "friends," all
within one day. In around two weeks, X is supposed to receive $31,250.
Suppose every person who receives the letter follows the instructions (including
sending $10 to the person listed first!). Show that if there are only finitely many peo-
ple, the scheme cannot work (in some sense of "cannot work" that you should make
precise). Show that if there are countably infinitely many people, the scheme can work. - Show for the natural numbers N that
P(N)I > INI- Challenge: Show that I JR = P(N) 1. (Hint: Use the Cantor-Schr6der-Bemstein The-
orem. To show that IR I < I P(N) I, you might use function D : JR --+ P(Q) where for
r E R, D(r) = {q e Q : q <r}.)
- Show that / is algebraic.
- Show that there are infinite sets
XO, X 1 , X 2. Xk, Xk±1l....where for each k E N, I Xk I < I Xk+1 I.- Challenge: Show how to modify Cantor's second diagonal argument so that the real
number produced is always irrational. (Hint: There is more than one way to do this.) - (a) Show that the set of all finite sequences of elements of the one-element set {0} is
countably infinite.
(b) Show that the set of all finite sequences of elements of the two-element set {0, 1}
is countably infinite.
(c) Challenge: Show that the set of all finite sequences of natural numbers is count-
ably infinite. (Hint: Use a diagonal argument.) - (a) Show that the set of all infinite sequences of elements of the one element set {0}
is finite.