# Every infinite set contains a countable subset

Assuming the axiom of choice, it can be shown that every infinite set contains a countable subset. Also, it is my understanding that the proof of this statement requires at least countable choice - i.e., it is consistent with ZF that there exist infinite sets which contain no countable subset.

However, consider the following proof:

Given an infinite (i.e. not equinumerous to any natural number) set $S$, let $A_1$ be a set containing one element in $S$, and construct $A_n$ by adding to $A_{n-1}$ any element from $S$ not already in $A_{n-1}$. This can be done since $S$ is finite, so at no point is $A_{n-1}$ equal to all of $S$. We can construct every $A_n$ using only ZF, since we are only making finitely many choices. Now, define $f: \mathbb{N} \rightarrow S$ by defining $f(n)$ to be the unique element in $A_n \backslash A_{n-1}$. $f$ is injective since $f(n) \notin A_m$ for every $m < n$, so $f(n) \neq f(m)$. Hence, $f$ is an injection from $\mathbb{N}$ to $S$, and the image of $f$ is a countable subset of $S$.

My problem is figuring out where in this proof the axiom of choice is used. It seems the construction of the $A_n$'s can be done without AC, since we are only making a finite number of choices. The construction of $f$ involves choosing an element from $A_n \backslash A_{n-1}$, but since we have a systematic way for choosing (take the unique element in the set) that should be allowed. I know this proof must depend on the axiom of choice, but where is it used?

• This was discussed several times before. Have you searched the site? – Asaf Karagila Oct 17 '16 at 21:40
• I've looked at several threads discussing this fact and its relation to the axiom of choice. However I didn't find this particular proof or something equivalent, and am still not sure where the dependency on AC is. – Jeffrey Dawson Oct 17 '16 at 21:46
• Here's where: “…construct $A_n$ by adding to $A_{n−1}$ any element from $S$ not already in $A_{n−1}$”. – egreg Oct 17 '16 at 21:48
• ZF allows you to make finitely many choices though, right? – Jeffrey Dawson Oct 17 '16 at 21:50
• Finitely many choices, yes. But you are doing infinitely many. – fleablood Oct 17 '16 at 23:16

The issue is that induction only tells you that something is true for every finite integer.

For example, by induction we can prove that every natural number $n$ has exactly $n$ predecessors ($0$ is a natural number). Does that mean that there exists a natural number with infinitely many predecessors? No. It does not.

Similarly here. If $A$ is an infinite set, without the axiom of choice we can prove that for every $n$ there is a subset of $A$ of size $n$. But can we prove there exists a subset equipotent with $\Bbb N$ itself? No. That requires us more. That requires that the choices we made during the inductive proof were coherent with one another, which essentially tells us that there is some sort of choice function that we can work with.

And indeed, without the axiom of choice, it is consistent that there are infinite sets without countably infinite subsets. These are called Dedekind-finite sets.

Perhaps the following elaboration is going to clarify this issue. Let's look at what the inductive proof really does.

You start with the empty set, and you have $A$ to choose from. That gives you $|A|$ many choices for a first element in your sequence. Suppose that you managed to get through $n$ choices, that gives you $|A|-n$ many choices to continue, and that's fine, since $|A|$ is not a finite integer, we can always make at least one choice and continue the construction.

But what are we really constructing? It's a tree of options. We start with the root, which is the empty sequence. Then at each step, we have splitting according to our options. In this case, however, there are infinitely many splittings at each step.

The inductive construction simply tells us that we constructed a tree without maximal points. The axiom of choice tells us that this tree has a branch, which in turn can be translated into a countably infinite subset. But the existence of a branch relies heavily on the axiom of choice. Why would you choose the first element to be one and not another? How about the second element? There is no canonical preference to make here, in the arbitrary case.

So what happens is that without choice, you might end up with a tree that has no maximal nodes, but no infinite branches either.

(In Mitchell Spector's answer he discusses inductive definitions, in that case, there is a function which chooses "the next step", so the tree is in fact a unique branch, and everything is fine. But in the proof you suggest, there is no such function, you appeal to choosing arbitrary elements at each step.)

• I understand this, but through induction I have defined the function f for every natural number n, hence it is an injection from $\mathbb{N}$ to $S$. Where does the construction of the function use AC? – Jeffrey Dawson Oct 17 '16 at 21:50
• No. You have defined an injection, for every natural number separately. How can you ensure that for all the natural numbers, these injections extend one another? – Asaf Karagila Oct 17 '16 at 22:11
• Let $f_n$ be the injection from $\{1 \dots n\}$ to S using my method. By construction, it is clear that $f_m(i) = f_n(i)$ for $i < m,n$. Thus, taking the union over $n$ of all the $f_n$ (here we are viewing functions as collections of ordered pairs) gives us an injection from $\mathbb{N}$ to $S$. – Jeffrey Dawson Oct 17 '16 at 22:26
• So, for each $n$ you chose $f_n$. Isn't that an exercise in using the axiom of choice? More specifically, suppose that you constructed $f_n$. Then you have $A\setminus\{f(0),\ldots,f(n-1)\}$ to choose a next candidate from. This gives you an infinite pool of candidates. Unless you can argue some specific method to pick a candidate, all of them are equally viable. And the fact you need not only to make infinitely many choices, but the fact that each choice depends on the previous ones (if you chose $a_n$, it means that you can't choose it in the future, and vice versa), mean that you use AC – Asaf Karagila Oct 17 '16 at 22:38
• I see. Once I have constructed my nested sequence of finite sets $A_n$ as described in the OP, it seems I should be able to construct $f$ without AC, defining it by $f(n)$ being the unique element of $A_n \setminus A_{n-1}$. So is it the construction of the $A_n$'s the step that uses choice? I guess my confusion is that it seems that every $A_n$ should be constructible without AC as it only uses finitely many choices. So why is it that any $A_n$ individually can be constructed in ZF, but all of them together requires AC? – Jeffrey Dawson Oct 18 '16 at 4:00

I think it will clarify things to think about how you would actually set up the definition of the $A_n$ by induction. Spelling it out in detail will show exactly where the axiom of choice is used.

First, the formal principle of definition by mathematical induction that you are using looks like this:

Principle of definition by mathematical induction:

To define a function $f$ from $\omega$ to a set $E$ by induction, start with a function $g\colon E \to E$ and a specific $e_0\in E.$ You can then conclude that there is a unique $f\colon\omega\to E$ such that for all $n\lt\omega,$ $$f(n)=\begin{cases}e_0,&\text{ if }n=0, \\ g(f(n-1)),&\text{ if }n\gt 0. \end{cases}$$

(There are variants—for example, $g$ can be allowed to depend on $n$ also, or you could set things up for strong induction, but the above is sufficient for what you're doing.)

The function $f$ you are defining by induction is $n\mapsto A_n.$ To fit it into the above template, you can set $E$ equal to the collection of all finite subsets of $S$ (where $S$ is the infinite set that you are starting out with), and you can set $e_0=\emptyset$ (you actually started out with $A_1$ being a $1\text{-element}$ set, but this is easier).

But what are you going to use for $g?$

For your construction to work, the function $g\colon E\to E$ needs to satisfy the following property:

For any finite subset $X$ of $S,$ $g(X)\in S\setminus X.$

It's true that for any finite subset $X$ of $S,$ the set $S\setminus X$ is non-empty. Nevertheless, it requires a use of the axiom of choice to conclude that there is a function $g$ with domain $E$ such that for all $X$ in $E,$ $\;g(X)\in S\setminus X.$