To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Paris–Harrington theorem

From Wikipedia, the free encyclopedia

In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system. The combinatorial principle is, however, provable in slightly stronger systems.

This result 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.

YouTube Encyclopedic

  • 1/3
    Views:
    174 696
    369 481
    1 758 773
  • How Infinity Explains the Finite | Infinite Series
  • Friends and Strangers Theorem - Numberphile
  • Gödel's Incompleteness Theorem - Numberphile

Transcription

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 = {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 (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 combinatorial principle can be proven assuming induction up to for a relevant classes of formulas. Alternatively, it can be proven assuming the reflection principle, for the arithmetic theory, for -sentences. The reflection principle also implies the consistency of Peano arithmetic. It is provable in second-order arithmetic (or the far stronger Zermelo–Fraenkel set theory) and so is true in the standard model.

The smallest number N that satisfies the strengthened finite Ramsey theorem is then a computable function of n, m, k, but grows extremely fast. In particular it is not primitive recursive, but it is also far faster-growing than standard examples of non-primitive recursive functions such as the Ackermann function. It dominates every computable function provably total in Peano arithmetic,[1] which includes functions such as the Ackermann function.

See also

References

  1. ^ Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". The Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985.

External links

This page was last edited on 23 March 2024, at 23:46
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.