patternMinor
What is the definition of a $\Pi_1$-sentence?
Viewed 0 times
definitionthewhatpi_1sentence
Problem
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.
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.
Solution
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.
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:
- How to prove a $\Pi_2$ statement properly?
- Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?
- After all, P vs. NP can be expressed as a $\Pi_2$-sentence
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.
Context
StackExchange Computer Science Q#29275, answer score: 2
Revisions (0)
No revisions yet.