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
    I appended an explanation to my answer.2012-12-02