Twierdzenie Gödla

Z Wikipedii

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: niewłaściwe sformułowanie twierdzeń, definicji. Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

Twierdzenie Gödla to jeden z najbardziej znanych rezultatów logiki matematycznej. W istocie znane są dwa różne twierdzenia Gödla: pierwsze z nich to twierdzenie o niezupełności, drugie zaś to jego bezpośredni (równoważny) wniosek nazywany też twierdzeniem o niedowodliwości niesprzeczności. Oba twierdzenia zostały udowodnione w 1931 roku przez austriackiego matematyka i logika Kurta Gödla. Uważa się również, że twierdzenia te dają negatywną odpowiedź na drugi problem Hilberta, i w ten sposób mają spore znaczenie w filozofii matematyki. Inne bardzo ważne twierdzenia Gödla to: twierdzenie o istnieniu modelu i twierdzenie o nierozstrzygalności (patrz: Teoria (logika), Struktura matematyczna).

Spis treści 1 Kontekst 2 Twierdzenia 2.1 Pierwsze, o niezupełności 2.2 Drugie, o niedowodliwości niesprzeczności 3 Zarys dowodu 4 Wnioski 4.1 Błędne interpretacje 5 Przypisy

[edytuj] Kontekst

Twierdzenie Gödla było odpowiedzią na próbę przedstawienia wszystkich aksjomatów i twierdzeń matematycznych w postaci czysto symbolicznej (syntaktycznej), tzn. bez odwoływania się do ich znaczenia (czyli w oderwaniu od semantyki, por. logicyzm, formalizm (matematyka)). Próby takiej podjął się m.in. David Hilbert.

System formalny niesprzeczny – system, w którym nie da się udowodnić jednocześnie pewnego zdania i jego zaprzeczenia.

System formalny zupełny – system, w którym możliwe jest przeprowadzenie dowodu dowolnego, prawidłowo zapisanego zdania tego systemu, lub jego zaprzeczenia.

[edytuj] Twierdzenia

Dalej, termin: prawdziwość używany będzie w znaczeniu: możliwość przeprowadzenia dowodu, a nie w sensie Tarskiego: spełnienia przez model. (Dotyczy bowiem zdań w systemach formalnych, które w ogólności modeli nie posiadają.)

[edytuj] Pierwsze, o niezupełności

Twierdzenie to mówi, że dowolny system formalny zawierający w sobie aksjomaty arytmetyki liczb naturalnych, jest albo zupełny albo niesprzeczny i nigdy nie posiada obu tych cech jednocześnie. Innymi słowy: można dowodzić prawdziwości wszystkich zdań takiego systemu, jednak wówczas istnieje w systemie pewne prawdziwe zdanie P, którego zaprzeczenie ~P również jest prawdziwe. Tym samym system albo jest sprzeczny wewnętrznie, albo system nie musi być sprzeczny, lecz wówczas istnieją zdania, których prawdziwości nie da się wywieść z aksjomatów i twierdzeń rozważanego systemu formalnego.

[edytuj] Drugie, o niedowodliwości niesprzeczności

To twierdzenie jest konsekwencją poprzedniego. Głosi ono, iż nie da się dowieść, w ramach tego systemu, niesprzeczności żadnego systemu formalnego zawierającego arytmetykę liczb naturalnych. Aby taki dowód przeprowadzić, niezbędny jest system wyższego rzędu, którego niesprzeczności w ramach niego samego również nie da się dowieść – i tak ad infinitum.

[edytuj] Zarys dowodu

Jeżeli zebrać wszystkie dowody w systemie w ciąg (Π_i) i wszystkie formuły zdaniowe jednoargumentowe w ciąg (P_i), to istnieje formuła

Zdanie Gödla P_k(k) oznacza więc, że nie można go dowieść. Gdyby można było go dowieść, byłoby fałszywe, a system byłby sprzeczny, więc jest prawdziwe, choć nie można go dowieść^[1].

[edytuj] Wnioski

Obydwa twierdzenia Gödla można uogólnić na dowolne systemy formalne zawierające skończoną lub rekurencyjnie przeliczalną liczbę aksjomatów. Warunkiem jest, aby w skład takiego systemu wchodziła arytmetyka liczb naturalnych lub zawierał on skończoną liczbę aksjomatów umożliwiającą przeprowadzenie tzw. arytmetyzacji twierdzeń.

Można oznaczyć G₀=P_k(k) i dodać to zdanie do aksjomatów systemu. Wtedy również będzie istniało zdanie G₁ niezależne od poszerzonych aksjomatów. W ten sposób można dodać G₂, G₃..., a nawet G_ω, G_ω+1, G_ω+2..., G_ω2, G_ω2+1..., G_ω3, G_ω4... i G_ω².^[1]

[edytuj] Błędne interpretacje

Potoczne rozumienie twierdzeń Gödla prowadzi zwykle do nieprawidłowych wniosków, np.:

• nie wiadomo, co jest prawdą,
• każdy system rozumowania jest sprzeczny albo niezupełny.

Warto także pamiętać, że dowód pierwszego twierdzenia Gödla polega na skonstruowaniu explicite zdania prawdziwego, którego nie da się dowieść w arytmetyce liczb naturalnych. Wyraźnie więc odróżnia się tu prawdziwość zdania od możliwości samego jego dowodzenia.

W codziennym życiu zwykle nie mamy do czynienia z systemami formalnymi, a co ważniejsze: kryteria prawdy nie są oparte wyłącznie na rachunku predykatów i innych formach logicznego rachunku zdań. Ponadto, prace późniejszych matematyków i logików doprowadziły poprzez zastosowanie tzw. indukcji pozaskończonej do konstrukcji systemów formalnych zawierających arytmetykę liczb naturalnych, będących jednocześnie niesprzecznymi i zupełnymi.

Istnieją również alternatywne formy twierdzeń Gödla posługujące się pojęciami m.in. z zakresu tak zwanych zbiorów rekurencyjnych.

Przypisy