Let large Latin symbols as $X$ and $Y$ denote sets of natural numbers and small symbols as $n$ and $n´$ denote natural numbers and small Greek letters stand for formulas.


Suppose $\alpha$ is $\Pi\_1^0$ or $\Sigma\_1^0$. Is ($\forall X$)($\exists n$)($\forall Y$)$\alpha(X,Y,n)$ $\Pi\_2^1$, or what?



A Question related to the Formula Hierarchy
There is an additional twist in the case where $\alpha$ is $\Sigma^0\_1$. Assuming $\mathsf{WKL}\_0$ ([Weak König Lemma](http://en.wikipedia.org/wiki/K%C3%B6nig's_lemma)), $\forall Y\alpha(X,Y,n)$ is equivalent to a $\Sigma^0\_1$ statement and hence so are $\exists n \forall Y \alpha(X,Y,n)$ and $\forall X\exists n \forall Y\alpha(X,Y,n)$.


The reason why $\exists X\phi(X)$ remains $\Sigma^0\_1$ can be seen as follows. The verification that $\phi(X)$ holds for a specific $X$ can only use a finite amount of information about the set $X$. It follows that if we identify subsets of $\mathbb{N}$ with their characteristic functions, then $\{X \subseteq \mathbb{N} : \phi(X)\}$ is an open set in $2^{\mathbb{N}}$. Because $2^{\mathbb{N}}$ is compact, $\forall X\phi(X)$ holds if and only if there is an $n$ such that $\phi(X)$ holds for every $X \subseteq \{0,\ldots,n-1\}$ and $\phi(X)$ only uses information about membership in $X$ for numbers less than $n$ (and therefore $\phi(X')$ also holds whenever $X = X' \cap \{0,\ldots,n-1\}$). Since subsets of $\{0,\ldots,n-1\}$ are easily coded using numbers $\{0,\ldots,2^n-1\}$ this means that $\forall X \phi(X)$ is equivalent to a $\Sigma^0\_1$ formula $\exists n\forall x < 2^n\widehat{\phi}(n,x)$, where $\widehat{\phi}(n,x)$ can be effectively computed from the original formula $\phi(X)$.


Note that this doesn't work if one uses functions $\mathbb{N}\to\mathbb{N}$ instead of subsets of $\mathbb{N}$ since Baire space $\mathbb{N}^{\mathbb{N}}$ is far from compact.




---


As Emil pointed out in the comments, a similar trick applies for the case when $\alpha(X,Y,n)$ is $\Pi^0\_1$. Suppose $\alpha(X,Y,n)$ is $\forall m\alpha\_0(X,Y,n,m)$ where $\alpha\_0(X,Y,n,m)$ is bounded. Because universal quantifiers commute, $\forall Y\alpha(X,Y,n)$ is equivalent to $\forall m\forall Y\alpha\_0(X,Y,n,m)$. Because $\alpha\_0(X,Y,n,m)$ is bounded, the statement $\exists Y\lnot \alpha\_0(X,Y,n,m)$ is equivalent to a $\Sigma^0\_1$ statement for if $\alpha\_0(X,Y,n,m)$ holds for some set $Y$ it also holds for some finite set $Y$. (Furthermore, this is provable in $\mathsf{RCA}\_0$ instead of $\mathsf{WKL}\_0$.) It follows that the negation $\forall Y\alpha\_0(X,Y,n,m)$ is equivalent to a $\Pi^0\_1$ statement and hence $\exists n\forall Y\alpha(X,Y,n)$ is equivalent to a $\Sigma^0\_2$ statement. Finally, we conclude that $\forall X\exists n\forall Y\alpha(X,Y,n)$ is $\Pi^1\_1$ and this is provable in $\mathsf{RCA}\_0$.


The Kleene Normal Form Theorem (provable in $\mathsf{ACA}\_0$) shows that every $\Sigma^1\_1$ statement is equivalent to one of the form $\exists X\phi(X)$ where $\phi(X)$ is $\Pi^0\_2$ (since $\Pi^0\_2$ is enough to characterize graphs of total functions). So the last statement $\forall X\exists n\forall Y\alpha(X,Y,n)$ could be as complex as any other $\Pi^1\_1$ statement assuming $\mathsf{ACA}\_0$. Therefore, this case does not lead to a perpetual collapse as in the previous case.


