7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Oh I'm sorry I missed that word, my bad. $\endgroup$ – Noah Schweber May 3 at 17:28
  • 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$ – none May 4 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 Gruber May 4 at 19:33
  • 1
    $\begingroup$ @FrançoisG.Dorais, the OP might also be looking for an example with a proof. $\endgroup$ – Matt F. May 5 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 Buchholtz May 6 at 20:29
3
$\begingroup$

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''

| cite | improve this answer | |
$\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.