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?
O co tak naprawdę chodzi z twierdzeniem Godla?
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: O co tak naprawdę chodzi z twierdzeniem Godla?
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.
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.
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:
dowód:
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.