Twierdzenie Parisa-Harringtona

Twierdzenie Parisa-Harringtona – twierdzenie logiki matematycznej udowodnione przez Jeffa Parisa i Leo Harringtona podające pierwszy naturalny przykład prawdziwego twierdzenia, które nie może być wykazane w arytmetyce Peana. Istnienie takich zdań wynika z twierdzenia Gödla o niezupełności. Przykład jest wzmocnieniem twierdzenia Ramseya.

Wzmocnienie twierdzenia Ramseya

Dla dowolnych $k,r,t\in \mathbb {N}$ istnieje liczba $n$ o tej własności, że dla dowolnego $m\geqslant n$ i dowolnego pokolorowania podzbiorów $r$-elementowych zbioru $m$-elementowego $t$ kolorami $C\colon {\mathcal {P}}_{r}(\{1,\dots ,m\})\to \{1,\dots ,t\}$ istnieje zbiór $Y\subseteq {1,\dots ,m},$ taki że $\min Y\leqslant |Y|,\ k\leqslant |Y|$ oraz wszystkie $r$-elementowe podzbiory zbioru $Y$ są tego samego koloru.

Dowód twierdzenia korzysta z nieskończonej wersji twierdzenia Ramseya i nie może być ono udowodnione bez korzystania z logiki drugiego rzędu. Dla ustalonych wartości $r$ może być udowodnione w logice pierwszego rzędu, jednak dowody dla różnych $r$ są różne i nie mogą być złożone w jeden wspólny dowód dla wszystkich $r.$ Bez warunku $\min Y\leqslant |Y|$ jest to wniosek ze skończonego twierdzenia Ramseya.

$H(k,r,t)$

Niech $H(k,r,t)$ oznacza najmniejszą z liczb $n,$ o której mowa w tezie twierdzenia. Jest to funkcja obliczalna, ale liczby $H(k,r,t)$ rosną nieporównanie szybciej ze wzrostem argumentów niż np. analogiczne liczby Ramseya. Funkcja $f(n)=H(n+1,n,n)$ rośnie zbyt szybko by mogła być zdefiniowana za pomocą dodawania, mnożenia i indukcji. W arytmetyce Peana nie można wykazać, że $H(k,r,t)$ jest poprawnie zdefiniowana dla wszystkich argumentów.

Bibliografia

• J. Paris, L. Harrington, A Mathematical Incompleteness in Peano Arithmetic, w: Handbook for Mathematical Logic (ed. J. Barwise). Amsterdam, Netherlands: North-Holland, 1976.
• W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.