Szkic Dowodu Twierdzenia Gödla

WSTĘP

[Praca ta jest prawie dokładnie odtworzonym pierwszym rozdziałem Gödel’s Incompletness Theorems Raymonda Smullyana, podane są tu ogólne założenia dla rozważanych twierdzeń i dowody niezupełności bez wyspecyfikowania dane go języka. W szczególności, nie pokazałem, jak wyrazić (P~)* w językach które rozważamy (a zrobił to Gödel w swojej słynnej pracy z 1931 roku. Jednakże, ostatnie twierdzenie tekstu jest udowodnione, więc można powiedzieć, że po przeczytaniu rozumiemy argument Gödla. W dalszych częściach przedstawię szczegółowy dowód dla danego języka (Arytmetyki Peano z Potęgowaniem), będący jednocześnie najprostszym znanym dowodem niezupełności.
Autor: lion137]

1. Ogólne formy Twierdzeń Gödla i Tarskiego

Języki do których ma zastosowanie Twierdzenie Gödla muszą zawierać co najmniej:
1. Przeliczalny zbiór ℰ, którego elementy nazywamy wyrażeniami.
2. Podzbiór 𝓢 zbioru ℰ którego elementy nazywamy zdaniami języka 𝓛.
3. Podzbiór 𝓟 zbioru 𝓢, którego elementy to zdania dowodliwe w 𝓛.
4. Podzbiór 𝓡 zdań , którego elementy nazywa się zdaniami niedowodliwymi.
5. Zbiór 𝓗 wyrażeń, którego elementy nazywamy predykatami [Gödel we wstępie do swej pracy nazywa je nazwami klas (class names), można pomyśleć o każdym predykacie 𝓗, jako o nazwie pewnego zbioru liczb naturalnych].
6. Funkcja 𝜱, która przyporządkowuje każdemu wyrażeniu E, i każdej liczbie naturalnej n wyrażenie E(n). Funkcja ta jest potrzebna, aby spełnić warunek, że dla każdego predykatu H i dla każdej liczby naturalnej n, wyrażenie H(n) jest zdaniem. [Nieformalnie, zdanie H(n) stwierdza, że liczba n należy do zbioru nazywanego przez H.]
W pierwszym dowodzie niezupełności, jaki podamy dla danego systemu 𝓛, użyjemy podstawowego pojęcia, które precyzyjnym uczynił Alfred Tarski [1936], tj., pojęcia zdania prawdziwego (zdefiniowanego nieco inaczej niż dowodliwość w systemie).
7. Zbiór 𝓣, zdań, którego elementy nazywa się zdaniami prawdziwymi języka𝓛.

Wyrażalność dla 𝓛. Przy definiowaniu wyrażalności w języku bierzemy pod uwagę zbiór zdań prawdziwych, ale nie rozważamy zbiorów 𝓟, ani 𝓡.
Słowo liczba będzie znaczyć, w dalszej części tekstu liczba naturalna. Powiemy, że predykat H jest prawdziwy dla liczby n lub, że n spełnia H, jeśli H(n) jest zdaniem prawdziwym (tj., elementem 𝓣). Przez set wyrażany przez H, rozumiemy zbiór wszystkich n spełniających H. Stąd, dla każdego zbioru liczbowego A, H wyraża ten zbiór, wtedy i tylko wtedy gdy, dla każdej liczby n:

H(n) ϵ 𝓣 ↔ n ϵA.

Definicja. Zbiór A nazywamy wyrażalnymi lub nazywalnym w 𝓛 jeśli A jest wyrażane przez jakiś predykat w 𝓛.
Ponieważ w 𝓛 jest przeliczalnie wiele wyrażeń, dlatego też jest tylko przeliczalnie wiele predykatów. Ale z dobrze nam znanego twierdzenia Cantora, mamy nieprzeliczalnie wiele zbiorów liczb naturalnych. Dlatego nie każdy zbiór liczb jest wyrażalny w 𝓛.

Definicja. System 𝓛 nazywamy poprawnym, jeśli każde dowodliwe zdanie jest prawdziwe, a każde niedowodliwe jest fałszywe (nie prawdziwe). To znaczy, że 𝓟 jest podzbiorem 𝓣 i 𝓡 jest rozdzielne z 𝓣. Chcemy teraz znaleźć wystarczające warunki na to, żeby 𝓛, przy założeniu, że jest poprawny, zawierał zdanie prawdziwe, ale niedowodliwe w 𝓛.

Numery Gödla i Diagonalizacja. Niech funkcja g będzie funkcją jedno - jednoznaczną, która każdemu wyrażeniu E przypisuje liczbę naturalną g(E) zwaną liczbą Gödla E. Funkcja ta będzie stała przez resztę rozdziału. Zakładając, że każda liczba naturalna jest numerem Gödla jakiegoś wyrażenia, niech E_n będzie wyrażeniem, którego numerem Gödla jest n. Stąd, g(E_n)= n.

Diagonalizacja. Przez Diagonalizację wyrażenia E_n rozumiemy wyrażnie E_n(n). Jeśli E_n jest predykatem to jego diagonalizacją jest oczywiście jakieś zdanie; zdanie to jest prawdziwe wtw(wtedy i tylko wtedy), jeśli predykat E_n jest spełniony przez swoją własną liczbę Gödla n.
Dla każdego n, d(n) będzie numerem Gödla E_n(n); nazywamy tę funkcję funkcja diagonalną
funkcją systemu.
Używamy terminu zbiór liczbowy (number-set) w znaczeniu zbioru liczb naturalnych. Dlakażdego zbioru liczbowego A, przez A* będziemy rozumieć zbiór wszystkich takich liczb n, że d(n) ϵ A. Stąd dla każdego n równoważność
n ϵA* ↔ d(n) ϵ A
zachodzi z definicji A*.

Ogólna Forma Twierdzenia Gödla. Niech 𝓟 będzie zbiorem liczb Gödla wszystkich dowodliwych zdań. Dla każdego zbioru liczbowego A, przez jego dopełnienie A~ nazywamy dopełnienie A względem zbioru N liczb naturalnych - t.j.,A~ jest zbiorem liczb naturalnych, które nie są w A.

Twierdzenie (GT) - Gödla, z punktu widzenia Tarskiego. Jeśli zbiór (P~)* jest wyrażalny w 𝓛 i 𝓛 jest poprawny, to istnieje w 𝓛 zdanie prawdziwe, ale nie będące tezą 𝓛.
Dowód. Złóżmy, że 𝓛 jest poprawny i (P~)* jest wyrażalny w 𝓛. Niech H będzie predykatem wyrażającym (P~)* w 𝓛, i niech h będzie numerem Gödla H. Niech G będzie diagonalizacją H (tj., zdaniem H(h)). Pokażemy, żeG jest prawdziwe,ale nie dowodliwe w 𝓛.
Ponieważ H wyraża (P~)* w 𝓛, to dla każdej liczby n, H(n) jest prawdziwe ↔ n ϵ (P~)*. Ponieważ równoważność ta zachodzi dla każdego n, zachodzi też dla szczególnego n mianowicie dla n = h (i to jest część rozumowania zwana diagonalizacją), więc mamy równowazność:
H(h) jest prawdziwe ↔ h ϵ (P~)*.
Teraz,
h ϵ (P~)* ↔ d(h) ϵ P~ ↔ d(h) ∉ P.
Ale d(h) jest numerem Gödla H(h) (ponieważ h jest numerem Gödla H) i wiemy też, że d(h) ϵ P jest równoważne temu, iżH(h) jest dowodliwe w 𝓛 i d(h) ∉ P ↔ H(h) nie jest dowodliwe w 𝓛. I teraz mamy:
1. H(h) jest prawdziwe ↔ H(h) nie jest tezą 𝓛. To znaczy, że H(h) jest albo prawdziwe i niedowodliwe w 𝓛, albo fałszywe i dowodliwe w 𝓛. Druga możliwość przeczy założeniu, że 𝓛 jest poprawny. Stąd, musi być, że H(h) jest prawdziwe, ale nie dowodliwe w 𝓛.

Przy analizie konkretnych języków formalnych, należy pokazać, jak wyrazić (P~)* w 𝓛. Można to zrobić pokazując, że zachodzą następujące warunki:
G1 : Dla każdego zbioru A wyrażalnego w 𝓛, zbiór A* jest wyrażalny w 𝓛.
G2 : Dla każdego zbioru A wyrażalnego w 𝓛, zbiór A~ jest wyrażalny w 𝓛.
G3 : Zbiór 𝓟 jest wyrażalny w 𝓛.

Zdania Gödla. Nazwijmy zdanie En zdaniem Gödla dla zbioru liczbowego A, jeśli En jest prawdziwe, a jego numer Gödla leży w A; albo En jest fałszywe i jego numer Gödla leży poza A. Stąd, En jest zdaniem Gödla dla A wtedy i tylko wtedy gdy zachodzi:
En ϵ 𝓣 ↔ n ϵ A.

Lemat (D) - Diagonalny. (a) dla każdego zbioru A, jeśli A* jest wyrażalne w 𝓛, to istnieje zdanie Gödla dla A.
(b) Jeśli 𝓛 spełnia warunek G1, to dla każdego zbioru A wyrażalnego w 𝓛, jest zdanie Gödla dla A.
Dowód.
(a) Załóżmy, że H jest predykatem, który wyraża A* w 𝓛; niech h będzie jego numerem Gödla. Wtedy d(h) jest numerem Gödla H(h). Dla każdego n, H(n) jest prawdziwe ↔ n ϵ A*, z tego wynika, że H(h) jest prawdziwe ↔ h ϵ A*. Mamy też h ϵ A* ↔ d(h) ϵ A. Stąd wynika, że H(h) jest prawdziwe ↔
d(h) ϵ A, a ponieważ d(h) jest numerem Gödla H(h), to H(h) jest zdaniem Gödla dla A.
(b) Natychmiast wynika z (a).
Ogólna Forma Twierdzenia Tarskiego. Lemat D ma ważną konsekwencję: Niech T będzie zbiorem numerów Gödla zdań prawdziwych 𝓛. Wtedy zachodzą następujące twierdzenia.
Twierdzenie (T) ( Tarskiego).
1. Zbiór (T~)* nie jest nazywalny w 𝓛.
2. Jeżeli zachodzi G1, to zbiór T~ nie jest nazywalny w 𝓛.
3. Jeżeli jednocześnie zachodzą G1 i G2 , zbiór 𝓣 jest nienazywalny w 𝓛.

Uwagi.
1. Konkluzja (1) powyżej jest czasami cytowana jako: Dla dostatecznie silnych systemów, prawda nie jest definiowalna wewnątrz systemu. Fraza “ dostatecznie silna” była interpretowana na wiele sposobów. My chcieliyśmy podkreślić, że warunki G1 i G2 są “wystarczająco silne”.
2. Gödel (1931) powiązał swój dowód ze słynnym paradoksem Kreteńczyka, który mówi, że wszyscy Kreteńczycy to kłamcy. Analogia bliższa Twierdzeniu Gödla jest następująca: Wyobraźmy sobie kraj, którego każdy mieszkaniec albo zawsze mówi prawdę albo zasze kłamie. Niektórzy z mieszkańców to Ateńczycy, niektórzy to Kreteńczycy. Ateńczycy w tym kraju zawsze mówią prawdę a Kreteńczycy zawsze kłamią. Jakie zdanie musi wypowiedzieć mieszkaniec tego kraju aby przekonać nas, że mówi on prawdę, a nie jest Ateńczykiem?
Móglby on powiedzieć: “ Nie jestem Ateńczykiem” Kłamca nie może tego stwierdzić (ponieważ kłamca nie może być Ateńczykiem; tylko prawdomówni są Ateńczykami). Stąd też musi mówić prawdę. Skoro jego stwierdzenie jest prawdziwe, to znaczy, że nie może on być Ateńczykiem. Tak więc mówi an prawdę nie będąc Ateńczykiem.
Jeśli założymy, że Ateńczycy są zdaniami 𝓛, które są nie tylko prawdziwe, ale i dowodliwe w 𝓛, to każdy autochton, który twierdzi, że jest Ateńczykiem gra rolę zdania Gödla G, które obwieszcza swą własną niedowodliwość w 𝓛.

2. Zdania Nierozstrzygalne w 𝓛

Jak dotąd nie braliśmy pod uwagę zbioru 𝓡 zdań niedowodliwych. Teraz będą grały kluczową rolę.
𝓛 nazywamy niesprzecznym, jeśli żadne zdanie nie jest jednocześnie dowodliwe i niedowodliwe w 𝓛(tj., zbiory 𝓟 i 𝓡 są rozłączne) i sprzecznym w przeciwnym przypadku. Definicja niesprzeczności odnosi się tylko do zbiorów 𝓟 i 𝓡, nie do zbioru 𝓣. Jednakże, jeśli 𝓛 jest poprawny, to jest automatycznie niesprzeczny (ponieważ, jeśli 𝓟 jest podzbiorem 𝓣, a 𝓣 jest rozdzielne z 𝓡, to 𝓟 musi być rozdzielne 𝓡). Wynikanie w drugą stronę niekoniecznie zachodzi (później będziemy rozważać systemy, które są niesprzeczne, ale nie poprawne).
Zdanie X nazywamy rozstrzygalnymi w 𝓛, jeśli jest albo dowodliwe albo niedowodliwe w 𝓛, a nierozstrzygalne w 𝓛 przeciwnym przypadku. System 𝓛 nazywamy zupełnym w 𝓛, jeśli każde zdanie jest w nim rozstrzygalne i niezupełnym jeśli istnieje w nim jakieś nierozstrzygalne zdanie.
Załóżmy, że język 𝓛 spełnia założenia Twierdzenia GT. Wtedy pewne zdanie G jest prawdziwe ale nie dowodliwe w 𝓛. Ponieważ G jest prawdziwe, więc również nie może być niedowodliwe (z założenia o poprawności systemu). Stąd G jest nieorozstrzygalne w 𝓛. I mamy

Twierdzenie 1. Jeśli 𝓛 jest poprawny i zbiór (P~)* jest wyrażalny w 𝓛, to 𝓛 jest niezupełny.