# Why can countable recursive constructions not be done using countable choice?

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

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

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.

-
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