Uniformization property of $\mathbf{\Sigma}^0_n(\mathscr X\times\omega)$ for $n>1$

Question

This question is about exercise 1C.6 from Moschovakis.

The exercise is to prove if $P\subset\mathscr X\times \omega$ is in $\mathbf{\Sigma}^0_n$ for $n>1$, then there is some $P^*\subset P$ that is also in $\mathbf{\Sigma}^0_n$ which uniformizes $P$.

Since $P$ is $\mathbf\Sigma^0_n$, there exists $Q\subset \mathscr X\times\omega\times\omega$ in $\mathbf \Pi^0_{n-1}$ such that $P=\exists^\omega Q$. The hint of the exercise defines $R\subset Q$ such that $(x,s_0,s_1)\in R$ iff $(x,s_0,s_1)\in Q$ and $(x,t_0,t_1)\notin Q$ for all $(t_0,t_1)=t<s=(s_0,s_1)$, where I assume $<$ is a well-order on $\omega\times\omega$. I understand why $P^*=\exists^\omega R$ uniformizes $P$, but I don't understand why $R$ is $\mathbf{\Pi}^0_{n-1}$.

Answer 1

I am not sure the order-type of $<$ over $\omega\times\omega$, but if its order-type is $\omega$, then $R$ is $\mathbf{\Delta}^0_n$, since it is a conjunction of

• a $\mathbf{\Pi}^0_{n-1}$ formula ($(x,s_0,s_1)\in Q$) and
• a $\mathbf{\Sigma}^0_{n-1}$ formula ($(x,t_0,t_1)\notin Q$ for all $(t_0,t_1)<(s_0,s_1)$. Adding the quantifier bounded by $(s_0,s_1)$ does not increase the complexity.)

Hence $P^*=\exists^\omega R$ is $\mathbf{\Sigma}^0_n$.