4
$\begingroup$

Let $V$ be a set such that $V$ is not a singleton. I have to prove that there doesn't exist an injection from $V^V$ to $V$.

As predecessor to this exercise, I have proven that there doesn't exist a surjection from $V$ to $V^V$, and I was wondering if i) the method is correct at all and ii) if I could use the same method for this question:

Proof. Suppose there exists a surjection $f:V\rightarrow V^V$. $V$ is not a singleton, so we can find distinct elements $v_0,v_1$ in $V$. We construct $g:V\rightarrow V$ such that there doesn't exist a $v\in V$ such that $f(v)=g$. Define $g$ as follows:

  • If $v_0$ is a fixed point of $f(v_0)$, let $g(v_0)=v_1$, else let $g(v_0)=v_0$. From this we know $f(v_0)\neq g$.
  • If $v_1$ is a fixed point of $f(v_1)$, let $g(v_1)=v_0$, else let $g(v_1)=v_1$. From this we know $f(v_1)\neq g$.
  • Now let $v\in V\setminus\{v_0,v_1\}$. Repeat, if $v$ is a fixed point of $f(v)$, let $g(v)=v_0$, else $g(v)=v$.

But then we know there is no $v\in V$ such that $f(v)=g$, so $f$ is no surjection.$\tag*{$\square$}$

Now, is this principle also applicable to the "reverse"?

$\endgroup$
  • 4
    $\begingroup$ If an injection exists from $X\to Y$ and $X$ is not empty, then it's easy to build a surjection $Y\to X$. $\endgroup$ – egreg Sep 17 '15 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.