Let $A$ be infinite, meaning that there is no injection from $A$ to $\{1,…,n\}$ for all $n\in \mathbb{N}$ and assume there exists $f:A\rightarrow \mathbb{N}$ which is injective. I am trying to show there must be an bijection from $A$ to $\mathbb{N}$.
My train of thought so far has been:
Assume there is no bijection from $A$ to $\mathbb{N}$. Then $f$ is not surjective. Let $i \in \mathbb{N}$ be the smallest element of $\mathbb{N}$ which is not mapped to $\mathbb{N}$ by $f$. This gives rise to an injective map $f_i:A \rightarrow \mathbb{N}\setminus \{i\}$. If $f_i$ were surjective this means for all $j \in \mathbb{N}\setminus \{i\}$ there exists some $a_j$ in $A$ such that $f_i(a_j)=j$. Define $g:\mathbb{N}\setminus \{i\} \rightarrow \mathbb{N}$ by $g(n)=n$ for $i<n$ and $g(n)=n-1$ for $n>i$. $g$ is a bijection, and so $g\circ f_i: A \rightarrow \mathbb{N}$ is a bijection, contradiction our assumption no such function exists. Thus $f_i$ cannot be surjective. Repeating this process shows that there is no bijective map
$$f_P:A \rightarrow \mathbb{N}\setminus \{P\},$$
where $P$ is a finite set of elements of $\mathbb{N}$.
I really don't know if this is going anywhere though. Is this train of thought correct, and (if so) is there a way to extend it to a proof? If not, how would one show this?
Note: this is not homework,at least not my homework. I found it in some lecture notes I was reading.
Best Answer
Here is an alternative way to prove that:
Let $B\subseteq\mathbb N$ be the range of the injection $f\colon A\to\mathbb N$.
We will define $g\colon B\to\mathbb N$ which is a bijection, then $g\circ f\colon A\to\mathbb N$ will be a bijection (can you see why?).
$B$ is infinite and therefore non-empty, therefore it has a minimal element. Let $b_0$ be the minimal element of $B$, denote $B_0=B\setminus\{b_0\}$. Note that $B_0$ is infinite.
Suppose that $b_n$ and $B_n$ were defined. Since $B_n$ is infinite, it is non-empty and thus has a minimal element. Call this element $b_{n+1}$, and define $B_{n+1}=B_n\setminus\{b_{n+1}\}$. We only removed one element, so $B_{n+1}$ is infinite.
The map $g(b_n)=n$ is a bijection between $B$ and $\mathbb N$. It is surjective because we defined $b_n$ for all $n\in\mathbb N$ in the induction process, and it is injective because whenever $b,b'\in B$, and $b\neq b'$ there is some $n$ such that $b\in B_n$ and $b'\notin B_n$ (or vice versa). In such case $g(b)\geq n>g(b')$.
Now we have a bijection between $A$ and $\mathbb N$ defined as $g\circ f$.