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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 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)$.

Answer 4

Choices are variables.

It's easy to fall into the trap of thinking of a variable as an unspecified constant, in which case your argument would be just collecting all of the constants together in a single object, but the failure of arguments like this shows the flaws in that way of thinking.

If we dig a step deeper in the abstraction layer, what your argument is saying is that there is a sequence of nonempty sets $\mathscr{C}_n$ containing all of the possible choice functions on $n$ elements -- your expression $C(n)$ is an indeterminate variable ranging over $\mathscr{C}_n$. Your argument is essentially just choosing an "extension" map $e_{n-1} : \mathscr{C}_{n-1} \to \mathscr{C}_n$. But that again is a choice; $e_{n-1}$ is an indeterminate variable ranging over a subset of $\mathscr{C}_n^{\mathscr{C}_{n-1}}$. Although your choices are of course related by $C(n) = e_{n-1}(C(n-1))$.

And finally, you want to assert that these choices can all be put together: that there exists elements of the infinite product

$$ \mathscr{C}_0 \times \mathscr{C}_1^{\mathscr{C}_0} \times \mathscr{C}_1 \times \mathscr{C}_2^{\mathscr{C}_1} \times \cdots $$

that are "consistently chosen" sequences. The problem is that without the axiom of choice, things could fail so badly that this infinite product might be the empty set!

You need some form of the axiom of choice to ensure that you really and truly can aggregate infinitely many choices like that, and then make a (single) choice out of the set of all possible aggregations.

Answer 5

As Andrej Bauer pointed out, to get the function $C$ with the coherence requirement that you claimed, you are actually using dependent choice, which is a stronger axiom than countable choice. The coherence requirement, however, isn't really needed. Suppose you had a function $C$ that assigns to each $n\in\mathbb N$ a choice function $C(n)$, with domain $\{1,2,\dots,n\}$. Then you could produce a choice function $F$ with domain all of $\{1,2,\dots\}$ by setting $F(n)=C(n)(n)$.

Although you don't need the coherence, you do need the countable axiom of choice to produce your $C$. You know, by induction on $n$, that there exist choice functions $c$ on $\{1,2,\dots,n\}$ for each $n$. $C$ is supposed to pick one such $c$ for each $n$, and the possibility of doing that is exactly what the countable axiom of choice gives you. (As Andrej also pointed out, the use of a notation like $c_n$ for such a $c$ suggests erroneously that a particular $c$ has already been chosen for each $n$.)

To put it another way, you have "reduced" the problem of getting a choice function for the sequence of sets $A_n$ to the analogous problem for the sequence of sets $B_n$, where $B_n$ consists of all the partial choice functions $c$ on $\{1,2,\dots,n\}$ such that $c(i)\in A_i$ for each $i\leq n$.

Answer 6

My motivation for asking this question was to understand if the standard proof of the Bolzano-Weierstrass theorem used axiom of choice in any way. If S is an infinite subset of [0,1], BW asserts the existence of a limit point. It is proved by repeatedly halving the interval and picking the half which contains infinitely points in S, much like Konig's lemma in Carl Mummert's reply.

As a result of the informative replies above, it is completely clear that the proof of BW does not use the axiom of choice in any way. The key point is that each new interval in the sequence can be defined as a function of the previous interval with a representative predicate. Therefore ordinary induction suffices.

On the other hand, one may use the axiom of dependent choice to prove that any infinite set contains a countably infinite subset. Even the weaker axiom of countable choice suffices (see comment below). In fact, the statement about every infinite set containing a countably infinite subset is even weaker than the countable axiom of choice (see comment below).

Thanks to Asaf Karagila, Andrej Bauer, and most of all, Carl Mummert for clarifying the role of the axiom of dependent choice. Thanks to Andreas Blass for pointing out that the coherence requirement in the original argument serves no purpose. Thanks to Hurkyl for pointing out that the original argument makes so many choices as to exhaust all the available free will in a world without the axiom of choice!