6
$\begingroup$

The following fact, which I've heard being called "soft version of Moschovakis's lemma" (see top answer here) is the following:

Under AD, if there is a surjection $\Bbb R\rightarrow\alpha$, then there is a surjection $\Bbb R\rightarrow\mathcal{P}(\alpha)$.

I remember few days ago I have seen a really nice proof of this result, which directly used AD (and possibly DC, can't remember) and not some complex workaround using scales and things like that. However, when yesterday I wanted to show the proof to a friend of mine, I couldn't have find it anywhere, and I would be very thankful if anyone pointed out where I could have seen this proof.

The rough idea of the proof is the following:

  1. Fix a surjection $f:\Bbb R\rightarrow\alpha$.
  2. For each $X\subseteq\alpha$, using $f$, define a game $G(X)$ on $\omega$.
  3. Show that, for any $X\neq Y$, no winning strategy for $G(X)$ is a winning strategy for $G(Y)$.
  4. Thus, the function $F:\Bbb R\rightarrow\mathcal{P}(\alpha)$, defined as $F(r)=X$ if $r$ codes a winning strategy for $G(X)$, and $F(r)=\varnothing$ if $r$ codes no winning strategy, is well-defined.
  5. By AD, every $G(X)$ has a winning strategy for some player, so $F$ is surjective.

Hope this helps to find the proof I meant. Thanks in advance.

$\endgroup$
  • 2
    $\begingroup$ This is Theorem 28.15 in Kanamori's book. $\endgroup$ – Andrés E. Caicedo Jun 14 '15 at 21:28
  • $\begingroup$ @AndresCaicedo Can you confirm that Kanamori's book has the proof I am talking about? Note that I am looking for a specific proof of the fact. $\endgroup$ – Wojowu Jun 15 '15 at 5:58
  • $\begingroup$ The proof is basically like you say, except that it is also combined with an induction of surjections onto $P(\beta)$ for $\beta<\alpha$. You play a game where player I tries to play a real coding an initial segment of the image of $X$ (using the earlier surjections), and player II tries to play a longer initial segment. It is then not difficult to show that if $X\neq Y$ then no winning strategy in $G(X)$ is winning in $G(Y)$. $\endgroup$ – Joel David Hamkins Jun 17 '15 at 20:40
  • $\begingroup$ @AndresCaicedo I feel dumb for not doing this myself before, but I have just now checked that Kanamori's book indeed has the proof I was thinking about. Feel free to post this as the answer, and I'll award you the bounty. $\endgroup$ – Wojowu Jun 18 '15 at 13:00
  • 1
    $\begingroup$ @AndresCaicedo If you wish to get a bounty for this question, now is your last chance, because bounty is ending. $\endgroup$ – Wojowu Jun 24 '15 at 20:14
5
+50
$\begingroup$

The argument you are looking for is given in Kanamori's book, see Theorem 28.15.

For the more nuanced version of the lemma, see section 7D in Moschovakis's descriptive set theory book (particularly 7.D.5-8), or section 3.1 in the Koellner-Woodin chapter of the Handbook.

$\endgroup$

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.