Problem: For any set $A$, finite or infinite, let $B^{A}$ be the set of all functions mapping $A$ into the set $B=\{0,1\}$. Show that the cardinality of $B^{A}$ is the same as the cardinality of the power set of $A$, $\mathscr{P}(A) .\left[\right.$ Hint: Each element of $B^{A}$ determines a subset of $A$ in a natural way. $]$
Starting with finite sets, the cardinality of $\mathscr{P}(A)$, is $2^{S}$ where $S$ is the cardinality of $A$. So I need to prove that the cardinality of $B^{A}$ is also $2^{S}$. Now lets look at an example set: $A_3=\{1,2,3\}$.
$B^{A_3}=\{ \{(1,0), (2,0), (3,0)\},\\ \{(1,0), (2,0), (3,1)\}, \\ \{(1,0), (2,1), (3,0)\},\\\{(1,1), (2,0), (3,0)\},\\ \{(1,0), (2,1), (3,1)\},\\ \{(1,1), (2,1), (3,0)\},\\\{(1,1), (2,0), (3,1)\},\\\{(1,1), (2,1), (3,01)\} \}$
Each function in $B^{A_3}$ has a cardinality of 3 because the cardinality of $A_3$ is 3. Since $A_3$ is the domain of the functions in $B^{A_3}$, each function has to have 3 elements to satisfy the properties of in the definition of a function. The only thing that sets all the functions in $B^{A_3}$ apart is the ordering and repetitions of $0$ and $1$ in the second entries of the ordered pairs.
Similarly, for any finite set, $A$, each function in $B^A$ will have a cardinality of $S$ and the only thing setting these functions apart will be the $0's$ and the $1's$. Thus, we can ignore the first entries of the ordered pairs in the functions and reduce this problem down to permutations of $0$ and $1$ where the number of times repetition is allowed is equal to $S$ (because of the cardinality of each function). The formula for permutations with repetitions is $n^r$ where where $n$ is the number of things to choose from, and we choose $r$ of them. Thus the cardinality of $B^{A}$ is $2^{S}$.
I think my proof for the finite sets is correct but my problem is with the infinite sets. My idea is that I can show a pairing between each element in $\mathscr{P}(A)$ to a nonnegative binary integer. That works very nicely with the permutations of the $0's$ and $1's$.The problem is that $A$ could be the set of all real numbers. The pairing to the nonnegative binary numbers doesn't work anymore. So I'm kind of lost here. You could have sets that have cardinalities of higher infinities. How am I supposed to prove the cardinality is the same for all infinities?
