Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
Making $Z$ countable doesn’t ensure that $\mathcal{G}$ is countable; in general it won’t be. – Brian M. Scott Dec 4 '12 at 8:03
@BrianM.Scott So it doesn't even work if I restrict to $Z = X = \omega$? (because $\omega^\omega$ is uncountable?) – Rudy the Reindeer Dec 4 '12 at 8:10
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$. – Brian M. Scott Dec 4 '12 at 8:15
@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? – Rudy the Reindeer Dec 4 '12 at 8:17
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.) – Andreas Blass Dec 24 '12 at 19:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.