4
$\begingroup$

If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a $\Sigma_{n-1}$-oracle. Then, because we do not have oracles, we shouldn't be able to prove any such statement with $n\geq 2$ within PA, even if $\phi$ is true in the standard N.

If the answer to the question is yes, does that mean that any theory stronger than PA that proves a $\phi$ true in N (but independent of PA) equivalent to introducing axioms about oracles? Are then math theories (or formal systems) stronger than PA ontologically equivalent to educated guesses about oracles?

Bonus question: Is the CH or any other axiom of set theory and beyond equivalent to some kind of transfinite halting question using some kind of "super" oracle?

More distilled question: I agree that even if ϕ is independent from PA, ϕ∨¬ϕ is not, because it is a tautology. Then, for instance, if ϕ∨¬ϕ is Σ3, then ϕ∨¬ϕ is equivalent to state that a given Turing machine halts on input C using a Σ2-oracle (and that will be true). Now, does the fact that we were able to prove ϕ∨¬ϕ mean that the oracle is not necessary? or stating it in a different way, doest it mean that, even if ϕ∨¬ϕ is Σ3, and because it can be proved, it is also equivalent to state that the same Turing machine will halt on input C even without an oracle?

1 Answers 1

4

The statement about oracles is known as Post's theorem.

You can certainly prove statements in PA of arbitrarily high quantifier complexity. For example, every instance of $\phi \lor \lnot \phi$ is provable in PA, regardless of the quantifier structure of $\phi$. Similarly, the induction scheme in PA contains formulas that are arbitrarily high in the arithmetical hierarchy.

The continuum hypothesis is (equivalent to) a $\Sigma^2_1$ formula. Thus you can indeed view it as solved by the "super oracle" that is able to decide this kind of type 2 quantification, namely existential quantifiers over functions from $\omega^\omega$ to $\omega$ applied to formulas of second-order arithmetic with variables for such functions. But at that level we are very, very far from "computability" in the usual sense.

  • 2
    An example of a nontrivial statement provable in PA is this finite version of Ramsey's theorem: for every $k$ and $M$ there is an $N$ such that for every $k$-coloring of the natural numbers from$1$to $N$ there are at least $M$ numbers in that range which receive the same color. That statement takes some work to express as a formula in the language of arithmetic, but just looking at the quantifiers in English shows it is at least $\Pi^0_4$.2012-11-15