If $R$ is $\Sigma_n$ and $(x,y)\in A\iff (\forall z < y) R(x,y,z)$, then $A$ is $\Sigma_n$

17 Views Asked by At

Suppose $R\in \Sigma_n$ and $A$ is defined by $$(x,y)\in A\iff (\forall z < y) R(x,y,z)$$

The claim is that $A\in \Sigma_n$.

I've been trying to prove this by just expanding the expression:

We know that there is a computable $S\subset N^{n+3}$ such that $$(x,y,z)\in R\iff \exists t_1\forall t_2\dots \exists t_n S(x,y,z,t_1,\dots, t_n)$$

so we have $$(x,y)\in A\iff (\forall z)(z < y \to \exists t_1\forall t_2\dots \exists t_n S(x,y,z,t_1,\dots, t_n) )$$

I guess we can "factor out" the inner quantifier one by one since the antecedent of the implication doesn't contain those variables:

$$(x,y)\in A\iff (\forall z)\exists t_1\forall t_2\dots \exists t_n(z < y \to S(x,y,z,t_1,\dots, t_n) )$$

but now the expression starts with the universal quantifier, which is no good. What to do with it?