Question

Bijection between power set of natural numbers and {0,1}^n

Answer 1

Answer:

The set {0,1}N{0,1}N is the set of functions from NN to {0,1}{0,1}. The power set of NN is the set of all subsets of NN. How do you relate these two?

Similarly, to each subset S∈NS∈N you can associate a function, let's call it fSfS, such that fS(n)=1fS(n)=1 if n∈Sn∈S, and fS(n)=0fS(n)=0 if n∉Sn∉S.

In this way we make every function in {0,1}N{0,1}N correspond to exactly one subset of NN, and viceversa. To finish the proof, note that fSf=ffSf=f and SfS=SSfS=S. This is why it's an equivalence (the technical term is "bijection").

Step-by-step explanation: