This is a follow-up question to the discussion about the finite axiom of choice here.
Suppose we have a countable collection of non-empty sets $\{A_1, A_2, A_3,\cdots\}$ Reasoning as indicated in that discussion, we can prove the existence of a choice function $c_n$ such that $c_n(i)$ belongs to $A_i$ for $i = 1,\cdots,n$
Again reasoning as suggested and using induction, we can prove the existence of a function $C$ defined over $\{1, 2, \cdots\}$ such that $C(n)$ is a choice function defined for $i=1,\cdots,n$ with $C(n)(i)$ an element of A_i. We can require in addition that $C(n)(i)$ and $C(n-1)(i)$ are equal for $i=1,\cdots,n-1$.
Now it would it seem that we can prove the countable axiom of choice by taking the union of $C(1)$, $C(2)$, $\cdots$
The question is as follows: why is that proof wrong? I suspect the answer may have something to do with the axiom of union.
Best Answer
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.