Skip to main content
1 of 2
Rachid Atmai
  • 3.8k
  • 2
  • 24
  • 36

Moskovakis 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 Moskovakis 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?

Rachid Atmai
  • 3.8k
  • 2
  • 24
  • 36