Twierdzenie Parisa-Harringtona

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

Dla dowolnych istnieje liczba o tej własności, że dla dowolnego i dowolnego pokolorowania podzbiorów -elementowych zbioru -elementowego kolorami istnieje zbiór , taki że , oraz wszystkie -elementowe podzbiory zbioru 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 może być udowodnione w logice pierwszego rzędu, jednak dowody dla różnych są różne i nie mogą być złożone w jeden wspólny dowód dla wszystkich . Bez warunku jest to wniosek ze skończonego twierdzenia Ramseya.

[edytuj | edytuj kod]

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

Bibliografia[edytuj | edytuj kod]

  • 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.