MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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$.

(This is basically just showing that the Axiom of Choice holds for finite collections of sets.)

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.

share|cite|improve this answer
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 Schweber 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
Oh, hold on minute. I can't use transfinite inductions here, we're under AD :) Only your case will work. – Carlo Von Schnitzel Oct 10 '11 at 2:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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