Twierdzenia o niezupełności Gödla - Gödel's incompleteness theorems

Niezupełności twierdzenia Gödla dwa twierdzenia z logiki matematycznej , które są zainteresowane w granicach dowodliwości formalnej teorii aksjomatycznych. Wyniki te, opublikowane przez Kurta Gödla w 1931 roku, są ważne zarówno w logice matematycznej, jak iw filozofii matematyki . Twierdzenia te są szeroko, ale nie powszechnie, interpretowane jako pokazujące, że program Hilberta mający na celu znalezienie kompletnego i spójnego zestawu aksjomatów dla całej matematyki jest niemożliwy.

Pierwsze stany niekompletność twierdzenie, że ma spójny system z axioms których twierdzenia mogą być wymienione przez skutecznej procedury (tj algorytm ) nie może dowieść, wszystkie prawdy o arytmetyki liczb naturalnych . Dla każdego takiego spójnego systemu formalnego zawsze będą istniały twierdzenia o liczbach naturalnych, które są prawdziwe, ale których w ramach systemu nie da się udowodnić. Drugie twierdzenie o niezupełności, będące rozszerzeniem pierwszego, pokazuje, że system nie może zademonstrować własnej spójności.

Stosując argument diagonalny , twierdzenia Gödla o niezupełności były pierwszym z kilku ściśle powiązanych twierdzeń o ograniczeniach systemów formalnych. Po nich nastąpiło twierdzenie Tarskiego o niedefiniowalności prawdy o formalnej niedefiniowalności, dowód Churcha , że Entscheidungsproblem Hilberta jest nierozwiązywalny, oraz twierdzenie Turinga , że nie ma algorytmu do rozwiązania problemu zatrzymania .

Systemy formalne: kompletność, spójność i skuteczna aksjomatyzacja

Twierdzenia o niezupełności stosują się do systemów formalnych o wystarczającej złożoności, aby wyrazić podstawową arytmetykę liczb naturalnych, które są spójne i skutecznie zaaksjomatyzowane. Pojęcia te są szczegółowo opisane poniżej. Szczególnie w kontekście logiki pierwszego rzędu systemy formalne nazywane są również teoriami formalnymi . Ogólnie rzecz biorąc, system formalny to aparat dedukcyjny, który składa się z określonego zestawu aksjomatów wraz z regułami manipulacji symbolicznej (lub regułami wnioskowania), które pozwalają na wyprowadzenie nowych twierdzeń z aksjomatów. Jednym z przykładów takiego systemu jest arytmetyka Peano pierwszego rzędu , system, w którym wszystkie zmienne mają oznaczać liczby naturalne. W innych systemach, takich jak teoria mnogości , tylko niektóre zdania systemu formalnego wyrażają zdania o liczbach naturalnych. Twierdzenia o niezupełności dotyczą formalnej dowodliwości w tych systemach, a nie „dowodliwości” w nieformalnym sensie.

Istnieje kilka właściwości, które może mieć system formalny, w tym kompletność, spójność i istnienie skutecznej aksjomatyzacji. Twierdzenia o niezupełności pokazują, że systemy, które zawierają wystarczającą ilość arytmetyki, nie mogą posiadać wszystkich tych trzech właściwości.

Efektywna aksjomatyzacja

O systemie formalnym mówi się, że jest efektywnie zaksjomatyzowany (zwany także efektywnie generowanym ), jeśli jego zbiór twierdzeń jest zbiorem rekurencyjnie przeliczalnym ( Franzén 2005 , s. 112) .

Oznacza to, że istnieje program komputerowy, który w zasadzie mógłby wyliczyć wszystkie twierdzenia systemu, nie wymieniając żadnych stwierdzeń, które nie są twierdzeniami. Przykłady efektywnie generowanych teorii obejmują arytmetykę Peano i teorię mnogości Zermelo-Fraenkla (ZFC).

Teoria znana jako prawdziwa arytmetyka składa się ze wszystkich prawdziwych stwierdzeń dotyczących standardowych liczb całkowitych w języku arytmetyki Peano. Ta teoria jest spójna i kompletna oraz zawiera wystarczającą ilość arytmetyki. Nie ma jednak rekursywnie przeliczalnego zbioru aksjomatów, a tym samym nie spełnia hipotez twierdzeń o niezupełności.

Kompletność

Zbiór aksjomatów jest ( syntaktycznie lub negacją -) zupełny, jeśli dla dowolnego zdania w języku aksjomatów to zdanie lub jego negacja jest dowodem z aksjomatów ( Smith 2007 , s. 24) . Jest to pojęcie istotne dla pierwszego twierdzenia o niezupełności Gödla. Nie należy jej mylić z kompletnością semantyczną , co oznacza, że ​​zbiór aksjomatów dowodzi wszystkich tautologii semantycznych danego języka. W swoim twierdzeniu o zupełności Gödel udowodnił, że logika pierwszego rzędu jest zupełna semantycznie . Ale nie jest ona kompletna składniowo, ponieważ istnieją zdania dające się wyrazić w języku logiki pierwszego rzędu, których nie można ani udowodnić, ani obalić na podstawie samych aksjomatów logiki.

W zwykłym systemie logicznym absurdem byłoby oczekiwać kompletności składniowej. Ale w systemie matematyki myśliciele tacy jak Hilbert wierzyli, że jest tylko kwestią czasu, aby znaleźć taką aksjomatyzację, która pozwoliłaby albo udowodnić, albo obalić (poprzez udowodnienie jej negacji) każdej formuły matematycznej.

System formalny może być z założenia niekompletny składniowo, podobnie jak logika. Lub może być niekompletny po prostu dlatego, że nie wszystkie niezbędne aksjomaty zostały odkryte lub uwzględnione. Na przykład geometria euklidesowa bez postulatu równoległego jest niekompletna, ponieważ niektórych twierdzeń w języku (takich jak sam postulat równoległy) nie można udowodnić z pozostałych aksjomatów. Podobnie teoria gęstych rzędów liniowych nie jest kompletna, ale uzupełnia się dodatkowym aksjomatem stwierdzającym, że w porządku nie ma punktów końcowych. Hipoteza continuum jest stwierdzenie w języku ZFC , który nie jest do udowodnienia w ciągu ZFC, więc ZFC nie jest kompletna. W tym przypadku nie ma oczywistego kandydata na nowy aksjomat, który rozwiąże problem.

Teoria arytmetyki pierwszego rzędu Peano wydaje się być spójna. Zakładając, że rzeczywiście tak jest, zauważ, że ma nieskończony, ale rekurencyjnie przeliczalny zbiór aksjomatów i może zakodować wystarczającą ilość arytmetyki dla hipotez twierdzenia o niezupełności. Zatem według pierwszego twierdzenia o niezupełności, arytmetyka Peano nie jest zupełna. Twierdzenie daje wyraźny przykład zdania arytmetycznego, którego nie można ani udowodnić, ani obalić w arytmetyce Peano. Co więcej, to stwierdzenie jest prawdziwe w zwykłym modelu . Ponadto żadne skutecznie zaksjomatyzowane, spójne rozszerzenie arytmetyki Peano nie może być kompletne.

Spójność

Zbiór aksjomatów jest (po prostu) niesprzeczny, jeśli nie ma takiego zdania, że ​​zarówno zdanie, jak i jego negację można udowodnić na podstawie aksjomatów, a w przeciwnym razie niespójny .

Arytmetyka Peano jest zgodna z ZFC, ale nie z samej siebie. Podobnie, ZFC nie jest niesprzeczne z samego siebie, ale ZFC + „istnieje niedostępny kardynał ” dowodzi, że ZFC jest niesprzeczny, ponieważ jeśli κ jest najmniejszym takim kardynałem, to V κ siedzący we wszechświecie von Neumanna jest modelem ZFC, i teoria jest spójna wtedy i tylko wtedy, gdy ma model.

Jeśli weźmie się wszystkie zdania w języku arytmetyki Peano jako aksjomaty, to teoria ta jest kompletna, ma rekurencyjnie przeliczalny zbiór aksjomatów i może opisywać dodawanie i mnożenie. Jednak nie jest to spójne.

Dodatkowe przykłady niespójnych teorii wynikają z paradoksów, które powstają, gdy w teorii mnogości przyjmuje się schemat aksjomatu nieograniczonego rozumienia .

Systemy zawierające arytmetykę

Twierdzenia o niezupełności dotyczą tylko systemów formalnych, które są w stanie udowodnić wystarczający zbiór faktów o liczbach naturalnych. Jednym wystarczającym zbiorem jest zbiór twierdzeń arytmetyki Robinsona Q . Niektóre systemy, takie jak arytmetyka Peano, mogą bezpośrednio wyrażać stwierdzenia dotyczące liczb naturalnych. Inne, takie jak teoria mnogości ZFC, potrafią interpretować twierdzenia dotyczące liczb naturalnych na swój język. Każda z tych opcji jest odpowiednia dla twierdzeń o niezupełności.

Teoria ciał algebraicznie domkniętych o danej charakterystyce jest zupełna, niesprzeczna i ma nieskończony, ale rekurencyjnie przeliczalny zbiór aksjomatów. Jednak nie jest możliwe zakodowanie liczb całkowitych w tej teorii, a teoria nie może opisywać arytmetyki liczb całkowitych. Podobnym przykładem jest teoria rzeczywistych ciał domkniętych , która jest zasadniczo odpowiednikiem aksjomatów Tarskiego dla geometrii euklidesowej . Tak więc sama geometria euklidesowa (w ujęciu Tarskiego) jest przykładem kompletnej, spójnej, skutecznie zaksjomatyzowanej teorii.

System arytmetyki Presburgera składa się ze zbioru aksjomatów dla liczb naturalnych z samą operacją dodawania (pominięto mnożenie). Arytmetyka Presburgera jest kompletna, spójna i rekurencyjnie przeliczalna i może kodować dodawanie, ale nie mnożenie liczb naturalnych, pokazując, że dla twierdzeń Gödla potrzebna jest teoria, która koduje nie tylko dodawanie, ale także mnożenie.

Dan Willard  ( 2001 ) badał pewne słabe rodziny systemów arytmetycznych, które pozwalają na dostateczną arytmetykę jako relacje, aby sformalizować numerację Gödla, ale które nie są wystarczająco silne, aby mieć mnożenie jako funkcję, a zatem nie udowadniają drugiego twierdzenia o niezupełności; systemy te są spójne i zdolne do udowodnienia własnej spójności (patrz teorie samoweryfikacji ).

Sprzeczne cele

Przy wyborze zestawu aksjomatów jednym celem jest możliwość udowodnienia jak największej liczby poprawnych wyników, bez udowadniania jakichkolwiek błędnych wyników. Na przykład, możemy sobie wyobrazić zbiór prawdziwych aksjomatów, które pozwalają nam udowodnić każde prawdziwe twierdzenie arytmetyczne dotyczące liczb naturalnych ( Smith 2007 , s. 2) . W standardowym systemie logiki pierwszego rzędu niespójny zbiór aksjomatów dowodzi każdego zdania w jego języku (jest to czasami nazywane zasadą wybuchu ), a zatem jest automatycznie zupełny. Zestaw aksjomatów, które jest zarówno kompletne i spójne, jednak okazuje się maksymalny zestaw z nie- sprzecznych twierdzeń ( Hinman 2005 , str. 143) .

Wzorzec zilustrowany w poprzednich sekcjach z arytmetykami Peano, ZFC i ZFC + "istnieje niedostępny kardynał" generalnie nie może zostać złamany. Tutaj ZFC + „istnieje niedostępny kardynał” nie może od siebie wykazać spójności. Nie jest też kompletna, co ilustruje w ZFC+ „istnieje niedostępna kardynalna” teoria nierozwiązana hipoteza kontinuum.

Pierwsze twierdzenie o niezupełności pokazuje, że w systemach formalnych, które mogą wyrażać podstawową arytmetykę, nigdy nie można stworzyć kompletnej i spójnej skończonej listy aksjomatów: za każdym razem, gdy jako aksjomat dodaje się dodatkowe, spójne zdanie, istnieją inne zdania prawdziwe, które nadal nie mogą być udowodnione, nawet z nowym aksjomatem. Jeśli kiedykolwiek zostanie dodany aksjomat, który czyni system kompletnym, dzieje się to kosztem uczynienia systemu niespójnym. Nie jest nawet możliwe, aby nieskończona lista aksjomatów była kompletna, spójna i skutecznie zaaksjomatyzowana.

Pierwsze twierdzenie o niezupełności

Pierwsze twierdzenie Gödla o niezupełności pojawiło się po raz pierwszy jako „Twierdzenie VI” w artykule Gödla z 1931 roku „ O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica and Related Systems I”. Hipotezy twierdzenia zostały wkrótce poprawione przez J. Barkleya Rossera ( 1936 ) przy użyciu sztuczki Rossera . Otrzymane twierdzenie (zawierające ulepszenie Rossera) można sparafrazować w języku angielskim w następujący sposób, gdzie „system formalny” obejmuje założenie, że system jest efektywnie generowany.

Pierwsze twierdzenie o niezupełności : „Każdy spójny system formalny F, w ramach którego można przeprowadzić pewną ilość elementarnej arytmetyki, jest niekompletny; tj. istnieją zdania języka F, których nie można ani udowodnić, ani obalić w F ”. (Raatikainen 2015)

Zdanie nie do udowodnienia G F, do którego odwołuje się twierdzenie, jest często nazywane „zdaniem Gödla” dla systemu F . Dowód konstruuje konkretne zdanie gödla dla systemu F , ale istnieje nieskończenie wiele zdań w języku systemu, które mają te same własności, takie jak koniunkcja zdania gödla i dowolnego logicznie ważnego zdania.

Każdy efektywnie wygenerowany system ma swoje zdanie Gödla. Możliwe jest zdefiniowanie większego systemu F',  który zawiera całość F plus G F jako dodatkowy aksjomat. Nie da to pełnego systemu, ponieważ twierdzenie Gödla będzie miało zastosowanie również do F' , a zatem F' również nie może być zupełne. W tym przypadku, G F jest rzeczywiście twierdzeniem F” , ponieważ jest to aksjomat. Ponieważ G F stwierdza tylko, że nie jest dowodliwa w F , nie ma sprzeczności w jego dowodliwości w F' . Jednakże, ponieważ twierdzenie o niezupełności odnosi się do F' , pojawi się nowa instrukcja Gödla G F′ dla F' , pokazująca, że F' również jest niekompletne. G F′ będzie się różnić od G F tym, że G F′ będzie odnosić się do F' , a nie  F .

Forma syntaktyczna zdania Gödla

Zdanie Gödla ma pośrednio odnosić się do siebie. Zdanie to stwierdza, że ​​kiedy określona sekwencja kroków jest użyta do skonstruowania innego zdania, to skonstruowane zdanie nie będzie dowodliwe w F . Niemniej jednak, kolejność etapów jest tak skonstruowany, że zdanie okazuje G F siebie. W ten sposób zdanie Gödel G F pośrednio stwierdza własną unprovability w F ( Smith 2007 , s. 135) .

Aby udowodnić pierwsze twierdzenie o niezupełności, Gödel wykazał, że pojęcie dowodliwości w systemie może być wyrażone wyłącznie w kategoriach funkcji arytmetycznych operujących na liczbach Gödla zdań systemu. Dlatego system, który może udowodnić pewne fakty dotyczące liczb, może również pośrednio dowodzić faktów dotyczących własnych twierdzeń, pod warunkiem, że jest skutecznie generowany. Pytania o dowodliwość zdań w systemie są reprezentowane jako pytania o arytmetyczne własności samych liczb, które byłyby rozstrzygane przez system, gdyby był kompletny.

Zatem chociaż zdanie gödla odnosi się pośrednio do zdań systemu F , to czytane jako zdanie arytmetyczne zdanie gödla odnosi się bezpośrednio tylko do liczb naturalnych. Twierdzi, że żadna liczba naturalna nie ma określonej własności, gdy ta własność jest dana przez pierwotną relację rekurencyjną ( Smith 2007 , s. 141) . Jako takie, zdanie Gödla może być napisane w języku arytmetyki za pomocą prostej formy składniowej. W szczególności, może być wyrażony jako wzór w języku arytmetyki składającej się z szeregu głównych kwantyfikatorami następnie ciało kwantyfikatora wolne (wzory te są na poziomie do arytmetycznego hierarchii ). Poprzez twierdzenie MRDP zdanie Gödla można przepisać jako stwierdzenie, że określony wielomian w wielu zmiennych o współczynnikach całkowitych nigdy nie przyjmuje wartości zero, gdy liczby całkowite są zastępowane za jego zmienne ( Franzén 2005 , s. 71) .

Prawda zdania Gödla

Pierwsze twierdzenie o niezupełności pokazuje, że zdanie Gödla G F odpowiedniej teorii formalnej F jest niedowodliwe w F . Ponieważ interpretowana jako stwierdzenie o arytmetyce ta niedowodliwość jest dokładnie tym, co zdanie (pośrednio) stwierdza, zdanie Gödla jest w rzeczywistości prawdziwe ( Smoryński 1977 , s. 825 ; por. także Franzén 2005 , s. 28–33 ). . Z tego powodu, zdanie G F jest często mówi się, że „prawda, ale nie do udowodnienia.” ( Raatikainen 2015 ) . Jednakże, ponieważ zdanie Gödel nie może sam formalnie określić zamierzony interpretacji prawdy zdaniu G F może być podjęta tylko przy via metaanalizie spoza systemu. Generalnie metaanaliza ta może być przeprowadzona w ramach słabego systemu formalnego, znanego jako pierwotna arytmetyka rekurencyjna , co dowodzi implikacji Con( F )→ G F , gdzie Con( F ) jest zdaniem kanonicznym potwierdzającym niesprzeczność F ( Smoryński 1977 , s. 840 , Kikuchi i Tanaka 1994 , s. 403 ).

Chociaż zdanie gödla spójnej teorii jest prawdziwe jako zdanie o zamierzonej interpretacji arytmetyki, zdanie gödla będzie fałszywe w niektórych niestandardowych modelach arytmetyki , jako konsekwencja twierdzenia o zupełności Gödla ( Franzén 2005 , s. 135) . Twierdzenie to pokazuje, że gdy zdanie jest niezależne od teorii, teoria będzie miała modele, w których zdanie jest prawdziwe i modele, w których zdanie jest fałszywe. Jak opisano wcześniej, zdanie gödla systemu F jest zdaniem arytmetycznym, które twierdzi, że nie istnieje liczba o określonej własności. Twierdzenie o niezupełności pokazuje, że twierdzenie to będzie niezależne od systemu F , a prawdziwość zdania gödla wynika z faktu, że żadna standardowa liczba naturalna nie ma tej własności. Każdy model, w którym zdanie Gödla jest fałszywe, musi zawierać jakiś element, który spełnia własność w tym modelu. Taki model musi być „niestandardowy” – musi zawierać elementy, które nie odpowiadają żadnej standardowej liczbie naturalnej ( Raatikainen 2015 , Franzén 2005 , s. 135 ).

Związek z paradoksem kłamcy

Gödel specjalnie cytuje paradoksu Richarda i paradoksu kłamca jak semantycznych analogów do jego składniowej wynik niezupełności w części wprowadzającej „ Na Formalnie nierozstrzygalny propozycji w Principia Mathematica oraz odpowiednich systemów I ”. Paradoks kłamcy jest zdanie „To zdanie jest fałszywe.” Analiza zdania kłamliwego pokazuje, że nie może ono być prawdziwe (bo wtedy, jak twierdzi, jest fałszywe), ani nie może być fałszywe (bo wtedy jest prawdziwe). Zdanie Gödla G dla systemu F daje podobne twierdzenie do zdania kłamliwego, ale z prawdą zastąpioną przez dowodliwość: G mówi " G nie jest dowodliwe w systemie F ". Analiza prawdziwości i dowodliwości G jest sformalizowaną wersją analizy prawdziwości wyroku kłamcy.

W zdaniu gödla nie można zastąpić słowa „nie do udowodnienia” słowem „fałsz”, ponieważ orzeczenie „Q jest liczbą gödla fałszywej formuły” nie może być reprezentowane jako formuła arytmetyczna. Wynik ten, znany jako twierdzenie Tarskiego o niedefiniowalności , został odkryty niezależnie zarówno przez Gödla, gdy pracował nad dowodem twierdzenia o niezupełności, jak i przez imiennika tego twierdzenia, Alfreda Tarskiego .

Rozszerzenia oryginalnego wyniku Gödla

W porównaniu z twierdzeniami przedstawionymi w artykule Gödla z 1931 roku, wiele współczesnych twierdzeń o niezupełności jest bardziej ogólnych na dwa sposoby. Te uogólnione stwierdzenia są sformułowane tak, aby miały zastosowanie do szerszej klasy systemów i są sformułowane tak, aby uwzględniały słabsze założenia spójności.

Gödel zademonstrował niekompletność systemu Principia Mathematica , szczególnego systemu arytmetycznego, ale równoległą demonstrację można było podać dla dowolnego efektywnego systemu o pewnej wyrazistości. Gödel skomentował ten fakt we wstępie do swojego artykułu, ale ograniczył dowód do jednego systemu konkretności. We współczesnych stwierdzeniach twierdzenia powszechne jest formułowanie warunków skuteczności i wyrazistości jako hipotez dla twierdzenia o niezupełności, tak że nie jest ono ograniczone do żadnego konkretnego systemu formalnego. Terminologia używana do określenia tych warunków nie została jeszcze opracowana w 1931 roku, kiedy Gödel opublikował swoje wyniki.

Oryginalne twierdzenie Gödla i dowód twierdzenia o niezupełności wymaga założenia, że ​​system jest nie tylko spójny, ale ω-spójny . System jest -niespójny, jeśli nie jest -niespójny, i jest ω-niespójny, jeśli istnieje orzecznik P taki, że dla każdej określonej liczby naturalnej m system dowodzi ~ P ( m ), a mimo to system dowodzi również, że istnieje istnieje liczba naturalna n taka, że P ( n ). Oznacza to, że system mówi, że istnieje liczba o właściwości P , ale zaprzecza, że ​​ma jakąkolwiek określoną wartość. Spójność systemu implikuje jego spójność, ale spójność nie implikuje -spójność. J. Barkley Rosser  ( 1936 ) wzmocnił twierdzenie o niezupełności, znajdując odmianę dowodu ( sztuczka Rossera ), która wymaga jedynie, aby system był spójny, a nie ω-spójny. Ma to głównie znaczenie techniczne, ponieważ wszystkie prawdziwe formalne teorie arytmetyczne (teorie, których aksjomaty są prawdziwymi stwierdzeniami o liczbach naturalnych) są ω-spójne, a zatem stosuje się do nich twierdzenie Gödla, jak pierwotnie podano. Silniejsza wersja twierdzenia o niezupełności, która zakłada jedynie spójność, a nie -spójność, jest obecnie powszechnie znana jako twierdzenie o niezupełności Gödla i jako twierdzenie Gödla-Rossera.

Drugie twierdzenie o niezupełności

Dla każdego systemu formalnego F zawierającego podstawową arytmetykę można kanonicznie zdefiniować formułę Cons( F ) wyrażającą niesprzeczność F . Formuła ta wyraża własność, że „nie istnieje liczba naturalna kodująca wyprowadzenie formalne w systemie F, którego wniosek jest sprzecznością składniową”. Często przyjmuje się, że sprzeczność składniowa wynosi „0=1”, w którym to przypadku Cons( F ) stwierdza, że ​​„nie ma liczby naturalnej, która kodowałaby wyprowadzenie „0=1” z aksjomatów F ”.

Drugie twierdzenie Gödla o niezupełności pokazuje, że przy ogólnych założeniach to twierdzenie o zgodności kanonicznej Cons( F ) nie będzie udowodnione w F . Twierdzenie to pojawiło się po raz pierwszy jako „Twierdzenie XI” w pracy Gödla z 1931 r. „ O formalnie nierozstrzygalnych twierdzeniach w Principia Mathematica i systemach pokrewnych I ”. W poniższym stwierdzeniu termin „system sformalizowany” obejmuje również założenie, że F jest skutecznie zaksjomatyzowane.

Drugi Niezupełność Twierdzenie : „Załóżmy, że F jest zgodny sformalizowany system, który zawiera elementarną arytmetykę wtedy. ”. ( Raatikainen 2015 )

Twierdzenie to jest silniejsze niż pierwsze twierdzenie o niezupełności, ponieważ zdanie skonstruowane w pierwszym twierdzeniu o niezupełności nie wyraża bezpośrednio spójności systemu. Dowód drugiego twierdzenia niekompletności otrzymuje się formalizującego dowód pierwszego twierdzenia niekompletności w systemie F siebie.

Wyrażając spójność

W drugim twierdzeniu o niezupełności kryje się techniczna subtelność dotycząca sposobu wyrażania niesprzeczności F jako formuły w języku F . Spójność systemu można wyrazić na wiele sposobów i nie wszystkie prowadzą do tego samego wyniku. Formuła Cons( F ) z drugiego twierdzenia o niezupełności jest szczególnym wyrazem spójności.

Inne formalizacje twierdzenia, że F jest niesprzeczne, mogą być nierównoważne w F , a niektóre mogą być nawet udowodnione. Na przykład arytmetyka Peano pierwszego rzędu (PA) może udowodnić, że „największy spójny podzbiór PA” jest spójny. Ale ponieważ PA jest niesprzeczny, największym niezmiennym podzbiorem PA jest po prostu PA, więc w tym sensie PA „udowadnia, że ​​jest niesprzeczny”. To, czego PA nie dowodzi, to fakt, że największy spójny podzbiór PA jest w rzeczywistości całością PA. (Termin „największy spójny podzbiór PA” ma być tutaj największym spójnym początkowym segmentem aksjomatów PA w ramach jakiegoś konkretnego efektywnego wyliczenia.)

Warunki Hilberta-Bernaysa

Standardowy dowód drugiego twierdzenia o niezupełności zakłada, że ​​predykat dowodliwości Prov A ( P ) spełnia warunki dowodliwości Hilberta-Bernaysa . Niech #( P ) reprezentuje liczbę Gödla formuły P , warunki dowodliwości mówią:

  1. Jeśli F dowodzi P , to F dowodzi Dowód A (#( P )).
  2. F dowodzi 1.; to znaczy, F dowodzi Prób A (#( P )) → Prób A (#(Prz A (#(P)))).
  3. F dowodzi Przyp A (#( PQ )) ∧ Przyp A (#( P )) → Przyp A (#( Q )) (analog modus ponens ).

Istnieją systemy, takie jak arytmetyka Robinsona, które są wystarczająco silne, aby spełnić założenia pierwszego twierdzenia o niezupełności, ale które nie udowadniają warunków Hilberta-Bernaysa. Arytmetyka Peano jest jednak wystarczająco silna, aby zweryfikować te warunki, podobnie jak wszystkie teorie silniejsze niż arytmetyka Peano.

Implikacje dla dowodów spójności

Drugie twierdzenie Gödla implikuje również, że system F 1 spełniający warunki techniczne przedstawione powyżej nie może dowieść niesprzeczności żadnego systemu F 2 , który dowodzi niesprzeczności F 1 . Dzieje się tak, ponieważ taki system F 1 może dowieść, że jeśli F 2 dowodzi niesprzeczności F 1 , to F 1 jest w rzeczywistości niesprzeczne. Twierdzenie, że F 1 jest niesprzeczne ma postać „dla wszystkich liczb n , n ma rozstrzygającą właściwość, że nie jest kodem dowodu sprzeczności w F 1 ”. Gdyby F 1 faktycznie było niespójne, to F 2 dowodziłoby dla pewnego n, że n jest kodem sprzeczności w F 1 . Ale gdyby F 2 również dowiodło, że F 1 jest niesprzeczne (to znaczy, że nie ma takiego n ), to samo byłoby niespójne. To rozumowanie można sformalizować w F 1, aby pokazać, że jeśli F 2 jest niesprzeczne, to F 1 jest niesprzeczne. Ponieważ przez drugie twierdzenie o niezupełności F 1 nie dowodzi swojej niesprzeczności, nie może też dowodzić niesprzeczności F 2 .

Ten wniosek z drugiego twierdzenia o niezupełności pokazuje, że nie ma nadziei na udowodnienie, na przykład, niesprzeczności arytmetyki Peano przy użyciu jakichkolwiek środków skończonych, które można sformalizować w systemie, którego niesprzeczność można udowodnić w arytmetyce Peano (PA). Na przykład system prymitywnej arytmetyki rekurencyjnej (PRA), który jest powszechnie akceptowany jako dokładna formalizacja matematyki skończonej, jest w PA dowodnie spójny. Zatem PRA nie może udowodnić spójności PA. Ten fakt jest ogólnie postrzegany jako implikujący, że program Hilberta , który miał na celu usprawiedliwienie użycia „idealnych” (nieskończoności) zasad matematycznych w dowodach „rzeczywistych” (finitystycznych) twierdzeń matematycznych poprzez podanie skończonego dowodu, że idealne zasady są spójne, nie można przeprowadzić ( Franzén 2005 , s. 106) .

Wniosek wskazuje również na epistemologiczne znaczenie drugiego twierdzenia o niezupełności. W rzeczywistości nie dostarczyłoby żadnych interesujących informacji, gdyby system F udowodnił swoją spójność. Dzieje się tak, ponieważ niespójne teorie dowodzą wszystkiego, łącznie z ich spójnością. Tak więc dowód niesprzeczności F w F nie dałby nam żadnej wskazówki, czy F rzeczywiście jest niesprzeczne; żadne wątpliwości co do niesprzeczności F nie zostałyby rozwiązane przez taki dowód niesprzeczności. Zainteresowanie dowodami niesprzeczności polega na możliwości udowodnienia niesprzeczności systemu F w jakimś systemie F', który jest w pewnym sensie mniej wątpliwy niż samo F , na przykład słabszy niż F . Dla wielu naturalnie występujących teorii F i F' , takich jak F = teoria mnogości Zermelo-Fraenkla i F' = pierwotna arytmetyka rekurencyjna, niesprzeczność F' jest dowodliwa w F , a zatem F' nie może udowodnić niesprzeczności F za pomocą powyższego następstwo drugiego twierdzenia o niezupełności.

Drugie twierdzenie o niezupełności nie wyklucza całkowicie możliwości udowodnienia niesprzeczności jakiejś teorii T , ale czyni to tylko w teorii, która sama T może dowieść być niesprzeczna. Na przykład Gerhard Gentzen udowodnił zgodność arytmetyki Peano w innym systemie, który zawiera aksjomat zakładający, że liczba porządkowa ε 0 jest dobrze ugruntowana ; zobacz dowód spójności Gentzen . Twierdzenie Gentzena pobudziło rozwój analizy porządkowej w teorii dowodu.

Przykłady nierozstrzygalnych stwierdzeń

W matematyce i informatyce istnieją dwa różne znaczenia słowa „nierozstrzygalny”. Pierwszym z nich jest sens dowodowo-teoretyczny stosowany w odniesieniu do twierdzeń Gödla, polegający na tym, że twierdzenie nie jest ani dowodliwe, ani obalalne w określonym systemie dedukcyjnym . Drugi sens, który nie będzie tutaj omawiany, jest używany w odniesieniu do teorii obliczalności i odnosi się nie do twierdzeń, ale do problemów decyzyjnych , które są przeliczalnie nieskończonymi zestawami pytań, z których każdy wymaga odpowiedzi tak lub nie. Mówi się, że taki problem jest nierozstrzygalny, jeśli nie ma obliczalnej funkcji, która poprawnie odpowiada na każde pytanie w zestawie problemów (patrz problem nierozstrzygalny ).

Ze względu na dwa znaczenia słowa nierozstrzygalny, termin niezależny jest czasami używany zamiast nierozstrzygalny w znaczeniu „ani do udowodnienia, ani do obalenia”.

Nierozstrzygalność zdania w konkretnym systemie dedukcyjnym sama w sobie nie odpowiada na pytanie, czy wartość logiczna zdania jest dobrze zdefiniowana, czy też może być określona innymi sposobami. Nierozstrzygalność oznacza jedynie, że rozważany konkretny system dedukcyjny nie dowodzi prawdziwości lub fałszu twierdzenia. Kwestią sporną w filozofii matematyki jest to, czy istnieją tak zwane twierdzenia „absolutnie nierozstrzygalne”, których wartość prawdziwości nigdy nie może być poznana lub jest źle określona .

Połączona praca Gödla i Paula Cohena dała dwa konkretne przykłady twierdzeń nierozstrzygalnych (w pierwszym znaczeniu tego terminu): Hipotezy continuum nie można ani udowodnić, ani obalić w ZFC (standardowa aksjomatyzacja teorii mnogości ) i aksjomat wybór nie może być ani udowodniony, ani obalony w ZF (co jest wszystkimi aksjomatami ZFC z wyjątkiem aksjomatu wyboru). Te wyniki nie wymagają twierdzenia o niezupełności. Gödel udowodnił w 1940 roku, że żadne z tych stwierdzeń nie może być obalone w teorii mnogości ZF lub ZFC. W latach 60. Cohen udowodnił, że żadnego z nich nie można udowodnić na podstawie ZF, a hipotezy kontinuum nie można udowodnić na podstawie ZFC.

W 1973 Saharon Shelah wykazał, że problem Whiteheada w teorii grup jest nierozstrzygalny, w pierwszym znaczeniu tego terminu, w standardowej teorii zbiorów.

Gregory Chaitin stworzył nierozstrzygalne twierdzenia w algorytmicznej teorii informacji i udowodnił w tym kontekście kolejne twierdzenie o niezupełności. Twierdzenie o niezupełności Chaitina mówi, że dla każdego systemu, który może reprezentować wystarczająco dużo arytmetyki, istnieje górna granica c taka, że ​​nie można udowodnić żadnej konkretnej liczby w tym systemie, aby mieć złożoność Kołmogorowa większą niż c . Podczas gdy twierdzenie Gödla jest powiązane z paradoksem kłamcy , wynik Chaitina jest powiązany z paradoksem Berry'ego .

Nierozstrzygnięte stwierdzenia, które można udowodnić w większych systemach

Są to naturalne matematyczne odpowiedniki zdania Gödla „prawdziwego, ale nierozstrzygalnego”. Można je udowodnić w większym systemie, który jest ogólnie akceptowany jako ważna forma rozumowania, ale są nierozstrzygalne w bardziej ograniczonym systemie, takim jak arytmetyka Peano.

W 1977 Paris i Harrington udowodnili, że zasada Paris-Harrington , wersja nieskończonego twierdzenia Ramseya , jest nierozstrzygalna w (pierwszego rzędu) arytmetyce Peano , ale może być udowodniona w silniejszym systemie arytmetyki drugiego rzędu . Kirby i Paris wykazali później, że twierdzenie Goodsteina , twierdzenie o ciągach liczb naturalnych nieco prostsze niż zasada Parisa-Harringtona, jest również nierozstrzygalne w arytmetyce Peano.

Twierdzenie Kruskala o drzewie , które ma zastosowanie w informatyce, jest również nierozstrzygalne z arytmetyki Peano, ale można je udowodnić w teorii mnogości. W rzeczywistości twierdzenie Kruskala (lub jego skończona forma) jest nierozstrzygalne w znacznie silniejszym systemie kodyfikującym dopuszczalne zasady oparte na filozofii matematyki zwanej predykatywizmem . Powiązane, ale bardziej ogólne twierdzenie o grafach (2003) ma konsekwencje dla teorii złożoności obliczeniowej .

Związek z obliczalnością

Twierdzenie o niezupełności jest ściśle powiązane z kilkoma wynikami dotyczącymi zbiorów nierozstrzygalnych w teorii rekurencji .

Stephen Cole Kleene  ( 1943 ) przedstawił dowód twierdzenia Gödla o niezupełności wykorzystując podstawowe wyniki teorii obliczalności. Jeden z takich wyników pokazuje, że problem zatrzymania jest nierozstrzygnięty: nie ma programu komputerowego, który mógłby poprawnie określić, biorąc pod uwagę dowolny program P jako dane wejściowe, czy P ostatecznie zatrzymuje się po uruchomieniu z konkretnym danym wejściem. Kleene wykazał, że istnienie kompletnego efektywnego systemu arytmetycznego z pewnymi własnościami spójności zmusiłoby problem zatrzymania do rozstrzygnięcia, jako sprzeczność. Tę metodę dowodową przedstawił również Shoenfield (1967 , s. 132) ; Charleswortha (1980) ; oraz Hopcroft i Ullman (1979) .

Franzén (2005 , s. 73) wyjaśnia, w jaki sposób rozwiązanie Matiyasevich jest do 10. problemu Hilberta mogą być wykorzystane w celu uzyskania dowodu do pierwszego twierdzenia Gödla niezupełności. Matiyasevich udowodnił, że nie ma algorytmu, który przy danym wielomianie wielowymiarowym p(x 1 , x 2 ,...,x k ) o współczynnikach całkowitych określa, czy istnieje całkowite rozwiązanie równania p = 0. Ponieważ wielomiany z liczbami całkowitymi współczynniki i same liczby całkowite są bezpośrednio wyrażalne w języku arytmetyki, jeśli wielomianowe równanie wielomianu liczb całkowitych p = 0 ma rozwiązanie w liczbach całkowitych, to udowodni to każdy wystarczająco silny system arytmetyczny T. Co więcej, jeśli układ T jest ω-spójny, to nigdy nie udowodni, że dane równanie wielomianowe ma rozwiązanie, gdy w rzeczywistości nie ma rozwiązania w liczbach całkowitych. Tak więc, gdyby T było zupełne i ω-spójne, byłoby możliwe algorytmicznie określić, czy równanie wielomianowe ma rozwiązanie, po prostu wyliczając dowody T, dopóki „ p nie ma rozwiązania” lub „ p nie ma rozwiązania” zostanie znalezione, w sprzeczność z twierdzeniem Matiyasevicha. Z tego wynika, że T nie może być w -spójne i kompletne. Co więcej, dla każdego spójnego, efektywnie generowanego układu T , możliwe jest efektywne wygenerowanie wielowymiarowego wielomianu p na liczbach całkowitych tak, że równanie p = 0 nie ma rozwiązań na liczbach całkowitych, ale braku rozwiązań nie można udowodnić w T ( Davis 2006 , str. 416 ; Jones 1980 ).

Smorynski (1977 , s. 842) pokazuje, jak istnienie zbiorów rekurencyjnie nierozłącznych może być wykorzystane do udowodnienia pierwszego twierdzenia o niezupełności. Dowód ten jest często rozszerzany, aby pokazać, że systemy takie jak arytmetyka Peano są zasadniczo nierozstrzygalne (zob. Kleene 1967 , s. 274 ).

Twierdzenie o niezupełności Chaitina podaje inną metodę tworzenia zdań niezależnych, opartą na złożoności Kołmogorowa . Podobnie jak wspomniany powyżej dowód przedstawiony przez Kleene, twierdzenie Chaitina stosuje się tylko do teorii z dodatkową własnością, że wszystkie ich aksjomaty są prawdziwe w standardowym modelu liczb naturalnych. Twierdzenie Gödla o niezupełności wyróżnia się tym, że ma zastosowanie do spójnych teorii, które mimo to zawierają fałszywe twierdzenia w modelu standardowym; teorie te są znane jako ω-niespójne .

Szkic dowodowy dla pierwszego twierdzenia

Dowód nie wprost ma trzy zasadnicze części. Na początek wybierz formalny system, który spełnia proponowane kryteria:

  1. Wyrażenia w systemie mogą być reprezentowane przez liczby naturalne (znane jako liczby Gödla). Znaczenie tego jest takie, że własności zdań — takie jak ich prawdziwość i fałsz — będą równoważne ustaleniu, czy ich liczby Gödla mają pewne własności, i że własności zdań można zatem wykazać, badając ich liczby Gödla. Punktem kulminacyjnym tej części jest skonstruowanie formuły wyrażającej ideę, że „zdanie S jest dowodliwe w systemie” (którą można zastosować do dowolnego zdania „S” w systemie).
  2. W systemie formalnym można skonstruować liczbę, której zgodne zdanie, po zinterpretowaniu, jest samoodnoszące się do siebie i zasadniczo mówi, że jest ono (tj. samo zdanie) niedowodliwe. Odbywa się to za pomocą techniki zwanej „ diagonalizacją ” (tak zwanej ze względu na jej pochodzenie jako argument diagonalny Cantora ).
  3. W ramach systemu formalnego to stwierdzenie pozwala wykazać, że nie jest ani dowodliwe, ani obalone w systemie, a zatem system nie może być w rzeczywistości ω-spójny. Stąd pierwotne założenie, że proponowany system spełnia kryteria, jest fałszywe.

Arytmetyzacja składni

Główny problem w rozwinięciu dowodu opisanego powyżej polega na tym, że na początku wydaje się, że aby skonstruować zdanie p, które jest równoważne z „ p nie da się udowodnić”, p musiałoby jakoś zawierać odwołanie do p , co mogłoby łatwo dać początek nieskończony regres. Pomysłową techniką Gödla jest pokazanie, że zdania mogą być kojarzone z liczbami (często nazywane arytmetyzacją składni ) w taki sposób, że „udowodnienie zdania” można zastąpić „testowaniem, czy liczba ma daną właściwość” . Pozwala to na skonstruowanie formuły autoreferencyjnej w taki sposób, aby uniknąć nieskończonego regresu definicji. Ta sama technika została później użyta przez Alana Turinga w swojej pracy nad problemem Entscheidungs .

Mówiąc prościej, można wymyślić metodę, dzięki której każda formuła lub zdanie, które można sformułować w systemie, otrzymuje unikalną liczbę, zwaną jej liczbą Gödla , w taki sposób, że możliwe jest mechaniczne przekształcenie tam i z powrotem między formułami i Gödla. liczby. Liczby, o których mowa, mogą być rzeczywiście bardzo długie (pod względem liczby cyfr), ale nie stanowi to bariery; liczy się tylko to, że takie liczby można skonstruować. Prostym przykładem jest sposób, w jaki angielski jest przechowywany jako sekwencja liczb w komputerach za pomocą ASCII lub Unicode :

  • Słowo HELLOjest reprezentowane przez 72-69-76-76-79 przy użyciu dziesiętnego ASCII , czyli liczby 7269767679.
  • Wyrażenie logiczne x=y => y=xjest reprezentowane przez 120-061-121-032-061-062-032-121-061-120 przy użyciu ósemkowego ASCII , czyli liczby 120061121032061062032121061120.

Zasadniczo udowodnienie, że zdanie jest prawdziwe lub fałszywe, może być równoznaczne z udowodnieniem, że liczba odpowiadająca temu zdaniu ma lub nie ma danej właściwości. Ponieważ system formalny jest wystarczająco silny, aby wspierać wnioskowanie o liczbach w ogóle , może również wspierać wnioskowanie o liczbach reprezentujących formuły i stwierdzenia . Co ważne, ponieważ system może wspierać wnioskowanie o własnościach liczb , wyniki są równoważne z wnioskowaniem o dowodliwości ich równoważnych stwierdzeń .

Konstrukcja oświadczenia o „dowodliwości”

Po wykazaniu, że w zasadzie system może pośrednio formułować twierdzenia o dowodliwości, analizując własności tych liczb reprezentujących twierdzenia, można teraz pokazać, jak stworzyć twierdzenie, które faktycznie to robi.

Formuła F ( x ), która zawiera dokładnie jedną wolną zmienną x, nazywana jest formularzem instrukcji lub znakiem klasy . Gdy tylko x zostanie zastąpione określoną liczbą, forma oświadczenia zamienia się w oświadczenie w dobrej wierze , a następnie albo można to udowodnić w systemie, albo nie. Dla pewnych wzorów można wykazać, że dla każdej liczby naturalnej n , jest prawdziwe wtedy i tylko wtedy, gdy można ją udowodnić (dokładny wymóg w oryginalnym dowodzie jest słabszy, ale dla szkicu dowodowego to wystarczy). W szczególności dotyczy to każdej określonej operacji arytmetycznej między skończoną liczbą liczb naturalnych, np. „2  ×  3 = 6”.

Same formy oświadczeń nie są oświadczeniami i dlatego nie można ich udowodnić ani obalić. Ale każdej formie instrukcji F ( x ) można przypisać liczbę Gödla oznaczoną przez G ( F ). Wybór wolnej zmiennej użytej w postaci F ( x ) nie ma znaczenia dla przypisania liczby Gödla G ( F ).

Samo pojęcie dowodliwości może być również zakodowane przez liczby Gödla w następujący sposób: skoro dowód jest listą zdań, które podlegają pewnym regułom, można zdefiniować liczbę Gödla dowodu. Teraz dla każdego zdania p można zapytać, czy liczba x jest liczbą Gödla jej dowodu. Relacja między liczbą Gödla p i x , potencjalną liczbą Gödla jej dowodu, jest relacją arytmetyczną między dwiema liczbami. Dlatego istnieje zdanie w formie Bew( y ), które wykorzystuje tę relację arytmetyczną do stwierdzenia, że ​​istnieje liczba Gödla dowodu y :

Bew( y ) = ∃ x ( y jest liczbą Gödla formuły, a x jest liczbą Gödla dowodu formuły zakodowanej przez y ).

Nazwa Bew jest skrótem od beweisbar , niemieckiego słowa oznaczającego „sprawdzalne”; ta nazwa była pierwotnie używana przez Gödla na oznaczenie właśnie opisanej formuły dowodliwości. Zauważ, że „Bew( y )” jest jedynie skrótem, który reprezentuje konkretną, bardzo długą formułę w oryginalnym języku T ; sam ciąg „Bew” nie jest uważany za część tego języka.

Ważną cechą wzoru Bew( y ) jest to, że jeśli zdanie p jest dowodliwe w systemie, to Bew( G ( p )) jest również dowodliwe. Dzieje się tak, ponieważ każdy dowód p miałby odpowiednią liczbę Gödla, której istnienie powoduje, że Bew( G ( p )) jest spełniony.

Diagonalizacja

Następnym krokiem w dowodzie jest uzyskanie stwierdzenia, które pośrednio potwierdza swoją niedowodliwość. Chociaż Gödel skonstruował to zdanie wprost, istnienie przynajmniej jednego takiego zdania wynika z diagonalnego lematu , który mówi, że dla każdego wystarczająco silnego systemu formalnego i dowolnego zdania o postaci F istnieje zdanie p takie, że system dowodzi

PF ( G ( t )).

Niech F będzie negacją Bew( x ), otrzymujemy twierdzenie

P~ Bew ( G ( t ))

a p zdefiniowane przez to z grubsza stwierdza, że ​​jego własna liczba Gödla jest liczbą Gödla niedowodliwej formuły.

Zdanie p nie jest dosłownie równe ~Bew( G ( p )); raczej p stwierdza, że ​​jeśli wykonywane jest pewne obliczenie, wynikowa liczba Gödla będzie liczbą niedowodliwego stwierdzenia. Ale kiedy to obliczenie jest wykonywane, wynikowa liczba Gödla okazuje się być liczbą Gödla samego p . To jest podobne do następującego zdania w języku angielskim:

„, gdy jest poprzedzone w cudzysłowie, jest niedowodliwe.”, gdy jest poprzedzone w cudzysłowie, jest niedowodliwe.

Zdanie to nie odnosi się bezpośrednio do siebie, ale gdy dokonana jest zadana transformacja, w rezultacie otrzymuje się zdanie oryginalne, a zatem to zdanie pośrednio stwierdza swoją niedowodliwość. Dowód lematu diagonalnego wykorzystuje podobną metodę.

Załóżmy teraz, że system aksjomatyczny jest ω-spójny i niech p będzie stwierdzeniem otrzymanym w poprzednim podrozdziale.

Gdyby p było dowodliwe, to Bew( G ( p )) byłoby dowodliwe, jak argumentowano powyżej. Ale p stwierdza negację Bew( G ( p )). W ten sposób system byłby niespójny, dowodząc jednocześnie twierdzenia i jego negacji. Ta sprzeczność pokazuje, że p nie może być udowodnione.

Gdyby negacja p była dowodliwa, wtedy Bew( G ( p )) byłaby dowodliwa (ponieważ p zostało skonstruowane jako równoważne negacji Bew( G ( p ))). Jednak dla każdej określonej liczby x , x nie może być liczbą Gödla dowodu p , ponieważ p nie jest dowodliwe (z poprzedniego akapitu). Tak więc z jednej strony system dowodzi, że istnieje liczba o pewnej własności (że jest to liczba Gödla dowodu p ), ale z drugiej strony, dla każdej określonej liczby x , możemy udowodnić, że nie ma tego własność. Jest to niemożliwe w systemie -spójnym. Tak więc negacja p nie jest dowodowa.

Tak więc zdanie p jest nierozstrzygalne w naszym systemie aksjomatycznym: nie można go ani udowodnić, ani obalić w ramach systemu.

W rzeczywistości wykazanie, że p nie jest dowodliwe, wymaga jedynie założenia, że ​​system jest spójny. Aby pokazać, że negacja p nie jest dowodowa, wymagane jest silniejsze założenie o -spójności. Tak więc, jeśli p jest konstruowane dla konkretnego systemu:

  • Jeśli system jest ω-spójny, nie może udowodnić ani p, ani jego negacji, a więc p jest nierozstrzygalne.
  • Jeśli system jest spójny, może mieć taką samą sytuację lub może dowodzić negacji p . W drugim przypadku mamy stwierdzenie („nie p ”), które jest fałszywe, ale możliwe do udowodnienia, a system nie jest -spójny.

Jeśli ktoś próbuje „dodać brakujące aksjomaty”, aby uniknąć niekompletności systemu, to jako aksjomaty trzeba dodać albo p, albo „nie p ”. Ale wtedy zmienia się definicja „bycia liczbą Gödla dowodu” zdania. co oznacza, że ​​formuła Bew( x ) jest teraz inna. Zatem, gdy zastosujemy lemat diagonalny do tego nowego Bew, otrzymamy nowe zdanie p , różne od poprzedniego, które będzie nierozstrzygalne w nowym systemie, jeśli będzie ω-spójne.

Dowód poprzez paradoks Berry'ego

George Boolos  ( 1989 ) szkicuje alternatywny dowód pierwszego twierdzenia o niezupełności, który wykorzystuje paradoks Berry'ego zamiast paradoksu kłamcy do skonstruowania prawdziwej, ale niedowodliwej formuły. Podobną metodę dowodową odkrył niezależnie Saul Kripke ( Boolos 1998 , s. 383) . Dowód Boolosa polega na skonstruowaniu, dla dowolnego przeliczalnego zbioru S zdań prawdziwych arytmetyki, innego zdania, które jest prawdziwe, ale nie zawiera się w S . Daje to pierwsze twierdzenie o niezupełności jako wniosek. Według Boolosa dowód ten jest interesujący, ponieważ dostarcza „innego rodzaju powodu” niekompletności skutecznych, spójnych teorii arytmetycznych ( Boolos 1998 , s. 388) .

Dowody zweryfikowane komputerowo

Twierdzenia o niezupełności należą do stosunkowo niewielkiej liczby twierdzeń nietrywialnych, które zostały przekształcone w sformalizowane twierdzenia, które można całkowicie zweryfikować za pomocą oprogramowania wspomagającego dowód . Oryginalne dowody Gödla na twierdzenia o niezupełności, podobnie jak większość dowodów matematycznych, zostały napisane w języku naturalnym, przeznaczonym dla ludzi.

Zweryfikowane komputerowo dowody wersji pierwszego twierdzenia o niezupełności zostały ogłoszone przez Natarajana Shankara w 1986 roku przy użyciu Nqthm ( Shankar 1994 ) , Russella O'Connora w 2003 roku przy użyciu Coqa ( O'Connor 2005 ) oraz przez Johna Harrisona w 2009 roku przy użyciu HOL Light ( Harrisona 2009 ) . Zweryfikowany komputerowo dowód obu twierdzeń o niezupełności został ogłoszony przez Lawrence'a Paulsona w 2013 roku przy użyciu Isabelle ( Paulson 2014 ) .

Szkic dowodowy dla drugiego twierdzenia

Główną trudnością w udowodnieniu drugiego twierdzenia o niezupełności jest wykazanie, że różne fakty dotyczące dowodliwości użyte w dowodzie pierwszego twierdzenia o niezupełności mogą być sformalizowane w systemie S przy użyciu formalnego predykatu dla dowodliwości. Gdy jest to wykonane, drugie twierdzenie niekompletność następuje przez formalizującego całą dowód pierwszego twierdzenia niekompletności w ramach systemu Ś się.

Niech p stojak dla zdaniu nierozstrzygalnym skonstruowanego powyżej, i przyjąć w celu uzyskania sprzeczność konsystencja systemu według S można udowodnić z układu S się. Jest to równoznaczne z udowodnieniem stwierdzenia „System S jest spójny”. Rozważmy teraz zdanie c , gdzie c = „Jeżeli system S jest niesprzeczny, to p nie jest udowodnione”. Dowód zdania c może być sformalizowany w systemie S , a zatem zdanie c „ p nie jest dowodliwe” (lub identycznie „nie P ( p )”) może być udowodnione w systemie S .

Zauważmy więc, że jeśli możemy udowodnić, że system S jest niesprzeczny (tj. stwierdzenie w hipotezie c ), to udowodniliśmy, że p nie jest dowodliwe. Jest to jednak sprzeczność, ponieważ zgodnie z pierwszym twierdzeniem o niezupełności to zdanie (tj. to, co jest implikowane w zdaniu c , "p" nie jest dowodliwe") jest tym, co konstruujemy jako niedowodliwe. Zauważ, że właśnie dlatego wymagamy sformalizowania pierwszego twierdzenia o niezupełności w S : aby udowodnić drugie twierdzenie o niezupełności, otrzymujemy sprzeczność z pierwszym twierdzeniem o niezupełności, które można osiągnąć tylko przez wykazanie, że twierdzenie jest spełnione w S . Nie możemy więc udowodnić, że system S jest spójny. I następuje drugie twierdzenie o niezupełności.

Dyskusja i implikacje

Wyniki niezupełności wpływają na filozofię matematyki , a zwłaszcza na wersje formalizmu , które do definiowania swoich zasad używają jednego systemu logiki formalnej.

Konsekwencje dla logiki i drugi problem Hilberta

Uważa się czasem, że twierdzenie o niezupełności ma poważne konsekwencje dla programu logiki zaproponowanego przez Gottloba Frege i Bertranda Russella , który miał na celu zdefiniowanie liczb naturalnych w terminach logicznych ( Hellman 1981 , s. 451-468) . Bob Hale i Crispin Wright twierdzą, że nie stanowi to problemu dla logikizmu, ponieważ twierdzenia o niezupełności stosują się w równym stopniu do logiki pierwszego rzędu, jak i do arytmetyki. Twierdzą, że problem ten mają tylko ci, którzy wierzą, że liczby naturalne należy definiować w kategoriach logiki pierwszego rzędu.

Wielu wierzy, że logicy niekompletność twierdzenia Gödla uderzył śmiertelny cios David Hilbert „s drugiego problemu , który zapytał o finitary konsystencji dowód na matematyce. W szczególności drugie twierdzenie o niezupełności jest często postrzegane jako uniemożliwiające problem. Jednak nie wszyscy matematycy zgadzają się z tą analizą, a status drugiego problemu Hilberta nie jest jeszcze przesądzony (patrz „ Współczesne poglądy na status problemu ”).

Umysły i maszyny

Autorzy, w tym filozof JR Lucas i fizyk Roger Penrose , dyskutowali, co, jeśli w ogóle, twierdzenia o niezupełności Gödla implikują o ludzkiej inteligencji. Duża część debaty skupia się na tym, czy ludzki umysł jest równoważny maszynie Turinga , czy też według tezy Kościoła Turinga , jakiejkolwiek skończonej maszynie. Jeśli tak jest i jeśli maszyna jest niesprzeczna, wówczas stosują się do niej twierdzenia o niezupełności Gödla.

Hilary Putnam  ( 1960 ) zasugerował, że chociaż twierdzeń Gödla nie można zastosować do ludzi, ponieważ popełniają błędy i dlatego są niespójne, można je zastosować do ludzkiego wydziału nauk ścisłych lub ogólnie matematyki. Zakładając, że jest niesprzeczny, albo nie można udowodnić jego spójności, albo nie może być reprezentowany przez maszynę Turinga.

Avi Wigderson  ( 2010 ) zaproponował, aby koncepcja matematycznej „poznawalności” opierała się na złożoności obliczeniowej, a nie logicznej rozstrzygalności. Pisze on, że „kiedy poznawalność jest interpretowana przez współczesne standardy, a mianowicie poprzez złożoność obliczeniową, zjawiska Gödla są bardzo z nami”.

Douglas Hofstadter w swoich książkach Gödel, Escher, Bach i I Am a Strange Loop przytacza twierdzenia Gödla jako przykład tego, co nazywa dziwną pętlą , hierarchiczną, samoodnoszącą się strukturą istniejącą w aksjomatycznym systemie formalnym. Twierdzi, że jest to ten sam rodzaj struktury, z której powstaje świadomość, poczucie „ja” w ludzkim umyśle. Podczas gdy samoodniesienie w twierdzeniu Gödla pochodzi od zdania gödla, które stwierdza swoją niedowodliwość w ramach formalnego systemu Principia Mathematica, samoodniesienie w ludzkim umyśle pochodzi ze sposobu, w jaki mózg abstrahuje i kategoryzuje bodźce na „symbole”, lub grupy neuronów, które odpowiadają pojęciom, w tym, co w efekcie jest również systemem formalnym, dając w końcu początek symbolom modelującym pojęcie samej istoty dokonującej percepcji. Hofstadter twierdzi, że dziwna pętla w wystarczająco złożonym systemie formalnym może prowadzić do przyczynowości „w dół” lub „do góry nogami”, sytuacji, w której normalna hierarchia przyczyn i skutków zostaje odwrócona do góry nogami. W przypadku twierdzenia Gödla objawia się to w skrócie następująco:

„Jedynie znając znaczenie formuły, można wywnioskować jej prawdziwość lub fałszywość bez żadnego wysiłku wyprowadzenia jej w staromodny sposób, który wymaga metodycznego wspinania się „w górę” od aksjomatów. (...) Normalnie nie można po prostu spojrzeć na to, co mówi matematyczne przypuszczenie, i po prostu odwołać się do samej treści tego stwierdzenia, aby wywnioskować, czy jest ono prawdziwe, czy fałszywe”. ( Jestem dziwną pętlą. )

W przypadku umysłu, znacznie bardziej złożonego systemu formalnego, ta „w dół przyczynowość” przejawia się, zdaniem Hofstadtera, jako niewysłowiony ludzki instynkt, że przyczynowość naszych umysłów leży na wysokim poziomie pragnień, koncepcji, osobowości, myśli i idee, a nie na niskim poziomie oddziaływań między neuronami czy nawet fundamentalnymi cząstkami, chociaż zgodnie z fizyką te ostatnie wydają się mieć moc przyczynową.

„Istnieje zatem dziwna odwrotność naszego normalnego ludzkiego sposobu postrzegania świata: jesteśmy stworzeni, aby postrzegać „duże rzeczy”, a nie „małe rzeczy”, mimo że domena maleńkich wydaje się być tam, gdzie rzeczywiste silniki jeżdżą rzeczywistość zamieszkuje”. ( Jestem dziwną pętlą. )

Logika parakonsystentna

Chociaż twierdzenia Gödla są zwykle badane w kontekście logiki klasycznej, odgrywają również rolę w badaniu logiki parakonsystentnej i twierdzeń wewnętrznie sprzecznych ( dialetheia ). Graham Priest  ( 1984 , 2006 ) twierdzi, że zastąpienie pojęcia formalnego dowodu w twierdzeniu Gödla zwykłym pojęciem nieformalnego dowodu może być użyte do wykazania, że ​​naiwna matematyka jest niespójna i używa tego jako dowodu na dialetyzm . Przyczyną tej niespójności jest włączenie predykatu prawdy dla systemu do języka systemu ( Priest 2006 , s. 47) . Stewart Shapiro  ( 2002 ) przedstawia bardziej mieszaną ocenę zastosowań twierdzeń Gödla do dialeizmu.

Odwołuje się do twierdzeń o niezupełności w innych dziedzinach

Odwoływanie się i analogie do twierdzeń o niezupełności są czasami czynione na poparcie argumentów, które wykraczają poza matematykę i logikę. Kilku autorów negatywnie skomentowało takie rozszerzenia i interpretacje, w tym Torkel Franzén (2005); Panu Raatikainen (2005) ; Alan Sokal i Jean Bricmont  ( 1999 ); oraz Ophelia Benson i Jeremy Stangroom  ( 2006 ). Bricmont i Stangroom (2006 , s. 10) przytaczają na przykład komentarze Rebeki Goldstein na temat rozbieżności między deklarowanym platonizmem Gödla a antyrealistycznymi zastosowaniami, do których czasami przypisywane są jego idee. Sokal i Bricmont (1999 , s. 187) krytykują odwołanie się Régisa Debraya do twierdzenia w kontekście socjologii; Debray bronił tego użycia jako metaforycznego (tamże).

Historia

Po tym, jak Gödel opublikował swój dowód twierdzenia o zupełności jako swoją rozprawę doktorską w 1929 roku, zwrócił się do drugiego problemu na habilitację . Jego pierwotnym celem było uzyskanie pozytywnego rozwiązania drugiego problemu Hilberta ( Dawson 1997 , s. 63). W tamtym czasie teorie liczb naturalnych i liczb rzeczywistych podobne do arytmetyki drugiego rzędu były znane jako „analiza”, podczas gdy teorie samych liczb naturalnych były znane jako „arytmetyka”.

Gödel nie był jedyną osobą zajmującą się problemem spójności. Ackermann opublikował wadliwy dowód niesprzeczności do analizy w 1925 roku, w którym próbował użyć metody ε-podstawienia pierwotnie opracowanej przez Hilberta. Później w tym samym roku von Neumann był w stanie skorygować dowód dla systemu arytmetycznego bez żadnych aksjomatów indukcji. Do 1928 roku Ackermann przekazał Bernaysowi zmodyfikowany dowód; ten zmodyfikowany dowód doprowadził Hilberta do ogłoszenia swojego przekonania w 1929 r., że udowodniono spójność arytmetyki i że prawdopodobnie wkrótce nastąpi dowód spójności analizy. Po tym, jak opublikowanie twierdzeń o niezupełności wykazało, że zmodyfikowany dowód Ackermanna musi być błędny, von Neumann przedstawił konkretny przykład pokazujący, że jego główna technika była błędna ( Zach 2007 , s. 418; Zach 2003 , s. 33).

W trakcie swoich badań Gödel odkrył, że chociaż zdanie, które stwierdza własną fałszywość, prowadzi do paradoksu, to zdanie, które stwierdza własną niedowodliwość, nie prowadzi do paradoksu. W szczególności Gödel był świadom wyniku zwanego obecnie twierdzeniem Tarskiego o niedefiniowalności , chociaż nigdy go nie opublikował. Gödel ogłosił swoje pierwsze twierdzenie o niezupełności Carnapowi, Feigelowi i Waismannowi 26 sierpnia 1930; wszyscy czterej wezmą udział w Drugiej Konferencji Epistemologii Nauk Ścisłych , kluczowej konferencji w Królewcu w następnym tygodniu.

Zapowiedź

Konferencja w Królewcu z 1930 r. była wspólnym spotkaniem trzech towarzystw akademickich, w których uczestniczyło wielu kluczowych logików tamtych czasów. Carnap, Heyting i von Neumann wygłosili jednogodzinne przemówienia na temat matematycznych filozofii logiki, intuicjonizmu i formalizmu ( Dawson 1996 , s. 69). Konferencja obejmowała również przemówienie emerytalne Hilberta, który opuszczał stanowisko na Uniwersytecie w Getyndze. Hilbert wykorzystał przemówienie, aby udowodnić swoje przekonanie, że wszystkie problemy matematyczne można rozwiązać. Swój adres zakończył słowami:

Dla matematyka nie ma Ignorabimus i moim zdaniem w ogóle nie ma też dla nauk przyrodniczych. ... Prawdziwym powodem, dla którego [nikomu] nie udało się znaleźć nierozwiązywalnego problemu jest, moim zdaniem, to, że nie ma nierozwiązywalnego problemu. W przeciwieństwie do niemądrego Ignorabimusa , nasze credo broni: Musimy wiedzieć. Poznamy!

Przemówienie to szybko stało się znane jako podsumowanie przekonań Hilberta na temat matematyki (ostatnie sześć słów, „ Wir müssen wissen. Wir werden wissen! ”, zostało użytych jako epitafium Hilberta w 1943 r.). Chociaż Gödel prawdopodobnie był obecny na przemówieniu Hilberta, ci dwaj nigdy nie spotkali się twarzą w twarz ( Dawson 1996 , s. 72).

Gödel ogłosił swoje pierwsze twierdzenie o niezupełności podczas dyskusji przy okrągłym stole trzeciego dnia konferencji. Ogłoszenie to nie wzbudziło większego zainteresowania, poza ogłoszeniem von Neumanna, który odciągnął Gödla na bok do rozmowy. Później w tym samym roku, pracując samodzielnie ze znajomością pierwszego twierdzenia o niezupełności, von Neumann uzyskał dowód drugiego twierdzenia o niezupełności, które ogłosił Gödelowi w liście z 20 listopada 1930 r. ( Dawson 1996 , s. 70). Gödel niezależnie uzyskał drugie twierdzenie o niezupełności i umieścił je w swoim rękopisie, który otrzymał Monatshefte für Mathematik 17 listopada 1930 r.

Artykuł Gödla został opublikowany w Monatshefte w 1931 roku pod tytułem „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” („ O formalnie nierozstrzygalnych twierdzeniach w Principia Mathematica i systemach pokrewnych I ”). Jak wskazuje tytuł, Gödel pierwotnie planował opublikować drugą część artykułu w kolejnym tomie Monatshefte ; szybka akceptacja pierwszego artykułu była jednym z powodów, dla których zmienił swoje plany ( van Heijenoort 1967 , s. 328, przypis 68a) .

Uogólnienie i akceptacja

Gödel wygłosił serię wykładów na temat swoich twierdzeń w Princeton w latach 1933–1934 dla publiczności, do której należeli Church, Kleene i Rosser. W tym czasie Gödel pojął, że kluczową właściwością, której wymagały jego twierdzenia, jest to, że system musi być efektywny (w tamtym czasie używano terminu „ogólna rekurencyjna”). Rosser udowodnił w 1936 r., że hipotezę ω-spójności, która była integralną częścią oryginalnego dowodu Gödla, można zastąpić prostą niesprzecznością, jeśli zdanie Gödla zostało odpowiednio zmienione. Te zmiany pozostawiły twierdzenia o niezupełności w zasadniczo ich nowoczesnej formie.

Gentzen opublikował swój dowód niesprzeczności dla arytmetyki pierwszego rzędu w 1936 roku. Hilbert przyjął ten dowód jako „skończony”, chociaż (jak już pokazało twierdzenie Gödla) nie można go sformalizować w systemie arytmetyki, który został udowodniony jako niesprzeczny.

Wpływ twierdzeń o niezupełności na program Hilberta został szybko uświadomiony. Bernays zamieścił pełny dowód twierdzeń o niezupełności w drugim tomie Grundlagen der Mathematik ( 1939 ), wraz z dodatkowymi wynikami Ackermanna dotyczącymi metody podstawienia ε i dowodem zgodności arytmetyki Gentzena. Był to pierwszy pełny opublikowany dowód drugiego twierdzenia o niezupełności.

Krytyka

Finsler

Paul Finsler  ( 1926 ) użył wersji paradoksu Richarda do skonstruowania wyrażenia, które było fałszywe, ale niemożliwe do udowodnienia w określonej, nieformalnej strukturze, którą opracował. Gödel nie wiedział o tym artykule, gdy udowodnił twierdzenia o niezupełności (Dzieła zebrane, t. IV, s. 9). Finsler napisał do Gödla w 1931 roku, aby poinformować go o tym artykule, który zdaniem Finslera ma pierwszeństwo dla twierdzenia o niezupełności. Metody Finslera nie opierały się na sformalizowanej dowodliwości i miały jedynie powierzchowne podobieństwo do pracy Gödla ( van Heijenoort 1967 , s. 328) . Gödel przeczytał artykuł, ale uznał, że jest głęboko wadliwy, a jego odpowiedź dla Finslera wyrażała obawy dotyczące braku formalizacji ( Dawson , s. 89 ). Finsler nadal argumentował za swoją filozofią matematyki, która unikała formalizacji, przez resztę swojej kariery.

Zermelo

We wrześniu 1931 roku Ernst Zermelo napisał do Gödla, aby ogłosić to, co określił jako „istotną lukę” w argumentacji Gödla ( Dawson , s. 76 ). W październiku Gödel odpowiedział 10-stronicowym listem ( Dawson , s. 76 , Grattan-Guinness , s. 512–513 ), w którym zwrócił uwagę, że Zermelo błędnie założył, że pojęcie prawdy w systemie jest definiowalne w tym systemie (co nie jest generalnie zgodne z twierdzeniem Tarskiego o niedefiniowalności ). Ale Zermelo nie ustąpił i opublikował swoją krytykę drukiem z „raczej zjadliwym akapitem na temat swojego młodego konkurenta” ( Grattan-Guinness , s. 513 ). Gödel uznał, że dalsze prowadzenie sprawy jest bezcelowe, a Carnap zgodził się ( Dawson , s. 77 ). Znaczna część późniejszych prac Zermelo dotyczyła logiki silniejszej niż logika pierwszego rzędu, za pomocą której miał nadzieję pokazać zarówno spójność, jak i kategoryczność teorii matematycznych.

Wittgenstein

Ludwig Wittgenstein napisał kilka fragmentów o twierdzeniach o niezupełności, które zostały opublikowane pośmiertnie w swoich uwagach na temat podstaw matematyki z 1953 r. , w szczególności jeden rozdział czasami nazywany „osławionym akapitem”, w którym wydaje się mylić pojęcia „prawda” i „możliwość udowodnienia” w System Russella. Gödel był członkiem Koła Wiedeńskiego w okresie, w którym wczesna idealna filozofia języka Wittgensteina i Tractatus Logico-Philosophicus zdominowały myślenie kręgu. Pojawiły się pewne kontrowersje dotyczące tego, czy Wittgenstein źle zrozumiał twierdzenie o niezupełności, czy po prostu wyraził się niejasno. Pisma w Nachlass Gödla wyrażają przekonanie, że Wittgenstein błędnie odczytuje jego idee.

Wielu komentatorów odczytało Wittgensteina jako nieporozumienie Gödla ( Rodych 2003 ) , chociaż Juliet Floyd i Hilary Putnam  ( 2000 ), a także Graham Priest  ( 2004 ) przedstawili odczyty tekstowe, twierdząc, że większość komentarzy nie rozumie Wittgensteina. Po wydaniu Bernays, Dummett i Kreisel napisali osobne recenzje na temat uwag Wittgensteina, z których wszystkie były skrajnie negatywne ( Berto 2009 , s. 208) . Jednomyślność tej krytyki spowodowała, że ​​uwagi Wittgensteina dotyczące twierdzeń o niezupełności miały niewielki wpływ na społeczność logiczną. W 1972 roku Gödel stwierdził: „? Czy Wittgenstein postradał zmysły Czy on myśli poważnie On celowo wypowiada trywialnie nonsensownych stwierdzeń” ( Wang 1996 , str 179). , I napisał do Karla Mengera , że komentarze Wittgensteina wykazywać niezrozumienia twierdzeń niekompletność pismo:

Z cytowanych przez ciebie fragmentów jasno wynika, że ​​Wittgenstein nie zrozumiał [pierwszego twierdzenia o niezupełności] (lub udawał, że go nie rozumie). Zinterpretował to jako rodzaj logicznego paradoksu, podczas gdy w rzeczywistości jest wręcz przeciwnie, mianowicie twierdzenie matematyczne w ramach absolutnie niekontrowersyjnej części matematyki (teoria liczb skończonych lub kombinatoryka). ( Wang 1996 , s. 179)

Od czasu opublikowania Wittgensteina Nachlass w 2000 roku, w serii artykułów filozoficznych starano się ocenić, czy pierwotna krytyka uwag Wittgensteina była uzasadniona. Floyd i Putnam (2000) twierdzą, że Wittgenstein miał pełniejsze zrozumienie twierdzenia o niezupełności niż wcześniej zakładano. Są oni szczególnie zainteresowani interpretacją zdania Gödla dla systemu ω-niespójnego jako faktycznie mówiącego „nie jestem dowodliwa”, ponieważ system nie ma modeli, w których predykat dowodliwości odpowiada rzeczywistej dowodliwości. Rodych (2003) twierdzi, że ich interpretacja Wittgensteina nie jest historycznie uzasadniona, podczas gdy Bays (2004) sprzeciwia się filozoficznej analizie predykatu dowodliwości przeprowadzonej przez Floyda i Putnama. Berto (2009) bada związek między twórczością Wittgensteina a teoriami logiki parakonsystentnej.

Zobacz też

Bibliografia

Cytaty

Artykuły Gödel

  • Kurt Gödel, 1931, „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”, Monatshefte für Mathematik und Physik , t. 38 przyn. 1, s. 173–198. doi : 10.1007/BF01700692
  • —, 1931, „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”, w: Solomon Feferman , red., 1986. Kurt Gödel. ja . Oxford University Press, s. 144-195. ISBN  978-0195147209 . Oryginał niemiecki z tłumaczeniem na język angielski, poprzedzony uwagą wstępną autorstwa Stephena Cole Kleene .
  • —, 1951, "Niektóre podstawowe twierdzenia o podstawach matematyki i ich implikacjach", w Solomon Feferman , red., 1995. Kurt Gödel Collected works, Vol. III , Oxford University Press, s. 304-323. ISBN  978-0195147223 .

Tłumaczenia, za jego życia, papieru Gödla na angielski

Żadne z poniższych nie zgadza się we wszystkich przetłumaczonych słowach i typografii. Typografia to poważna sprawa, ponieważ Gödel wyraźnie chciał podkreślić „te pojęcia metamatematyczne, które zostały wcześniej zdefiniowane w ich zwykłym sensie…”. ( van Heijenoort 1967 , s. 595) . Istnieją trzy tłumaczenia. Z pierwszego John Dawson stwierdza, że: „Tłumaczenie Meltzera było poważnie niedostateczne i otrzymało druzgocącą recenzję w Journal of Symbolic Logic ;” Gödel również skarżył się na komentarz Braithwaite'a ( Dawson 1997 , s. 216). „Na szczęście wkrótce tłumaczenie Meltzera zostało zastąpione lepszym, przygotowanym przez Elliotta Mendelsona do antologii Martina Davisa The Undecidable… uznał, że tłumaczenie „nie jest tak dobre”, jak się spodziewał… [ale z powodu ograniczeń czasowych ] wyraził zgodę na jego publikację” (ibid). (W przypisie Dawson stwierdza, że ​​„pożałowałby swego podporządkowania się, ponieważ opublikowany tom był naznaczony niechlujną typografią i licznymi błędami drukarskimi” (ibid)). Dawson stwierdza, że ​​„tłumaczeniem, które preferował Gödel, było tłumaczenie Jeana van Heijenoorta” (ibid). Dla poważnego studenta inna wersja istnieje jako zestaw notatek z wykładów, nagranych przez Stephena Kleene i JB Rossera „podczas wykładów wygłoszonych przez Gödla w Institute for Advanced Study wiosną 1934” (por. komentarz Davisa 1965 , s. 39 i od str. 41); ta wersja nosi tytuł „O nierozstrzygalnych propozycjach formalnych systemów matematycznych”. W kolejności publikacji:

  • B. Meltzer (tłumaczenie) i RB Braithwaite (wprowadzenie), 1962. O formalnie nierozstrzygalnych propozycjach Principia Mathematica and Related Systems , Dover Publications, New York (wydanie Dover 1992), ISBN  0-486-66980-7 (pbk.) zawiera przydatne tłumaczenie niemieckich skrótów Gödla na s. 33–34. Jak wspomniano powyżej, typografia, tłumaczenie i komentarz są podejrzane. Niestety, to tłumaczenie zostało przedrukowane wraz z całą podejrzaną treścią przez
  • Stephen Hawking redaktor, 2005. Bóg stworzył liczby całkowite: matematyczne przełomy, które zmieniły historię , Running Press, Philadelphia, ISBN  0-7624-1922-9 . Artykuł Gödla pojawia się od s. 1097, z komentarzem Hawkinga zaczynającym się na s. 1089.
  • Redaktor Martin Davis , 1965. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions , Raven Press, New York, brak ISBN. Referat Gödla zaczyna się na stronie 5, poprzedzony jedną stroną komentarza.
  • Redaktor Jean van Heijenoort , 1967, 3. wydanie 1967. Od Frege do Gödel: A Source Book in Mathematical Logic, 1879-1931 , Harvard University Press, Cambridge Mass., ISBN  0-674-32449-8 (pbk). van Heijenoort wykonał tłumaczenie. Twierdzi, że „profesor Gödel zatwierdził tłumaczenie, które w wielu miejscach było dostosowane do jego życzeń”. (s. 595). Artykuł Gödla zaczyna się na s. 595; Komentarz van Heijenoorta rozpoczyna się na s. 592.
  • Redaktor Martin Davis, 1965, ibid. „O nierozstrzygalnych propozycjach formalnych systemów matematycznych”. Egzemplarz z poprawkami Gödla erraty i dodanymi notatkami Gödla zaczyna się na stronie 41, poprzedzony dwiema stronami komentarza Davisa. Dopóki Davis nie włączył tego do swojego tomu, wykład ten istniał tylko w formie powielonych notatek.

Artykuły innych

Książki o twierdzeniach

Różne odniesienia

Zewnętrzne linki