# 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.

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.

• Thanks that makes sense! – J. Rowe Nov 10 '17 at 3:34

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.

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.

• That is what the OP was trying to prove. – Stephen Meskin Nov 10 '17 at 3:49
• The OP is trying to prove that $A^A>A$, and this answer reduces it to showing that $2^A>A$, a much more "standard" result. – Carmeister Nov 10 '17 at 10:02
• @StephenMeskin I should have been more explicit, as in the previous comment. – Ethan Bolker Nov 10 '17 at 11:19