7
$\begingroup$

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
    Making $Z$ countable doesn’t ensure that $\mathcal{G}$ is countable; in general it won’t be.2012-12-04
  • 0
    @BrianM.Scott So it doesn't even work if I restrict to $Z = X = \omega$? (because $\omega^\omega$ is uncountable?)2012-12-04
  • 0
    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$.2012-12-04
  • 0
    @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?2012-12-04
  • 0
    You need to be a bit more explicit about $X=Z=\omega$. What about $W$?2012-12-04
  • 0
    I should also add that independence proofs are extremely difficult from the current material. They will require learning forcing (again), and about symmetric extensions, and even then the arguments are hardly ever simple. If you are willing to accept the fact that at this point some proofs you are going to take as a black box, then perhaps find something which you know countable choice cannot prove and show this principle proves it.2012-12-04
  • 0
    (Not exactly elementary any more, are we now?)2012-12-04
  • 1
    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.)2012-12-24
  • 0
    Godel's constructible class L is defined recursively and was developed in order to show (among other things) the consistency of Choice. So it is better to have a proof of the Recursion principle that does not depend on Choice or any of its weaker variants.2015-12-26
  • 0
    @user254665: What?2015-12-26

1 Answers 1