# Moschovakis Coding Lemma

I trying to study the Coding Lemma (in descriptive Set Theory) and there is a small point in the proof that I don't understand. Let me first recall the version I'm studying ( there are different version of the Moschovakis Coding lemma).

Assume AD. Let $\Gamma$ be a non-self-dual pointclass closed under real quantification and conjunction. Suppose that $\prec$ is a $\Gamma$ wellfounded relation on $\omega^{\omega}$. Then for any $R\subseteq dom(\prec)\times \omega^{\omega}$ such that $\forall x \in dom(\prec) \exists y R(x,y)$, there is an $A\subseteq dom(\prec)\times \omega^{\omega}$, $A\in \Gamma$, which is a choice set for $R$. That is,

$\forall \alpha < |\prec| \exists x \in dom(<) \exists y [|x|_{\prec}=\alpha \wedge A(x,y)]$

$\forall x, y[A(x,y) \rightarrow R(x,y)]$.

Now here's what I don't get. The proof starts as follows: Since $\Gamma$ is non-self-dual, let $U \subseteq (\omega^{\omega})^3$ be a universal set in $\Gamma$ for the $\Gamma$ subsets of $\omega^{\omega} \times \omega^{\omega}$. Let $\delta$ be the least length of $\prec$ such that the theorem fails. Then $\delta$ is a limit ordinal.

Why is $\delta$ a limit ordinal?

-

I might be missing something, but I believe the answer is the following. First suppose $\Gamma$ isn't present. Then this just amounts to showing that, if $R\subseteq X\times Y$, $Z$ is a cofinite subset of $X$, and I have a choice set $C$ for the induced $R'\subseteq Z\times Y$ (that is, $R'=R\cap (Z\times Y))$, then I can extend that choice set to a choice set for $R$. To see that I can do this, we just use the fact that $X-Z$ is finite. Write $X-Z=\{z_1, . . . , z_n\}$, and let $y_1, . . . , y_n$ be such that $R(z_i, y_i)$ holds for all $i$. Then the set $C\cup\lbrace (z_i, y_i): 1\le i\le n\rbrace$ is a choice set for $R$.
Now in the case of the theorem in question, our choice sets need to be taken from some class $\Gamma$. This means that we'll need to rely on some closure property of $\Gamma$; fortunately, we appear to have that, so (unless I'm missing something) the above proof works.
I am sorry I am not understanding your answer. You say the above proof works. I think the point of the coding lemma is that we have definable choice sets given some conditions. Also my question is about the following point: when we take $\delta$ to be the least such that the theorem fails, why does it have to be a limit ordinal? –  Carlo Von Schnitzel Oct 9 '11 at 18:33
The reason it's a limit ordinal is - again, unless I'm missing something - just the argument above. Think about it this way: if I have a (definable) choice set for an initial segment of length $\beta$, I can extend it to a (definable) choice set of length $\beta+1$ just by adding to the definition of the choice set for length $\beta$ a single clause describing its behavior at one more term. –  Noah S Oct 9 '11 at 20:26
Ok. That is what I had in mind but I was not sure about it. After running through this argument I would kept telling myself that the situation would be the same with a limit ordinal: say I have choice sets of length $\delta<\beta$ then by transfinite induction (maybe over wellfounded relations) this should also hold for $\beta$. Something must be wrong with what I just said this but I don't know what it is. –  Carlo Von Schnitzel Oct 10 '11 at 1:48