Countable axiom of choice: why you can't prove it from just ZF

Solution 1:

You cannot, in general, ensure that $C(n)(i)$ and $C(n+1)(i)$ are identical for $i \leq n$. If you could do that, you could indeed take $\cup_n C(n)$ to obtain a choice function. But the problem is not with the axiom of union, the problem is that you have overstated what induction actually gives you.

It is true that, when you prove the inductive step, you temporarily obtain $C(n)(i)= C(n+1)(i)$, because you extend the previous finite choice function. But when you apply the principle of induction, all that it tells you is that $$ (\forall n)(\exists C)[C \text{ is a choice function on } \{A_1, \ldots, A_n\}] $$ You do not get that there is an infinite sequence $C(n)$ of compatible finite choice functions.

This is one place where the difference between "we construct an infinite sequence inductively" and "we construct a sequence by induction" really matters. To construct an infinite sequence inductively means to give a construction of an infinite sequence $\langle \alpha_0, \alpha_1, \ldots\rangle$ that tells how to construct $\alpha_0$ and then tells how to construct $\alpha_{i+1}$ from $\alpha_i$.

The principle of mathematical induction, on the other hand, has the general form $$ [P(0) \land (\forall n)[P(n)\to P(n+1)]] \to (\forall n)P(n). $$ It does not, on its own, give you a way to take a collection of finite sequences and combine them into an infinite sequence. An inductive construction, written in full generality, may require some side proofs by induction to verify that the conditions needed in the construction are maintained at each step. But the power of inductive constructions truly goes beyond the power of mathematical induction.

There are two general situations we can find ourselves in with the inductive construction of a sequence $\langle \alpha_0, \alpha_1, \ldots\rangle$.

Situation 1: We can select $\alpha_{i+1}$ uniquely. For example, there may be a function $f$ so that $\alpha_{i+1}$ can simply be taken to equal $f(\langle \alpha_0, \ldots, \alpha_i\rangle)$. In this case, the axiom of choice is not required for the inductive construction.

One example is the proof of weak Konig's lemma: any infinite $\{0,1\}$ tree has path. We construct the path inductively; given a finite path $\langle \alpha_0, \ldots, \alpha_i\rangle$, if there are infinitely many nodes in the tree above $\alpha_i \smallfrown 0$ then we make $\alpha_{i+1} = \alpha_i \smallfrown 0$. Otherwise we take $\alpha_{i+1} = \alpha_i \smallfrown 1$. This inductive construction does not require the axiom of choice; it can be seen as simply iterating a certain function to produce the path. The function is defined so that $f(\sigma) = \sigma\smallfrown 0$ if there are infinitely many nodes of the tree above $\sigma\smallfrown 0$, and $f(\sigma) = \sigma\smallfrown 1$ otherwise. The axiom of choice is not at all required to construct this $f$.

Situation 2: We can prove the existence of at least one possible value for each $\alpha_{i+1}$, as the construction progresses, but we do not have a function that can be used to guide the construction. This is precisely the situation that the axiom of dependent choice is intended to handle. Dependent choice is precisely the principle you need to prove the axiom of countable choice by inductively constructing the choice function.

Solution 2:

Because induction only proves that for every finite number, there is a choice function. In order to ensure that there is such a sequence of partial choices which agree with one another so their union is a full choice function, you would have to go beyond the powers of mathematical induction, and you would have to make infinitely many choices at once. Otherwise there is no guarantee that you could have constructed a sequence of choice function like that.

Therefore the idea would work if you had a choice function to begin with (from which you took initial segments), but that's just not true in general.

More concretely, the principle which allows us to deduce the existence of such sequence, just by knowing that arbitrarily ling finite sequences exist, is called The Principle of Dependent Choice. The proof you suggest is exactly how we prove countable choice from dependent choice; but the principle itself is not provable from $\sf ZF$ itself.

Solution 3:

In your first paragraph you used countable choice when you said "for each $i$ we can prove the existence of a choice function $c_i$ for $A_i$". The choice is hidden in plain sight, in the fact that you used "$c_i$" for the choice function on $A_i$. You have thus created a function $i \mapsto c_i$. If you want to avoid this sort of thing, you must say: "for each $i$ we can prove that there exists a choice function $c$ for $A_i$". It is now clear that $c$ depends on $i$, but we have not assumed a specific assignment $i \mapsto c_i$, which would be choice.

In your second paragraph, on the iterative construction of a choice function $C$, you used Dependent choice, which is even stronger than countable choice. The dependent choice has the following form: we construct a sequence $a_0, a_1, a_2, \ldots$ where each $a_{n+1}$ is constructed from $a_n$, and there is some freedom in what exactly $a_{n+1}$ is, so we just choose one of the available options for $a_{n+1}$. To avoid dependent choice, you would have to specify how to get a unique $C(n+1)$ from $C(n)$.