3
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ Where? It’s $\Pi^1_1$ if you have $\Sigma^1_1$-AC, but only $\Pi^1_3$ otherwise. $\endgroup$ Oct 29, 2014 at 17:04
  • $\begingroup$ @Emil I do not understand the import of the question for location. $\endgroup$ Oct 29, 2014 at 17:12
  • $\begingroup$ “Where” = “in which theory do you need the formula to be proven equivalent to something of a particular complexity”. Regarding the second comment, I’d rather leave that to someone familiar with subsystems of second-order arithmetic, however, I assume so by analogy with the corresponding question in the arithmetic hierarchy: no true $\Pi_2$-axiomatized theory can prove that all $\forall\exists\forall\Delta_0$ formulas with the existential quantifier bounded are equivalent to $\Pi_2$ formulas (whereas $B\Sigma_1$ proves they are $\Pi_1$). $\endgroup$ Oct 29, 2014 at 17:37
  • 1
    $\begingroup$ I should say that I was ignoring the requirement on the complexity of $\alpha$; the speculation that the formula may not be $\Pi^1_2$ without $\Sigma^1_1$-AC was supposed to apply to arbitrary arithmetic $\alpha$ (though $\Sigma^0_2$ should suffice). As shown in François’s answer, this makes a lot of difference. $\endgroup$ Oct 30, 2014 at 11:26
  • 1
    $\begingroup$ @EmilJeřábek: Indeed, for strict $\Sigma^1_1$-formulas of the form $\exists X\phi(X,n)$ where $\phi(X,n)$ is $\Pi^0_1$, choice follows from $\mathsf{WKL}_0$. Additionally, if $\phi(X,n)$ is $\Sigma^0_2$ then choice follows from $\mathsf{ACA}_0$. The general case is when $\phi(X,n)$ is $\Pi^0_2$ (the complexity of saying that a set is the graph of a total function). $\endgroup$ Oct 30, 2014 at 13:21

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ This is a very good point. Do I understand it correctly that if $\alpha$ is $\Pi^0_1$, a similar agument makes the formula $\Pi^1_1$ already in RCA_0? $\endgroup$ Oct 30, 2014 at 11:02
  • $\begingroup$ @François Somehow your statement must be further and appropriately qualified it seems to me. If not, the whole second order formula hierarchy of Second Order Arithmetic collapses for systems stronger than $WKL_0$, right? $\endgroup$ Oct 30, 2014 at 13:26
  • $\begingroup$ (Of course, there is a qualification in that the argument presupposes the compactness of $2^\mathbb{N}$.) $\endgroup$ Oct 30, 2014 at 13:30
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I am also interested in the foundational issues here, and even true complexity. As a follow up, this reminds me of Skolem functions. Is my association to the point? $\endgroup$ Oct 29, 2014 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.