| Paris-harrington Theorem |
Website Links For Theorem |
Information AboutParis-harrington Theorem |
| CATEGORIES ABOUT PARIS–HARRINGTON THEOREM | |
| independence results | |
| paris-harrington theorem | |
| mathematical theorems | |
|
THE PARIS–HARRINGTON PRINCIPLE The Paris–Harrington principle is a statement that is not provable in Peano arithmetic. (It should not be confused with the Paris–Harrington theorem, which states that the Paris–Harrington principle is not provable in Peano arithmetic.) This principle states that:
Without the condition that the number of elements of ''Y'' is at least the smallest element of ''Y'', this is exactly the statement of the Finite Ramsey Theorem . Moreover the Paris–Harrington principle 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 Roughly speaking, Paris and Harrington showed that the Paris–Harrington principle 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 Godel's theorem, this shows that Peano arithmetic cannot prove the Paris–Harrington principle. The smallest number ''l'' that satisfies the Paris–Harrington principle 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
|
|
|