# The existence of the sequence corresponding to some asymptotic sequence

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!

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.
• 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. – dazaga May 14 '15 at 16:31
• @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. [...] – Asaf Karagila Jun 9 '15 at 6:44