Derive from the axiom of choice that any infinite set contains a denumerable subset
Proving any infinite set has a denumerable subset with the Axiom of Choice
-
0well order it, take the first, second, third, etc. or define $f:\mathbb{N}\to X$ by choosing $f(0), f(1),...$ knowing that you wont run out since $X$ is infinite – 2011-05-04
3 Answers
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
-
0thank you so very much, I have to call it a night, any alternate questions will come in the morning, hopefully you are around, thanks again – 2011-05-04
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$.
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.
-
0@Asaf: Thanks again! I'll definitely take a look at it. :) – 2011-05-04