Vtyjkyuk

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 Amid a'<a|$.

1. $f$ is injective
   

For $a_1,a_2in A$ and $a_1<a_2$, then $a'in Amid a'<a_1 subsetneq a'in Amid a'<a_2$, then $|a'in Amid a'<a_1| < |a'in Amid a'<a_2|$. Thus $f(a_1)<f(a_2)$. It follows that $f$ is injective.

2. $f$ is surjective
   

Assume the contrary that $f$ is not surjective. Let $k=min n in Bbb N mid n notin operatornameranf$. It's clear that $0 in operatornameranf$ since $|f(min A)|=|a'in Amid a'<min A|=|emptyset|=0$. It follows that $0<k$. Let $k=p+1$, then $p = f(b)=|a'in Amid a'<b|$ for some $b in A$. Let $c=min a' in A mid b<a'$, then $a'in Amid b le a'<c=b$. Next we prove $f(c)=k$.

We have $a'in Amid a'<c =a'in Amid a'<b bigcup a'in Amid b le a'<c=a'in Amid a'<b bigcup b$, thus $|a'in Amid a'<c|=|a'in Amid a'<b| + |b|=p+1$. Thus $f(c)=p+1=k$, and consequently $k in operatornameranf$. This contradicts the fact that $k=min n in Bbb N mid n notin operatornameranf$. 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.

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 textran , f$ for all $k in mathbbN_0$.

$k=0$: ... that's the first part of the first paragraph on surjectivity.

$k to k+1$: If $k in textran , 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$.

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 $mathbbN$.

Since $A$ is infinite, the set $B=bin A:b>a$ is not empty. Let $a'=min B$.

Then $xin A:x<a'=xin A:x<acupa$. One inclusion is clear. Let $yinxin A:x<a'$. If $y<a$, then $yinxin A:x<a$; otherwise $yge a$, so $ale y<a'$ and we conclude $y=a$ by minimality of $a'$.

Since $xin A:x<acapa=emptyset$, we have
$$
|xin A:x<a'|=|xin A:x<acupa|=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 $fcolonmathbbNto A$. Therefore $|mathbbN|le|A|$.

Here $A$ need not be a subset of $mathbbN$.

Since $AsubseteqmathbbN$, we have $|A|le|mathbbN|$.

By Cantor-Schröder-Bernstein, $|A|=|mathbbN|$.