In
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, the Paris–Harrington theorem states that a certain
combinatorial principle In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.
The rule of sum, rule of product, and inclusion–exclusion principle are often used for enumerative purposes. Bij ...
in
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
, namely the strengthened finite Ramsey theorem, is true, but not provable in
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
. This has been described by some (such as the editor of the ''Handbook of Mathematical Logic'' in the references below) as 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.
Strengthened finite Ramsey theorem
The strengthened finite Ramsey theorem is a statement about colorings and natural numbers and states that:
: For any positive integers ''n'', ''k'', ''m'', such that ''m ≥ n'', one can find ''N'' with the following property: if we color each of the ''n''-element subsets of ''S'' = 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 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
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
for details). This proof can be carried out in
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.
A precurs ...
.
The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
.
Paris–Harrington theorem
Roughly speaking,
Jeff Paris and
Leo Harrington
Leo Anthony Harrington (born May 17, 1946) is a professor of mathematics at the University of California, Berkeley who works in
recursion theory, model theory, and set theory.
Having retired from being a Mathematician, Professor Leo Harrington is ...
(1977) 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 itself. Since Peano arithmetic cannot prove its own consistency by
Gödel's second incompleteness 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
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
of ''n'', ''m'', ''k'', but grows extremely fast. In particular it is not
primitive recursive
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
, but it is also far larger than standard examples of non-primitive recursive functions such as the
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. All primitive recursive functions are total ...
. 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.
See also
*
Goodstein's theorem
In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every ''Goodstein sequence'' eventually terminates at 0. Kirby and Paris showed that it is unprovable in Pea ...
*
Kanamori–McAloon theorem In mathematical logic, the Kanamori–McAloon theorem, due to , gives an example of an incompleteness in Peano arithmetic, similar to that of the Paris–Harrington theorem. They showed that a certain finitistic theorem in Ramsey theory is not prova ...
*
Kruskal's tree theorem
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.
History
The theorem was conjectured by Andrew Vázsonyi and proved by ...
References
*
mathworld entry*
External links
''A brief introduction to unprovability''(contains a proof of the Paris–Harrington theorem) b
Andrey Bovykin
{{DEFAULTSORT:Paris-Harrington Theorem
Independence results
Theorems in the foundations of mathematics