The following proof of the axiom of choice by induction is obviously false:
Let $(\Lambda)_{i=1, 2, \ldots}$ be an infinite sequence of nonempty sets. When $i=1$, self-evident. We will assume this statement holds for $n$, then for $n+1$, we can choose element $a_{n+1}$ from $\Lambda_{n+1}$ because $\Lambda_{n+1}\neq \emptyset$. Therefore, using the axiom of induction, we have proved the above statement holds for every $n \in \mathbf{N}$.
However, from this argument the axiom of choice doesn't follow because we have proved for only every finite $n \in \mathbf{N}$, though we have to choose from infinite sequence of sets $(\Lambda_i)$.

Next, we will prove by induction. the asymptotic formula, say, $a_1=1$ and $a_{n+1} = a_n+1$, actually defines a sequence. $n=1$ is OK and if it holds for $n$, $n+1$ is OK. Then, we can say that for all $n\in\mathbf{N}$, we can get the finite sequence $a_1, a_2, \ldots, a_n$. However, does this argument proves the existence of the infinite sequence corresponding to the asymptotic formula? I think the wrong proof of axiom of choice and the latter proof of infinite sequence are parallel, but if the latter proof is wrong, I have no idea how to prove the existence of the corresponding sequence. Someone please help me!


When you give a recursive definition of a sequence, then you define a sequence uniquely.

You're not making arbitrary choices, since $a_{n+1}$ is picked uniquely once you know the values of $a_0,\ldots,a_n$. So giving a recursive formula and a starting condition makes no appeals to the axiom of choice.

This is different from the fake proof you presented, since there you have to choose an arbitrary element from each set. So the axiom of choice had to be involved in order to glue these choices together into an infinite sequence.

  • $\begingroup$ Thank you for answering. Why the arbitrary choice makes difference? In both proof, at $n$th step, we have to select one element from a set. I think whether it's arbitrary or not, the fact doesn't change that you have to take one element in 1st step, 2nd step, 3rd step, ... one by one repeatedly. $\endgroup$ – dazaga May 14 '15 at 16:31
  • $\begingroup$ @dazaga: Constructively (in a certain sense), you cannot obtain an infinite sequence in finite time. However, in ZF you glue the finite subsequences together essentially by taking the union. Without a unique choice at each step, you would be unable to construct the sequence of subsequences in the first place and hence not able to take the union, unless you have the axiom of dependent or countable choice depending on the type of choice you have to make. $\endgroup$ – user21820 Jun 9 '15 at 6:38
  • $\begingroup$ @dazaga: Induction gives you the following "If you have picked $n$ elements, then you can pick $n+1$ elements", by picking a new one. But I defy you to sit and write to me the actual object that you get at the end. What is the first element of the sequence? It could be any element of the set. What is the second element? It could be any element, except the first one. So if I ask you what is the fifth element, you have to repeat the construction, and hope that you chose the first element the same as before, and the second element the same as before, and so on. [...] $\endgroup$ – Asaf Karagila Jun 9 '15 at 6:44
  • $\begingroup$ [...] But there is no guarantee that this will happen. You are picking arbitrary elements! What the usual proof does, really, is fixing a choice function and using it to say which element you chose at the first step, and so on, so you are guaranteed to get the same sequence. The choice is not arbitrary anymore, since it is guided by the choice function chosen. Of course no one really does that (except in texts about the axiom of choice), which is the reason why people often think you don't need choice for this. But the induction does not give you a well-defined sequence. $\endgroup$ – Asaf Karagila Jun 9 '15 at 6:46
  • $\begingroup$ @user21820: Thanks, I must have forgot to write an answer to that comment. $\endgroup$ – Asaf Karagila Jun 9 '15 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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