05 - 09. 11. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna


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:

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:

  1. 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:

oraz

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:

_ _

_

/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:

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'

  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:

- 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ść”.

  1. 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...

  1. 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”



Wyszukiwarka

Podobne podstrony:
06 - 16. 11. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
08 - 30. 11. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
07 - 23. 11. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
09 - 07. 12. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
11 - 04. 01. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
01 - 05. 10. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
10 - 14. 12. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
04 - 26. 10. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
02 - 12. 10. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
03 - 19. 10. 2010, Filozofia, Notatki FO, III Semestr, Semantyka logiczna
05 - 05. 11. 2010, Filozofia, Notatki FO, III Semestr, Filozofia nauki
06 - 10. 11. 2010, Filozofia, Notatki FO, III Semestr, Filozofia kultury
02 - 15. 10. 2010, Filozofia, Notatki FO, III Semestr, Filozofia nauki
10 - 08. 12. 2010, Filozofia, Notatki FO, III Semestr, Filozofia kultury
12 - 05. 01. 2011, Filozofia, Notatki FO, III Semestr, Filozofia kultury
13 - 12. 01. 2011, Filozofia, Notatki FO, III Semestr, Filozofia kultury
15 - 26. 01. 2011, Filozofia, Notatki FO, III Semestr, Filozofia kultury
ETYKA ŻP, Filozofia, Notatki FO, III Semestr, Etyka
Zielarstwo - wyk-ad 5 - 09.11.2010, OGRODNICTWO UP LUBLIN (buka), Semestr III, ZIELARSTWO

więcej podobnych podstron