Simplest independent first-order expression in PA

In summary, there are examples of first-order expressions that are independent of Peano Arithmetic but decidable in ZFC, such as Paris-Harrington theorem and Goodstein's theorem. The concept of simplicity may vary, but one can find examples by searching for "kirby paris hydra" or "hydra game". These examples require stronger systems like ZFC to prove their totality, but there are also cases where ZFC cannot prove their totality.
  • #1
ad infinitum
17
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
  • #2
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 fresh_42

What is the simplest independent first-order expression in PA?

The simplest independent first-order expression in PA (Peano Arithmetic) is the successor function, denoted by the symbol "S" or "+".

How does the successor function work in PA?

The successor function in PA takes a number and produces the next number in the sequence. For example, S(0) = 1, S(1) = 2, S(2) = 3, and so on.

Why is the successor function considered independent in PA?

The successor function is considered independent in PA because it is not defined in terms of any other operation or function in the system. It is a fundamental building block in the axioms of PA.

What are some examples of first-order expressions in PA?

Examples of first-order expressions in PA include "x + y", "x * y", "x < y", where x and y are variables representing numbers in the system.

How is the simplest independent first-order expression used in PA?

The simplest independent first-order expression, the successor function, is used in the axioms and rules of inference in PA to define the natural numbers and their properties, such as addition, multiplication, and ordering.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
28
Views
5K
  • Linear and Abstract Algebra
Replies
2
Views
950
  • Quantum Interpretations and Foundations
8
Replies
249
Views
9K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
  • Mechanical Engineering
Replies
15
Views
788
Replies
1
Views
909
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
4K
Back
Top