Paris–Harrington theorem
Encyclopedia
In mathematical logic
, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory
is true, but not provable in Peano arithmetic. This was the first "natural" example of a true statement about the integers that could be stated in the language of arithmetic, but not proved in Peano arithmetic; it was already known that such statements existed by Gödel's first incompleteness theorem.
Without the condition that the number of elements of Y is at least the smallest element of Y, this is a corollary the statement of the finite Ramsey theorem
in
, with N given by:
Moreover the strengthened finite Ramsey theorem can be deduced from the infinite Ramsey theorem in almost exactly the same way that the finite Ramsey theorem can be deduced from it, using a compactness argument (see the article on Ramsey's theorem
for details). This proof can be carried out in second-order arithmetic
.
and Leo Harrington
showed that the strengthened finite Ramsey theorem is unprovable in Peano arithmetic by showing that (in Peano arithmetic) it implies the consistency of Peano arithmetic. Since Peano arithmetic cannot prove its own consistency by Gödel's theorem, this shows that Peano arithmetic cannot prove the strengthened finite Ramsey theorem.
The smallest number N that satisfies the strengthened finite Ramsey theorem is a computable function of n, m, k, but grows extremely fast. In particular it is not primitive recursive, but it is also far larger than standard examples of non primitive recursive functions such as the Ackermann function
. Its growth is so large that Peano arithmetic cannot prove it is defined everywhere, although Peano arithmetic easily proves that the Ackermann function is well defined.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
is true, but not provable in Peano arithmetic. This was the first "natural" example of a true statement about the integers that could be stated in the language of arithmetic, but not proved in Peano arithmetic; it was already known that such statements existed by Gödel's first incompleteness theorem.
The strengthened finite Ramsey theorem
The strengthened finite Ramsey theorem is a statement about colorings and natural numbers. (It should not be confused with the Paris–Harrington theorem, which is a statement about the strengthened finite Ramsey theorem, namely, that the strengthened Ramsey theorem is not provable in Peano arithmetic.) This theorem states that:- For any positive integers n, k, m we can find N with the following property: if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y.
Without the condition that the number of elements of Y is at least the smallest element of Y, this is a corollary the statement of the finite Ramsey theorem
Ramsey's theorem
In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
in
, with N given by:Moreover the strengthened finite Ramsey theorem can be deduced from the infinite Ramsey theorem in almost exactly the same way that the finite Ramsey theorem can be deduced from it, using a compactness argument (see the article on Ramsey's theorem
Ramsey's theorem
In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
for details). This proof can be carried out in second-order arithmetic
Second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. It was introduced by David Hilbert and Paul Bernays in their...
.
The Paris–Harrington theorem
Roughly speaking, Jeff ParisJeff Paris
Jeffrey Bruce Paris is a British mathematician known for his work on mathematical logic, in particular provability in arithmetic, uncertain reasoning and inductive logic with an emphasis on rationality and common sense principles....
and Leo Harrington
Leo Harrington
Leo Anthony Harrington is a professor of mathematics at the University of California, Berkeley who works inrecursion theory, model theory, and set theory.* Harrington and Jeff Paris proved the Paris–Harrington theorem....
showed that the strengthened finite Ramsey theorem is unprovable in Peano arithmetic by showing that (in Peano arithmetic) it implies the consistency of Peano arithmetic. Since Peano arithmetic cannot prove its own consistency by Gödel's theorem, this shows that Peano arithmetic cannot prove the strengthened finite Ramsey theorem.
The smallest number N that satisfies the strengthened finite Ramsey theorem is a computable function of n, m, k, but grows extremely fast. In particular it is not primitive recursive, but it is also far larger than standard examples of non primitive recursive functions such as the Ackermann function
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
. Its growth is so large that Peano arithmetic cannot prove it is defined everywhere, although Peano arithmetic easily proves that the Ackermann function is well defined.
External links
- A brief introduction to unprovability (contains a proof of the Paris-Harrington theorem) by Andrey Bovykin.