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?

  • 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, 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$ May 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$ May 4, 2020 at 22:59
  • 1
    $\begingroup$ @FrançoisG.Dorais, the OP might also be looking for an example with a proof. $\endgroup$
    – user44143
    May 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$ May 6, 2020 at 20:29

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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