##### 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

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

(2)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$

This problem is awesome!

First, the $\LaTeX$ syntax for $\mathcal{P}(\mathbb{N})$ is

Let $X$ be set of all sequences of 0's and 1's. Each element of $X$ is of the form $(a_i)_{i=1}^{\infty}$, where each $a_i$ equals 0 or 1 (but not both!). In order to show that $\mathcal{P}(\mathbb{N})$ and $X$ have the same cardinality, we need to show that there is a 1-1 correspondence between the two sets. Our job is to construct a function between these two sets and then show that it is (1) 1-1, and (2) onto. The hardest part is figuring out what the function should be and actually writing it down nicely. I'll do that part for you now.

Define $f: \mathcal{P}(\mathbb{N}) \to X$ via

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

(2)The $\LaTeX$ syntax for the above definition of $a_i$ is

All that remains to do is to show that $f$ is 1-1 and onto.

ReplyOptions