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$
5
  • 2
    $\begingroup$ This is Theorem 28.15 in Kanamori's book. $\endgroup$ Jun 14, 2015 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, 2015 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$ Jun 17, 2015 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, 2015 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, 2015 at 20:14

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.