If an endofunction is surjective and non-injective its domain is infinite

elementary-set-theoryfunctionsinfinity

I'm currently reading about proofs and would appreciate some feedback on my attempted proof below.

"A surjective and non-injective function $ f : A \longrightarrow A$ exists if and only if A is infinite."

Consider the infinite set $A = \mathbb{N}$.

If A is infinite there exists a subset $S$ such that $S \subset A$ and $S \sim A$ (proper and equinumerous).

Suppose a function $ f : A \longrightarrow A$, such that

$f : a \mapsto \left\{
\begin{array}{rcl}
\frac{a}{2} & \mbox{if } 2\mid a \\
{a} & \mbox{otherwise}
\end{array}
\right.
$

$f(1) = f(2) = 1,$ thus $f$ is not injective, but surjective.

The set of all positive even numbers $S = \{2n : n \in \mathbb{N}\} $ is a proper and equinumerous subset of $A$. $A$ is therefore infinite and the initial proposition is true.

Is this proof acceptable? Have I proved the "if and only if" as well?

Best Answer

You seem to have misunderstood the statement that you are asked to prove. It is meant to be read with an implicit universal quantifier on $A$, so it means

For all $A$, a surjective and non-injective function $ f : A \longrightarrow A$ exists if and only if $A$ is infinite.

You have instead just given one example of a set $A$ which is infinite and has such a function. This would prove the "if and only if" statement for that one particular value of $A$, but you need to prove it no matter what $A$ is. (In any case, there would be an easier way to give an example of just one set for which the statement is true--you could instead pick an $A$ such that both sides are false, such as $A=\emptyset$.)

Related Question