Axiom of countable choice

Question

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.

Answer 1

This is a good question. It highlights the difference between the intuitive way we may think about sets, and the formal rules that ensure the existence of sets in $\mathsf{ZF}$. When working on $\mathsf{ZF}$, sets exist if we can apply the axioms and verify their existence. The comprehension axiom is a useful way of doing this, but it requires we exhibit first-order formulas. $(n+1)!=(n+1)n!$ does not quite give us a formula $\phi$ defining the factorial function, $\phi(x,y)$ holds iff $x$ is a natural number and $y=x!$, because the formula would seem to be $\phi(x,y)$ iff $x=0$ and $y=1$, or $x=n+1$ for some natural number $n$, and $y=(n+1)z$ where $\phi(n,z)$, but of course this completely natural recursive approach is not a valid rule of formation when working in a first-order language.

You are saying: By recursion, pick $x_n\in A_n$. Maybe you are explicitly finding $x_n$ in an unambiguous way, so that anybody else following your instructions will end up with the same $x_n$. In that case, you have indeed produced a sequence $(x_n)_{n\in\mathbb N}$ with $x_n\in A_n$ and choice was not used. This is possible in specific cases, of course.

For example, each $A_n$ could be a non-empty finite set of reals. Your rule could be: Let $x_n$ be the least element of $A_n$. Or each $A_n$ could be a non-empty closed subset of $\mathbb R$, and your rule could be: List the integers as $0,1,-1,2,-2,\dots$ and, according to this enumeration, let $m$ be least such that $[m,m+1)\cap A_n\ne\emptyset$, and let $x_n$ be the least element of this intersection.

Note that in the examples above there is no actual recursion, so we are just defining a function $f:\mathbb N\to\bigcup_n A_n$ with $f(n)=x_n\in A_n$ for all $n$ (using, say, the comprehension axiom).

It may be that $x_n$ is defined in a matter that actually involves the previous $x_m$. Then we cannot naively apply comprehension to $\mathbb N\times\bigcup_n A_n$, as we do not seem to have a first-order formula that $x$ satisfies iff $x=(n,x_n)$ for some $n$ (as suggested with the similar problem when defining the factorial function above). Typically proofs of recursion theorems actually spend most of the argument verifying that we indeed produce such a formula when arguing by recursion.

To complete the example of the factorial function, what you do is to first verify that there is a formula $\psi(n,x)$ that holds iff $n$ is a natural number and $x$ is a function with domain $\{0,\dots,n-1\}$ and such that if $n>0$, then $x(0)=1$, and if $m+1\in\mathrm{dom}(x)$, then $x(m+1)=(m+1)x(m)$. One then proves that for all $n$ there is a unique $x$ such that $\psi(n,x)$, and that if $\psi(n,x)$ and $\psi(m,y)$, and $m<n$, then the restriction of $x$ to domain $\{0,\dots,m-1\}$ is precisely $y$. Once all this is done, one argues that the set $A=\{x\mid$ there is an $n$ such that $\psi(n,x)\}$ exists, and one lets the factorial function be the union of all $x$ in the set $A$. Of course, one needs to check that this is indeed a function, and its domain in $\mathbb N$, and it satisfies the recursive definition of the factorial. The point of saying all of this is to stress that there is a healthy amount of work going from the intuitive description of a recursive process to the verification of the existence of the sequence the recursion is describing. (See here for more details in a more restrictive setting.)

If it turns out that our recursion was sufficiently specific, then yes, the process described above gives us a sequence, and choice was not invoked. But if the process is not specific enough, we run into problems. Consider, for example, the case where the $A_n$ are infinite sets of reals, and we want to ensure that $x_n\in A_n$ for all $n$ (and $x_n\ne x_m$ for $n\ne m$). Clearly, given any $x_0,\dots,x_{n-1}$, we can pick $x_n\in A_n$ different from all the previous $x_i$, since $A_n$ is infinite. However, if this is all we say in terms of a recursive description, the argument suggested above is not going to give us a sequence at the end. The problem is that, indeed, we have that for each $n$ there is a sequence $(x_0,\dots,x_n)$ as required (we can argue by induction to ensure that such sequences exist), but we are not ensuring the uniqueness of these sequences, so there may be a completely different sequence $(y_0,\dots,y_n)$ that also satisfies the requirements: The $y_i$ are distinct, and $y_i\in A_i$. Not having uniqueness, we cannot carry out the last step of the process, where we took the union of the partial sequences and obtained as a result the infinite sequence we were after. Now, we have many partial sequences, which need not be compatible with one another, and their union will not be a sequence.

Again, unless a very specific description is provided in the recursive process that makes matters unambiguous, we have not ensured that we obtain a sequence at the end. It is only an appeal to an additional axiom that ensures that this is the case in general. (As you are probably aware, it is consistent with the other axioms of set theory that there is no way of fixing the naive approach, and there may be sequences of non-empty sets $(A_n)_{n\in\mathbb N}$ without choice functions $(x_n)_{n\in\mathbb N}$ with $x_n\in A_n$ for all $n$. For example, see here and its suggested references).

See also here, where I illustrate some examples hopefully further clarifying the subtleties involved.

Answer 2

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

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

2. 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.

Answer 3

The principle of recursion that you want to appeal to says something like this:

For any set $X$, given $b \in X$ and a function $R: X \times \mathbb{N} \rightarrow X$, then there is a (unique) function $f : \mathbb{N} \rightarrow X$ such that:

$$\begin{align*} f(0) &= b\\ f(n+1) &= R(f(n), n) \end{align*}$$

To give the function $f$ we want, we will need to define an $R$ such that $R(x, n) \in A_{n+1}$ whenever $x \in A_n$. But we have no justification for the existence of such an $R$ without assuming some kind of choice principle.

Answer 4

The essential step would go like this: By assumption the set of functions $f\colon\{1,\ldots,n\}\to\bigcup A_k$ with $f(k)\in A_k$ is not empty. Even without Axiom of countable Choice we can make one choice of such a function $f$ and one choice of an element $y$ of $A_{n+1}$. Then letting $g(k)=f(k)$ for $k\le n$ and $g(n+1)=y$ we obtain a function $\{1,\ldots,n+1\}\to\bigcup A_k$ with the desired properties, hence the set of such functions is nonempty.

This works. Howeverit does not show that the set of functions $f\colon \mathbb N\to \bigcup A_k$ with $f(k)\in A_k$ is nonempty.

Answer 5

Because definitions are inherently finite. Defining a countable choice function would require some mechanism for infinite definitions. The axiom of choice is such mechanism.