Ciąg Goodsteina potrafi rosnąć niewyobrażalnie długo, zawsze spada do zera — ale arytmetyka Peana nie potrafi udowodnić tego ogólnego faktu
W ciągu Goodsteina liczbę zapisuje się w dziedzicznej postaci potęgowej w pewnej podstawie, zwiększa podstawę o 1, a następnie odejmuje 1. Początkowo wartości mogą eksplodować do gigantycznych rozmiarów. Mimo to twierdzenie Goodsteina mówi, że każdy taki ciąg ostatecznie osiąga zero. Kirby i Paris wykazali, że tego uniwersalnego stwierdzenia nie można udowodnić w arytmetyce Peana, jeśli PA jest spójna. Twierdzenie jest jednak dowodliwe w silniejszych systemach, wykorzystując porządek liczb porządkowych poniżej ε₀.
Reguła wygląda jak przepis na wzrost
Zaczynamy od liczby zapisanej w podstawie b, przy czym również wykładniki zapisujemy rekurencyjnie w tej podstawie. Następnie wszędzie zastępujemy b przez b+1 i odejmujemy 1. Zwiększenie podstawy może spowodować gigantyczny skok wartości, więc początkowe wyrazy sekwencji często gwałtownie rosną zamiast maleć.
Dlaczego mimo tego wszystko kończy się zerem
Dowód przypisuje każdemu wyrazowi odpowiednią liczbę porządkową, zastępując rosnącą podstawę symbolem ω. Chociaż zwykłe wartości całkowite mogą rosnąć, odpowiadające im liczby porządkowe ściśle maleją. Nie istnieje nieskończony ściśle malejący ciąg ordynałów poniżej ε₀, więc proces musi się zakończyć.
Gdzie pojawia się granica arytmetyki Peana
Siła indukcji potrzebna do pełnego uzasadnienia porządku aż do ε₀ przekracza to, co arytmetyka Peana potrafi udowodnić o własnych procesach. Kirby i Paris wykazali, że ogólne twierdzenie Goodsteina jest niezależne od PA przy standardowym założeniu jej spójności. To naturalny przykład niezupełności, nie specjalnie skonstruowane zdanie mówiące o dowodach.
Prawdziwe dla zwykłych liczb, niedowodliwe w danym systemie
Każdy konkretny skończony przypadek można w zasadzie potwierdzić, a twierdzenie o wszystkich początkach jest prawdziwe w standardowych liczbach naturalnych. Niedowodliwość dotyczy PA jako systemu aksjomatów. Silniejsza teoria mnogości może formalizować argument z liczbami porządkowymi i dowieść zakończenia wszystkich ciągów.
Jaki rodzaj granicy tu widzimy?
Ten przykład warto czytać bardzo precyzyjnie. W matematyce „nie ma rozwiązania” może oznaczać kilka zupełnie różnych sytuacji: problem może być nadal otwarty, może istnieć dowód niemożliwości przy zadanych regułach, może nie istnieć uniwersalny algorytm, albo dane zdanie może być niezależne od wybranego systemu aksjomatów. Te przypadki nie są zamienne. Siła matematycznego wyniku bierze się właśnie z dokładnego określenia warunków: dowód nie mówi ogólnie, że „człowiek tego nie potrafi”, lecz wskazuje, czego nie można uzyskać przy konkretnych założeniach. To odróżnia granicę matematycznej wiedzy od zwykłego braku pomysłu.
Dlaczego naturalne przykłady były ważnym krokiem po Gödelu
Oryginalne konstrukcje Gödla są genialne, ale powstają specjalnie po to, aby formalny system mówił o własnej dowodliwości. Późniejsi logicy chcieli wiedzieć, czy niezupełność pojawia się również w matematyce, którą badano by niezależnie od logiki formalnej. Goodstein i Paris–Harrington pokazują, że tak: granica PA ujawnia się w prostych procesach liczbowych i skończonej kombinatoryce, których treść nie wspomina o dowodach ani aksjomatach.
Siłę teorii można mierzyć przez to, jakie procesy potrafi uzasadnić
Systemy formalne różnią się nie tylko listą twierdzeń, lecz również siłą zasad indukcji i dobrze ufundowanych porządków, których mogą użyć. Gdy proces wymaga argumentu wykraczającego poza tę siłę, zdanie może być prawdziwe, ale niedowodliwe w słabszej teorii. Dzięki temu niezależność przestaje być abstrakcyjną ciekawostką: można ją zobaczyć jako granicę kontroli nad bardzo szybko rosnącymi funkcjami, malejącymi ordynałami albo ekstremalnymi liczbami kombinatorycznymi. Co szczególnie ważne, treść takich twierdzeń można sformułować bez odwoływania się do maszyn Turinga czy kodów dowodów. Dopiero analiza metamatematyczna ujawnia, że do ich uzasadnienia potrzeba silniejszych zasad. Dzięki temu widać, że niezupełność nie jest marginesem logiki, lecz realnie przecina zwykłą matematykę skończonych liczb i struktur.