Twierdzenie Gödla o niezupełności w prostych słowach. Formalne teorie aksjomatyczne i liczby naturalne

Twierdzenia o niezupełności Kurta Gödla były punktem zwrotnym w matematyce XX wieku. A w jego rękopisach, opublikowanych po jego śmierci, zachował się logiczny dowód na istnienie Boga. Podczas ostatnich czytań świątecznych ciekawy raport Profesor nadzwyczajny Seminarium Teologicznego w Tobolsku, kandydat teologii Ksiądz Dymitr KIRYANOV mówił o tym mało znanym dziedzictwie. „NS” poprosił o wyjaśnienie głównych idei naukowca.

Twierdzenia Gödla o niezupełności: dziura w matematyce

— Czy istnieje jakiś popularny sposób wyjaśnienia twierdzeń Gödla o niezupełności? Fryzjer goli tylko tych, którzy sami się nie golą. Czy fryzjer goli się sam? Ten słynny paradoks czy to ma coś z nimi wspólnego?

Główna teza logicznego dowodu na istnienie Boga, wysunięta przez Kurta Gödla: "Bóg istnieje w myślach. Ale istnienie w rzeczywistości to coś więcej niż istnienie tylko w myśli. Dlatego Bóg musi istnieć." Na zdjęciu: autor twierdzenia o niezupełności Kurt Gödel ze swoim przyjacielem, autorem teorii względności Albertem Einsteinem. Priston. Ameryka. 1950

- Tak, oczywiście, że tak. Przed Gödelem istniał problem aksjomatyzacji matematyki i problem takich zdań paradoksalnych, które formalnie można zapisać w dowolnym języku. Na przykład: „To stwierdzenie jest fałszywe”. Jaka jest prawda w tym stwierdzeniu? Jeśli to prawda, to jest fałszywe, jeśli to jest fałszywe, to jest prawdą; Prowadzi to do paradoksu językowego. Gödel studiował arytmetykę i w swoich twierdzeniach wykazał, że jej spójności nie można udowodnić w oparciu o jej oczywiste zasady: aksjomaty dodawania, odejmowania, dzielenia, mnożenia itp. Aby to uzasadnić, potrzebujemy dodatkowych założeń. To jest najbardziej najprostsza teoria, ale co z bardziej złożonymi (równaniami fizycznymi itp.)! Aby uzasadnić jakikolwiek system wnioskowania, zawsze zmuszeni jesteśmy uciekać się do jakiegoś dodatkowego wnioskowania, które nie jest uzasadnione w ramach systemu.

Przede wszystkim wskazuje to na przedawnienie roszczeń umysł ludzki w poznaniu rzeczywistości. Oznacza to, że nie możemy powiedzieć, że zbudujemy jakąś wszechstronną teorię wszechświata, która wszystko wyjaśni – taka teoria nie może być naukowa.

— Co matematycy myślą obecnie o twierdzeniach Gödla? Czy nikt nie próbuje im zaprzeczyć lub jakoś je obejść?

„To jakby próbować obalić twierdzenie Pitagorasa”. Twierdzenia mają ścisły dowód logiczny. Jednocześnie podejmuje się próby znalezienia ograniczeń stosowalności twierdzeń Gödla. Jednak debata toczy się głównie wokół filozoficznych implikacji twierdzeń Gödla.

— Jak daleko rozwinął się dowód Gödla na istnienie Boga? Czy to już koniec?

„Zostało to szczegółowo opracowane, chociaż sam naukowiec nie odważył się go opublikować aż do śmierci”. Gödel rozwija ontologiczny (metafizyczny. - „NS”) argument zaproponowany po raz pierwszy przez Anzelma z Canterbury. Argument ten można przedstawić w skondensowanej formie w następujący sposób: „Bóg z definicji jest Tym, od którego nic nie można pojąć. Bóg istnieje w myśleniu. Ale istnienie w rzeczywistości to coś więcej niż istnienie tylko w myślach. Dlatego Bóg musi istnieć.” Argument Anzelma rozwinęli później René Descartes i Gottfried Wilhelm Leibniz. Zatem zdaniem Kartezjusza myślenie o Najwyższej Istocie Doskonałej, która nie istnieje, oznacza popadnięcie w logiczną sprzeczność. W kontekście tych idei Gödel rozwija swoją wersję dowodu, który mieści się dosłownie na dwóch stronach. Niestety nie da się przedstawić jego argumentacji bez przedstawienia podstaw bardzo złożonej logiki modalnej.

Oczywiście logiczna bezbłędność wniosków Gödla nie zmusza człowieka do wiary pod presją siły dowodu. Nie powinniśmy być naiwni i wierzyć, że każdego inteligentnie uda nam się przekonać myślący człowiek wierzyć w Boga za pomocą argumentu ontologicznego lub innego dowodu. Wiara rodzi się, gdy człowiek staje twarzą w twarz z oczywistą obecnością najwyższej transcendentalnej Rzeczywistości Boga. Możemy jednak wymienić przynajmniej jedną osobę, do której doprowadził dowód ontologiczny wiara religijna, - to pisarz Clive Staples Lewis, sam to przyznał.

Odległa przyszłość to odległa przeszłość

— Jak współcześni traktowali Gödla? Czy przyjaźnił się z którymś z wielkich naukowców?

— zaświadcza o tym asystent Einsteina w Princeton jedyna osoba, z którym się przyjaźnił ostatnie latażycia, był Kurt Gödel. Różnili się niemal wszystkim – Einstein był towarzyski i wesoły, natomiast Gödel był niezwykle poważny, całkowicie samotny i nieufny. Ale mieli ogólna jakość: obaj podeszli bezpośrednio i szczerze w stronę kwestie centralne nauka i filozofia. Pomimo przyjaźni z Einsteinem Gödel miał swój własny, specyficzny pogląd na religię. Odrzucił ideę Boga jako istoty bezosobowej, jaką był Bóg dla Einsteina. Przy tej okazji Gödel zauważył: „Religia Einsteina jest zbyt abstrakcyjna, podobnie jak filozofia Spinozy i indyjska. Bóg Spinozy to mniej niż osoba; mój Bóg jest czymś więcej niż osobą; ponieważ Bóg może odgrywać rolę osobowości”. Mogą istnieć duchy, które nie mają ciała, ale mogą komunikować się z nami i wpływać na świat.

— Jak Gödel znalazł się w Ameryce? Uciekł przed nazistami?

— Tak, przybył do Ameryki w 1940 r. z Niemiec, mimo że naziści uznali go za Aryjczyka i wielkiego naukowca, uwalniając go od służba wojskowa. Wraz z żoną Adele przedostał się przez Rosję Koleją Transsyberyjską. Nie pozostawił żadnych wspomnień z tej podróży. Adele tylko pamięta ciągły lęk w nocy, że zatrzymają się i wrócą. Po ośmiu latach mieszkania w Ameryce Gödel został obywatelem USA. Jak wszyscy ubiegający się o obywatelstwo, musiał odpowiedzieć na pytania dotyczące amerykańskiej konstytucji. Jako osoba skrupulatna, przygotowywał się do tego egzaminu bardzo starannie. Na koniec powiedział, że znalazł niespójność w Konstytucji: „Odkryłem logicznie uzasadnioną możliwość, w której Stany Zjednoczone mogą stać się dyktaturą”. Jego przyjaciele uznali, że niezależnie od logicznej wartości argumentacji Gödla, możliwość ta ma charakter czysto hipotetyczny, i przestrzegali przed obszernym poruszaniem tego tematu na egzaminie.

— Czy Gödel i Einstein korzystali ze swoich pomysłów w Praca naukowa?

— W 1949 r. Gödel wyraził swoje idee kosmologiczne w eseju matematycznym, który według Alberta Einsteina stanowił ważny wkład w ogólną teorię względności. Gödel wierzył, że czas – „ta tajemnicza, a jednocześnie wewnętrznie sprzeczna esencja, która stanowi podstawę świata i naszej własnej egzystencji” – w końcu stanie się największą iluzją. To „kiedyś” przestanie istnieć, a nadejdzie inna forma istnienia, którą można nazwać wiecznością. Ta koncepcja czasu doprowadziła wielkiego logika do nieoczekiwanego wniosku. Napisał: „Jestem przekonany o życiu pozagrobowym, niezależnie od teologii. Jeśli świat został inteligentnie zaprojektowany, musi istnieć życie pozagrobowe.”

- „Czas jest bytem wewnętrznie sprzecznym.” Brzmi dziwnie; ma trochę znaczenie fizyczne?

— Gödel pokazał, że w ramach równania Einsteina można zbudować model kosmologiczny z czasem zamkniętym, w którym zbiegają się odległa przeszłość i odległa przyszłość. W tym modelu podróże w czasie stają się teoretycznie możliwe. Brzmi to dziwnie, ale da się to wyrazić matematycznie – o to właśnie chodzi. Model ten może, ale nie musi, mieć implikacje eksperymentalne. Jest to konstrukt teoretyczny, który może przydać się w konstruowaniu nowych modeli kosmologicznych – lub może okazać się niepotrzebny. Nowoczesny Fizyka teoretyczna, w szczególności kosmologia kwantowa, ma taki kompleks struktura matematycznaże struktury te są bardzo trudne do jednoznacznego zrozumienia filozoficznego. Co więcej, niektórych jego projektów teoretycznych nie da się jak dotąd przetestować eksperymentalnie z tego prostego powodu, że ich weryfikacja wymaga wykrycia cząstek o bardzo wysokiej energii. Pamiętacie, jak ludzie byli zaniepokojeni wystrzeleniem Wielkiego Zderzacza Hadronów: oznacza środki masowego przekazu nieustannie straszyli ludzi zbliżającym się końcem świata. Faktycznie, potraktowano to poważnie eksperyment naukowy przy sprawdzaniu modelu kosmologia kwantowa oraz tak zwane „teorie wielkiej unifikacji”. Gdyby możliwe było wykrycie tzw. cząstek Higgsa, byłby to kolejny krok w naszym zrozumieniu większości wczesne stadia istnienie naszego Wszechświata. Ale chociaż nie ma danych eksperymentalnych, konkurencyjne modele kosmologii kwantowej nadal pozostają po prostu modelami matematycznymi.

Wiara i intuicja

— „...Mój Bóg jest czymś więcej niż osobą; skoro Bóg może odgrywać rolę osoby...” Czy jednak wiara Gödla daleka jest od wyznania prawosławnego?

— Zachowało się bardzo niewiele wypowiedzi Gödla na temat jego wiary, były one zbierane stopniowo. Pomimo tego, że pierwsze projekty własna wersja Gödel wysuwał tę tezę już w 1941 r., do 1970 r., w obawie przed wyśmiewaniem ze strony kolegów, nie wypowiadał się na ten temat. W lutym 1970 roku, przeczuwając zbliżającą się śmierć, pozwolił swojemu asystentowi skopiować wersję swojego dowodu. Po śmierci Gödla w 1978 r. w jego pracach odkryto nieco inną wersję argumentu ontologicznego. Żona Kurta Gödla, Adele, powiedziała dwa dni po śmierci męża, że Gödel „chociaż nie chodził do kościoła, był osobą religijną i w każdą niedzielę rano czytał Biblię w łóżku”.

Kiedy mówimy o naukowcach takich jak Gödel, Einstein czy, powiedzmy, Galileusz czy Newton, należy podkreślić, że nie byli oni ateistami. Widzieli, że za Wszechświatem kryje się Umysł, rodzaj Siły Wyższej. Dla wielu naukowców wiara w istnienie Najwyższa Inteligencja była jedną z konsekwencji ich refleksji naukowej, która nie zawsze prowadziła do powstania głębokiej więzi religijnej między człowiekiem a Bogiem. W odniesieniu do Gödla można powiedzieć, że odczuwał on potrzebę tego połączenia, gdyż podkreślał, że jest teistą i myśli o Bogu jako o osobie. Ale oczywiście jego wiary nie można nazwać ortodoksyjną. Był, że tak powiem, „domowym luteraninem”.

- Możesz dać przykłady historyczne: w jaki sposób różni naukowcy dochodzą do wiary w Boga? Oto genetyk Francis Collins, według swoich wyznań badanie struktury DNA doprowadziło go do wiary w Boga...

— Naturalne poznanie Boga samo w sobie nie jest wystarczające do poznania Boga. Nie wystarczy odkryć Boga studiując przyrodę, ważne jest, aby nauczyć się Go poznawać poprzez Objawienie, które Bóg dał człowiekowi. Dojście do wiary, niezależnie od tego, czy jest naukowcem, czy nie, zawsze opiera się na czymś, co wykracza poza zwykłe argumenty logiczne i naukowe. Francis Collins pisze, że do wiary doszedł w wieku 27 lat po długiej intelektualnej debacie ze sobą i pod wpływem Clive'a Staplesa Lewisa. Dwie osoby znajdują się w tej samej sytuacji historycznej, w tych samych warunkach początkowych: jedna staje się osobą wierzącą, druga – ateistą. Po pierwsze, badanie DNA prowadzi do wiary w istnienie Boga. Inne badania i nie dochodzą do tego wniosku. Dwie osoby patrzą na zdjęcie: jedna uważa, że jest piękna, a druga mówi: „No i takie sobie zdjęcie!” Jeden ma gust i intuicję, a drugi nie. Profesor prawosławnego kościoła św. Tichona uniwersytet humanitarny Władimir Nikołajewicz Katasonow, lekarz nauki filozoficzne, matematyk z wykształcenia, mówi: „Żaden dowód w matematyce nie jest możliwy bez intuicji: matematyk najpierw widzi obraz, a następnie formułuje dowód”.

Kwestia dojścia do wiary jest zawsze kwestią wykraczającą poza logiczne rozumowanie. Jak możesz wyjaśnić, co doprowadziło cię do wiary? Mężczyzna odpowiada: Poszedłem do świątyni, pomyślałem, przeczytałem to i tamto, zobaczyłem harmonię wszechświata; ale najważniejszego, najbardziej wyjątkowego momentu, w którym człowiek nagle dowiaduje się, że spotkał obecność Boga, nie da się wyrazić. To zawsze tajemnica.

- Potrafisz zidentyfikować problemy, których nie możesz rozwiązać nowoczesna nauka?

— W końcu nauka jest przedsiębiorstwem na tyle pewnym siebie, niezależnym i dobrze rozwijającym się, że można się z nią tak ostro wypowiadać. To dobre i bardzo przydatne narzędzie w ludzkich rękach. Od czasów Francisa Bacona wiedza naprawdę stała się siłą, która zmieniła świat. Nauka rozwija się zgodnie ze swoimi wewnętrznymi prawami: naukowiec stara się zrozumieć prawa rządzące wszechświatem i nie ma wątpliwości, że poszukiwania te zakończą się sukcesem. Ale jednocześnie konieczne jest rozpoznanie granic nauki. Nie należy mylić nauki z kwestiami ideologicznymi, które można podnosić w związku z nauką. Kluczowe problemy dzisiaj dotyczą nie tyle metody naukowej, co orientacji na wartości. Nauka przez długi wiek XX była postrzegana przez ludzi jako dobro absolutne, przyczyniające się do postępu ludzkości; i widzimy, że wiek XX stał się najbardziej okrutny pod względem ofiar ludzkich. I tu pojawia się pytanie o wartości postęp naukowy, wiedza w ogóle. Wartości etyczne nie wynikają z samej nauki. Genialny naukowiec może wynaleźć broń mającą na celu zniszczenie całej ludzkości, a to rodzi pytanie o moralną odpowiedzialność naukowca, na które nauka nie jest w stanie odpowiedzieć. Nauka nie jest w stanie wskazać człowiekowi sensu i celu jego istnienia. Nauka nigdy nie będzie w stanie odpowiedzieć na pytanie, dlaczego tu jesteśmy? Dlaczego Wszechświat istnieje? Pytania te rozwiązuje się na innym poziomie wiedzy, takim jak filozofia i religia.

— Czy oprócz twierdzeń Gödla istnieją inne dowody na to, że metoda naukowa ma swoje ograniczenia? Czy sami naukowcy to przyznają?

— Już na początku XX wieku zwracali uwagę filozofowie Bergson i Husserl wartość względna wiedza naukowa Natura. Obecnie wśród filozofów nauki stało się niemal powszechne przekonanie, że teorie naukowe reprezentują hipotetyczne modele wyjaśniania zjawisk. Jeden z twórców mechanika kwantowa— Erwin Schrödinger tak powiedział cząstki elementarne to tylko obrazy, ale bez problemu możemy się bez nich obejść. Zdaniem filozofa i logika Karla Poppera teorie naukowe są jak sieć, przez którą próbujemy złapać świat, a nie fotografie. Teorie naukowe znajdują się w ciągły rozwój i zmienić. O granicach metody naukowej mówili twórcy mechaniki kwantowej, tacy jak Pauli, Bohr i Heisenberg. Pauli napisał: „...Fizykę i psychikę można uważać za dodatkowe aspekty tej samej rzeczywistości” – i podkreślał nieredukowalność wyższe poziomy będąc do niższych. Różne wyjaśnienia obejmują tylko jeden aspekt materii na raz, ale nigdy nie zostanie osiągnięta wszechstronna teoria.

Piękno i harmonia wszechświata zakłada możliwość jego poznania metody naukowe. Jednocześnie chrześcijanie zawsze rozumieli niezrozumiałość tajemnicy kryjącej się za tym materialnym wszechświatem. Wszechświat nie ma podstawy w sobie i wskazuje na doskonałe źródło istnienia – Boga.

Dowolny system aksjomatów matematycznych zaczynający się od pewien poziom złożoność jest albo wewnętrznie sprzeczna, albo niekompletna.

W 1900 roku odbyła się w Paryżu Światowa Konferencja Matematyków, na której David Hilbert (1862-1943) przedstawił w formie tez 23 najważniejsze, jego zdaniem, problemy, które teoretycy nadchodzącego XX wieku musieli rozwiązać. Numer dwa na jego liście był jednym z nich proste zadania, na które odpowiedź wydaje się oczywista, dopóki nie kopniesz trochę głębiej. Mówienie język nowoczesny brzmiało pytanie: czy matematyka jest samowystarczalna? Drugie zadanie Hilberta sprowadzało się do konieczności ścisłego udowodnienia, że system aksjomaty- podstawowe twierdzenia, na których opiera się matematyka bez dowodu - jest doskonałe i kompletne, to znaczy pozwala matematycznie opisać wszystko, co istnieje. Należało wykazać, że możliwe jest zdefiniowanie takiego systemu aksjomatów, aby po pierwsze były one wzajemnie spójne, a po drugie, można było z nich wyciągnąć wniosek o prawdziwości lub fałszywości dowolnego twierdzenia.

Weźmy przykład ze szkolnej geometrii. Standard Planimetria euklidesowa(geometria płaszczyzny) można bezwarunkowo udowodnić, że twierdzenie „suma kątów w trójkącie wynosi 180°” jest prawdziwe, a twierdzenie „suma kątów w trójkącie wynosi 137°” jest fałszywe. Zasadniczo w geometrii euklidesowej każde stwierdzenie jest albo fałszywe, albo prawdziwe i nie ma trzeciej opcji. A na początku XX wieku matematycy naiwnie wierzyli, że tę samą sytuację należy zaobserwować w każdym logicznie spójnym systemie.

A potem, w 1931 roku, pewien wiedeński matematyk w okularach Kurt Gödel opublikował krótki artykuł, który po prostu wstrząsnął całym światem tak zwanej „logiki matematycznej”. Po długich i skomplikowanych wstępach matematycznych i teoretycznych ustalił dosłownie, co następuje. Weźmy dowolne stwierdzenie typu: „Założenie nr 247 w tym systemie aksjomatów jest logicznie nie do udowodnienia” i nazwijmy je „twierdzeniem A”. Zatem Gödel po prostu udowodnił, co następuje niesamowita nieruchomość każdy systemy aksjomatów:

„Jeśli można udowodnić twierdzenie A, to można udowodnić twierdzenie nie-A.”

Innymi słowy, jeśli uda się udowodnić słuszność stwierdzenia „założenie 247 Nie da się udowodnić”, wówczas można udowodnić słuszność twierdzenia „założenie 247 udowodnione" To znaczy, wracając do sformułowania drugiego problemu Hilberta, jeśli system aksjomatów jest kompletny (to znaczy można udowodnić dowolne zawarte w nim stwierdzenie), to jest on sprzeczny.

Jedynym wyjściem z tej sytuacji jest przyjęcie niekompletnego systemu aksjomatów. Oznacza to, że musimy pogodzić się z faktem, że w kontekście dowolnego systemu logicznego nadal będziemy mieć stwierdzenia „typu A”, które są oczywiście prawdziwe lub fałszywe - i możemy jedynie ocenić ich prawdziwość poza ramach przyjętej przez nas aksjomatyki. Jeśli nie ma takich twierdzeń, to nasze aksjomatyki są sprzeczne i w ich ramach nieuchronnie znajdą się sformułowania, które można zarówno udowodnić, jak i obalić.

A więc sformułowanie Pierwszy,Lub słaby Twierdzenia Gödla o niezupełności: „Każdy formalny system aksjomatów zawiera nierozwiązane założenia”. Ale Gödel nie poprzestał na formułowaniu i udowadnianiu drugi, Lub mocny Twierdzenie Gödla o niezupełności: „Logicznej kompletności (lub niekompletności) jakiegokolwiek systemu aksjomatów nie można udowodnić w ramach tego systemu. Aby to udowodnić lub obalić, potrzebne są dodatkowe aksjomaty (wzmocnienie systemu).”

Bezpieczniej byłoby sądzić, że twierdzenia Gödla mają charakter abstrakcyjny i nie dotyczą nas, a jedynie obszarów wzniosłej logiki matematycznej, a tak naprawdę okazało się, że są one bezpośrednio związane ze strukturą ludzkiego mózgu. Angielski matematyk i fizyk Roger Penrose (ur. 1931) wykazał, że twierdzenia Gödla można wykorzystać do udowodnienia istnienia fundamentalnych różnic między ludzkim mózgiem a komputerem. Znaczenie jego rozumowania jest proste. Komputer działa ściśle logicznie i nie jest w stanie określić, czy zdanie A jest prawdziwe, czy fałszywe, jeśli wykracza poza aksjomatykę, a takie zdania, zgodnie z twierdzeniem Gödla, nieuchronnie istnieją. Osoba, mając do czynienia z tak logicznie niepotwierdzonym i niepodważalnym twierdzeniem A, zawsze jest w stanie określić jego prawdziwość lub fałszywość – na podstawie codziennego doświadczenia. Przynajmniej w tym ludzki mózg lepszy od komputera powiązanego przez pure obwody logiczne. Ludzki mózg jest w stanie zrozumieć całą głębię prawdy zawartej w twierdzeniach Gödla, ale mózg komputera nigdy tego nie zrobi. Dlatego ludzki mózg nie jest niczym innym jak komputerem. Jest zdolny decyzje, a test Turinga przejdzie pomyślnie.

Zastanawiam się, czy Hilbert miał pojęcie, jak daleko zaprowadzą nas jego pytania?

Kurta Godela, 1906-78

Austriacki, następnie amerykański matematyk. Urodzony w Brünn (obecnie Brno, Czechy). Ukończył Uniwersytet Wiedeński, gdzie pozostał nauczycielem na wydziale matematyki (od 1930 r. – profesor). W 1931 roku opublikował twierdzenie, które później otrzymało jego imię. Będąc osobą czysto apolityczną, niezwykle przeżył zamordowanie swojego przyjaciela i kolegi z wydziału przez nazistowskiego studenta i popadł w głęboką depresję, której nawroty prześladowały go do końca życia. W latach 30. wyemigrował do USA, ale wrócił do rodzinnej Austrii i ożenił się. W 1940 r., u szczytu wojny, został zmuszony do ucieczki do Ameryki w tranzycie przez ZSRR i Japonię. Przez pewien czas pracował w Princeton Institute for Advanced Study. Niestety psychika naukowca nie wytrzymała tego i zmarł w klinice psychiatrycznej z głodu, odmawiając jedzenia, gdyż był przekonany, że go otrują.

Każdy system aksjomatów matematycznych, zaczynając od pewnego poziomu złożoności, jest albo wewnętrznie sprzeczny, albo niekompletny.

W 1900 roku w Paryżu odbyła się Światowa Konferencja Matematyków, na której David Hilbert (1862–1943) przedstawił w formie tez 23 najważniejsze, jego zdaniem, problemy, które teoretycy nadchodzącego XX wieku musieli rozwiązać. Numer dwa na jego liście to jeden z tych prostych problemów, których rozwiązanie wydaje się oczywiste, dopóki nie zagłębisz się nieco głębiej. We współczesnym ujęciu brzmiało pytanie: czy matematyka jest samowystarczalna? Drugie zadanie Hilberta sprowadzało się do konieczności ścisłego udowodnienia, że system aksjomatów – podstawowych twierdzeń przyjętych w matematyce za podstawę bez dowodu – jest doskonały i kompletny, to znaczy pozwala matematycznie opisać wszystko, co istnieje. Należało wykazać, że możliwe jest zdefiniowanie takiego systemu aksjomatów, aby po pierwsze były one wzajemnie spójne, a po drugie, można było z nich wyciągnąć wniosek o prawdziwości lub fałszywości dowolnego twierdzenia.

Weźmy przykład ze szkolnej geometrii. W standardowej planimetrii euklidesowej (geometrii na płaszczyźnie) można wykazać ponad wszelką wątpliwość, że prawdziwe jest stwierdzenie „suma kątów w trójkącie wynosi 180°”, a stwierdzenie „suma kątów w trójkącie wynosi 137° °” jest fałszywe. Zasadniczo w geometrii euklidesowej każde stwierdzenie jest albo fałszywe, albo prawdziwe i nie ma trzeciej opcji. A na początku XX wieku matematycy naiwnie wierzyli, że tę samą sytuację należy zaobserwować w każdym logicznie spójnym systemie.

A potem, w 1931 roku, pewien wiedeński matematyk w okularach Kurt Gödel opublikował krótki artykuł, który po prostu wstrząsnął całym światem tak zwanej „logiki matematycznej”. Po długich i skomplikowanych wstępach matematycznych i teoretycznych ustalił dosłownie, co następuje. Weźmy dowolne stwierdzenie typu: „Założenie nr 247 w tym systemie aksjomatów jest logicznie nie do udowodnienia” i nazwijmy je „twierdzeniem A”. Zatem Gödel po prostu udowodnił następującą niesamowitą właściwość dowolnego systemu aksjomatów:

„Jeśli można udowodnić twierdzenie A, to można udowodnić twierdzenie nie-A.”

Innymi słowy, jeśli można udowodnić prawdziwość stwierdzenia „założenie 247 jest nie do udowodnienia”, to można również udowodnić prawdziwość stwierdzenia „założenie 247 jest do udowodnienia”. To znaczy, wracając do sformułowania drugiego problemu Hilberta, jeśli system aksjomatów jest kompletny (to znaczy można udowodnić dowolne zawarte w nim stwierdzenie), to jest on sprzeczny.

Jedynym wyjściem z tej sytuacji jest przyjęcie niekompletnego systemu aksjomatów. Oznacza to, że musimy pogodzić się z faktem, że w kontekście dowolnego systemu logicznego nadal będziemy mieli stwierdzenia „typu A”, które są w sposób oczywisty prawdziwe lub fałszywe – a ich prawdziwość możemy oceniać jedynie poza ramami aksjomatyki, które posiadamy przyjęty. Jeśli nie ma takich twierdzeń, to nasze aksjomatyki są sprzeczne i w ich ramach nieuchronnie znajdą się sformułowania, które można zarówno udowodnić, jak i obalić.

Zatem sformułowanie pierwszego, czyli słabego twierdzenia Gödla o niezupełności: „Każdy formalny system aksjomatów zawiera nierozwiązane założenia”. Ale Gödel nie poprzestał na tym, formułując i udowadniając drugie, mocne twierdzenie Gödla o niezupełności: „Logicznej kompletności (lub niekompletności) jakiegokolwiek systemu aksjomatów nie można udowodnić w ramach tego systemu. Aby to udowodnić lub obalić, potrzebne są dodatkowe aksjomaty (wzmocnienie systemu).”

Bezpieczniej byłoby sądzić, że twierdzenia Gödla mają charakter abstrakcyjny i nie dotyczą nas, a jedynie obszarów wzniosłej logiki matematycznej, a tak naprawdę okazało się, że są one bezpośrednio związane ze strukturą ludzkiego mózgu. Angielski matematyk i fizyk Roger Penrose (ur. 1931) wykazał, że twierdzenia Gödla można wykorzystać do udowodnienia istnienia fundamentalnych różnic między ludzkim mózgiem a komputerem. Znaczenie jego rozumowania jest proste. Komputer działa ściśle logicznie i nie jest w stanie określić, czy zdanie A jest prawdziwe, czy fałszywe, jeśli wykracza poza aksjomatykę, a takie zdania, zgodnie z twierdzeniem Gödla, nieuchronnie istnieją. Osoba, mając do czynienia z tak logicznie niepotwierdzonym i niepodważalnym twierdzeniem A, zawsze jest w stanie określić jego prawdziwość lub fałszywość – na podstawie codziennego doświadczenia. Przynajmniej pod tym względem ludzki mózg jest lepszy od komputera ograniczonego czystymi obwodami logicznymi. Ludzki mózg jest w stanie zrozumieć całą głębię prawdy zawartej w twierdzeniach Gödla, ale mózg komputera nigdy tego nie zrobi. Dlatego ludzki mózg nie jest niczym innym jak komputerem. Potrafi podejmować decyzje i testować Turing przejdzie z powodzeniem.

Zastanawiam się, czy Hilbert miał pojęcie, jak daleko zaprowadzą nas jego pytania?

Kurta Gödla
Kurt Godel, 1906–78

Komentarze: 0

Jak rozwija się model naukowy w nauki przyrodnicze? Gromadzi się doświadczenia codzienne lub naukowe, ich kamienie milowe są starannie formułowane w formie postulatów i stanowią podstawę modelu: zbioru stwierdzeń akceptowanych przez wszystkich, którzy pracują w ramach tego modelu.

Anatolij Wasserman

W 1930 roku Kurt Gödel udowodnił dwa twierdzenia, które przetłumaczone z języka matematycznego na język ludzki mają w przybliżeniu następujące znaczenie: Każdy system aksjomatów wystarczająco bogaty, aby można go było zastosować do zdefiniowania arytmetyki, będzie albo niekompletny, albo sprzeczny. Nie kompletny system- oznacza to, że w systemie możliwe jest sformułowanie twierdzenia, którego za pomocą tego systemu nie da się ani udowodnić, ani obalić. Ale Bóg z definicji jest ostateczną przyczyną wszystkich przyczyn. Z punktu widzenia matematyki oznacza to, że wprowadzenie aksjomatu o Bogu uzupełnia całą naszą aksjomatę. Jeśli Bóg istnieje, to każde twierdzenie można udowodnić lub obalić, odnosząc się w ten czy inny sposób do Boga. Jednak według Gödla cały system aksjomatów jest nieuchronnie sprzeczny. Oznacza to, że jeśli wierzymy, że Bóg istnieje, to zmuszeni jesteśmy dojść do wniosku, że w przyrodzie możliwe są sprzeczności. A skoro nie ma sprzeczności, bo inaczej cały nasz świat by się od tych sprzeczności zawalił, to trzeba dojść do wniosku, że istnienia Boga nie da się pogodzić z istnieniem przyrody.

Sosiński A. B.

Twierdzenie Gödla, wraz z odkryciami teorii względności, mechaniki kwantowej i DNA, jest powszechnie uważane za największe osiągnięcie naukowe XX wiek. Dlaczego? Jaka jest jego istota? Jakie jest jego znaczenie? Na te pytania podczas swojego wykładu w ramach projektu „ Wykłady publiczne„Polit.ru” ujawnia Aleksieja Bronisławowicza Sosińskiego, matematyka, profesora Niezależnego Uniwersytetu Moskiewskiego, oficera Orderu Palm Akademickich Republiki Francuskiej, laureata Nagrody Rządu Rosyjskiego w dziedzinie edukacji w 2012 roku. W szczególności podano kilka różnych jego sformułowań, opisano trzy podejścia do jego dowodu (Kołmogorow, sam Chaitin i Gödel) oraz jego znaczenie dla matematyki, fizyki, Informatyka i filozofia.

Uspienski V. A.

Wykład poświęcony jest syntaktycznej wersji twierdzenia Gödla o niezupełności. Sam Gödel udowodnił wersję syntaktyczną, stosując założenie silniejsze niż spójność, a mianowicie tzw. spójność omega.

Uspienski V. A.

Wykłady Letnia szkoła « Nowoczesna matematyka", Dubna.

Jedno z najsłynniejszych twierdzeń logiki matematycznej oznacza szczęście i pecha jednocześnie. Pod tym względem przypomina szczególną teorię względności Einsteina. Z jednej strony prawie każdy coś o nich słyszał. Z kolei w popularnej interpretacji teoria Einsteina, jak wiadomo, „mówi, że wszystko na świecie jest względne”. Oraz twierdzenie Gödla o niezupełności (zwane dalej po prostu TGN), w mniej więcej tym samym, swobodnie potocznym sformułowaniu, „dowodzi, że istnieją rzeczy niepojęte dla ludzkiego umysłu”. I dlatego niektórzy próbują zaadaptować to jako argument przeciwko materializmowi, inni zaś, wręcz przeciwnie, za jego pomocą udowadniają, że Boga nie ma. Zabawne jest nie tylko to, że obie strony nie mogą mieć jednocześnie racji, ale także to, że ani jedna, ani druga nie zadają sobie trudu, aby dowiedzieć się, co tak naprawdę stwierdza to twierdzenie.

Więc co? Poniżej postaram się Wam o tym opowiedzieć „na palcach”. Moja prezentacja nie będzie oczywiście rygorystyczna i intuicyjna, ale proszę matematyków, aby nie oceniali mnie surowo. Możliwe, że dla nie-matematyków (do których zresztą i ja) będzie coś nowego i przydatnego w tym, co opisano poniżej.

Logika matematyczna jest rzeczywiście nauką dość złożoną i, co najważniejsze, mało znaną. Wymaga ostrożnych i rygorystycznych manewrów, przy czym ważne jest, aby nie mylić tego, co faktycznie zostało udowodnione, z tym, co „już jasne”. Mam jednak nadzieję, że do zrozumienia poniższego „zarysu dowodu TGN” czytelnikowi będzie potrzebna jedynie wiedza z zakresu szkolnej matematyki/informatyki, umiejętności logiczne myślenie i 15-20 minut czasu.

Upraszczając nieco, TGN twierdzi, że w wystarczająco skomplikowanych językach istnieją stwierdzenia, których nie da się udowodnić. Ale w tym zdaniu prawie każde słowo wymaga wyjaśnienia.

Zacznijmy od ustalenia, czym jest dowód. Weźmy szkolne zadanie arytmetyczne. Załóżmy na przykład, że musisz udowodnić poprawność następującego prostego wzoru: „ ” (przypomnę, że symbol ten brzmi „dla dowolnego” i nazywany jest „kwantyfikatorem uniwersalnym”). Możesz to udowodnić, identycznie przekształcając, powiedzmy, w ten sposób:

Przejście z jednej formuły do drugiej następuje według pewnych dobrze znanych zasad. Przejście z czwartej formuły do piątej nastąpiło, powiedzmy, ponieważ każda liczba jest sobie równa - jest to aksjomat arytmetyki. Zatem cała procedura dowodowa tłumaczy formułę na wartość logiczną PRAWDA. Rezultatem może być również KŁAMSTWO - jeśli odrzucimy jakąś formułę. W tym przypadku udowodnilibyśmy jego zaprzeczenie. Można sobie wyobrazić program (a takie programy faktycznie napisano), który udowadniałby podobne (i bardziej złożone) stwierdzenia bez interwencji człowieka.

Ujmijmy to samo trochę bardziej formalnie. Załóżmy, że mamy zbiór składający się z ciągów znaków jakiegoś alfabetu i istnieją reguły, według których z tych ciągów możemy wybrać podzbiór tzw. sprawozdania- czyli wyrażenia znaczące gramatycznie, z których każde jest prawdziwe lub fałszywe. Można powiedzieć, że istnieje funkcja, która kojarzy instrukcje z jedną z dwóch wartości: PRAWDA lub FAŁSZ (to znaczy odwzorowuje je na zbiór boolowski składający się z dwóch elementów).

Nazwijmy taką parę - zbiór instrukcji i funkcję od do - „język wypowiedzi”. Należy zauważyć, że w sensie potocznym pojęcie języka jest nieco szersze. Na przykład rosyjskie zdanie "Chodź tu!" ani prawdziwe, ani fałszywe, czyli z punktu widzenia logiki matematycznej nie jest stwierdzeniem.

Do tego, co następuje, potrzebujemy koncepcji algorytmu. Nie będę tu podawać formalnej definicji tego zagadnienia – to by nas zaprowadziło dość daleko na manowce. Ograniczę się do nieformalnych: "algorytm" to ciąg jednoznacznych instrukcji („program”), który za ostateczny numer kroki konwertuje dane źródłowe na wyniki. To, co jest napisane kursywą, jest zasadniczo ważne - jeśli program zapętli się na jakichś danych początkowych, to nie opisuje algorytmu. Dla uproszczenia i zastosowania się do naszego przypadku czytelnik może przyjąć, że algorytm to program napisany w dowolnym znanym mu języku programowania, który dla dowolnych danych wejściowych z danej klasy ma gwarancję zakończenia swojej pracy i wygenerowania wyniku logicznego.

Zadajmy sobie pytanie: dla każdej funkcji istnieje „algorytm dowodzący” (w skrócie "dedukcyjny"), równoważny tej funkcji, to znaczy przekształcający każdą instrukcję na dokładnie tę samą wartość logiczną, co ona? To samo pytanie można sformułować bardziej zwięźle w następujący sposób: czy każda funkcja jest na zbiorze instrukcji obliczeniowy? Jak już się domyślacie, z ważności TGN wynika, że nie, nie każda funkcja - istnieją funkcje tego typu nieobliczalne. Innymi słowy, nie każde prawdziwe stwierdzenie można udowodnić.

Bardzo możliwe, że to stwierdzenie wywoła w Tobie wewnętrzny protest. Wynika to z kilku okoliczności. Po pierwsze, kiedy jesteśmy nauczani szkolna matematyka, wówczas czasami powstaje fałszywe wrażenie niemal całkowitej identyczności wyrażeń „twierdzenie jest prawdziwe” i „twierdzenie można udowodnić lub zweryfikować”. Ale jeśli się nad tym zastanowić, nie jest to wcale oczywiste. Niektóre twierdzenia można udowodnić w prosty sposób (na przykład poprzez wypróbowanie niewielkiej liczby opcji), inne zaś są bardzo trudne. Rozważmy na przykład słynne Ostatnie Twierdzenie Fermata:

którego dowód znaleziono dopiero trzy i pół wieku po pierwszym sformułowaniu (i nie jest on wcale elementarny). Należy rozróżnić prawdziwość twierdzenia od jego możliwości udowodnienia. Znikąd nie wynika, że nie ma prawdziwych, ale niemożliwych do udowodnienia (i nie do końca weryfikowalnych) twierdzeń.

Drugi intuicyjny argument przeciwko TGN jest bardziej subtelny. Powiedzmy, że mamy jakieś stwierdzenie, którego nie da się udowodnić (w ramach tej dedukcji). Co powstrzymuje nas od przyjęcia tego jako nowego aksjomatu? W ten sposób nieco skomplikujemy nasz system dowodowy, ale nie jest to straszne. Argument ten byłby całkowicie poprawny, gdyby istniała skończona liczba twierdzeń, których nie da się udowodnić. W praktyce może się zdarzyć następująca sytuacja: postulując nowy aksjomat, natkniesz się na nowe stwierdzenie, którego nie da się udowodnić. Jeśli przyjmiesz to jako kolejny aksjomat, natkniesz się na trzeci. I tak w nieskończoność. Mówią, że odliczenie pozostanie niekompletny. Możemy również wymusić zakończenie algorytmu sprawdzającego w skończonej liczbie kroków z pewnym wynikiem dla dowolnej wypowiedzi języka. Ale jednocześnie zacznie kłamać – prowadząc do prawdy w przypadku błędnych stwierdzeń lub do kłamstw – w imieniu wiernych. W takich przypadkach mówią, że odliczenie sprzeczny. Zatem inne sformułowanie TGN brzmi następująco: „Istnieją języki zdań, dla których niemożliwa jest całkowita spójna dedukcja” - stąd nazwa twierdzenia.

Czasami nazywane „twierdzeniem Gödla” stwierdza, że każda teoria zawiera problemy, których nie można rozwiązać w ramach samej teorii i wymagają jej uogólnienia. W pewnym sensie jest to prawdą, choć sformułowanie to raczej zaciemnia problem niż go wyjaśnia.

Zaznaczę też, że gdybyśmy mówili o znanych funkcjach odwzorowujących na nią zbiór liczb rzeczywistych, to „nieobliczalność” tej funkcji nikogo by nie zdziwiła (tylko nie mylcie „funkcji obliczeniowych” z „liczbami obliczalnymi” ” - to są różne rzeczy). Każde dziecko w wieku szkolnym wie, że, powiedzmy, w przypadku funkcji trzeba mieć dużo szczęścia z argumentem, aby proces obliczenia dokładnej wartości reprezentacja dziesiętna Wartość tej funkcji kończyła się w skończonej liczbie kroków. Ale najprawdopodobniej obliczysz to za pomocą nieskończonej serii, a to obliczenie nigdy nie doprowadzi do dokładnego wyniku, chociaż może być tak blisko, jak chcesz - po prostu dlatego, że wartość sinusa większości argumentów jest irracjonalna. TGN po prostu mówi nam, że nawet wśród funkcji, których argumentami są ciągi znaków i których wartością jest zero lub jeden, istnieją również funkcje nieprzeliczalne, chociaż są one zbudowane w zupełnie inny sposób.

Dla dalszych celów opiszemy „język arytmetyki formalnej”. Rozważmy klasę ciągów tekstowych o skończonej długości, składających się z cyfr arabskich, zmiennych (liter Alfabet łaciński), otrzymujący walory przyrodnicze, spacje, znaki działania arytmetyczne, równość i nierówność, kwantyfikatory („istnieje”) i („dla dowolnego”) i być może jakieś inne symbole (ich dokładna liczba i skład nie są dla nas istotne). Oczywiste jest, że nie wszystkie takie linie mają znaczenie (na przykład „ ” to nonsens). Podzbiór wyrażeń znaczących z tej klasy (czyli ciągów znaków, które z punktu widzenia zwykłej arytmetyki są prawdziwe lub fałszywe) będzie naszym zbiorem instrukcji.

Przykłady formalnych instrukcji arytmetycznych:

itp. Nazwijmy teraz „formułę z wolnym parametrem” (FSP) ciąg znaków, który stanie się instrukcją, jeśli jako ten parametr zostanie podstawiona liczba naturalna. Przykłady FSP (z parametrem):

itp. Innymi słowy, FSP są równoważne funkcjom argumentów naturalnych z wartościami logicznymi.

Oznaczmy zbiór wszystkich FSP literą . Jasne jest, że można to uporządkować (np. najpierw wypisujemy wzory jednoliterowe uporządkowane alfabetycznie, potem formuły dwuliterowe itp.; nie jest dla nas istotne, w jakim alfabecie nastąpi uporządkowanie). Zatem każdy FSP odpowiada jego numerowi na uporządkowanej liście i będziemy to oznaczać .

Przejdźmy teraz do szkicu dowodu TGN w następującym sformułowaniu:

Dla języka zdań arytmetyki formalnej nie ma całkowicie spójnego systemu dedukcyjnego.

Udowodnimy to przez zaprzeczenie.

Załóżmy więc, że taki system dedukcyjny istnieje. Opiszmy następujący algorytm pomocniczy, który przypisuje wartość logiczną liczbie naturalnej w następujący sposób:

Mówiąc najprościej, algorytm daje wartość TRUE wtedy i tylko wtedy, gdy wynik podstawienia własnego numeru w FSP na naszej liście daje fałszywe stwierdzenie.

Tutaj dochodzimy do jedynego miejsca, w którym poproszę czytelnika, aby uwierzył mi na słowo.

Jest oczywiste, że przy powyższych założeniach dowolny FSP można porównać do algorytmu zawierającego na wejściu liczbę naturalną i wartość logiczną na wyjściu. Odwrotność jest mniej oczywista:

Dowód tego lematu wymagałby przynajmniej formalnej, a nie intuicyjnej definicji pojęcia algorytmu. Jeśli jednak się nad tym chwilę zastanowić, jest to całkiem prawdopodobne. W rzeczywistości algorytmy są zapisane języki algorytmiczne, wśród których są takie egzotyczne, jak na przykład Brainfuck, składający się z ośmiu jednoznakowych słów, na których mimo wszystko można zaimplementować dowolny algorytm. Byłoby dziwne, gdyby bogatszy język formuł arytmetyki formalnej, który opisaliśmy, okazał się uboższy – chociaż niewątpliwie nie za bardzo nadaje się do zwykłego programowania.

Minąwszy to śliskie miejsce, szybko docieramy do końca.

Powyżej opisaliśmy algorytm. Zgodnie z lematem, o który prosiłem, istnieje równoważny FSP. Ma jakiś numer na liście - powiedzmy . Zadajmy sobie pytanie, co jest równe? Niech to będzie PRAWDA. Zatem zgodnie z konstrukcją algorytmu (a więc i równoważnej mu funkcji) oznacza to, że wynikiem podstawienia liczby do funkcji jest FAŁSZ. Odwrotność sprawdza się w ten sam sposób: z FAŁSZ wynika PRAWDA. Doszliśmy do sprzeczności, co oznacza, że pierwotne założenie jest błędne. Zatem nie ma kompletnego, spójnego systemu dedukcyjnego dla arytmetyki formalnej. co było do okazania

Warto tu przypomnieć Epimenidesa (patrz portret w tytule), który, jak wiadomo, oświadczył, że wszyscy Kreteńczycy są kłamcami, sam będąc Kreteńczykiem. W bardziej zwięzłym sformułowaniu jego stwierdzenie (znane jako „paradoks kłamcy”) można wyrazić następująco: „Kłamię”. To właśnie tego rodzaju twierdzenie, które samo w sobie obwieszcza jego fałszywość, wykorzystaliśmy jako dowód.

Podsumowując, chcę zauważyć, że TGN nie twierdzi nic szczególnie zaskakującego. Przecież wszyscy od dawna są przyzwyczajeni do tego, że nie wszystkie liczby można przedstawić jako stosunek dwóch liczb całkowitych (pamiętacie, że to stwierdzenie ma bardzo elegancki dowód, który ma ponad dwa tysiące lat?). I pierwiastki wielomianów z racjonalne współczynniki Nie wszystkie liczby też są. A teraz okazuje się, że nie wszystkie funkcje argumentu naturalnego są obliczalne.

Szkic podanego dowodu dotyczył arytmetyki formalnej, ale łatwo zauważyć, że TGN ma zastosowanie do wielu innych języków zdań. Oczywiście nie wszystkie języki są takie. Na przykład zdefiniujmy język w następujący sposób:

„Dowolne zdanie język chiński jest stwierdzeniem prawdziwym, jeśli jest zawarte w księdze cytatów towarzysza Mao Zedonga, i nieprawidłowym, jeśli nie jest zawarte.”

Wtedy odpowiadający mu kompletny i spójny algorytm dowodzenia (można go nazwać „dogmatycznym dedukcjonizmem”) wygląda mniej więcej tak:

„Przeglądaj księgę cytatów towarzysza Mao Zedonga, aż znajdziesz powiedzenie, którego szukasz. Jeśli zostanie znaleziony, to jest to prawda, ale jeśli księga cytatów się skończyła, a stwierdzenie nie zostało znalezione, to jest błędne”.

To, co nas tutaj ratuje, to fakt, że każda książka z cytatami jest oczywiście skończona, więc proces „udowadniania” nieuchronnie się zakończy. Zatem TGN nie ma zastosowania do języka twierdzeń dogmatycznych. Ale mówiliśmy o językach złożonych, prawda?

na temat: „TWIERDZENIE GODLA”

Kurta Gödla

Kurt Gödel jest wiodącym ekspertem ds logika matematyczna– urodzony 28 kwietnia 1906 w Brunn (obecnie Brno, Czechy). Ukończył studia na Uniwersytecie Wiedeńskim, gdzie obronił rozprawę doktorską, a w latach 1933–1938 był adiunktem. Po Anschlussie wyemigrował do USA. Od 1940 do 1963 Gödel pracował w Instytucie Princeton Wyższe studia. Gödel – doktorat honoris causa uniwersytetów Yale i Harvard, członek Akademia Narodowa Nauki USA i Amerykańskie Towarzystwo Filozoficzne.

W 1951 roku najwyższe wyróżnienie otrzymał Kurt Gödel nagroda naukowa USA - Nagroda Einsteina. W artykule poświęconym temu wydarzeniu inny ważny matematyk naszych czasów, John von Neumann, napisał: „Wkład Kurta Gödla we współczesną logikę jest naprawdę monumentalny. To coś więcej niż tylko pomnik. To kamień milowy oddzielający dwie epoki... Bez żadnej przesady można powiedzieć, że dzieło Gödla radykalnie zmieniło sam przedmiot logiki jako nauki.

Rzeczywiście, nawet sucha lista osiągnięć Gödla w logice matematycznej pokazuje, że ich autor w zasadzie położył podwaliny pod całe działy tej nauki: teorię modeli (1930; tzw. twierdzenie o zupełności wąskiego rachunku predykatów, pokazujące, z grubsza, wystarczalność środków „logiki formalnej” „do udowodnienia wszystkich prawdziwych zdań wyrażonych w jej języku), logika konstruktywna (1932–1933; skutkuje możliwością zredukowania pewnych klas zdań logiki klasycznej do ich intuicjonistycznych odpowiedników, co położyło podstawą do systematycznego stosowania „operacji osadzania”, które pozwalają na taką redukcję różnorodnych systemy logiczne siebie), arytmetykę formalną (1932–1933; wynika o możliwości sprowadzenia arytmetyki klasycznej do arytmetyki intuicjonistycznej, pokazując w pewnym sensie zgodność pierwszej z drugą), teorię algorytmów i funkcji rekurencyjnych (1934; definicja koncepcji ogólnej funkcji rekurencyjnej, która z jednej strony odegrała decydującą rolę w ustaleniu algorytmicznej nierozwiązywalności szeregu najważniejszych problemów matematyki, a z drugiej w realizacji problemów logiczno-matematycznych na komputerach elektronicznych, z drugiej inne), aksjomatyczna teoria mnogości (1938; dowód względnej spójności aksjomatu wyboru i hipotezy kontinuum Cantora z aksjomatów teorii mnogości, co położyło podwaliny pod szereg ważnych wyników dotyczących względnej spójności i niezależności zasad teorii mnogości ).

Twierdzenie Gödla o niezupełności

Wstęp

W 1931 roku w jednym z niemieckich czasopism naukowych ukazał się stosunkowo niewielki artykuł pod raczej zastraszającym tytułem „O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica i systemów pokrewnych”. Jej autorem był dwudziestopięcioletni matematyk z woj Uniwersytet Wiedeński Kurta Gödela, który później pracował w Instytucie Studiów Zaawansowanych w Princeton. Dzieło to odegrało decydującą rolę w historii logiki i matematyki. W decyzji Uniwersytetu Harvarda o przyznaniu Gödelowi tytułu honorowego doktorat(1952) została scharakteryzowana jako jedna z Największe osiągnięcia nowoczesna logika.

Jednak w momencie publikacji nie było też nazwy dzieła Gödla. Dla większości matematyków żadna z jego treści nie miała żadnego znaczenia. Wspomniana w tytule Principia Mathematica to monumentalny, trzytomowy traktat Alfreda Northa Whiteheada i Bertranda Russella na temat logiki matematycznej i podstaw matematyki; znajomość traktatu w żadnym wypadku nie była warunek konieczny Dla udana praca w większości działów matematyki. Zainteresowanie problematyką poruszaną w twórczości Gödla zawsze było domeną bardzo małej grupy naukowców. Jednocześnie rozumowanie podane przez Gödla w jego dowodach było tak niezwykłe jak na tamte czasy. Że ich pełne zrozumienie wymagało wyjątkowego opanowania tematu i znajomości literatury poświęconej tym jakże specyficznym problemom.

Pierwsze twierdzenie o niezupełności

Pierwsze twierdzenie Gödla o niezupełności, najwyraźniej, jest najbardziej znaczącym wynikiem w logice matematycznej. Brzmi to tak:

Dla dowolnej spójnej teorii formalnej i obliczeniowej, w której można udowodnić podstawowe twierdzenia arytmetyczne, można skonstruować prawdziwe twierdzenie arytmetyczne, którego prawdziwości nie można udowodnić w ramach teorii. Innymi słowy, całkowicie dowolny przydatna teoria, wystarczający do przedstawienia arytmetyki, nie może być jednocześnie spójny i kompletny.

Tutaj słowo „teoria” oznacza „ nieskończony zestaw„twierdzenia, z których niektóre uważa się za prawdziwe bez dowodu (takie twierdzenia nazywane są aksjomatami), podczas gdy inne (twierdzenia) można wydedukować z aksjomatów i dlatego uważa się je (udowodniono) za prawdziwe. Wyrażenie „teoretycznie dające się udowodnić” oznacza „wyprowadzane z aksjomatów i prymitywów teorii (stałe symbole alfabetu) przy użyciu standardowej logiki (pierwszego rzędu)”. Teoria jest spójna (spójna), jeśli nie można udowodnić w niej twierdzenia sprzecznego. Wyrażenie „można skonstruować” oznacza, że istnieje pewna mechaniczna procedura (algorytm), która może skonstruować zdanie w oparciu o aksjomaty, prymitywy i logikę pierwszego rzędu. „Elementarna arytmetyka” obejmuje operacje dodawania i mnożenia na liczbach naturalnych. Powstałe w ten sposób prawdziwe, ale niemożliwe do udowodnienia stwierdzenie jest często określane w przypadku danej teorii jako „ciąg Gödla”, ale w teorii istnieje nieskończona liczba innych twierdzeń, które mają tę samą właściwość: nie dającą się udowodnić prawdę w teorii.

Założenie, że teoria jest obliczalna, oznacza, że w zasadzie możliwa jest implementacja algorytmu komputerowego ( program komputerowy), który (jeśli pozwoli się na obliczenia w dowolnie długim czasie, aż do nieskończoności) obliczy listę wszystkich twierdzeń teorii. W rzeczywistości wystarczy obliczyć tylko listę aksjomatów i z takiej listy można skutecznie wyprowadzić wszystkie twierdzenia.

Pierwsze twierdzenie o niezupełności zostało zatytułowane „Twierdzenie VI” w artykule Gödla z 1931 roku O zdaniach formalnie nierozstrzygalnych w Principia Mathematica i systemach pokrewnych I. W oryginalnym nagraniu Gödla brzmiało to tak:

„Ogólny wniosek na temat istnienia zdań nierozstrzygalnych jest następujący:

Twierdzenie VI .

Dla każdej klasy rekurencyjnej spójnej z ω k FORMUŁA istnieją rekurencyjne OZNAKI R takie, że ani (w gen R), ani ¬( w gen R)nie należą do Flg (k)(gdzie v jest DARMOWA ZMIENNA R ) ».

Przeznaczenie Flg pochodzi od niego. Folgerungsmenge– wiele sekwencji, gen pochodzi od niego. Uogólnienie– uogólnienie.

Z grubsza rzecz biorąc, oświadczenie Gödla G stwierdza: „prawda G nie da się udowodnić.” Jeśli G można by udowodnić w ramach teorii, wówczas w tym przypadku teoria zawierałaby twierdzenie, które jest sprzeczne sama w sobie, a zatem teoria byłaby sprzeczna. Ale jeśli G nie do udowodnienia, to jest prawdziwa, a zatem teoria jest niekompletna (stwierdzenie G nie da się z tego wywnioskować).

To jest wyjaśnienie w prostym języku angielskim język naturalny, a zatem nie jest całkowicie matematycznie rygorystyczne. Aby zapewnić rygorystyczny dowód, Gödel ponumerował twierdzenia liczbami naturalnymi. W tym przypadku teoria opisująca liczby również należy do zbioru twierdzeń. Pytania o dowodliwość twierdzeń można w tym przypadku przedstawić w postaci pytań o własności liczb naturalnych, które muszą być obliczalne, jeśli teoria jest kompletna. W tym sensie stwierdzenie Gödla mówi, że nie ma liczby o jakiejś określonej właściwości. Liczba posiadająca tę własność będzie dowodem niespójności teorii. Jeśli taka liczba istnieje, teoria jest niespójna, wbrew pierwotnym założeniom. Zakładając więc, że teoria jest spójna (co założono w przesłance twierdzenia), okazuje się, że taka liczba nie istnieje, a twierdzenie Gödla jest prawdziwe, ale w ramach teorii nie da się tego udowodnić ( stąd teoria jest niekompletna). Ważnym punktem koncepcyjnym jest to, że aby uznać stwierdzenie Gödla za prawdziwe, należy założyć, że teoria jest spójna.

Drugie twierdzenie Gödla o niezupełności

Drugie twierdzenie Gödla o niezupełności brzmi następująco:

Dla każdej formalnie rekurencyjnie przeliczalnej (tj. efektywnie wygenerowanej) teorii T, w tym podstawowych arytmetycznych twierdzeń prawdy i pewnych formalnych twierdzeń dowodowych, tę teorię T zawiera twierdzenie o własnej spójności wtedy i tylko wtedy, gdy teoria T jest niespójna.

Innymi słowy, za pomocą tej teorii nie można udowodnić spójności dostatecznie bogatej teorii. Może się jednak okazać, że zgodność z jednym konkretna teoria można zainstalować przy użyciu innego, mocniejszego teoria formalna. Ale wtedy pojawia się pytanie o spójność tej drugiej teorii itd.

Aby to udowodnić, użyj tego twierdzenia inteligentna działalność Nie sprowadza się to do obliczeń, wielu próbowało. Na przykład w 1961 roku słynny logik John Lucas wymyślił podobny program. Jego rozumowanie okazało się dość kruche – postawił jednak zadanie szerzej. Roger Penrose przyjmuje nieco inne podejście, które zostało opisane w książce całkowicie „od zera”.

Dyskusje

Konsekwencje twierdzeń wpływają na filozofię matematyki, zwłaszcza na te formalizmy, które wykorzystują logikę formalną do określenia swoich zasad. Możemy przeformułować pierwsze twierdzenie o niezupełności w następujący sposób: „ niemożliwe jest znalezienie wszechstronnego systemu aksjomatów, który można by udowodnić Wszystko prawd matematycznych, a nie ani jednego kłamstwa" Z drugiej strony, z punktu widzenia ścisłej formalności, to przeformułowanie nie ma specjalne znaczenie, ponieważ zakłada, że pojęcia „prawdy” i „fałszu” są definiowane w sensie absolutnym, a nie względnym dla każdego konkretnego systemu.