I am having difficulty understanding the answer to this question.
How many functions are there with domain $A$ and codomain $\{0, 1\}$?
$A = P(\{1, 2, 3, 4\})$.
$|A| = 2^{|{1,2,3,4}|} = 16$, so there are $16$ possible inputs. For each of these inputs, we can choose whether to map them to $0$ or $1$. So there are $2^{16} = 65536$ such functions.
I understand the first part ($2^4=16$), but the second part ($2^{16}$) is a little bit confusing to me.
On
Let's take a simpler example. Suppose $A=\{a,b,c\}$. Then if $f: A \rightarrow B$ is a function from $A$ to $B=\{0,1\}$, we have two choices for $f(a)$ - either $f(a)=0$ or $f(a)=1$. Similarly there are two choice for $f(b)$ and two choices for $f(c)$. Each set of choices gives a different function, so there are $2 \times 2 \times 2 = 2^3 = 8$ different functions from $A$ to $B$.
In the question above $|A|=16$ so the number of functions from A to B is $2^{16}=65,536$.
On
There is a reason for using $2^X$ to denote $\mathscr{P}(X)$, and for using $Y^X$ to denote the set of functions $X\to Y$. The cardinality of $2^X$ is $2^{|X|}$, and the cardinality of $Y^X$ is $|Y|^{|X|}$
So you are asking for the cardinality of $Y^X$, where $Y=\{0,1\}$ and $X=\mathscr{P}(\{1,2,3,4\})$. Since $|X|=2^4$ from above and $|Y|=2$, we have the desired cardinality $$|Y^X|=|Y|^{|X|}=2^{2^4}=2^{16}=\boxed{65,536}$$
So $|\mathscr{P}(X)|=|\{0,1\}^X|=|\{0,1\}|^{|X|}=2^{|X|}$.
The size of $A$ is the number of subsets that you can create with the $4$ elements $A$ has, you can choose to use or not and element, since you got $4$ elements there are $4$ chooses of put or not to be made: $|A| = 2^4 = 16$. Now to count the functions from $A$ to ${0,1}$ just think that we need to associate an image to each element of $A$ and we have $2$ possible imagens. Enumerate the sets of $A$, choose an image to the first set (2 choices), than choose an image to the second set (times 2 choices from the multiplication rule), keep going and you will end in $2^{16}$.