Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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)$. –  Andres Caicedo Feb 18 '13 at 17:57
1  
You are choosing an $x_n$ from each $A_n$. So you are assuming countable choice. –  Francis Adams Feb 18 '13 at 18:00
6  
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
1  
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
show 3 more comments

4 Answers

up vote 11 down vote accepted

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\}}$.

share|improve this answer
1  
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
2  
@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
3  
@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
1  
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
1  
@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
show 8 more comments

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.