Paris-Harrington Theorem
المؤلف:
Borwein, J. and Bailey, D
المصدر:
Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.
الجزء والصفحة:
...
18-1-2022
1660
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.
الاكثر قراءة في المنطق
اخر الاخبار
اخبار العتبة العباسية المقدسة
