Question

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 `NN`. So every natural number corresponds to a particular subset of `NN`.

Answer 1

This mapping only works for finite subsets of `NN`, 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 `NN` and `NN`.

In other words, the set of finite subsets of `NN` is countable.

This is not the whole power set of `NN`, 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 `NN`.

Such infinite strings essentially describe functions from `NN` to `2 = {0, 1}`. So a common notation for the power set of `NN` is `2^NN`.