O twierdzeniach formalnie nierozstrzygalnych Principia Mathematica i systemach pokrewnych

Ten artykuł dotyczy papieru. Twierdzenia udowodnione w tym artykule można znaleźć w twierdzeniach Gödla o niezupełności .

„ Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I ” („ O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica i systemów pokrewnych I ”) to artykuł Kurta Gödla z logiki matematycznej . Złożony 17 listopada 1930 r., został pierwotnie opublikowany w języku niemieckim w tomie Monatshefte für Mathematik z 1931 r . W druku ukazało się kilka tłumaczeń na język angielski, a artykuł został włączony do dwóch zbiorów klasycznych artykułów z zakresu logiki matematycznej. Papier zawiera Twierdzenia Gödla o niezupełności , teraz fundamentalne wyniki w logice, które mają wiele implikacji dla dowodów spójności w matematyce. Artykuł znany jest również z wprowadzenia nowych technik wymyślonych przez Gödla w celu udowodnienia twierdzeń o niezupełności.

Zarys i kluczowe wyniki

twierdzenia Gödla o niezupełności , które wywarły ogromny wpływ na dziedzinę logiki matematycznej . Pojawiają się one w artykule odpowiednio jako twierdzenia VI i XI.

Aby udowodnić te wyniki, Gödel wprowadził metodę znaną obecnie jako numeracja Gödla . W tej metodzie każdemu zdaniu i dowodowi formalnemu w arytmetyce pierwszego rzędu przypisywana jest określona liczba naturalna. Gödel pokazuje, że wiele właściwości tych dowodów można zdefiniować w ramach dowolnej teorii arytmetyki, która jest wystarczająco silna, aby zdefiniować prymitywne funkcje rekurencyjne . (Współczesna terminologia funkcji rekurencyjnych i prymitywnych funkcji rekurencyjnych nie była jeszcze ustalona w momencie publikacji artykułu; Gödel użył słowa rekursiv („rekurencyjne”) dla tak zwanych prymitywnych funkcji rekurencyjnych). Metoda numeracji Gödla stała się od tego czasu powszechna w logice matematycznej.

Ponieważ metoda numeracji Gödla była nowatorska i aby uniknąć wszelkich dwuznaczności, Gödel przedstawił listę 45 wyraźnych formalnych definicji prymitywnych funkcji rekurencyjnych i relacji używanych do manipulowania i testowania liczb Gödla. Użył ich, aby podać jednoznaczną definicję formuły Bew( x ) , która jest prawdziwa wtedy i tylko wtedy, gdy x jest liczbą Gödla zdania φ i istnieje liczba naturalna, która jest liczbą Gödla dowodu φ . Nazwa tej formuły pochodzi od Beweis , niemieckiego słowa oznaczającego dowód.

Drugą nową techniką wymyśloną przez Gödla w tym artykule było użycie zdań odnoszących się do samych siebie. Gödel wykazał, że klasyczne paradoksy samoodniesienia, takie jak „ To zdanie jest fałszywe ”, można przekształcić jako samoodnoszące się formalne zdania arytmetyczne. Nieformalnie zdanie użyte do udowodnienia pierwszego twierdzenia Gödla o niezupełności brzmi: „Tego twierdzenia nie da się udowodnić”. Fakt, że takie samoodniesienie można wyrazić w ramach arytmetyki, nie był znany, dopóki nie pojawił się artykuł Gödla; niezależna praca Alfreda Tarskiego nad jego twierdzeniem o nieokreślalności przeprowadzono mniej więcej w tym samym czasie, ale opublikowano dopiero w 1936 roku.

W przypisie 48a Gödel stwierdził, że planowana druga część artykułu ustanowi związek między dowodami spójności a teorią typów (stąd „I” na końcu tytułu artykułu, oznaczające pierwszą część), ale Gödel nie opublikował druga część artykułu przed śmiercią. Jego artykuł z 1958 roku w Dialectica pokazał jednak, w jaki sposób można wykorzystać teorię typów do uzyskania dowodu spójności dla arytmetyki.

Opublikowane tłumaczenia angielskie

Za jego życia wydrukowano trzy angielskie tłumaczenia artykułu Gödla, ale proces ten nie przebiegał bez trudności. Pierwsze angielskie tłumaczenie było autorstwa Bernarda Meltzera ; została opublikowana w 1963 roku jako samodzielna praca przez Basic Books i od tego czasu została przedrukowana przez Dover i przedrukowana przez Hawkinga ( God Created the Integers , Running Press, 2005:1097ff). Wersja Meltzera - opisana przez Raymonda Smullyana jako „ładne tłumaczenie” - została negatywnie zrecenzowana przez Stefana Bauera-Mengelberga (1966). Według biografii Gödla Dawsona (Dawson 1997: 216),

Na szczęście tłumaczenie Meltzera zostało wkrótce wyparte przez lepsze, przygotowane przez Elliotta Mendelsona do antologii Martina Davisa The Undecidable ; ale Gödel zwrócił na to uwagę dopiero prawie w ostatniej chwili, a nowe tłumaczenie nadal nie do końca mu odpowiadało… kiedy poinformowano go, że nie ma wystarczająco dużo czasu, aby rozważyć zastąpienie innego tekstu, oświadczył, że tłumaczenie Mendelsona było „ ogólnie bardzo dobry” i wyraził zgodę na jego publikację. 3 [ 3 Później żałował, że się podporządkował, ponieważ opublikowany tom był w całości zepsuty niechlujną typografią i licznymi błędami drukarskimi.]

Tłumaczenie Elliotta Mendelsona pojawia się w zbiorze The Undecidable (Davis 1965: 5ff). To tłumaczenie spotkało się również z ostrą recenzją Bauera-Mengelberga (1966), który oprócz podania szczegółowej listy błędów typograficznych opisał również to, co uważał za poważne błędy w tłumaczeniu.

Tłumaczenie Jeana van Heijenoorta pojawia się w zbiorze From Frege to Gödel: A Source Book in Mathematical Logic (van Heijenoort 1967). Recenzja Alonzo Churcha (1972) opisał to jako „najdokładniejsze tłumaczenie, jakie zostało wykonane”, ale zawierała również kilka konkretnych uwag krytycznych. Dawson (1997:216) zauważa:

Ulubionym tłumaczeniem Gödla było tłumaczenie Jeana van Heijenoorta… We wstępie do tomu van Heijenoort zauważył, że Gödel był jednym z czterech autorów, którzy osobiście przeczytali i zatwierdzili tłumaczenia jego dzieł.

Ten proces zatwierdzania był pracochłonny. Gödel wprowadził zmiany do swojego tekstu z 1931 r., A negocjacje między mężczyznami „przeciągały się”: „Prywatnie van Heijenoort oświadczył, że Gödel był najbardziej wybredną osobą, jaką kiedykolwiek znał”. Między nimi „wymienili łącznie siedemdziesiąt listów i dwukrotnie spotkali się w biurze Gödla, aby rozstrzygnąć kwestie dotyczące subtelności w znaczeniu i użyciu słów niemieckich i angielskich”. (Dawson 1997:216-217).

Chociaż nie jest to tłumaczenie oryginalnego artykułu, istnieje bardzo użyteczna czwarta wersja, która „obejmuje podstawy dość podobne do tych, które omówiono w oryginalnym artykule Godla z 1931 r. O nierozstrzygalności” (Davis 1952: 39), a także własne rozszerzenia Gödla i komentarz do tematu. To pojawia się jako On Undecidable Propositions of Formal Mathematical Systems (Davis 1965: 39ff) i przedstawia wykłady w transkrypcji Stephena Kleene i J. Barkleya Rossera podczas gdy Gödel dostarczył je w Institute for Advanced Study w Princeton w stanie New Jersey w 1934 r. Davis dodał do tej wersji dwie strony erraty i dodatkowe poprawki Gödla. Ta wersja jest również godna uwagi, ponieważ w niej Gödel najpierw opisuje Herbranda , która doprowadziła do (ogólnej, tj. Herbranda-Gödla) formy rekurencji .

  • Stefana Bauera-Mengelberga (1966). Przegląd The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problemy and Computable Functions . The Journal of Symbolic Logic , tom. 31, nr 3. (wrzesień 1966), s. 484–494.
  • Kościół Alonza (1972). Przegląd książki źródłowej z logiki matematycznej 1879–1931 . The Journal of Symbolic Logic , tom. 37, nr 2. (czerwiec 1972), s. 405.
  •   Martina Davisa , wyd. (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven, Nowy Jork. Przedruk, Dover, 2004. ISBN 0-486-43228-9 .
  •   Martina Davisa (2000). Silniki logiki: matematyka i pochodzenie komputera , WW Norton & Company, Nowy Jork. ISBN 0-393-32229-7 pbk.
  • Kurt Gödel (1931), „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”. Monatshefte für Mathematik und Physik 38 : 173–198. doi : 10.1007/BF01700692 . Dostępne online za pośrednictwem SpringerLink.
  • Kurta Godela (1958). „Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes”. Dialektyka t. 12, s. 280–287. Przedruk w tłumaczeniu na język angielski w Gödel's Collected Works , tom II, Soloman Feferman i in., wyd. Oxford University Press, 1990.
  • Jean van Heijenoort , wyd. (1967). Od Fregego do Gödla: książka źródłowa o logice matematycznej 1879–1931 . Wydawnictwo Uniwersytetu Harvarda.
  •   Bernarda Meltzera (1962). O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica i systemach pokrewnych. Tłumaczenie niemieckiego oryginału przez Kurta Gödla, 1931. Basic Books, 1962. Przedruk, Dover, 1992. ISBN 0-486-66980-7 .
  • Raymonda Smullyana (1966). Przegląd O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica i systemów pokrewnych . Amerykański miesięcznik matematyczny , tom. 73, nr 3. (marzec 1966), s. 319–322.
  •   Johna W. Dawsona (1997). Dylematy logiczne: życie i twórczość Kurta Gödla , AK Peters, Wellesley, Massachusetts. ISBN 1-56881-256-6 .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems&oldid=1096952942 ”