O co tak naprawdę chodzi z twierdzeniem Godla?

[Borneq]

Z jego najbardziej znanym twierdzeniem?
Czy o to że istnieją zdania prawdziwe, które nie będą miały dowodów? Można sobie wyobrazić że hipoteza Goldbacha jest prawdziwa ale nie ma dowodów.
Czy też zawsze będą przypadki jak hipoteza continuum, gdzie ani zdanie ani jego zaprzeczenie nie będzie prawdziwe?

[Slup]

Jest na to dobra z książki Smullyana.

Powiedzmy, że dana jest maszyna \(\displaystyle{ \mathcal{M}}\), która jest podłączona do monitora. Działanie \(\displaystyle{ \mathcal{M}}\) polega na tym, że co jedną sekundę przesyła ona do monitora pewien łańcuch następujących znaków (znaki oddzielam przecinkami):

$$(,\,),\,P,\,N,\,\neg$$

i ten łańcuch jest na monitorze wyświetlany. Np. jeden z łańcuchów, które maszyna może wyświetlić na monitorze jest:

$$)(PPPN\neg\neg ((PN)N(P)\neg$$

Zbiór wszystkich takich łańcuchów będę oznaczał \(\displaystyle{ \mathcal{Ł}}\). Niektóre z łańcuchów z \(\displaystyle{ \mathcal{Ł}}\) będziemy nazywali "zdaniami \(\displaystyle{ \mathcal{M}}\)" i ich zbiór będziemy oznaczali \(\displaystyle{ \mathcal{Z}}\). Teraz ten zbiór opiszemy.

1. Jeśli \(\displaystyle{ X \in \mathcal{Ł}}\), to \(\displaystyle{ P(X)\in \mathcal{Z}}\) oraz \(\displaystyle{ \neg P(X)\in \mathcal{Z}}\).

2. Jeśli \(\displaystyle{ X\in \mathcal{Ł}}\), to \(\displaystyle{ PN(X)\in \mathcal{Z} }\) oraz \(\displaystyle{ \neg PN(X)\in \mathcal{Z}}\).

Elementy zbioru \(\displaystyle{ \mathcal{Z}}\) umówimy się rozumieć jako pewne zdania w języku polskim dotyczące działania maszyny \(\displaystyle{ \mathcal{M}}\).

1. Element \(\displaystyle{ P(X)\in \mathcal{Z}}\) będziemy rozumieli jako zdanie: "Maszyna \(\displaystyle{ \mathcal{M}}\) w czasie swojego działania wypisuje na ekranie łańcuch \(\displaystyle{ X}\)"

2. Element \(\displaystyle{ \neg P(X)\in \mathcal{Z}}\) będziemy rozumieli jako zdanie: "Maszyna \(\displaystyle{ \mathcal{M}}\) nigdy nie wypisze na ekranie łańcucha \(\displaystyle{ X}\)"

3. Element \(\displaystyle{ PN(X)\in \mathcal{Z}}\) będziemy rozumieli jako zdanie: "Maszyna \(\displaystyle{ \mathcal{M}}\) w czasie swojego działania wypisuje na ekranie łańcuch \(\displaystyle{ X(X)}\)"

4. Element \(\displaystyle{ \neg PN(X)\in \mathcal{Z}}\) będziemy rozumieli jako zdanie: "Maszyna \(\displaystyle{ \mathcal{M}}\) nigdy nie wypisze na ekranie łańcucha \(\displaystyle{ X(X)}\)"

Wreszcie ostatnie oznaczenie. Oznaczmy przez \(\displaystyle{ \mathcal{Ł}_{print}}\) zbiór wszystkich łańcuchów, które maszyna \(\displaystyle{ \mathcal{M}}\) wypisze w czasie swojego działania. Oczywiście \(\displaystyle{ \mathcal{Ł}_{print}\subseteq \mathcal{Ł}}\) i być może ta inkluzja jest ostra (nigdzie nie zakładamy, że \(\displaystyle{ \mathcal{M}}\) wypisze wszystkie łańcuchy z \(\displaystyle{ \mathcal{Ł}}\)). Teraz można udowodnić następujące.

Twierdzenie.
Załóżmy, że zbiór \(\displaystyle{ \mathcal{Z}\cap \mathcal{Ł}_{print}}\) wszystkich "zdań \(\displaystyle{ \mathcal{M}}\)", które maszyna wypisuje, po przełożeniu na język polski składa się ze zdań, które są prawdziwe. Wówczas istnieje element zbioru \(\displaystyle{ \mathcal{Z}}\), którego maszyna nie wypisze i który po przełożeniu na język polski jest zdaniem prawdziwym.

heurystyka dowodu:    

Najpierw warto pomyśleć o tym dowodzie w języku polskim, a potem przełożyć rozwiązanie na język maszynowy. Weźmy takie zdanie \(\displaystyle{ z_p}\) w języku polskim:

"Maszyna \(\displaystyle{ \mathcal{M}}\) nie wypisze tego zdania"

Łatwo widać, że jeśli można je zapisać w języku maszynowym, to twierdzenie jest udowodnione. Powstaje kwestia, czy język maszynowy jest wystarczająco pojemny by je wyrazić. Spróbujmy od tyłu. Powiedzmy, że mamy już przekład zdania \(\displaystyle{ z_p}\) na język maszynowy. Oznaczmy go przez \(\displaystyle{ z_m}\). Wówczas \(\displaystyle{ z_m\in \mathcal{Z}}\). Zdanie \(\displaystyle{ z_p}\) zawiera zaprzeczenie, więc wydaje się, że \(\displaystyle{ z_m}\) też powinno. Zatem \(\displaystyle{ z_m = \neg P(X)}\) lub \(\displaystyle{ z_m = \neg PN(X)}\) dla pewnego łańcucha \(\displaystyle{ X}\). Ta druga możliwość wydaje się bardziej pociągająca, więc ją wypróbujmy. Załóżmy więc, że \(\displaystyle{ z_m = \neg PN(X)}\). Zdanie \(\displaystyle{ z_m}\) oznacza wtedy, że łańcuch \(\displaystyle{ X(X)}\) nie jest wypisywany przez maszynę. Z drugiej strony zdanie \(\displaystyle{ z_m}\) jest przekładem zdania \(\displaystyle{ z_p}\) w języku polskim na język maszynowy, a więc powinno oznaczać, że \(\displaystyle{ z_m}\) nie jest wypisywane przez maszynę. Stąd widać, że byłoby świetnie, gdyby
$$z_m = X(X)$$
ale wobec równości
$$z_m = \neg PN(X)$$
mamy
$$X(X) = \neg PN(X)$$
Skracając łańcuchy w ostatnim równaniu dostajemy
$$X = \neg PN$$
Stąd \(\displaystyle{ z_m = \neg PN(\neg PN)}\).

dowód:    

Weźmy zdanie

$$\neg PN(\neg PN)$$

po przetłumaczeniu tego zdania na język polski dostajemy zdanie

"Maszyna \(\displaystyle{ \mathcal{M}}\) nie wypisuje łańcucha \(\displaystyle{ \neg PN(\neg PN)}\)"

Załóżmy teraz, że maszyna wypisze zdanie \(\displaystyle{ \neg PN(\neg PN)}\). Z racji, że maszyna wypisuje tylko zdania prawdziwe, wynika, że prawdą jest, że maszyna \(\displaystyle{ \mathcal{M}}\) nie wypisuje łańcucha \(\displaystyle{ \neg PN(\neg PN)}\). Niestety właśnie to zrobiła, a więc sprzeczność.
Zatem maszyna nie wypisuje zdania \(\displaystyle{ \neg PN(\neg PN)}\). Wtedy jednak to zdanie jest prawdziwe, bo mówi ono dokładnie tyle, że maszyna nie wypisuje łańcucha \(\displaystyle{ \neg PN(\neg PN)}\). Zatem \(\displaystyle{ \neg PN(\neg PN)}\) jest prawdziwym zdaniem, którego \(\displaystyle{ \mathcal{M}}\) nie wypisze.

Dodano po 38 minutach 47 sekundach:
Powyższa prezentacja oparta jest na zjawisku samo-odniesienia. W książce Y.Manina Mathematical Logic twierdzenie Gödla jest zaprezentowane w taki sposób, że najpierw przedstawia się język SELF, który pochodzi od Smullyana i pozwala wyrażać samo-odniesienie (podobnie jak powyższy język maszynowy) a następnie formułuje się język SAr, który też pochodzi od Smullyana, ma taką samą siłę wyrazu jak język arytmetyki pierwszego rzędu i też umożliwia samo-odniesienie.