Proving any infinite set has a denumerable subset with the Axiom of Choice Derive from the axiom of choice that any infinite set contains a denumerable subset
 A: Here's a way to get started. Let $A$ be an infinite set. Let $F$ be a choice function on $\mathscr{P}(A)-\{\emptyset\}$. Now let $B$ be the collection of all finite subsets of $A$, and let $\emptyset\in B$ as well. Now let $f\colon B\to B$ be defined by $X\mapsto X\cup\{F(A-X)\}$.
By the recursion theorem on $\omega$, we know there exists a function
$h\colon\omega\to B$ such that $h(0)=\emptyset$ and 
$$
h(n^+)=f(h(n))=h(n)\cup\{F(A-h(n))\}
$$ 
for every $n\in\omega$. 
Claim. For every $m\leq n$, we have $h(m)\subset h(n)$. To see this, use induction. Let
$$
K=\{n\in\omega\ |\ m\leq n\implies h(m)\subset h(n)\}.
$$
Clearly $0\in K$, for if $m\leq 0$, then $m=0$, and obviously $h(0)\subset h(0)$. So suppose $n\in K$. If $m\leq n^+$ then either $m\leq n$ or $m=n^+$. In the first case, $h(m)\subset h(n)\subset h(n^+)$. In the second, $h(m)=h(n^+)$, so the conclusion follows either way. Hence $n^+\in K$, so $K=\omega$. 
Now let $g\colon\omega\to A$ be defined as $n\mapsto F(A-h(n))\in A-h(n)$, which implies immediately that $g(n)\notin h(n)$. Try showing that $g$ is injective, which will prove that $g$ is surjective onto its range, which is a subset of $A$. Since $g$ is then a bijection from $\omega$ onto $\text{ran }g$, $\text{ran }g$ will be countable, and you'll have your result.
Added: To show $g$ is injective, suppose $m\neq n$, and let's suppose $m<n$. This means $m^+\leq n$, so by the above claim, $h(m^+)\subset h(n)$. Then
$$
h(m^+)=h(m)\cup\{F(A-h(m))\}=h(m)\cup\{g(m)\}.
$$
What does this tell you about $g(m)$ in relation to $h(m^+)$ and $h(n)$? Is it then possible that $g(m)=g(n)$? Why not? This proves $g$ is injective. 
A: A somewhat simpler solution:
Suppose $X$ is an infinite set, using the well ordering principle (which is equivalent to the axiom of choice) take any well ordering of $X$, since $X$ is infinite the order type is some $\alpha>\omega$.
Now simply take the first $\omega$ elements of the order, it is a countable subset of $X$.
A: Here is another simple proof. Countable choice is enough here:
Let $X$ be an infinite set. Let's denote $X_n=\{ Y\subset X : |Y|=n\}$. Observe that because $X$ is infinite these sets are always non-empty. Now take the set $A=\{X_n : n\in\omega\}$. Assuming the countable axiom of choice we get a choice function $f$ for $A$. Take the set $B=\bigcup ran(f)$. Of course $B\subset X$ and as a countable union of finite sets it has countable many elements.
