Paris-Harrington Theorem

The Paris-Harrington theorem is a strengthening of the finite Ramsey's theorem by requiring that the homogeneous set be large enough so that . Clearly, the statement can be expressed in the first-order language of arithmetic. It is easily provable in the second-order arithmetic, but is unprovable in first-order Peano arithmetic (Paris and Harrington 1977; Borwein and Bailey 2003, p. 34).

The original unprovability proof by Paris and Harrington used a model-theoretic argument. In any model , the Paris-Harrington principle in its nonstandard instances allows construction of an initial segment which is a model of Peano arithmetic. It also follows that the function  such that for any colouring of -tuples of  into  colors there is a subset  of  of size  which is relatively large and such that  eventually dominates every function provably recursive in Peano arithmetic.

Later, another approach to proving unprovability of the theorem using ordinals was introduced by J. Ketonen and R. Solovay.

REFERENCES

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.

Bovykin, A. "Arithmetical Independence results. Short Online Tutorial." http://www.csc.liv.ac.uk/~andrey/tutorial.html.Paris, J. and Harrington, L. "A Mathematical Incompleteness in Peano Arithmetic." In Handbook for Mathematical Logic (Ed. J. Barwise). Amsterdam, Netherlands: North-Holland, 1977.