Prob 3 Sec 9 in Munkres TOPOLOGY 2nd ed: injections $f_n\colon\{1,\ldots,n\}\to A$ implies an injection $f \colon\mathbb{N}\to A$? Suppose that $A$ is a set and $\{f_n\}_{n\in\mathbb{N}}$ is a given indexed family of injective functions 
$$f_n \colon \{1, \ldots, n\} \to A.$$ 
Then (I can) show that $A$ is infinite. 
How to define an injective function $f \colon \mathbb{N} \to A$ without using the choice axiom? 
My effort: 
Let 
$$f(1) \colon= f_1(1).$$
Now as $f_2 \colon \{1, 2\} \to A$ is injective, we must have $f_2(1) \neq f_2(2)$. 
So we can conclude that either $f_2(1) \neq f_1(1)$ or $f_2(2) \neq f_1(1)$. 
That is, either $f_2(1) \neq f(1)$ or $f_2(2) \neq f(1)$. 
So the set $f\left(\{1, 2 \}\right) - f\left(\{1 \}\right)$ has at least one element. 
Let $k_1$ be the smaller  element of the set $\{1,2\}$ such that $f_2(k_1) \neq f_1(1)$. We define $f(2) \colon= f_2(k_1)$. 
Then $f(2) \neq f(1)$. 
Now $f_3 \colon \{1, 2, 3\} \to A$ is injctive, so the set $f_3\left(\{1,2,3\}\right)$ has exactly three elements, whereas the set $f(\{1,2\})$ has exactly two elements. Thus the set $f_3\left(\{1,2,3\}\right) - f(\{1,2\})$ has at least one element. 
Let $k_2$ be the smallest element of the set $\{1, 2, 3, \}$ such that $f_3(k_2) \not\in f(\{1,2\})$. 
Let's define $f(3) \colon= f_3(k_2)$. 
Then $f(3) \not\in f(\{1,2\})$. So $f(3) \neq f(1)$ and $f(3) \neq f(2)$. 
Suppose that $n \in \mathbb{N}$ such that $n \geq 2$, and suppose also that $f(1), \ldots, f(n)$ have beeen defined so that $f(i) \neq f(j)$ for any $i , j\in \{1, \ldots, n \}$ such that $i \neq j$. 
Now as the function $f_{n+1} \colon \{ 1, \ldots, n+1 \} \to A$ is injective, the set $f_{n+1}\left(\{1, \ldots, n+1 \}\right)$ has exactly $n+1$ elements. On the other hand, the set $f\left(\{1,\ldots, n\}\right)$ has exactly $n$ elements. So the set $f_{n+1}\left(\{1, \ldots, n+1 \}\right) - f\left(\{1,\ldots, n\}\right)$ has at least one element. 
Let $k_n$ be the smallest element of the set $\{1, \ldots, n+1\}$ such that $f_{n+1}(k_n) \not\in f\left(\{1,\ldots, n\}\right)$. So let's define 
$f(n+1) \colon= f_{n+1}(k_n)$. 
Obviously, $f(n+1) \neq f(i)$ for any $i \in \{1, \ldots, n \}$. 
In this way, we have defined a function $f \colon \mathbb{N} \to A$ such that $f(m) \neq f(n)$ for any $m, n \in \mathbb{N}$ such that $m>n$. 
Is this proof good enough? Is it rigorous enough? 
 A: No Choice is needed! Your proof looks just fine, and proceeds by the Principle of Countable Recursion. You could even shorten it as follows:

We define $f:\Bbb N\to A$ by recursion as follows. Let 
  $$f(1) \colon= f_1(1).$$
Suppose that $n \in \mathbb{N}$ and that $f$ has been injectively-defined on $\{1,...,n\}.$
Now as the function $f_{n+1} \colon \{ 1, \ldots, n+1 \} \to A$ is injective, the set $f_{n+1}\left(\{1, \ldots, n+1 \}\right)$ has exactly $n+1$ elements. On the other hand, the set $f\left(\{1,\ldots, n\}\right)$ has exactly $n$ elements. So the set $f_{n+1}\left(\{1, \ldots, n+1 \}\right) - f\left(\{1,\ldots, n\}\right)$ has at least one element. 

At this stage, one could simply rely on the Axiom of Dependent Choice, and conclude that there is a function $f:\Bbb N\to A$ such that $f(1)=f_1(1)$ and such that $f(n+1)\in f_{n+1}\left(\{1, \ldots, n+1 \}\right) - f\left(\{1,\ldots, n\}\right)$ for all $n.$ Fortunately, we don't have to!

Let $k_n$ be the smallest element of the set $\{1, \ldots, n+1\}$ such that $f_{n+1}(k_n) \not\in f\left(\{1,\ldots, n\}\right),$ and let 
  $$f(n+1) \colon= f_{n+1}(k_n).$$

By taking the smallest element in each successive step, you explicitly describe the recursive construction, thereby eliminating any reliance on Choice.
