Need help proving there is not a surjective function from A to the set of all functions from A to A We have $F_A = \{ f|f:A\rightarrow A \}$ is the set of all functions from A to A, where A is a nonempty set that could be infinite. I'm trying to show that if $|A|>1$ then $|A| < | F_A |$. I have shown that $|A| \leq | F_A |$ by finding a one to one function from A to $F_A $, but I don't know how to go about showing there isn't an onto function.
 A: Suppose we have a surjective map $m: A \rightarrow F_A$, consider the image of an element $a \in A$ under this map; it will be a mapping $f_a : A \rightarrow A$, now consider the image of $a$ under this map, $ f_a(a)$ will be an element of  $ A$. Define a mapping $x:A \rightarrow A $ by requiring $x(a)$ is an element of $A$ that is different from $f_a(a)$; this function will not be in the image of $m$ and thus $m$ is not surjective.
A: If $A$ is finite then there is one constant function for each element of $A$ and since $|A| \ge 2$ there is at least one non-constant function.   
If $A$ is infinite use Cantor's diagonalization method. Assume there is a bijection $ \theta : A \to F_A$ let $f: A \to A$ be defined as follows: for all  $ a \in A,  f(a) \ne \theta(a)(a)^*$, then $f \not \in Image\theta$ contradicting that $\theta$ is a bijection.  
*1. Since $\theta (a)$ is a function  $\theta(a)(a)$ makes sense.
 2. As written, the proof seems to rely on the Axiom of Choice. This can be avoided if anything is known about $A$. Or presumably one can chose two elements of $A$ when one starts and use them for all $a$ without having to invoke the A of C.
A: If $A$ has more than one element then suppose two of them happen to be $0$ and $1$ (any other names will do). Then every function from $A$ to $\{0,1\}$ can be thought of as a function from $A$ to itself. But those special functions are the characteristic functions of the subsets of $A$, so correspond to elements of the power set $2^A$ of $A$. It's well known that the power set is larger.
