3
$\begingroup$

Since the Goldbach conjecture is in $\Pi_1^0$, if it were proven to be independent of Peano Arithmetic, it would follow that the Goldbach conjecture is true (i.e. true in the standard model), since informally speaking, if it were indeed false, we would have a counterexample of the Goldbach conjecture, contradicting the claim that the Goldbach conjecture is independent.

This argument initially lead me to the intuition that quantifiers (or at least $\forall$, I'm not sure if this method equally applies for statements in $\Sigma^0_1$) allow us to remove a single level of undecidability, turning it into negation, but still leaving the possibility that, the decidability of the Goldbach conjecture could be undecidable, leaving us no metamathematical proof of the truth of the Goldbach conjecture. However, how this argument works for other statements in the arithmetical hierarchy is not clear to me.

Certainly in $\Pi^0_0$, nothing can be done to reduce independence to truth or falsity via metamathematical means, so statements in $\Pi^0_0$ proven to be independent are "actually independent". However, I run into problems thinking about $\Pi^0_n$ for $ n > 1 $. My initial thought was that possibly, building on my intuition, $\Pi^0_n$ statements should reduce "n-fold undecidability" to truth, but this intuition does not seem to be correct. For example, this answer to a math overflow question claims that since the twin primes conjecture is a $\Pi^0_2$ statement, "Neither it nor its negation are obviously true if verified independent", plus, if I am interpreting this other answer correctly, we cannot actually prove n-fold undecidability for $n > 1$. My question then is, what are the possibilities for a general statement in $\Pi_n^0$ which has been proven to be independent? When can we reduce such a statement to truth or falsity using metamathematical means, and when can we say that it is "absolutely undecidable"?

$\endgroup$
  • 2
    $\begingroup$ Since the negation of $\Pi^0_0$ is in itself $\Pi^0_0$, it follows that $\Pi^0_0$ statements are not independent of Peano. They are either provable or refutable. More generally, PA is $\Sigma_1$-complete, it proves every true $\Sigma_1$ statement; so if a statement is "simpler" (i.e. $\Pi^0_0$) it will either prove it or prove its negation. $\endgroup$ – Asaf Karagila Jan 11 '16 at 20:35
5
$\begingroup$

To clarify matters, this does not apply to arbitrary theories, so let's concentrate on PA. The key is the $\Sigma_1$-completeness of PA (I omit the $0$ in the superscript). So if a $\Pi_1$ sentence is consistent with PA (note that this is weaker than independent), then it is true. Indeed, otherwise its negation is true and hence provable in PA as it is $\Sigma_1$.

A $\Pi_0$ sentence is also $\Pi_1$, so this applies to $\Pi_0$ sentences as well. However a $\Pi_0$ sentence is also $\Sigma_1$. Hence every true $\Pi_0$ sentence is provable in PA. So $\Pi_0$-sentences cannot be independent. (See also Asaf's comment).

This argument does not extend to $\Pi_n$ for $n > 1$ as PA is no longer $\Sigma_n$-complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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