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 ∈ N {\displaystyle k,r,t\in \mathbb {N} } istnieje liczba n {\displaystyle n} o tej własności, że dla dowolnego m ⩾ n {\displaystyle m\geqslant n} i dowolnego pokolorowania podzbiorów r {\displaystyle r} -elementowych zbioru m {\displaystyle m} -elementowego t {\displaystyle t} kolorami C : P r ( { 1 , … , m } ) → { 1 , … , t } {\displaystyle C\colon {\mathcal {P}}_{r}(\{1,\dots ,m\})\to \{1,\dots ,t\}} istnieje zbiór Y ⊆ 1 , … , m , {\displaystyle Y\subseteq {1,\dots ,m},} taki że min Y ⩽ | Y | ,   k ⩽ | Y | {\displaystyle \min Y\leqslant |Y|,\ k\leqslant |Y|} oraz wszystkie r {\displaystyle r} -elementowe podzbiory zbioru Y {\displaystyle 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 {\displaystyle r} może być udowodnione w logice pierwszego rzędu, jednak dowody dla różnych r {\displaystyle r} są różne i nie mogą być złożone w jeden wspólny dowód dla wszystkich r . {\displaystyle r.} Bez warunku min Y ⩽ | Y | {\displaystyle \min Y\leqslant |Y|} jest to wniosek ze skończonego twierdzenia Ramseya.

H ( k , r , t ) {\displaystyle H(k,r,t)}

Niech H ( k , r , t ) {\displaystyle H(k,r,t)} oznacza najmniejszą z liczb n , {\displaystyle n,} o której mowa w tezie twierdzenia. Jest to funkcja obliczalna, ale liczby H ( k , r , t ) {\displaystyle 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 ) {\displaystyle 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 ) {\displaystyle 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.