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!$ ?

  • 1
    $\begingroup$ $A$ has $16$ members, not $15$. The empty set is a $member$ of $P(\{1,2,3,4\})$. $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.