Knowing $|A| \leq |B|$, how do I prove $|C^A| \leq |C^B|$? Given three (nonempty) sets $A, B$ and $C$, and knowing that $|A| \leq |B|$, how can I prove that $|C^A| \leq |C^B|$? This problem is trivial if we want to prove that the sets are equipotent, because it is very easy to create a bijective function. 
Here, we know that there exists an injective function $\phi: A \rightarrow B$, and we have to construct another injection, $\psi: C^A \rightarrow C^B$. I came up with this: let $f: A \rightarrow C$ and $b \in B$; then
$(\psi(f))(b) = 
\begin{cases}
f(a)  & \exists \,a \in A \;\; \phi(a) = b\\
??? & \text{otherwise}
\end{cases}
$
But I couldn't figure out what to do in the second case (which is very possible because we know that $A \subseteq B$). Intuitively, it is rather obvious that if we have less elements in $A$ than in $B$, then less functions transforming $A$ into $C$ exist, but of course some sort of formal proof is needed.
Since I don't know how standard that notation is, I'd like to clarify that $A^B$ denotes the set of all possible functions transforming elements of $B$ into elements of $A$. 
 A: Since $\left|A\right|\leq\left|B\right|$, we have an injection $\phi:A\to B$. Fix some $c_0\in C$ and define
$$\psi:C^A\to C^B$$
by
$$\left(\psi\left(f\right)\right)\left(b\right)=\left\{\begin{matrix}\phi\left(a\right)&\exists a\in A:\phi\left(a\right)=b\\c_0&\textrm{Otherwise}\end{matrix}\right.$$
This is the desired injection.
A: If you don't mind using the Axiom of Choice, here's an alternative to using an injection $A\to B$.
By assumption, $A\ne\emptyset$. Thus $\lvert A\rvert \le \lvert B\rvert$ implies (using AC) that there is a surjection $\varphi\colon B\to A$. Now we can define an injection:
$$
f\mapsto f\circ \varphi\colon C^A\to C^B.
$$
This is an injection because $\varphi$ is an surjection and therefore an epimorphism i.e. right-cancellable: if $f\circ\varphi = g\circ\varphi$ then $f=g$. (To prove that: if $f\circ\varphi = g\circ\varphi$, then for any $a\in A$, $a=\varphi(b)$ for some $b\in B$, so $f(a) = f(\varphi(b)) = g(\varphi(b)) = g(a)$.)
By the way, the statement is not true for $C = \emptyset$:
$$\lvert \emptyset^X \rvert = \begin{cases} 
1 &\text{if $X = \emptyset$,} \\
0 &\text{if $X \ne \emptyset$.} \\
\end{cases}$$
