Simplest independent first-order expression in PA

  • Context: Undergrad 
  • Thread starter Thread starter ad infinitum
  • Start date Start date
  • Tags Tags
    Expression Independent
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 1K views
ad infinitum
Messages
17
Reaction score
1
What is the simplest known first-order expression known to be independent of Peano Arithmetic but decidable in ZFC for some reasonable notion of simplicity (such as number of quantifiers, nesting depth etc.); the precise definition of simplicity does not matter, I just want to see a concrete example.
 
Physics news on Phys.org
Here are few examples:
https://en.wikipedia.org/wiki/Paris–Harrington_theorem
https://en.wikipedia.org/wiki/Goodstein's_theorem

You can also search for "kirby paris hydra" or the "hydra game" and many interesting results come up. Basically it is a single player game of sorts where the player playing the game always wins "eventually". However, proving that seems to require strength beyond PA.

Based upon my limited knowledge/understanding, there is going to be a fairly large spectrum of strictly increasing (total) recursive functions whose totality will be provable in a stronger system such as ZFC but not in PA. Of course, eventually, there are going to be strictly increasing (total) recursive functions whose totality ZFC won't be able to prove either.
 
  • Like
Likes   Reactions: fresh_42