A Question related to the Formula Hierarchy 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: It's $\Pi^1_1$ - you can shuffle number quantifiers around set quantifiers, and "fuse" two second-order quantifiers of the same type (just as you can with first-order quantifiers).
Essentially the proof of quantifier shuffling: consider the sentence $\psi\equiv\exists n\forall X\varphi(n, X)$ where $\varphi$ is some formula. This is equivalent to the following statement: $$\hat{\psi}\equiv\forall X\exists i\varphi(i, X_i)$$ where $X_i$ denotes the $i$th row of $X$, thinking of $X$ as an array of sets via some nicely definable bijection $\omega\cong\omega^2$. The point is: if $\psi$ is true, then clearly $\hat{\psi}$ is true. Meanwhile, if $\psi$ is false, then we can pick a sequence of sets $X_i$ such that $\neg\varphi(i, X_i)$; then $X=(X_i)_{i\in\omega}$ provides a counterexample to $\hat{\psi}$.
If memory serves, this is treated in more detail in Kleene's original paper on the arithmetic and analytic hierarchies, "???." There he also treats the problem of simplifying the matrix of a sentence in the analytic hierarchy: if $\varphi$ is an arithmetic formula, and $Q$ is some block of second-order quantifiers, then $$Q\varphi\equiv Q\hat{\varphi}$$ for some $\Sigma^0_1$ formula $\hat{\varphi}$.

EDIT: In my argument showing that it's $\Pi^1_1$, I'm invoking "enough logic;" in particular, I need to be able to build the sequence $(X_i)_{i\in\omega}$ of counterexamples, just by knowing that a counterexample exists for each $i$. As Emil points out in his comment, this is (at least from the point of view of reverse math) a very strong assumption: in particular, a weak theory - say, $RCA_0$ - may not be able to prove that your sentence is $\Pi^1_1$ (more precisely, there may be no $\Pi^1_1$ sentence which $RCA_0$ proves is equivalent to your sentence). So it depends what you are asking for: provable complexity over some theory, or "true" complexity.
A: There is an additional twist in the case where $\alpha$ is $\Sigma^0_1$. Assuming $\mathsf{WKL}_0$ (Weak König 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.
