Proof that every infinite set has a countably infinite subset

Proof

We define the subset by recursion, with a choice function.

1. Let $A$ be an infinite set. Let $X$ be the set of nonempty subsets of $A$.
2. By the axiom of choice, there is a choice function $c$ on $X$. So $c(S) \in S$ for each nonempty $S \subseteq A$.
3. Let $F \subseteq A$ be a finite set. Then $A \setminus F$ is nonempty. Otherwise $A = F$, and $A$ would be finite.
4. Let $\Phi$ be the set of finite subsets of $A$. Define $g \colon \N \times \Phi \to \Phi$ by $g(n, F) = F \cup \{c(A \setminus F)\}$. This set is finite, since it adds one element to $F$. So $g$ is well defined.
5. By definition by recursion, there is a function $n \mapsto F_n$ from $\N$ to $\Phi$ with $F_0 = \emptyset$ and $F_{n+1} = g(n, F_n)$.
6. Define $f \colon \N \to A$ by $f(n) = c(A \setminus F_n)$. Then $f(n) \in A \setminus F_n$ and $F_{n+1} = F_n \cup \{f(n)\}$.
7. By induction on $n$, $F_n = \{f(0), \dots, f(n-1)\}$. This holds for $n = 0$, and step 6 gives the inductive step.
8. Let $m < n$ be natural numbers. Then $f(m) \in F_n$ by step 7. But $f(n) \notin F_n$ by step 6. So $f(m) \neq f(n)$.
9. Hence $f$ is injective.
10. As a function onto its image, $f \colon \N \to f(\N)$ is injective and surjective, so it is a bijection.
11. Thus $f(\N) \subseteq A$ is countably infinite, which proves the statement.