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

1 Answer
Jun 11, 2017

Answer:

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