[Solved]: What is the definition of a $\Pi_1$-sentence?

Problem Detail: 

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.

Asked By : Thomas Klimpel

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29275

3.2K people like this

 Download Related Notes/Documents