Equivalent sets proof Let $A$ be a set. Show that $\cal P(A)$ - the power set of $A$ - is equivalent (same cardinal) to ${\{0, 1\}}^A$ - the set of all functions from $A$ to $\{0, 1\}$. Suppose $A$ was $\mathbb{N}$; would this hold? How about if $A$ was $\mathbb{N}^\mathbb{N}$ (the set of sequences with values in $\mathbb{N}$)?
My friend gave me the following proof:
It suffices to construct a bijective function.
Suppose that $f: A \rightarrow \{0, 1\}$, and let $A_f$ be the set of elements such that $a\in  A_f \iff f(a)=1$. Define the map $h(f) =A_f$ then we proceed to show injectivity and surjectivity:
Injectivity:
Suppose that for functions $f, g$, we have $f\ne g$. Then there is an $x\in A$ so $f(x)=1$ and $g(x)=0$ or vice versa. Then $A_f\ne A_g$. By the contrapositive argument, $h$ is injective.
Surjectivity:
Let $X\in{\cal P}(A)$ and then define a function $f$ as follows:
$$f(x)=\cases{1, if x\in B\cr 0, if x \notin B }$$
Then $X = h(f)$ and $h$ is surjective.
We have a bijection $h:{\{0, 1\}}^A \rightarrow {\cal P}(A)$ so, we may conclude that the two sets are equivalent.
Is this proof correct? Is there a more formal or more detailed way to express it? In addition, does this proof carry forward to $\mathbb{N}$ and $\mathbb{N}^\mathbb{N}$ defined in the problem above? Any assistance much appreciated.
 A: I'd be more direct.
Let $f\in \{0,1\}^A$.  Then $f$ is a function $f: A \to \{0,1\}$
Consider $\{a\in A| f(a) = 1\}$.  That's well defined subset of $A$.
And so $\phi:\{0,1\}^A\to \mathscr P(A)$ via $\phi(f) = \{a\in A| f(a) = 1\}$ is a well-defined function.
Now its just a matter of proving it is surjective and injective.

*

*It is surjective.

Let $E\subset A$.  Define $g:A\to \{0,1\}$ via $g(a) =\begin{cases}1&a\in E\\0&a\not \in E\end{cases}$.  $g$ is a well defined function from $A\to \{0,1\}$. so $g \in \{0,1\}^A$.
Because that's what $\{0,1\}^A$ is:  Its the collection of all possible functions for $A\to \{0,1\}$ and $g$ certainly is a function that for every element of $A$ maps distinctly to either $0$ or $1$.
And $\phi(g)=\{a\in A|g(a)=1\} = \{a\in A|a \in E\} =E$.
SO for all $E\in \mathscr P(A)$ there a $g\in \{0,1\}^A$ so that $\phi(g) = E$. So $\phi$ is surjective.


*It is injective.

$f, g\in \{0, 1\}^A$ and $\phi(f)=\phi(g)=E$.  Then for every $a \in A$ we have either $a\in E$ in which case $f(a)=g(a) = 1$; or $a \not \in E$ in which case $f(a)=g(a)=0$. In either case $f(a) =g(a)$ for all $a \in A$.
So $f = g$.  For any $f,g \in \{0,1\}$ we have $\phi(f)=\phi(g) \iff f=g$ so $\phi$ is injective.
....
ANd that's that.
....
This will hold of $A = \mathbb N$ or $A =\mathbb N^{\mathbb N}$ or for any set.
$\{0,1\}^{\mathbb N}$ is the set of all functions from $\mathbb N \to \{0,1\}$.  We can find a one-to-correspondence between any subset of the natural numbers to a function (and vice versa) by for each subset considering the function where $f(n)=1$ if $n \in A\subset \mathbb N$ and $f(m) = 0$ if $m\not \in A$.
......
COuld you try harder to put your finger on what in your gut doesn't feel right because this is utterly complete and formal and foolproof so far as I can tell.
