“Paris–Harrington theorem”的意思、由来-开放百科全书

词条

Paris–Harrington theorem

释义

Strengthened finite Ramsey theorem
Paris–Harrington theorem
See also
References
External links

In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, 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.

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 one 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 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.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic.

Paris–Harrington theorem

Roughly speaking, Jeff Paris and Leo Harrington (1972) 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 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.

References

{{cite book |first=David |last=Marker |title=Model Theory: An Introduction |location=New York |publisher=Springer |year=2002 |isbn=0-387-98760-6 }}
mathworld entry
{{cite book |last=Paris |first=J. |authorlink2=Leo Harrington |last2=Harrington |first2=L. |chapter=A Mathematical Incompleteness in Peano Arithmetic |title=Handbook of Mathematical Logic |editor-first=J. |editor-last=Barwise |editor-link=Jon Barwise |location=Amsterdam, Netherlands |publisher=North-Holland |year=1977 }}

External links

[https://www.cs.umd.edu/~gasarch/TOPICS/largeramsey/bovINTRO.pdf A brief introduction to unprovability] (contains a proof of the Paris–Harrington theorem) by [https://web.archive.org/web/20110807192747/http://www.maths.bris.ac.uk/~maaib/ Andrey Bovykin]

2 : Independence results|Theorems in the foundations of mathematics

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Strengthened finite Ramsey theorem

Paris–Harrington theorem

See also

References

External links