Are there meaningful statements about the numbers which cannot be proved with Peano+(independence from Peano)

164 Views Asked by At

There are meaningful statements about the natural numbers not provable in Peano. Can all such statements be proven by Peano+(Their independence from Peano).

For example can Strengthened Finite Ramsey Theorem https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem#The_strengthened_finite_Ramsey_theorem be proven using only Peano+(the independence of Strengthened Finite Ramsey Theorem from Peano), and if so, are there any counterexamples?

1

There are 1 best solutions below

4
On BEST ANSWER

Well, regardless of what $P$ is, the sentence "$P$ is independent from PA" is a $\Pi^0_1$ sentence; so any sentence $P$ which is independent from PA and not provable from PA + any true $\Pi^0_1$ sentence will be an example. One important class of such statements are reflection (or soundness) principles: these roughly assert that PA proves only true things, and surprisingly are not provable in PA alone (see e.g. Lob's theorem)! E.g. I believe even $\Sigma^0_1$-reflection ("all $\Sigma^0_1$ sentences provable in PA are true") is already not provable from PA + $Th_{\Pi^0_1}(\mathbb{N})$.

Note that $\Sigma_1^0$-reflection and the like are indeed expressible in the language of arithmetic via appropriate Goedelian arguments (and in particular, they refer only to bounded truth predicates, so Tarski's undefinability theorem doesn't apply); by contrast, of course, full reflection is inexpressible (roughly, $\Sigma^0_n$-reflection is a $\Pi^0_{n+1}$-sentence, so as you want "more" reflection you get "more" quantifiers in your sentence, and you never manage to "catch your tail"). So these are meaningful sentences in the language of arithmetic which provide counterexamples to the claim in question.