Twierdzenie Gödla

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Twierdzenie Gödla to jeden z najbardziej znanych rezultatów logiki matematycznej. W istocie znane są dwa różne twierdzenia Gödla: pierwsze z nich to twierdzenie o niezupełności, drugie zaś to jego wniosek nazywany też twierdzeniem o niedowodliwości niesprzeczności. Oba twierdzenia zostały udowodnione w 1931 roku przez austriackiego matematyka i logika Kurta Gödla. Uważa się również, że twierdzenia te dają negatywną odpowiedź na drugi problem Hilberta, i w ten sposób mają spore znaczenie w filozofii matematyki. Oprócz rozpatrywanych w tym artykule twierdzeń, Gödel udowodnił też twierdzenie o istnieniu modelu i twierdzenie o nierozstrzygalności (patrz: teoria, struktura matematyczna).

Kontekst[edytuj | edytuj kod]

Twierdzenie Gödla było odpowiedzią na próbę przedstawienia wszystkich aksjomatów i twierdzeń matematycznych w postaci czysto symbolicznej (syntaktycznej), tzn. bez odwoływania się do ich znaczenia (czyli w oderwaniu od semantyki; por. logicyzm, formalizm). Próby takiej podjął się m.in. David Hilbert.

Język – zbiór termów (zdań) tworzonych według pewnych reguł.

Teoria matematyczna nad pewnym językiem – przyporządkowanie zdaniom w określonym języku własności prawdy lub fałszu. Teoria nadaje językowi znaczenie i opisuje pewną matematyczną rzeczywistość. Teoria pozwala odpowiedzieć, czy dane zdanie jest prawdziwe.

System formalny – zbiór aksjomatów (zdań) wraz z regułami wnioskowania (algorytmem), generujący pewien podzbiór zdań języka. System formalny jest "przybliżeniem" teorii matematycznej. Pozwala odpowiedzieć, czy dane zdanie jest dowodliwe. Dla jednej teorii może istnieć wiele różnych systemów formalnych (aksjomatyzacji), przybliżających ją lepiej lub gorzej. Jeżeli zdanie jest dowodliwe, to musi być ono prawdziwe (ale niekoniecznie na odwrót).

System formalny niesprzeczny – system, w którym nie da się udowodnić jednocześnie pewnego zdania i jego zaprzeczenia.

System formalny zupełny – system, w którym możliwe jest przeprowadzenie dowodu dowolnego prawidłowo zapisanego zdania tego systemu lub jego zaprzeczenia. W systemie zupełnym każde prawdziwe zdanie jest dowodliwe.

System formalny pierwszego rzędu – system, w którym użyto wyłącznie standardowych reguł wnioskowania oraz wszystkie jego aksjomaty są wyrażone w logice pierwszego rzędu, czyli nie dopuszcza się kwantyfikatorów po zmiennych przebiegających zbiory.

System formalny rozstrzygalny (efektywny) – taki system, którego algorytm wnioskowania da się zaprogramować na maszynie Turinga. Żeby system był rozstrzygalny, potrzeba i wystarcza, żeby istniała tylko jedna (ale odpowiednia) reguła wnioskowania (najczęściej przyjmuje się modus ponens) oraz żeby jego zbiór aksjomatów dał się wygenerować przy pomocy maszyny Turinga.

Aksjomatyka Peano – pewien system formalny pierwszego rzędu, opisujący liczby naturalne.

Twierdzenia[edytuj | edytuj kod]

Pierwsze, o niezupełności[edytuj | edytuj kod]

Każdy niesprzeczny rozstrzygalny system formalny pierwszego rzędu, zawierający w sobie aksjomaty Peano, musi być niezupełny.

Oznacza to, że żaden system formalny pierwszego rzędu nigdy nie "pokryje" w całości zbioru wszystkich twierdzeń arytmetyki. Nie oznacza to, że zbiór wszystkich twierdzeń arytmetyki nie istnieje, a jedynie, że nie może on być wygenerowany przez żaden system formalny. Inaczej mówiąc, dowodliwość jest zawsze słabsza od prawdziwości – zbiór zdań generowanych (dowodzonych) przez system formalny nigdy nie będzie równy ze zbiorem zdań prawdziwych teorii. Może on być albo mniejszy od zbioru zdań prawdziwych (system niesprzeczny, ale niezupełny), albo większy od niego (system zupełny ale sprzeczny).

Twierdzenie Gödla zachodzi także dla każdej teorii silniejszej od arytmetyki Peano (zawierającej w sobie tę arytmetykę). Oryginalne twierdzenie nic nie mówi o teoriach słabszych od arytmetyki, ale odkryto już słabsze teorie, które wystarczają do zachodzenia podobnych twierdzeń.

Można rozszerzyć definicję systemów formalnych tak, że twierdzenie Gödla nie będzie dla nich zachodzić. Jednak takie niestandardowe systemy nigdy nie będą rozstrzygalne, tzn. ich algorytm wnioskowania nie dałby się zaprogramować na maszynie Turinga lub ich zbiór aksjomatów nie dałby się taką maszyną wygenerować. Ponieważ każdy zbiór skończony jest rozstrzygalny, dlatego twierdzenie Gödla mówi, że nie istnieje żadna zupełna niesprzeczna, skończona aksjomatyzacja arytmetyki, ani nawet taka nieskończona, która da się wygenerować ze skończonej.

Drugie, o niedowodliwości niesprzeczności[edytuj | edytuj kod]

To twierdzenie jest konsekwencją poprzedniego. Głosi ono, iż w ramach tego systemu nie da się dowieść niesprzeczności żadnego systemu formalnego, zawierającego arytmetykę liczb naturalnych. Aby taki dowód przeprowadzić, niezbędny jest system wyższego rzędu, którego niesprzeczności w ramach niego samego również nie da się dowieść – i tak ad infinitum.

Zarys dowodu[edytuj | edytuj kod]

Gödel przyporządkował jednoznacznie każdemu predykatowi arytmetyki pewną liczbę. Ważną częścią dowodu twierdzenia jest sam fakt, że takie przyporządkowanie istnieje.

Każdej funkcji zdaniowej arytmetyki odpowiada więc pewna unikalna liczba. Oznaczmy to przyporządkowanie przez G:

G(\phi) = n

Istnieją także specjalne funkcje liczbowe, które pozwalają obliczać wartość G dla formuł złożonych. Przykładowo:

G(\phi \and \psi) = F(G(\phi), G(\psi))

Istnieje w końcu specjalny operator \square, który dla każdego zdania pozwala odpowiedzieć, czy zdanie to jest dowodliwe. Wyrażenie to samo w sobie jest zdaniem.

\square \chi - wtedy i tylko wtedy, kiedy istnieje dowód zdania \chi

Każda formuła ma wobec tego jakiś numer. Można odwrócić przyporządkowanie G i mówić o formule o numerze n: \Phi_{n}(x, y, z, ...). Przyporządkowanie G nie musiało być surjekcją, dlatego nie wszystkie wartości \Phi_{n}(x, y, z, ...) są sensowne, ale nie bierzemy ich pod uwagę.

W dalszym ciągu będą nas interesować wyłącznie predykaty jednoargumentowe. Oznaczmy listę wszystkich takich predykatów jako \Psi_{n}(x).

Rozważmy teraz wyrażenie "zdanie o numerze n zastosowane na argumencie n nie posiada dowodu":

D(n) \Leftrightarrow \lnot \square \Psi_{n}(n)

Powstał pewien jednoargumentowy predykat. Każdy taki predykat ma swój numer w przyporządkowaniu G. Oznaczmy ten numer przez d.

d = G(D)

czyli

\Psi_{d}(n) \Leftrightarrow D(n)

Rozważmy teraz właśnie ten predykat zastosowany na liczbie d: D(d). Z definicji powyżej mamy:

D(d) \Leftrightarrow \lnot \square \Psi_{d}(d)

czyli

D(d) \Leftrightarrow \lnot \square D(d)

Zdanie D(d) jest zwane zdaniem Gödla i jest równoważne stwierdzeniu, że ono samo nie posiada dowodu. Czy zdanie to jest prawdziwe, czy fałszywe? Jeżeli jest prawdziwe, to prawdą jest także, że nie posiada ono dowodu, co oznacza, że nasz system formalny jest niezupełny. Jeżeli jest fałszywe, to istnieje jego dowód, co oznacza, że system formalny jest sprzeczny.

Zatem systemy formalne spełniające pewne założenia zawsze muszą być albo zupełne albo niesprzeczne i nigdy nie posiadają obu tych własności jednocześnie.

Wnioski[edytuj | edytuj kod]

Obydwa twierdzenia Gödla można uogólnić na dowolne systemy formalne zawierające skończoną lub rekurencyjnie przeliczalną liczbę aksjomatów. Warunkiem jest, aby w skład takiego systemu wchodziła arytmetyka liczb naturalnych lub zawierał on skończoną liczbę aksjomatów umożliwiającą przeprowadzenie tzw. arytmetyzacji twierdzeń.

Można oznaczyć G0=Pk(k) i dodać to zdanie do aksjomatów systemu. Wtedy również będzie istniało zdanie G1 niezależne od poszerzonych aksjomatów. W ten sposób można dodać G2, G3..., a nawet Gω, Gω+1, Gω+2..., Gω2, Gω2+1..., Gω3, Gω4... i Gω²[1].

Przypadki, dla których twierdzenie nie zachodzi[edytuj | edytuj kod]

  • Twierdzenie Gödla nie zachodzi dla słabych teorii, gdzie niemożliwe jest zdefiniowanie przekształcenia z predykatów w liczby (arytmetyzacja twierdzeń). Dla takich teorii możliwe jest skonstruowanie systemu formalnego zupełnego i niesprzecznego.
  • Twierdzenie Gödla nie zachodzi dla różnych niestandardowych systemów formalnych. Stwierdzenie "istnieje dowód zdania teorii X" nie daje się wtedy zakodować jako zdanie tej teorii (wykracza poza nią).
  • Twierdzenia Gödla stosują się tylko do efektywnie generowanych (czyli rekurencyjnie przeliczalnych) teorii. Jeśli wszystkie prawdziwe stwierdzenia o liczbach naturalnych wziąć jako aksjomaty pewnej teorii, to ta teoria jest niesprzecznym i zupełnym rozszerzeniem arytmetyki Peano (nazywaną true arithmetic – „prawdziwą arytmetyką”), dla którego żadne z twierdzeń Gödla nie stosuje się w znaczący sposób, ponieważ ta teoria nie jest rekurencyjnie przeliczalna.

Błędne interpretacje[edytuj | edytuj kod]

Potoczne rozumienie twierdzeń Gödla prowadzi zwykle do nieprawidłowych wniosków, np.:

  • nie wiadomo, co jest prawdą,
  • każdy system rozumowania jest sprzeczny albo niezupełny.

Warto także pamiętać, że dowód pierwszego twierdzenia Gödla polega na skonstruowaniu explicite zdania prawdziwego, którego nie da się dowieść w arytmetyce liczb naturalnych. Wyraźnie więc odróżnia się tu prawdziwość zdania od możliwości samego jego dowodzenia.

W codziennym życiu zwykle nie mamy do czynienia z systemami formalnymi, a co ważniejsze: kryteria prawdy nie są oparte wyłącznie na rachunku predykatów i innych formach logicznego rachunku zdań.

Istnieją również alternatywne formy twierdzeń Gödla posługujące się pojęciami m.in. z zakresu tak zwanych zbiorów rekurencyjnych.

Przypisy

  1. Roger Penrose, Nowy umysł cesarza, ISBN 83-01-11819-9, str. 127-132