# Calculating number of functions with a power set

How many functions are there with domain $A = \mathcal{P}(\{1, 2, 3, 4\})$ and codomain $\{0, 1\}$?

If it was not a power set, I know that it would be $16$ derived from $2^4$. With the power set, I can make $15$ unique alternatives from $$\{1\},\{2\},\{3\},\{4\},\{1,2\},\{1,3\},\{1,4\}, \{2,3\},\{2,4\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,3,4\}.$$

Would I be correct in assuming that the number of functions would be $2^{15}$.

How many one-to-one functions are there with domain A and codomain $\{0, 1\}$?

Since there are $4$ elements in $A$, can I assume that the answer is $4!$ ?

• $A$ has $16$ members, not $15$. The empty set is a $member$ of $P(\{1,2,3,4\})$. Apr 17 '18 at 10:56

Let $A_n$ be a set with $n$ elements, so assume that $A_n=\{1,2,\dots,n\}$, and let $f:A_n\to\{0,1\}=A_1$. Then there is some subset $C_1 \subseteq A_n$ such that every element in it gets sent to $1$ by $f$, and so every element not in it gets sent to $0$ (that is, $C_0= A_n \setminus C_1$). As you can see, then, $f$ is in direct correspondence with a subset $C_1$ of $A_n$; but $f$ lives in the space of functions from $A_n$ to $A_1$, let’s call it $\mathrm{Map}(A_n;A_1)$, and $C_1$ lives in the power set $\mathcal P(A_n)$, so we may establish a bijection (or set isomorphism) $\Phi : \mathrm{Map}(A_n;A_1) \to \mathcal P(A_n)$ that associates to every $f$ the subset of $A_n$ that is the preimage of $1\in A_1$. Since $\Phi$ is a bijection, the cardinality of its domain and codomain must be the same, and we know that the cardinality of the codomain is $2^n$. So that’s also how many maps there are between $A_n$ and $\{0,1\}$.
In your situation, the domain is itself a power set $\mathcal P(A_4)$, which has $16 = 2^4$ elements (you forgot the empty set!), so the above discussion holds with $n=16$.
Concerning your last question, I’m not sure I understand. $A= \mathcal P(A_4)$ contains $16$ elements, not $4$, and since the codomain only contains $2$ it has to be that two different elements in $A$ get sent to the same element in $\{0,1\}$ (by the pigeonhole principle). So there can be no injections between $\mathcal P(A_4)$ and $A_1$.