Problem 7.4.9
Claim

The power set of the natural numbers $\mathcal{P}(\mathbb{N})$ has the same cardinality as the set of all sequences of 0's and 1's.

Proof

Let $X$ be the set of sequences of 0's and 1's.
Define $f: \mathcal{P}(\mathbb{N}) \to X$ via

(1)
\begin{align} f(A)=(A_i)_{i=1}^{\infty} \end{align}

where $A \subseteq \mathbb{N}$ and $(a_i)$ is defined by

(2)
\begin{align} a_i=\begin{cases} 0, & \text{if } i\notin A\\ 1, & \text{if } i\in A \end{cases}. \end{align}

We need to show that $f$ is one-to-one and onto.

1-1:
Let $A_i, A_2 \in \mathcal{P}(\mathbb{N})$. Assume $f(A_1) = f(A_2)$. Then $f(A_1) = (a_i)$ and $f(A_2) = (b_i)$, where $(a_i), (b_i) \in X$. So, $(a_i) = (b_i)$. For all $i$, $a_i = b_i$. The only way for $a_i = b_i$ to be true is if $A_1$ and $A_2$ have the same elements. Therefore, $A_1 = A_2$. Thus, $f$ is one-to-one.

Onto:
Let $(a_i) \in X$. Define $A$ via $i \in A$ iff $a_i = 1$. Hence, $f(A) = (a_i)$. Thus $f$ is onto.

In conclusion, $f$ is one-to-one correspondence, hence $\mathcal{P}(\mathbb{N})$ and $X$ have the same cardinality.

$\blacksquare$


Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License