# Why isn't this a valid argument to the “proof” of the Axiom of Countable Choice?

I am having a little trouble identifying the problem with this argument:

Let $\{A_1, A_2, \ldots, A_n, \ldots\}$ be a sequence of sets.

Let $X:= \{n \in \mathbb{N} :$ there is an element of the set $A_n$ associated to $n \}$

(1) $A_1$ is not empty. Therefore, there exists a $x_1 \in A_1$

(2) Given an $A_n$ (and a $x_n \in A_n$), we have that $A_{n+1}$ is non-empty and, therefore, there exists a $x_{n+1} \in A_{n+1}$

So, by induction, $X=\mathbb{N}$ and the axiom of countable choice is "proven".

Where is the error?

-
What do you mean by "associated to $n$"? There is an issue here, in that you will need to describe a uniform procedure, that is, a "function" $f$ such that for each $n$, $f(n)$ is an element of $A_n$ "associated to $n$". Another issue is that, even if you have finite sequences $(x_1,\dots,x_n)$ for each $n$, you may still not have a "thread" $(x_1,x_2,\dots)$. – Andrés Caicedo Feb 18 '13 at 17:57
You are choosing an $x_n$ from each $A_n$. So you are assuming countable choice. – Francis Adams Feb 18 '13 at 18:00
You have proved that for all $n\in \mathbb{N}$, the set $A_n$ is non-empty. Not a big surprise, since we need to start from non-empty sets. On a more serious note, it turned out that some early opponents of AC had implicitly used AC, at least in its countable form, in their work. Countable AC is, I think, intuitively fully reasonable. It is hard to avoid implicitly using it. – André Nicolas Feb 18 '13 at 18:03
To push @AndréNicolas comment slightly forward, Dependent Choice is even more natural, because it is exactly what we do when we define things by induction. – Asaf Karagila Feb 18 '13 at 18:06
@AndresCaicedo By "Associated to" I meant the existence of a function from a finite set, namely ${n}$, to $A_n$, and this is true, because ${n}$ is finite. – Aloizio Macedo Feb 18 '13 at 18:07

Inductions give you every finite case but not the infinite case. Induction is not "continuous" in this aspect.

Yes, $X=\Bbb N$ and from this follows the fact that every finite subcollection admits a choice function does not imply that you can actually choose from infinitely many sets at once.

Let me give you a ridiculous analogue to your argument, it is ridiculous so you can easily find the mistake there, and I hope that it will help you see your own mistake as well:

"Theorem". The set of natural numbers is finite.

"Proof". Let $X=\{n\in\mathbb N\mid\text{The set }\{k<n\mid k\in\Bbb N\}\text{ is finite}\}$; clearly $0\in X$, and if $n\in X$ then $n+1\in X$.

Therefore $X=\mathbb N$ and so $\Bbb N$ is finite as wanted. $\square\!\!\!\small?$

It is quite obvious what I did wrong here, I showed that every initial segment is finite, but not that the entire collection is finite.

Let's push this one step forward, here is a wrong argument which follows similarly, but its proof is slightly less exaggerated than the one above:

"Theorem". The power set of $\Bbb N$ is countable.

"Proof". Write $\Bbb N=\bigcup [k]$ where $[k]=\{0,\ldots,k-1\}$. Then for every $k$, $\mathcal P([k])$ is finite. Therefore $\mathcal P(\Bbb N)=\bigcup\mathcal P([k])$ is a countable union of finite sets, and so it is countable. $\square\!\!\!\small?$

In here we also proved by induction that every initial segment has a finite power set, but we made a mistake by concluding that the power set of $\Bbb N$ is this union, which if you look closely, does not even contain $\Bbb N$ itself. The mistake here is that we assume that the induction carries over to the limit stage, i.e. we falsely assume that $\sup\{2^n\mid n\in\mathbb N\}=2^{\sup\{n\mid n\in\mathbb N\}}$.

-
Aloizio, this is not the statement of the axiom of countable choice. The statement is that you have a function choose one from every set. Your proof shows that you have function$\bf S$ choosing from every finite subcollection of sets. – Asaf Karagila Feb 18 '13 at 18:06
@Aloizio, and this is the key mistake. You don't have a defined $x_n$. You can define $x_n$. And this is the key between actually choosing from all sets, and having all sets non-empty. You don't actually point to any $x_n$, you merely assert its existence. – Asaf Karagila Feb 18 '13 at 18:29
@AloizioMacedo More to the point, mathematics is not temporal. A variable is not undefined at one time and then defined at another, so that you can jump over infinitely many steps and have them all simultaneously defined. Even if you could perform infinitely many tasks and jump ahead to a time when they have all been completed, that does not mean that things will be in a consistent state at that point. For example, consider the process where I turn on a lamp at $t = 0$, turn it off at $t = \frac{1}{2}$, turn it on again at $t = \frac{3}{4}$, etc.; is the lamp on or off at $t = 1$? – Zhen Lin Feb 18 '13 at 18:37
No, there is certainly no problem with creating finite choice functions. Everyone has explained this. The problem is in assembling them together to make an infinite choice function. – Zhen Lin Feb 18 '13 at 19:02
@Aloizio: If you have any programming experience, this may clarify a bit. At every stage you call a function which assigns $x_n$ to some local variable, and then exists. This means that you can't really access the specified $x_n$ from outside this function. Therefore you cannot really combine all your choices into a uniform choice from all the sets at once, because the induction step allows you to prove $x_n$ can be assigned, but it doesn't tell you what is its value. If you want to access it, you have to reassign this value and you have no guarantee that it will be the same value again. – Asaf Karagila Feb 18 '13 at 20:01

As pointed out in comments and answers, the issue is that from the existence of finite sequences $(x_1,\dots,x_n)\in A_1\times \dots\times A_n$, we cannot conclude the existence of an infinite sequence $(x_1,x_2,\dots)\in A_1\times A_2\times\dots$ without some additional assumption (such as the axiom of countable choice).

This certainly seems strange when one first encounters it, so perhaps the following may indicate why there is something subtle going on:

From the work of Gödel, we know that there is no recursive consistent, complete set of axioms extending first-order Peano arithmetic $\mathsf{PA}$. What this means is that if $T$ is a set of axioms extending Peano Arithmetic, $T$ is consistent, and there is a computer program that, for each formula $\phi$, tells us whether $\phi$ is an axiom of $T$ or not, then there are statements $\psi$ such that $T$ cannot prove $\psi$, and cannot prove $\lnot\psi$ either.

(If you have issues with using Peano Arithmetic here, we can replace it with much weaker systems, such as Robinson's arithmetic $Q$; this is not an issue.)

Ok, consider now the following construction, that it is perhaps best explained as labelling the nodes of a subtree of $2^{<\mathbb N}$, the set of finite sequences of $0$s and $1$s.

Start by fixing a list $\phi_0,\phi_1,\dots$ of all sentences in the language of arithmetic. Put $\mathsf{PA}$ in the bottom node $\emptyset$. Given a finite sequence $t\in 2^{<\mathbb N}$, assume we have assigned a consistent set of axioms $T_t$ to the node $t$. This node has two successors, $t^\frown(0)$, and $t^\frown(1)$. Go through the list $\phi_0,\phi_1,\dots$, until you reach a $\phi_n$ such that $T_t$ does not prove $\phi_n$ and does not prove $\lnot\phi_n$. Assign to $t^\frown(0)$ the theory with axioms $T_t\cup\{\phi_n\}$, and to $t^\frown(1)$ the theory with axioms $T_t\cup\{\lnot\phi_n\}$.

Now, for each $n$, there is a computer program that lists the axioms of $T_s$ for all $s$ of length $n$ or less. However, this does not mean that we can find a computer program that lists the axioms through any of the branches of the tree, because any branch gives us a complete theory, and we would contradict Gödel's result. Think about this example, and note that "induction" would not help us here, as we can modify this construction slightly so that the theories at the end cannot be described in any "arithmetically definable" fashion. This is a much more generous notion than just "recursive", and it is still not enough.

The issue is the lack of uniformity: though for each $n$ there is a computer program that identifies the theories at level $n$, there is no algorithmic method for identifying the theories that are produced "at the end".

Similar issues are identified in the area of "reverse mathematics", where for example one studies the (complicated) informational content that a branch through a tree can carry, even if every node, or indeed the whole tree, is described by an easy process.

The point of countable choice is that the same issue can be carried out to the extreme. In the examples above, we have recursive information at each finite stage, and no recursive description at the end. Countable choice is needed because if we remove the requirement that the information at each finite stage is "recursive", we in fact may have no "definable" way of identifying the information at the end. So much that, in fact, we could have a whole universe of set theory where that information is not present. The way of thinking about this is that the information can be made so complicated that even having available all the definability present in a model of $\mathsf{ZF}$ set theory may not suffice to identify it.

-
Very good answer! I feel that I should add to the last paragraph that often countable choice itself is not enough to allow us to finish similar recursive constructions. For this we actually need a stronger axiom called The Principle of Dependent Choice. – Asaf Karagila Feb 18 '13 at 19:02

At best you show that for all $N\in\mathbb N$, there is a map $f_N\colon \{a,\ldots,N\}\to\bigcup_n A_n$ with $f_N(n)\in A_n$. That is, given $f_N$ you extend this to $f_{N+1}$ by chosing a single element $x_{n+1}\in A_{N+1}$.

What we really need, however, would be an $f_\omega$. You can't get yourself out of this trap by simply letting $f_\omega(n):=f_n(n)$ because you don't have all the $f_n$ available at once.

-
Actually the problem of defining $f_{\omega}$ is equivalent to the axiom of countable choice, isn't it? – N. S. Feb 18 '13 at 18:23
Hmm... Sort of as if, even if I defined a family of functions $f_n$, I can't use them to define a function "extended", by "uniting" the domains of $f_n$? Could you elaborate more, please? – Aloizio Macedo Feb 18 '13 at 18:30
@AloizioMacedo That's just the point: You don't define a family of functions, you merely describe how to obtain the elements of this would-be family of functions one by one (using a choice at each step). If you really had that family completed available, uniting would work. I'm afraid though that this may sound a bit like the unfamous "potential vs. actual infinity" debate ... – Hagen von Eitzen Feb 20 '13 at 16:42

It's true that at each $n$th stage, there is some element in $A_n$. The problem is, how do we choose which element of $A_n$ to call "$x_n$"? Countable choice lets us get around this issue, but since you're trying to prove it, we can't use it.

Your inductive argument really only shows that, for any $n$, we can find an $n$-tuple in $A_1\times\dots\times A_n.$ It does not let us "proceed to infinity", as you're attempting to do. That is, what you've proved here is the Theorem of finite choice, showing that it's fine to make arbitrary choices from finitely many non-empty sets.

-
The problem is, if that was true, wouldn't your argument lead to: How do we choose an element from a set, or a finite cartesian product? And we can do it without AC, can't we? – Aloizio Macedo Feb 18 '13 at 18:02
@Aloizio: This question has been asked before. Yes, we can choose from a finite collection of sets because we prove their product is not empty (and elements of the product are choice functions). – Asaf Karagila Feb 18 '13 at 18:04
But then, at the $n$th stage, since I have a finite collection of sets (just $\{n\}$), the way I choose the element is the same way the element is chosen the way you said. – Aloizio Macedo Feb 18 '13 at 18:13
@Aloizio: Yes, we can do that without any choice axiom--in fact, that's really what you've proved here. It's when we're trying to talk about making infinitely-many arbitrary choices that we find ourselves on ground that's shaky enough to need an axiom propping it up. – Cameron Buie Feb 18 '13 at 18:13

To avoid Choice, you need to have a definitive way of choosing an element from each set. For example, if each $A_n$ is a pair of shoes, you may always choose the left.

A typical useful case is when each $A_n$ has a distinguished member such as a unique minimum that you can choose. For example, Baire Category Theorem for a complete SEPARABLE metric space can be proved by a trick like this.

-

Imagine, philosophically, mathematical foundation needs to build up a language bridging finiteness at A and countable infinity at B. ACC is such a language leading us jumping from A right to B, while induction is a never ending process leading us to go through each mile in an infinite mileage, but just never get to the end point B.

In a single nonempty set, we can choose an element by the very meaning of the non-emptiness of the set. Induction then allows us to obtain a choice function for any of the finite collections of sets. Although there are infinitely many of such collections, we come short to obtain a choice function for a countable collection of sets, for that ACC is needed.

In the language of ordinality, induction covers every finite ordinal but comes a little bit short to cover the first infinite ordinal, which is the totality of all finite ordinals, in this sense not accessible by induction.

-
ACC is not a language. Even if by "philosophically" you mean "informally", technical terms actually have precise meanings. You may want to rephrase to remove the nonsense. – Andrés Caicedo Nov 23 '14 at 0:24
In addition to what Andres said, let me remark that it'd be best if you first come up with an actual answer compared to your very first write up here. I was considering to flag it as "low quality", but when I came to do so, I saw that you added something. This is particularly true since there is no "race" over this question, it's almost two years old, and was dormant for the most of that time. First thing about your answer, see if it satisfies you, then post it (especially for very old questions). – Asaf Karagila Nov 23 '14 at 6:42