4
$\begingroup$

What is meant when somebody says that a problem can be expressed as a $\Pi_1$-sentence? I know that for the arithmetical hierarchy, a $\Pi^0_1$-sentence is a sentence of the form $\forall n_1\forall n_2\dots\forall n_k \psi$ where $\psi$ is a formula in the language of Peano arithmetic with only bounded quantifiers. And for the analytical hierarchy, a $\Pi_1^1$-sentence is a sentence of the form $\forall X_1\forall X_2\dots\forall X_k \psi$ where $\psi$ is a formula in the language of second-order arithmetic with no set quantifiers.

I found the following definition for this notation in section "5 Proving Independence" of an article on the possibility of undecidability:

Let’s define a $\Pi_1$-sentence to be any sentence of the form, “For all $x$, $P (x)$,” where $P$ is function that can be proven to be recursive in Peano Arithmetic, PA.

People talking about $\Pi_1$- and $\Pi_2$-sentences sometimes refer to Shoenfield's absoluteness theorem, which seems to talk about $\Pi^1_2$-sentences, i.e. refers to the analytical hierarchy. Can I deduce from this that people talking about $\Pi_1$-sentences use $\Pi_1$ as a shorthand for $\Pi^1_1$ (because $x^1=x$...)? But the quoted definition looks much more like the condition from the arithmetical hierarchy to me, even so I'm not sure whether it is really equivalent to it.

$\endgroup$
3
$\begingroup$

Since Peano arithmetic is a first-order theory, all quantifiers are first-order, so it's a $\Pi_1^0$ sentence. The article probably contains examples supporting this interpretation.

$\endgroup$
2
$\begingroup$

What is meant when somebody says that a problem can be expressed as a $Π_1$-sentence?

It's a $\Pi^0_1$ sentence, just like Yuval Filmus said. Instead of proving that the cited definition is indeed equivalent to the condition of a $\Pi^0_1$ sentence (which should be possible), let me provide further evidence of actual usage:

In each of the cited cases, some people talk about $\Pi_1$ sentences and some people talk about $\Pi^0_1$ sentences, and both sides agree that they are talking about the same thing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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