We are asked to prove using the Axiom of Choice that if $A$ is a countably infinite set then there is an injection $f: \mathbb{N} \to A$.
Here is my attempt at a proof:
Proof. Suppose $A$ is a countably infinite set. Then there is a surjection $f: \mathbb{N} \to A$ and for each $a \in A$, define the sets
$$B_{a} = \{n | f(n) = a\}.$$
Now by AoC, we have $F: \{B_{a}\}_{a \in A} \to \bigcup_{a \in A} B_{a}$ s.t. $F(B_{a}) \in B_{a}$ for any $a \in A$. Define the set
$$C = \{F(B_{a}) | a \in A\} \subseteq \mathbb{N}.$$
Consider the restriction $f|_{C}:C \to A$. Clearly $f|_{C}$ is a bijection.
To finish the proof, I need to find an injection $g: \mathbb{N} \to C$ (that way $f|_{C} \circ g $ is our desired injection).
Any hints for defining $g$?
Use the recursive definition $g(n) = \min\{x\in C:x>g(n-1)\}$ (where $g(0) = \min C$), which makes sense as long as $C$ is infinite.
It is easy to see that $g$ is strictly monotonous, thus injective. Indeed: By definition $g(n) > g(n-1)$. Inductively this proves that $g$ is strictly monotonous.
Also $g$ is in fact surjective. Assume that $C\setminus g(\mathbb N)\neq \emptyset$. Then it contains a smallest element $y$. As $g$ is strictly monotonous eventually $g(n)>y$. So if $n$ is the smallest $n$ so that $g(n) >y$ then $g(n-1) < y$. But then $y\in\{x\in C:x>g(n-1)\}$ but $y<g(n)$. So this cannot happen.