Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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 φ? –  julian fernandez Dec 2 '12 at 22:33
    
I appended an explanation to my answer. –  Carl Mummert Dec 2 '12 at 22:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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