find if a function is injective or surjective, involving a set of all functions as well as the power set of the domain. For $n \in \mathbb{N}$, let $A = \{a_1, a_2, a_3, · · · , a_n\}$ be a set and let $F$ be the set of all functions $f : A \rightarrow \{0, 1\}$ from
$A$ to $\{0, 1\}$. What is the size of $F$?
Now, for $P(A)$, the power set of $A$, consider the function $g : F \rightarrow  P(A)$, defined as
$g(f) = \{a \in A : f(a) = 1\}$.
Is $g$ injective? Is $g$ surjective?
My answer to the first part is:
There are $2^n$ number of ways to make a function $f$. Since $F$ is the set of all functions $f$, then 
$|F| = 2^n$.
The second part of this question has me a bit perplexed. My attempt so far:
$g$ takes an element from $F$ and maps it to an element in $P(A)$. Now clearly we can tell that $A$ has a cardinality of $n$ elements. By the definition of a power set, $|P(A)| = 2^n$. Because we are told $g$ is a function, then all elements in $F$ to a unique element $p$ in $P(A)$. Thus $g$ can map all elements in $F$ to a unique element in $P(A)$ as both sets contain $2^n$ elements. This particular arrangement makes $g$ both injective and surjective. However, $g$ could also map two unequal elements in $F$ to a single element in $P(A)$. This would make $g$ neither injective or surjective. Note, these are the only possibilities. $g$ can only be both injective and surjective or neither injective or surjective. The possibility of $g$ being injective but not surjective or vice-versa does not exist. 
 A: Suppose $f_1\neq f_2$
Then that implies that there must be at least one specific value of $a_0\in A$ for which $f_1(a_0)\neq f_2(a_0)$
Since $f~:~A\to\{0,1\}$ this implies that one of two things are true:


*

*Case 1:  $f_1(a_0)=1$ and $f_2(a_0)=0$

*Case 2: $f_1(a_0)=0$ and $f_2(a_0)=1$
Without loss of generality, suppose it was the first case.
Then $g(f_1)\ni a_0$ but $g(f_2)\not\ni a_0$ implying $g(f_1)\neq g(f_2)$
The remaining case is analogous.
We learned then that $f_1\neq f_2\implies g(f_1)\neq g(f_2)$.  By contrapositive, that is the same as saying $g(f_1)=g(f_2)\implies f_1=f_2$, the very definition of what it means to be injective.
As noted, if two finite sets have the same cardinality then a function between them is injective if and only if it is also surjective, so we learn that $g$ must also be surjective.
We could prove surjectivity without this however.
Suppose $K\in\mathcal{P}(A)$.  We wish to prove that there exists some $f_K~:~A\to\{0,1\}$ such that $g(f_K)=K$.
Indeed, if we define $f_K~:~A\to\{0,1\}$ as the following:
$$f_K(x)=\begin{cases}0&\text{if}~x\notin K\\1&\text{if}~x\in K\end{cases}$$
then we trivially have $g(f_K)=K$ by construction, thereby proving that $g$ is surjective.
