Let $A$ be an infinite subset of $\Bbb N$. Then there exists a bijection from $A$ to $\Bbb N$.
My attempt:
We define $f:A \to \Bbb N$ by $f(a)=|\{a'\in A\mid a'<a\}|$.
- $f$ is injective
For $a_1,a_2\in A$ and $a_1<a_2$, then $\{a'\in A\mid a'<a_1\} \subsetneq \{a'\in A\mid a'<a_2\}$, then $|\{a'\in A\mid a'<a_1\}| < |\{a'\in A\mid a'<a_2\}|$. Thus $f(a_1)<f(a_2)$. It follows that $f$ is injective.
- $f$ is surjective
Assume the contrary that $f$ is not surjective. Let $k=\min \{n \in \Bbb N \mid n \notin \operatorname{ran}f\}$. It's clear that $0 \in \operatorname{ran}f$ since $|f(\min A)|=|\{a'\in A\mid a'<\min A\}|=|\emptyset|=0$. It follows that $0<k$. Let $k=p+1$, then $p = f(b)=|\{a'\in A\mid a'<b\}|$ for some $b \in A$. Let $c=\min \{a' \in A \mid b<a'\}$, then $\{a'\in A\mid b \le a'<c\}=\{b\}$. Next we prove $f(c)=k$.
We have $\{a'\in A\mid a'<c\} =\{a'\in A\mid a'<b\} \bigcup \{a'\in A\mid b \le a'<c\}=\{a'\in A\mid a'<b\} \bigcup \{b\}$, thus $|\{a'\in A\mid a'<c\}|=|\{a'\in A\mid a'<b\}| + |\{b\}|=p+1$. Thus $f(c)=p+1=k$, and consequently $k \in \operatorname{ran}f$. This contradicts the fact that $k=\min \{n \in \Bbb N \mid n \notin \operatorname{ran}f\}$. Hence $f$ is surjective.
To sum up, $f$ is bijective.
Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!
Update: As @saz suggested in his answer, I did not explicitly use the fact that $A$ is infinite in my proof.
Let $c=\min \{a' \in A \mid b<a'\}$…
To show that such $c$ does exists, we must prove that $\{a' \in A \mid b<a'\}\neq \emptyset$. This claim is justified by the fact that $A$ is infinite.
Best Answer
As far as I can see, your reasoning is fine. Some remarks:
Remark 1: From your proof it is not really clear where you use that $A$ is infinite so I would stress this fact a bit more at the place(s) where you need it.
Remark 2:
Perhaps you could expand this a bit and write
This is probably a matter of taste, but in my opinion it often helps to name things. Many reader are aware of certain implications ( e.g. "strictly monotone $\implies$ injective" or "differentiable $\implies$ continuous or...) and it helps them to point them to the implication which you are using. Here it is quite obvious, but once you are dealing with more abstract/complicated objects, this becomes more important.
Remark 3:
This is certainly also a matter of taste, but I would find it more straight-forward to prove the assertion directly by induction. Essentially this is already what you are doing, but you are doing it (kind of artifically, in my opinion) by contradiction.
$k=0$: ... that's the first part of the first paragraph on surjectivity.
$k \to k+1$: If $k \in \text{ran} \, f$, then $k=f(b)$ for some $b \in A$ and you can follow exactly your reasoning to construct $c \in A$ such that $f(c)=k+1$.