Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of PA?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ I would say that the word problem for finitely presented groups is not metamathematical, although it asks for an algorithm. Its history goes back to before anyone was thinking about undecidability much. Its specific instances are $\Pi_1$ and some of them are undecidable. Whether concocting a specific undecidable one is natural is up to you, I guess. Same with Hilbert's tenth problem. $\endgroup$– noneMay 4, 2020 at 18:09
-
1$\begingroup$ My answer was bad, so I will delete it. But I wanted to save the two enlighting comments to my answer: Goodstein's theorem is a statement of the form $\forall\exists$ (i.e. $\Pi_2$) so unfortunately it's not $\Pi_1$. – user76284 The standard combinatorial statements from the 80s can all be stated as claims that some recursive function is total. Any such statement is $\Pi_2$, and all the famous examples of this kind are properly $\Pi_2$. – Andrés E. Caicedo $\endgroup$– Hermann GruberMay 4, 2020 at 19:33
-
$\begingroup$ Considering that Harvey's goal is to achieve simple and natural examples of undecidability, perhaps you have found the right source already. $\endgroup$– François G. DoraisMay 4, 2020 at 22:59
-
1$\begingroup$ @FrançoisG.Dorais, the OP might also be looking for an example with a proof. $\endgroup$– user44143May 5, 2020 at 2:19
-
2$\begingroup$ As a step in this direction (giving a natural-looking scheme rather than a single sentence), look at Anton Freund's recent A mathematical commitment without computational strength. $\endgroup$– Ulrik BuchholtzMay 6, 2020 at 20:29
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
You may look at Shelah's paper ``On logical sentences in PA''.
For a modern exposition of Shelah's work and an alternative example see ``Independence in Arithmetic: The Method of (L, n)-Models''
answered May 10, 2020 at 9:59