Axiom of countable choice I apologize in advance for my neophytic question. Let $(A_n)$ be a countable family of disjoint sets. Why is it not possible define a sequence $(x_n)$ with $x_n\in A_n$ using recursion? It seems clear to me that this should be possible, but I am clearly making a ridiculous mistake.
Thanks in advance.

To define a sequence $(x_n : n \in \mathbb{N})$ by recursion, we first need to do the following two things.


*

*Specify an element $x \in A_0$ to be our first element $x_0$.

*Specify a function $g$ such that for all $n \in \mathbb{N}$ and all possible previous values $x_0 \in A_0, \ldots, x_n \in A_n$, we have $g(x_0,\ldots,x_n) \in A_{n+1}$.
Once we have done steps (1) and (2) we can say "recursively define a sequence $(x_n : n \in \mathbb{N})$ by $x_0 = x$ and $x_{n+1} = g(x_0,\ldots,x_n)$.
Clearly we can pick $x \in A_0$ because $A_0$ is nonempty, so step (1) is no problem.
It is step (2) that is problematic without the axiom of countable choice.  The fact that each $A_{n+1}$ is nonempty doesn't mean that there is a single function $g$ such that $g(x_0,\ldots,x_n) \in A_{n+1}$ for all possible previous values $x_0 \in A_0, \ldots, x_n \in A_n$.
Certainly for each particular natural number $n$ there is a function $g$ such that $g(x_0,\ldots,x_n) \in A_{n+1}$ for all possible previous values $x_0 \in A_0, \ldots, x_n \in A_n$.  Indeed, because $A_{n+1}$ is nonempty we can just let $g(x_0,\ldots,x_n)$ be some fixed element of $A_{n+1}$ regardless of the arguments $x_0,\ldots,x_n$. However, what we need for a definition by recursion is a single function $g$ that works for all $n$.
We could try to save the argument by using a sequence of functions $(g_n : n \in \mathbb{N})$ such that each $g_n$ takes values in $A_n$, but getting such a sequence is just as hard as the original problem.
