Simplest independent first-order expression in PA

  • Context: Undergrad 
  • Thread starter Thread starter ad infinitum
  • Start date Start date
  • Tags Tags
    Expression Independent
Click For Summary
SUMMARY

The simplest known first-order expressions independent of Peano Arithmetic (PA) but decidable in Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC) include the Paris-Harrington theorem and Goodstein's theorem. These examples illustrate the complexity of certain mathematical statements that exceed the proof capabilities of PA. Additionally, the "hydra game" serves as a notable instance where the player can always win, yet proving this requires a system stronger than PA. The discussion highlights a spectrum of strictly increasing total recursive functions that can be proven in ZFC but not in PA.

PREREQUISITES
  • Understanding of Peano Arithmetic (PA)
  • Familiarity with Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC)
  • Knowledge of first-order logic and expressions
  • Basic concepts of recursive functions and their classifications
NEXT STEPS
  • Research the Paris-Harrington theorem and its implications in mathematical logic
  • Explore Goodstein's theorem and its proof techniques
  • Investigate the hydra game and its relation to proof theory
  • Study the classification of recursive functions and their provability in different logical systems
USEFUL FOR

Mathematicians, logicians, and computer scientists interested in the foundations of mathematics, proof theory, and the limitations of formal systems like Peano Arithmetic.

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

Similar threads

  • · Replies 64 ·
3
Replies
64
Views
3K
  • · Replies 13 ·
Replies
13
Views
3K
  • · Replies 28 ·
Replies
28
Views
6K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 11 ·
Replies
11
Views
4K
  • · Replies 16 ·
Replies
16
Views
3K
  • · Replies 3 ·
Replies
3
Views
10K
  • · Replies 6 ·
Replies
6
Views
3K