Let $f:X\to\Bbb N$ be your injection. Let $M=f[X]$. First define a bijection $g:\Bbb N\to M$ recursively as follows. First, $g(0)=\min M$. If $n\in\Bbb Z^+$, and $g(k)$ has been defined for $k<n$, let $$g(n)=\min\Big(M\setminus\{g(0),\dots,g(n-1)\}\Big)\;.$$ It’s straightforward to verify by induction that $g$ is a bijection.
Added: First, it’s clear that $g$ is injective, since the construction ensures that if $m<n$, then $g(n)\ne g(m)$. To show that $g$ is surjective, it suffices to show that for each $n\in\Bbb N$, $$\{g(k):k<n\}=\{m\in M:m<g(n)\}\;:\tag{1}$$ this ensures that each member of $M$ less than $g(n)$ is already ‘hit’ by the function $g$, so $g$ has no ‘holes’ in its range.
$(1)$ is trivially true for $n=0$: both sides are empty. Suppose that it holds for some $n\in\Bbb N$; we want to show that $\{g(k):k\le n\}=\{m\in M:m\le g(n)\}$. It’s clear that $\{g(k):k\le n\}\subseteq\{m\in M:m\le g(n)\}$, so suppose that $m\in M$, $m\le g(n)$, and $m\notin\{g(k):k\le n\}$. Then $m<g(n)$, and $m\notin\{g(k):k<n\}$, contradicting the definition of $g(n)$ as the smallest member of $M$ not in $\{g(k):k<n\}$. $\dashv$
Since $f$ is an injection, it’s a bijection from $X$ to $M$, and $f^{-1}$ is a bijection from $M$ to $X$. We now have
$$\Bbb N\overset{g}\longrightarrow M\overset{f^{-1}}\longrightarrow X\;,$$
where each of the maps is a bijection, so their composition is a bijection from $\Bbb N$ to $X$.
(1,2) As written, the proof certainly seems to appeal to the axiom of choice for choosing each of the $x_y$s. But this is not necessary and easily eliminated: since you know that $A$ is countable, you can choose a bijection $A\leftrightarrow \mathbb N$ once and for all, and then for every $y$ let $x_y$ be the element in $F_y$ that has the smallest index.
(3) Yes, this is the Cantor-Schröder-Bernstein theorem, and it does not depend on the axiom of choice. The corresponding theorem for surjections does require AC.
Best Answer
Unfortunately, there is no uniform agreement to the meaning of "countable". Specifically, does it mean only countably infinite, or do we include also finite sets?
Well. The answer depends on context, convenience, and author. Sometimes it's easier to separate the finite and infinite, and sometimes it's clearer if we lump them together.