4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks that makes sense! $\endgroup$ – J. Rowe Nov 10 '17 at 3:34
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That is what the OP was trying to prove. $\endgroup$ – Stephen Meskin Nov 10 '17 at 3:49
  • $\begingroup$ 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. $\endgroup$ – Carmeister Nov 10 '17 at 10:02
  • $\begingroup$ @StephenMeskin I should have been more explicit, as in the previous comment. $\endgroup$ – Ethan Bolker Nov 10 '17 at 11:19

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.