Logika 9. 11. 2010r
Def. 1) Zupełność/niezupełność w sensie klasycznym
a) zbiór formuł X jest zupełny (symbolicznie: X e ZUP) wtw dla każdego zdania A, albo A e CnL(X), albo (~A) e CnL(X).
b) Zbiór formuł X jest niezupełny (symbolicznie: X e/ ZUP) wtw istnieje zdanie A takie, że A e/ CnL(X) i zarazem (~A) e/ CnL(X)
[e/ → nie jest elementem]
/odpowiedzią na jakiekolwiek pytanie rozstrzygnięcia może być wyłącznie zdanie/.
Dygresja. Należy podkreślić, że mówi się tu o zdaniach, a nie o dowolnych formułach. Definicja tu podana wyraża fakt (nie)zupełności teorii, gdy X=CnL(X). Niezupełność teorii oznacza, że pewne zdanie (z jej języka) nie może być na podstawie jej aksjomatów ani udowodnione, ani obalone - rozgałęzia się ona ze względu na to zdanie.
Kilka twierdzeń charakteryzujących pojęcie zupełności:
Twierdzenie 1. X e ZUP wtw CnL(X) e ZUP.
Twierdzenie 2. Dla dowolnego zbioru formuł X, jeżeli X e/ ZUP, to X e NSP.
/NSP - niesprzeczność/.
Twierdzenie 3. Niech X e NSP. Wówczas X e ZUP wtw dla każdej formuły A takiej, że A e/ CnL(X), X u {A} e/ NSP.
Rozszerzenie niesprzecznego i zupełnego zbioru formuł X o formułę A względem niego niezależną prowadzi do sprzeczności.
Dowód: (→) Załóżmy, że X e NSP, X e ZUP i A e/ CnL(X). Wykażemy, że w tej sytuacji X u {A} e/ NSP. Skoro A e/ CnL(X), więc także
_ _
A e/ CnL(X). Ponieważ X e ZUP i A jest zdaniem, więc:
_
(~A) e CnL(X)
oraz
_
(~A) e CnL(X u {A}) [z uwagi na monotoniczność operacji CnL).
Z drugiej strony,
A e CnL(X u {A}) [z uwagi na zwrotność operacji CnL) i
_
A e CnL(X u {A}) [z uwagi na twierdzenie generalizacji]
To zaś oznacza, że X u {A} e/ NSP.
(←) Załóżmy, że dla każdej formuły A takiej, że A e/ CnL(X), X u {A} e/ NSP, zaś dla dowodu nie wprost załóżmy, że X e/ ZUP. Gdy X e/ ZUP, wówczas istnieje zdanie A takie, że A e/ CnL(X) i (~A) e/ CnL(X). Stąd wnosimy, że X u {A} e NSP, wbrew założeniu twierdzenia [korzystamy tu z twierdzenia: Jeżeli formuła A jest zdaniem oraz (~A) e/ CnL(X), to X u {A} e NSP).
Twierzenie do pozwala zdefiniować pojęcie niesprzeczności inaczej, w sposób bardziej ogólny:
Def 2. Zupełność / niezupełność w sensie Posta
a) zbiór formuł X jest zupełny w sensie Posta (lub maksymalnie niesprzeczny) wtw dla każdej formuły A takiej, że A e/ CnL(X), CnL(X u {A}) = J.
b) Zbiór formuł X jest niezupełny w sensie Posta wtw istnieje formuła A taka, że A e/ CnL(X) i CnL(X u {A}) =/= J.
/Def. Posta może być stosowana do języków beznegacyjnych/.
Lemat Lindenbauma o nadzbiorach zupełnych (maksymalnych).
Jeżeli X jest niesprzeczną teorią pierwszego rzędu w języku J, to istnieje teoria Y, która jest niesprzecznym i zupełnym rozszerzeniem teorii X. Zbiór Y nazywamy wówczas nadzbiorem Lindenbauma.
KRP nie jest zupełny ani w sensie pierwszym, ani drugim.
[Zupełny jest KRZ z kwantyfikatorami wiążącymi zmienne zdaniowe]
Twierdzenia Godla zachodzą dla dowolnej teorii pierwszego rzędu T, która spełnia następujące warunki:
Teoria T jest dana efektywnie, czyli jej twierdzenia (w szczególnośći aksjomaty) tworzą zbiór rekurencyjnie przeliczalny [istnieje efektywna procedura pozwalająca odróżnić formuły będące aksjomatami, do tych które nie są aksjomatami];
Teoria T zawiera elementarną arytmetykę [jak np. PA]
Pierwsze twierdzenie Godla głosi, że dowolny system formalny [pierwszego rzędu] - spełniający powyższe dwa warunki - jest albo zupełny, albo niesprzeczny, i nigdy nie posiada obu cech jednocześnie. Dokładniej:
Tw. Godla o niezupełności: Jeżeli PA jest fragmentem teorii T oraz T e NSP, to teoria T e/ ZUP, czyli istnieje zdanie A języka teorii T takie, że ani A, ani ~A nie są tezami T.
Dygresja: Twierdzenie udowodnione przez Godla zakładało omega - niesprzeczność, zredukowana potem do zwykłej niesprzezcności.
Niech T będzie teorią, której język zawiera nazwy wszystkich liczb naturalnych (tzw. liczebniki:
_ _ _
0, 1, 2, …).
Teoria T jest omega-niesprzeczna wtw nie istnieje formuła A(x) z jej języka taka, ze
_ _ _
T |- A(0), T |- A(1), T |- A(2), … oraz T |- 3x ~A(x).
W przeciwnym przypadku jest omega-sprzeczna.
Inaczej: gdy teoria jest omega niesprzeczna, to nie może dowodzić zarazem tego, że:
każda poszczególna liczba naturalna ma pewną własność
oraz
istnieje liczba naturalna, która nie ma tej własności.
Właność omega niesprzeczności jest silniejsza od niesprzeczności...
Dygresja. Przypomnijmy na mocy lematu Lindenbauma, każda niesprzeczna teoria 1. rzędu posiada niesprzeczna i zupełne rozszerzenie, a więc również teoria PA posiada takie rozszerzenie. Czy wynik ten pozostaje w konflikcie z wynikiem Godla?
Nie.
Owe niesprzeczne i zupełne rozszerzenia PA nie są [rekurencyjnie] aksjomatyzowalne [na mocy przyjętych założeń na temat teorii T, jeżeli rozważana teoria jest niesprzeczna, to zupełność wyklucza jej aksjomatyzowalność]. Twierdzenie Godla nadaje się też niekiedy następującą postać: Nie istnieje żadne niesprzeczne, zupełne i aksjomatyzowalne rozszerzenie PA [zob. np. Boolos, Burgess, Jeffrey Computability and Logic].
Dowód tw. Godla opierał się na pomyśle artymetyzacji. Arytemtyzacja polega na przypisaniu termom, formułom i ciągom formuł rozważanego język - liczb naturalnych jako ich kodów. Dzięki temu można było mówić o formułach oraz dowodach formuł, mówiąc o ich liczbowych kodach (szczególy arytemtyzacji tu pomijam). Ponadto dowód tego twierdzenia wykorzystuje tzw. lemat przekątniowy.
Lemat przekątniowy. Dla dowolnej formuły A(x) z jedną zmienną wolną istnieje zdanie B, które „mówi” o sobie, że ma własność opisywaną przez formułę A(x), czyli
_ _
PA |- B ↔ A(| B |).
_ _
Dygresja. | B | to nazwa kodu liczbowego [numeru Godla] zdania B - jakaś liczba.
Umożliwia to tworzenie zdań samoodnośnych na artymetyce.
Na mocy tego lematu istnieje zdanie - zdanie Godla - które o sobie samym głosi tylko, tyle że nie jest ono dowodliwe [na gruncie PA].
/przeformułowanie antynomii kłamcy na grunt PA]
Na gruncie PA dają się precyzyjnie określić formuły dow(x,y) i diag(x)=y w ten sposób, że:
_ _
dow(m, n) wyraża fakt, że ciąg formuł mający kod m jest dowodem formuły o kodzie n.
_
w konsekwencji formuła 3x dow(x, n) stwierdza, że formuła o kodzie n jest tezą PA.
_
Diag(m) = n wyraża, że liczba n jest kodem diagonalizacji formuły o kodzie m.
/diagonalizacja formuły A(x) nazywamy zdanie postaci A(|A(x)|), które powstało przez podstawienie do A(X) za zmienną x nazwy kodu formuły A(X). Intuicyjnie zdanie A(|A(X)|) orzeka o formnule A(x), że ma tę własność przez siebie opisywaną.
Zdanie Godla:
Niech G(y) będzie skrótem dla formuły ~3x dow(x, diag(y)) i niech liczba n będzie kodem dla
_
G(y): |G(y)| = n.
_
Wtedy zdanie G(n) stwierdza, że nie istnieje dowód formuły o kodzie, którego nazwą jest
_
diag(n).
Ale diag(n) nazywa kod zdania G(n): diag(n) = |G(n)|.
Widać więc, ze zdanie G(n) stwierdza o sobie samym, ze nie jest tezą PA (podobnie „zdanie kłamcy” stwierdza o sobie samym, że nie jest prawdziwe).
W dowodzie tw. Godla pokazuje się, że ani owo zdanie, ani jego negacja nie są tezami teorii T>
Zarzut: Zdanie Godla nie ma konkretnej treści matematycznej (jak np. 2+2=4).
[wiele lat po odkryciu Godla wskazano na zdania matematyczne, które udowodniono że ani one, ani ich negacje nie są tezami teorii PA].
Konsekwencja I tw. Godla jest tw. Głoszące, że nie da się dowieść, w ramach danego systemu (zawierającego arytmetykę liczb naturalnych i niesprzecznego) jego własnej niesprzeczności. Aby taki dowód przeprowadzić, niezbędny jest jakiś inny (bogatszy) system, którego niesprzeczności w ramach niego samego również nie da się dowieść - i tak ad infinitum.
Przypomnijmy:
Teoria T jest sprzeczna wtw wśród jej tez - czyli formuł posiadających dowód wewnątrz T - występują dwie formuły wzajemnie sprzeczne, A i ~A.
Sprzeczność teorii pociąga jej trywialność.
Jeżeli fragmentem teorii T jest PA, to jej tezą jest zdanie 0' =/= 1'. Gdy teoria T jest sprzeczna, wówczas tezą jest także danie 0' = 1'
…
twierdzenie Godla o niezupełności. Jeżeli PA jest fragmentem teorii T oraz T e NSP, to zdanie Cons(T) jest niedowodliwe wewnątrz teorii T.
Andrew Weil /Bóg istnieje ponieważ matematyka jest niesprzeczna, diabeł istnieje ponieważ nie możemy tego udowodnić/.
Implikacje filozoficzne:
podważa optymizm poznawczy, wskazując na istnienie zasadniczych barier poznawczych /D. Hilbert [1930r.] „przynajmniej w matematyce wszystko da się udowodnić/poznać”/
niemożność pełnej realizacji pomysłu Leibniza o characteristica universalis
/L. Projektował naukę jako mathesis universalis, miała to być matematyka obejmująca swoim zasięgiem matematykę, logikę, metafizykę i teologie - potrzebny był język, a całość byłaby rachowana w specjalnym rachunku - dzięki temu dyskutanci nie mogliby zabrnąć w spór bez wyjścia → wystarczyłoby porachować/;
podważa ideę bezzałożeniowego ugruntowania poznania (Kartezjusz, Husserl)
/K. - metodyczne wątpienie; H. - redukcja ejdetyczna. Nie da się w bezzałożeniowy sposób zbudować gmachu całej wiedzy/;
podważa formalizm matematyczny D. Hilberta.
/Hibert zaproponował program logicznego odtworzenia wiedzy matematycznej - efektem matematyka powinna być zupełna oraz powinna być niesprzeczna; składał się z dwóch etapów - 1. formalizacja całej matematyki /dowody, aksjomaty, itp./ → można by je badać metodami finitystycznymi - 2. dowód niesprzeczności całej matematyki; tw. Goedla pokazuje, że nie da się osiągnąć zupełności, ani nie da się udowodnić niesprzeczności teorii matematycznej/;
Umysł a maszyny /sztuczna inteligencja/:
- silna teza mechanicyzmu:
→ człowiek = maszyna (La Mattrie)
→ Umysł ludzki (w ogóle w pewnym zakresie, np. matematyki, tylko arytmetyki) = maszyna
- słaba teza mechanicyzmu:
→ człowiek może być symulowany przez maszynę [robota]
→ umysł ludzki - w ogóle lub w pewnym zakresie, np. matematyki, tylko arytmetyki - może być symulowany przez maszynę.
Argument Johna R. Lucasa przeciwko mechanicyzmowi:
Żadna maszyna nie może być równoważna umysłowi, bo umysł ludzki rozpoznaje prawdziwość zdania Godla dla niej, a sama maszyna - na mocy twierdzenia Godla - nie może, chyba że jest sprzeczna, ale wtedy na pewno nie jest równoważna umysłowi ludzkiemu.
/Komentarz: maszyna w sensie Lucasa = maszyna Turinga → Minds, Machines, and Godel, „Philosophy” 36 [1961r.] → przetłumaczony na polski w internecie/.
W cieniach umysłu Roger Penrose wyróżnia cztery stanowsika dotyczące zasad działania świadomości:
A) stanowisko silnej sztucznej inteligencji: „myślenie zawsze polega na obliczeniach a w szczególności świadome doznania powstają wskkutek realizacji odpowiedniego procesu obliczeniowego”.
B) Stanowisko słabej sztucznej inteligencji: „świadomość jest cechą fizyczną działającego mózgu; wprawdzie wszystkie fizyczne procesy można symulować obliczeniowo, symulacjom obliczeniowym nie towarzyszy jednak świadomość”.
Stanowisko Penrosa: „odpowiednie procesy fizyczne w mózgu powodują powstanie świadomości, ale tych procesów nie można nawet symulować obliczeniowo”. Penrose wnioskuje z tw. Godla, że ludzkiego rozumienia...
Mistyczne: nie da się.
Czy tw. Godla ma praktyczne implikacje? Czy potrafimy w naukach przyrodniczych w tej chwili wskazać konkretne pytania na które nie jesteśmy w stanie odpowiedzieć właśnie z powodu występowania w matematyce niezupełności?
Czy faktycznie twierdzenie Godla implikuje istnienie zasadniczych barier poznawczych? Czy nawet jeśli obecnie nie potrafimy wskazać konkrektnych przykładów oddziaływania twierdzenia Godla, to muszą się one w sposób konieczny pojawić? Czy zasadne jest stosowanie tw. Godla do naszej wiedzy przyrodniczej?
Lektura:
S. Krajewski „Twierdzenie Godla i jego interpretacje filozoficzne”
R. Murawski „Funkcje rekurencyjne i elementy matematyki”
E. Nagel, J. R. Newman „Twierdzenia Godla”