World Library  
Flag as Inappropriate
Email this Article

Paris-Harrington theorem

Article Id: WHEBN0003877866
Reproduction Date:

Title: Paris-Harrington theorem  
Author: World Heritage Encyclopedia
Language: English
Subject: Gödel's incompleteness theorems, Ramsey theory, Second-order arithmetic, Nqthm
Publisher: World Heritage Encyclopedia

Paris-Harrington theorem

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.

The 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 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 of the finite Ramsey theorem in K_{\mathcal{P}_n(S)}, with N given by:

\binom{N}{n} = |\mathcal{P}_n(S)| \ge R(\underbrace{ m, m, \ldots , m }_{k}).

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.

The Paris–Harrington theorem

Roughly speaking, Jeff Paris 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 itself. 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.

See also


  • David Marker, Model Theory: An Introduction, ISBN 0-387-98760-6
  • mathworld entry
  • Paris, J. and Harrington, L. A Mathematical Incompleteness in Peano Arithmetic. In Handbook for Mathematical Logic (Ed. J. Barwise). Amsterdam, Netherlands: North-Holland, 1977.

External links

  • Andrey Bovykin.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.