Let $A$ be an infinite subset of $\Bbb N$. Then there exists a bijection from $A$ to $\Bbb N$ 
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.
 A: 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:

Thus $f(a_1)<f(a_2)$. It follows that $f$ is injective

Perhaps you could expand this a bit and write

Thus $f(a_1)<f(a_2)$. This shows that $f$ is strictly increasing and hence injective.

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:

Assume that $f$ is not surjective

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.

Claim: $k \in \text{ran} \, f$ for all $k \in \mathbb{N}_0$.

$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$.
A: The proof of injectivity is correct. The fact that $A$ is infinite is not needed for this.
No contradiction is necessary for surjectivity.
First, $0=f(\min A)$.
Suppose $k=f(a)$; we want to find $a'\in A$ with $f(a')=k+1$. This will prove that the image of $f$ is $\mathbb{N}$.
Since $A$ is infinite, the set $B=\{b\in A:b>a\}$ is not empty. Let $a'=\min B$.
Then $\{x\in A:x<a'\}=\{x\in A:x<a\}\cup\{a\}$. One inclusion is clear. Let $y\in\{x\in A:x<a'\}$. If $y<a$, then $y\in\{x\in A:x<a\}$; otherwise $y\ge a$, so $a\le y<a'$ and we conclude $y=a$ by minimality of $a'$.
Since $\{x\in A:x<a\}\cap\{a\}=\emptyset$, we have
$$
|\{x\in A:x<a'\}|=|\{x\in A:x<a\}\cup\{a\}|=k+1
$$

A different approach uses Cantor-Schröder-Bernstein and the following theorem (which depends on countable choice).

If $A$ is infinite, there exists an injective map $f\colon\mathbb{N}\to A$. Therefore $|\mathbb{N}|\le|A|$.

Here $A$ need not be a subset of $\mathbb{N}$.
Since $A\subseteq\mathbb{N}$, we have $|A|\le|\mathbb{N}|$.
By Cantor-Schröder-Bernstein, $|A|=|\mathbb{N}|$.
