# Does the construction described below provide a correspondence between natural numbers and their power set?

## The binary representation of a natural number is writable as a sequence of $1$'s and $0$'s, corresponding to a sum of distinct powers of $2$. The indices of those powers form a subset of $\mathbb{N}$. So every natural number corresponds to a particular subset of $\mathbb{N}$.

Jun 11, 2017

This mapping only works for finite subsets of $\mathbb{N}$, so does not include all subsets.

#### Explanation:

I think you are suggesting that each set of natural numbers is equivalent to a natural number by forming a corresponding binary number.

That works, provided your sets are finite. So what you have found is a correspondence between the set of finite subsets of $\mathbb{N}$ and $\mathbb{N}$.

In other words, the set of finite subsets of $\mathbb{N}$ is countable.

This is not the whole power set of $\mathbb{N}$, which includes infinite subsets.

Transposing your binary representations and extending your scheme to infinite strings of $0$'s and $1$'s, we do have a representation of the elements of the power set of $\mathbb{N}$.

Such infinite strings essentially describe functions from $\mathbb{N}$ to $2 = \left\{0 , 1\right\}$. So a common notation for the power set of $\mathbb{N}$ is ${2}^{\mathbb{N}}$.