Section 9: Problem 8 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

$^{*}$ Show that $\mathcal{P}(\mathbb{Z}_{+})$ and $\mathbb{R}$ have the same cardinality. [Hint: You may use the fact that every real number has a decimal expansion, which is unique if expansions that end in an infinite string of $9$ ’s are forbidden.]

A famous conjecture of set theory, called the continuum hypothesis, asserts that there exists no set having greater cardinality than $\mathbb{Z}_{+}$ and lesser cardinality than $\mathbb{R}$ . The generalized continuum hypothesis asserts that, given the infinite set $A$ , there is no set having greater cardinality than $A$ and lesser cardinality than $\mathcal{P}(A)$ . Surprisingly enough, both of these assertions have been shown to be independent of the usual axioms for set theory. For a readable expository account, see [Sm].

Two sets have the same cardinality if there is a bijection between them (Exercise 6 of §7). Further, the same exercise shows that if for two sets there are injections from each one into the other, then the sets have the same cardinality. We are going to use this fact. We show that there are injections $\mathbb{R}\leftrightarrow[0,1)\leftrightarrow\mathcal{P}(\mathbb{Z}_{+})$ .

There is a bijective function $h$ from $\mathcal{P}(\mathbb{Z}_{+})$ onto $\{0,1\}^{\omega}$ given by $f(S)_{i}=1$ iff $i\in S$ for every $S\subset\mathbb{Z}_{+}$ . Now we use the following fact (which is slightly different from the one in the exercise as it uses a binary not decimal expansion): every real number $x\in[0,1)$ has a unique binary expansion such that it does not end in an infinite sequence of $1$ ’s, moreover, different $x$ ’s correspond to different expansions. We call this injective expansion as

. Now, using this fact, it is immediate that $h^{-1}\circ f$ is an injection from $[0,1)$ into $\mathcal{P}(\mathbb{Z}_{+})$ . Further, if we take any sequence $s=(s_{1},s_{2},\ldots)$ of $0$ ’s and $1$ ’s, and construct a new sequence $s'=(0,s_{1},0,s_{2},\ldots)$ , then there is a unique real number $x\in[0,1)$ corresponding to the constructed sequence, and different sequences correspond to different numbers. Hence, there is an injection $g$ from $\{0,1\}^{\omega}$ into $[0,1)$ , and $g\circ h$ is an injection from $\mathcal{P}(\mathbb{Z}_{+})$ into $[0,1)$ .

It remains to show that there are injections from $\mathbb{R}$ into $[0,1)$ and vice versa. One way, take $f(x)=1/(1+e^{x})$ , and the other way $[0,1)\subset\mathbb{R}$ .

Subpages

Section 9: Problem 8 Solution

Section 9: Problem 8 Solution