0
$\begingroup$

Prove that $f: \{0, \dots , n \} \mapsto \{0, \dots , n \}$ is surjective $\iff$ is injective

I have written a solution to this problem but I am not sure whether it's correct and formally satisfactory.

  1. injective $\Rightarrow$ surjective
    Assume that this function is not surjective. Then, there is $y \in img(f)$ such that there is no $x \in dom(f)$ such that $f(x) =y$. And so, there are $x_1, x_2 \in dom(f)$ such that $f(x_1) = f(x_2)$ But $f$ is injective - contradiction.

2.surjective $\Rightarrow$ injective
Assume that $f$ is not injective. Then, there are $x_1, x_2 \in dom(f)$ such that $f(x_1) = f(x_2)$ This implies that there is a $y \in img(f)$ such that there is no$x \in dom(f) $ satisfying $f(x) = y$. However,$f$ is injective. Contradiction.

What do you think of my proof, is it valid?

$\endgroup$
1
$\begingroup$

None of them is correct. In the first proof, you don't justify why there is a $y$ for which there is no $x$ such that $f(x)=y$. In the second one, you don't justify the assertion that begins with “This implies that…”.

Note that at no point you used the fact that you are working with the set $\{0,1,\ldots,n\}$.

$\endgroup$
0
$\begingroup$

In (1), if $\;y\in\text{Im}\,(f)\;$ , then by definition $\;f(x)=y\;$ for some $\;x\in X\;$ . Even overseeing this, why then would we get that there are $\;x_1,x_2\in X\;$ s.t. ...etc.?

The same can be said about (2): not clear at all how you deduce stuff.

Here are a few ideas: Suppose $\;f:\{0,1,...,n\}\to\{0,1,...,n\}\;$ is injective . This means $\;\left|\{0,1,...,n\}\right|=;\left|\{f(0),f(1),...,f(n)\}\right|\;$ (why?), and thus every element $\;y\in\{0,1,...,n\}\;$ must be accounted for, which means that for any $\;y\in\{0,1,...,n\}\;$ there exists $\;x\in\{0,1,...,n\}\;$ s.t. $\;f(x)=y\;$ .

Now try to do by yourself the other direction.

$\endgroup$

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.