In this problem we show that there are more real numbers than there are natural numbers

Chapter 25, Problem 25.19

(choose chapter or problem)

In this problem we show that there are more real numbers than there are natural numbers. To begin, we define a function f from subsets of N to R; that is, f W 2 N ! R. Let A be a subset of N. We put f .A/ D X a2A 10a : For example, if A D f1; 2; 4g, then f .A/ D 101 C 102 C 104 which equals 0.1101 in decimal notation. a. Suppose A is the set of odd natural numbers. What is f .A/? Express your answer both as a decimal and as a simple fraction. b. Show that f is one-to-one. From Cantors Theorem (Theorem 25.4) we know there are fewer natural numbers than subsets of natural numbers, and from this problem there are at least as many real numbers as there are subsets of N. In symbols: jNj < 2 N jRj and so there are fewer natural numbers than real numbers. In fact, one can show there is a bijection between 2 N and R, so the above can be replaced by an D.