 Solution

Use the well-order of the natural numbers to list $A$ in increasing order. Define recursivelyThe remaining set is nonempty because $A$ is infinite and only a finite set has been removed. Each chosen value is larger than the preceding one, so $f$ is an injective function.

To prove it is a surjective function, fix $a\in A$. If $a$ were never selected, every selected minimum would be at most $a$. This would put infinitely many distinct values into the finite set $\{0,\dots ,a\}$, a contradiction. HenceThe increasing enumeration of an infinite subset of natural numbers uses no arbitrary choice: each next element is the uniquely determined minimum.