Why can countable recursive constructions not be done using countable choice? For example, replace $Z$ by $\omega$ in the following theorem

enter image description here

Why can't one prove it using countable choice? (The proof for the given version is the following:

enter image description here

As pointed out in the comments by Brian, modifying the given argument won't work. But what about a different proof? Is it clear that that's not possible?

Thanks for your help.

  • 2
    $\begingroup$ Making $Z$ countable doesn’t ensure that $\mathcal{G}$ is countable; in general it won’t be. $\endgroup$ – Brian M. Scott Dec 4 '12 at 8:03
  • $\begingroup$ @BrianM.Scott So it doesn't even work if I restrict to $Z = X = \omega$? (because $\omega^\omega$ is uncountable?) $\endgroup$ – Rudy the Reindeer Dec 4 '12 at 8:10
  • $\begingroup$ Certainly the suggested argument doesn’t: there are just too many pairs $\big\langle\langle f,z\rangle, A\big\rangle$ such that $\varnothing\ne A\subseteq X$ and $f:I_W(z)\to X$. $\endgroup$ – Brian M. Scott Dec 4 '12 at 8:15
  • $\begingroup$ @BrianM.Scott Yes, ok, I accept that modifying the given argument won't work. What about a different argument? Is it "obvious" that such an argument cannot exist? Or might there be one? $\endgroup$ – Rudy the Reindeer Dec 4 '12 at 8:17
  • 1
    $\begingroup$ The special case of the "Principle of Generalized Recursive Constructions", with $Z$ being $\omega$ with the usual ordering, already implies the principle of Dependent Choice, which is known to be strictly stronger than Countable Choice. (In fact, this special case seems to be equivalent to Dependent Choice.) $\endgroup$ – Andreas Blass Dec 24 '12 at 19:20

The short answer is that recursive constructions1 give you a sequence by extending a specific sequence; whereas countable choice cannot guarantee the coherence in the choice of sequences.

Let's look at a typical situation where we can reduce recursive constructions to countable choice:

Theorem. Every infinite set $X$ contains a countably infinite subset.

Proof I. Consider the function $G^*$ whose domain is pairs $\langle f,n\rangle$ where $f$ is a function from $n=\{0,\ldots,n-1\}$ into $X$ and $G^*(f,n)=\{x\in X\mid x\notin\operatorname{rng}(f)\}$. By the principle of recursive constructions, there is $F\colon\omega\to X$ such that $F(n)\in G^*(F|n,n)$.2 It is not hard to show now that $F$ is injective by induction on $\omega$. $\square$

Proof II. Consider for every $n$ the following set $$A_n=\{\langle Y,f\rangle\mid Y\subseteq X\text{ with exactly }n\text{ elements}, f\colon Y\to\omega \text{ injective}\}$$ Then by the assumption that $X$ is infinite, for every $n$, $A_n\neq\varnothing$. By countable choice we can choose exactly one element from each $A_n$, $\langle Y_n,f_n\rangle$. Now we claim that $Y=\bigcup Y_n\subseteq X$ is a countably infinite set. It is clear that $Y$ is infinite, since we take unions of increasingly large finite sets. To see that $Y$ is countable, fix $y_0\in Y$ and define $F\colon\omega\times\omega\to Y$ as follows: $$F(n,m)=\begin{cases}f^{-1}_n(m) & m<n\\ y_0 & n\leq m\end{cases}$$ It is clear that $F$ is a surjection, and therefore $Y$ is countable. $\square$

So what happens here? We could do it relatively easily by recursion, simply pick one more element at each step (even if this is not presented as such). But we could be clever and directly choose finite sets with their enumerations, then the union of enumerated sets is well-orderable and in this case countable.

But what could have happened when we just picked the finite set? Why didn't we write a bijection with $\omega$ directly, and decided to opt for a surjection instead? Because the choices of the $Y_n$'s did not necessarily cohere with one another, so $Y_1$ may or may not have been a subset of $Y_2$ and $f_5$ may or may not have agree with $f_{42}$ on the common elements of their domain.

So what would have been a simple case of picking $f=\bigcup f_n$ as an injection into $\omega$ turns out to be possibly not a function at all. And so we needed to "correct" this by one way or another.

And this is exactly the difficulty in the general case. While countable choice allows us to choose infinitely many elements at once, it does not need to obey any laws of coherence between the choices. And the whole point of recursive constructions and definitions is that the choices are in fact coherent.

Formally speaking, we know that we cannot prove the recursive constructions principle from countable choice because there is a model in which countable choice holds, and the generalized principle of recursive constructions fails.

The idea behind the construction3 is to add a "very wide" tree of height $\omega$ without maximal elements, and only "remember" subsets which have bounded height, and things we can construct from those. It is a technical proof to show that countable choice still holds, but it is easy to show4 that there are no branches in that tree. And it is also quite easy to show that if recursive constructions can go through, then every such tree should have a branch.

So what happens in such a tree? Well, we can repeat something similar to the choice of arbitrarily long branches, but there we cannot combine them into a branch because the choices must be coherent, there is no way around that at all.


  1. I will only consider the case where $Z=\omega$, as that is the case in question.

  2. The version you use has a typo, and it should be $F(z)\in G^*(F|I_W(z),z)$ in the conclusion of the principle. And that makes sense too, since $G^*$ takes two variables.

  3. I actually wrote an ever so slightly more detailed version on MathOverflow which shows how to prove an even more general theorem about the failure of generalized recursive constructions (not necessarily countable), while still preserving arbitrarily high choice from well-ordered families.

  4. From the actual definition, anyway, not this hand-waving explanation.


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.