# 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

-
you'll get a lot more constructive responses on this site if you don't ask questions in the imperitive form and if you show what you have tried up to this point to solve the problem. –  Stijn May 4 '11 at 0:46
well 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 –  yoyo May 4 '11 at 0:51
Is this homework? If so, please tag it as such. –  yunone May 4 '11 at 0:55
What have you tried? –  Qiaochu Yuan May 4 '11 at 0:57

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.

-
sorry im new to this, it is homework –  Aaron Flood May 4 '11 at 1:07
this is what i have tried –  Aaron Flood May 4 '11 at 1:07
Let X be an infinite set. Since X is not empty, we can choose x1 as an element of X. Since X{x1} is non empty, we can choose x2 as an element of X{x1}. Since X is infinite we can continue this procedure, in general obtaining xi+1 as an element of X{x1,x2,...,xi} The set {x1,x2,x3,...} is a denumerable subset of X I need to now prove this using the axiom of choice, and really am not sure where to start. I know this is essentially the axiom of choice, as I am choosing an element randomly, but my proff wants a longer proof and I am unsure wher to go. Any help would be great. –  Aaron Flood May 4 '11 at 1:07
@Aaron, That is a good sketch idea, but to make your argument rigorous, you want to use a choice function $F$ to make an appropriate choice for you, you don't want to be picking up arbitrary elements by yourself. This is where the Axiom of Choice comes in. That's what my function $h$ does above. $h(n)$ is the elements we already have but for the next step, $h(n^+)$, we want to pick up an element we haven't chosen already. That's why we union in $F(A-h(n))$ which will be in $A-h(n)$ by definition of a choice function. –  yunone May 4 '11 at 1:11
@Aaron, I've expanded the last argument to hopefully make it more clear. Let me know if you have any specific questions. –  yunone May 4 '11 at 3:00

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.

-
Actually even less is enough, namely that every cardinality is comparable with $\aleph_0$ (which is strictly weaker than countable choice). –  Asaf Karagila May 4 '11 at 8:17
Also, very nice! –  Asaf Karagila May 4 '11 at 8:17
@Asaf: Thanks, I didn't know that was weaker. Actually, I don't know why I wrote my post that way. What I meant to say was "here's another simple way and the interesting thing about it is that it only uses countable choice" but it ended up completely different. I'll probably edit it. –  Apostolos May 4 '11 at 8:35
To be fair, when you think about it... this question asking you to prove that Axiom of choice implies that $\aleph_0$ is comparable with any cardinality. If you just assume that... :-) –  Asaf Karagila May 4 '11 at 8:43
As for the strictly weaker, cf. Jech's The Axiom of Choice. There's a whole chapter about the relations between AC/Well ordering principle/DC (which is really like a Zorn's lemma analogue in this context). Apparently DC is the strongest at any stage, implying both the others, while they do not imply one another in most cases. –  Asaf Karagila May 4 '11 at 8:45