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 Peano. 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\geq n$ i dowolnego pokolorowania podzbiorów $r$-elementowych zbioru $m$-elementowego $t$ kolorami $C:{\mathcal {P}}_{r}(\{1,\ldots ,m\})\rightarrow \{1,\ldots ,t\}$ istnieje zbiór $Y\subseteq {1,\ldots ,m}$, taki że $\min Y\leq |Y|$,$k\leq |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\leq |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. ananlogiczne 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 Peano 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.