3
$\begingroup$

According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C using a $\Sigma_{n-1}$-oracle halts, then C actually halts". Assuming this statement is correct, I have a doubt about the "if" part: Is every $\Sigma_n$ formula of PA semantically equivalent to a statement saying that a given program C using a $\Sigma_{n-1}$-oracle halts? or only some $\Sigma_n$ formulas, but not all of them are? Thanks!

Bonus questions: If there are formulas that are not equivalent to a halting problem, are they equivalent to some other analogy regarding Turing machines? and, are there PA sentences that are not semantically equivalent to any computational analogy?

1 Answers 1

2

Yes, by Post's theorem, for every $\Sigma^0_{m+1}$ formula $\phi(x)$ there is an oracle Turing machine $e$ such that, for every $i$, $\phi(i)$ holds if and only if machine $e$ halts on input $i$ when run with oracle $\emptyset^{(m)}$. Here $\emptyset^{(m)}$ is the $m$th Turing jump of the empty set, and is a $\Sigma^0_m$ set.

In general, Post's theorem shows that there is an extremely close connection between the arithmetical hierarchy, computability, and the sets $\emptyset^{(m)}$. The claim in the Wikipedia article is just one part of this connection.


Start with the negation of the twin primes conjecture. The negation is $\Sigma^0_2$ and thus by Post's theorem is equivalent to the claim that some particular oracle machine halts when it is run with $\emptyset'$ an oracle. Since there are no free variables, that machine does the same thing regardless of input - it ignores the input.

In this particular case, what the machine does is to search for the least $k$ such that there is no pair of twin primes greater than $k$, and then halts if it finds such a $k$. The oracle $\emptyset'$ is able to decide the set $$\{ k : \text{ there is a pair of twin primes greater than } k\}$$ because that set is $\Sigma^0_1$ and $\emptyset'$ is $\Sigma^0_1$ complete. So the oracle machine is able to use the oracle $\emptyset'$ to repeatedly test whether each $k$ is in the set and then halt if it finds a $k$ that is not in the set.

The the original twin primes conjecture is then equivalent to the claim that that machine does not halt when run with an oracle for $\emptyset'$. If it never halts, that means it never finds a $k$ such that there is no pair of twin primes greater than $k$, so there are arbitrarily large pairs of twin primes, and vice versa.

  • 0
    Thanks! It is still confusing to me what would be the interpretation for a φ that doesn't have any free variables. For instance, let us take the twin prime conjecture : ∀k:∃n:n>k∧ϕ(n) with ϕ(n) defined as "n−1 is prime and n+1 is prime". Since ϕ(n) is $\Pi_0^0$, φ is $\Pi_2^0$. So, what would be the statement for Post's theorem for φ? Specifically, I dont know what would play the role of "i" in "for every i, φ (i) holds if and only if machine e halts on input i ". What is "i" if there are no free variables in φ?2012-12-02
  • 0
    I appended an explanation to my answer.2012-12-02