Rozwój Teorii Dowodów

Spisu treści:

Rozwój Teorii Dowodów
Rozwój Teorii Dowodów
Anonim

Nawigacja wejścia

  • Treść wpisu
  • Bibliografia
  • Narzędzia akademickie
  • Podgląd PDF znajomych
  • Informacje o autorze i cytacie
  • Powrót do góry

Rozwój teorii dowodów

Po raz pierwszy opublikowano 16 kwietnia 2008; rewizja merytoryczna Pon 13.10.2014

Rozwój teorii dowodu można naturalnie podzielić na: prehistorię pojęcia dowodu w starożytnej logice i matematyce; odkrycie Fregego, że dowody matematyczne, a nie tylko twierdzenia matematyczne, mogą (i powinny) być reprezentowane w systemie logicznym; Stara aksjomatyczna teoria dowodu Hilberta; niepowodzenie celów Hilberta przez twierdzenia Gödla o niezupełności; Stworzenie przez Gentzena dwóch głównych typów systemów logicznych współczesnej teorii dowodu, dedukcji naturalnej i rachunku sekwencyjnego (patrz wpis dotyczący automatycznego rozumowania); zastosowania i rozszerzenia dedukcji naturalnej i rachunku sekwencyjnego, aż do interpretacji obliczeniowej dedukcji naturalnej i jej związków z informatyką.

  • 1. Prehistoria pojęcia dowodu
  • 2. Stara aksjomatyczna teoria dowodu Hilberta
  • 3. Niesprawność spójności
  • 4. Naturalna dedukcja i rachunek następczy
  • 5. Spójność działań arytmetycznych i analitycznych
  • 6. Późniejsze zmiany w dedukcji naturalnej
  • 7. Rachunek sekwencyjny: późniejsze osiągnięcia / zastosowania
  • 8. Cele teorii dowodu
  • Bibliografia

    • Teksty na temat teorii dowodu
    • Prace oryginalne i ich przedruki
    • Literatura dodatkowa
  • Narzędzia akademickie
  • Inne zasoby internetowe
  • Powiązane wpisy

1. Prehistoria pojęcia dowodu

Teorię dowodów można opisać jako badanie ogólnej struktury dowodów matematycznych i argumentów o sile dowodzenia, które napotyka się w logice. Idea takich argumentów demonstracyjnych, tj. Takich, których konkluzja wynika siłą rzeczy z przyjętych założeń, ma centralne znaczenie w Analytica Posteriora Arystotelesa: nauka dedukcyjna jest zorganizowana wokół szeregu podstawowych pojęć, które zakłada się, że są zrozumiałe bez dalszego wyjaśnienia, podstawowych prawd lub aksjomatów, które są natychmiast postrzegane jako prawdziwe. Zdefiniowane pojęcia i twierdzenia sprowadzają się do tych dwóch, przy czym drugie poprzez dowód. Arystotelesowskie ujęcie dowodu jako argumentu wskazującego bardzo dobrze pasuje do struktury starożytnej geometrii zaksjomatyzowanej u Euklidesa. Specyficzna forma logiki Arystotelesa, teoria sylogizmu, ma zamiast tego, jak się wydaje,prawie nie ma nic wspólnego z dowodami w geometrii euklidesowej. Dowody te pozostawały intuicyjne przez ponad dwa tysiące lat.

Przed pracą Fregego w 1879 roku nikt chyba nie utrzymywał, że może istnieć kompletny zestaw zasad dowodowych w sensie wyrażonym przez Frege'a, kiedy pisał, że w swoim symbolicznym języku

wszystko, co jest konieczne do prawidłowego wnioskowania, jest wyrażone w całości, ale to, co nie jest konieczne, na ogół nie jest wskazywane; nic nie pozostaje do zgadywania. (Begriffsschrift, str. 3)

(Można by twierdzić, że Boole jest wyjątkiem, jeśli chodzi o klasyczną logikę zdań). Krok naprzód Fregego był decydujący dla rozwoju logiki i studiów fundamentalnych. Kontrast do starożytnych jest wielki: Arystoteles podał wzór łączenia argumentów, ale idea skończonego, zamkniętego zbioru reguł była filozoficznie przekraczająca marzenia kogokolwiek przed Frege'em, z możliwym wyjątkiem Leibniza.

Jak wiemy dzisiaj, zasady dowodzenia Fregego są kompletne dla klasycznej logiki predykatów.

Około 1890 roku Giuseppe Peano sformalizował wnioskowanie logiczne, mając na celu przedstawienie formalnych dowodów w arytmetyce. Jego przełomowa praca Arithmetices principia, nova methodo exposita, napisana pierwotnie po łacinie, znajduje się w angielskim przekładzie w zbiorze From Frege to Gödel (1967), który redagował Jean van Heijenoort. Niestety, redaktorowi nie udało się rozpoznać, co Peano zrobił wnioskując formalnie, i rozpowszechnił się pogląd, że Peano sformalizował tylko język logiki i arytmetyki, a nie zasady dowodzenia. Jeśli przeczytamy dowody Peano nawet z niewielką uwagą, okaże się, że są to czysto formalne wyprowadzenia, które wykorzystują dwie zasady:

  1. Aksjomaty implikują ich instancje. Takie implikacje można zapisać jako wiersze w dowodach.
  2. Implikacja i jej poprzednik implikują razem następnik.

Peano bardzo starannie wymienia w każdym wierszu swoich wyprowadzeń, jaka jest formalna podstawa do napisania tego wiersza.

Russell podjął logikę Fregego, ale użył notacji i formalnych reguł dowodu Peano w artykule z 1906 roku pod tytułem „Teoria implikacji”. Jego formalna maszyneria jest dokładnie taka sama jak w Peano. W późniejszej pracy Russell zmienił system aksjomatyczny, a standard Principia Mathematica (Whitehead i Russell 1910–13) stał się standardem. Filozoficzna idea Russella, którą podążał za Frege, polegała na tym, że aksjomaty wyrażają podstawowe prawdy logiczne, a inne prawdy logiczne wywodzą się z nich poprzez modus ponens i uniwersalne uogólnienie, dwie zasady zidentyfikowane przez Frege. Matematyka miała zostać zredukowana do logiki, aby jej dowody zostały przedstawione w tym samym schemacie aksjomatycznym.

Podejście Fregego i Peano-Russella do logiki stało się powszechnie akceptowane, zwłaszcza pod wpływem Hilberta i jego współpracowników w latach dwudziestych XX wieku. W XIX wieku Frege był postacią marginalną, a dominujące było podejście algebraiczne do logiki, jak u Boole'a, a zwłaszcza Ernsta Schrödera. Oczywiste jest, że w tej tradycji istniało dobre zrozumienie zasad logiki predykatów, bo jak inaczej mogłoby istnieć twierdzenie Löwenheim-Skolema? Skolem dowiedział się o logice Fregego dzięki Principia Mathematica dopiero po opracowaniu twierdzenia w jego artykule z 1920 roku. Pierwsza część tego artykułu, szeroko czytana z powodu angielskiego tłumaczenia w książce Van Heijenoort From Frege to Gödel, oznacza koniec algebraicznej tradycja logiki, która po cichu połączyła się z teorią sieci. Inne części artykułu zawierają niezwykły początek analizy dowodów w teorii krat i geometrii rzutowej: Skolem rozważał aksjomaty teorii matematycznej z czysto kombinatorycznego i formalnego punktu widzenia, jako środki do tworzenia wyprowadzeń wzoru z danego wzory używane jako założenia. Na początku lat 90. XX wieku odkryto, że część dotycząca teorii krat zawiera rozwiązanie problemu decyzyjnego, zwanego problemem tekstowym dla swobodnie generowanych krat, którego znane rozwiązanie pochodzi z 1988 roku! Terminologia i notacja Skolema w teorii krat są takie, jak Schröder i to jest jeden z powodów, dla których jego praca była straconą szansą na teorię dowodu. Skolem rozważał aksjomaty teorii matematycznej z czysto kombinatorycznego i formalnego punktu widzenia, jako środki do tworzenia wyprowadzeń wzoru na podstawie podanych wzorów używanych jako założenia. Na początku lat 90. XX wieku odkryto, że część dotycząca teorii krat zawiera rozwiązanie problemu decyzyjnego, zwanego problemem tekstowym dla swobodnie generowanych krat, którego znane rozwiązanie pochodzi z 1988 roku! Terminologia i notacja Skolema w teorii krat są takie, jak Schröder i to jest jeden z powodów, dla których jego praca była straconą szansą na teorię dowodu. Skolem rozważał aksjomaty teorii matematycznej z czysto kombinatorycznego i formalnego punktu widzenia, jako środki do tworzenia wyprowadzeń wzoru na podstawie podanych wzorów używanych jako założenia. Na początku lat 90. XX wieku odkryto, że część dotycząca teorii krat zawiera rozwiązanie problemu decyzyjnego, zwanego problemem tekstowym dla swobodnie generowanych krat, którego znane rozwiązanie pochodzi z 1988 roku! Terminologia i notacja Skolema w teorii krat są takie, jak Schröder i to jest jeden z powodów, dla których jego praca była straconą szansą na teorię dowodu.nazwał zadanie tekstowe dla dowolnie generowanych krat, których znane rozwiązanie pochodziło z 1988 roku! Terminologia i notacja Skolema w teorii krat są takie, jak Schröder i to jest jeden z powodów, dla których jego praca była straconą szansą na teorię dowodu.nazwał zadanie tekstowe dla dowolnie generowanych krat, których znane rozwiązanie pochodziło z 1988 roku! Terminologia i notacja Skolema w teorii krat są takie, jak Schröder i to jest jeden z powodów, dla których jego praca była straconą szansą na teorię dowodu.

2. Stara aksjomatyczna teoria dowodu Hilberta

Książka Hilberta Grundlagen der Geometrie z 1899 r. Przygotowała grunt pod centralne, fundamentalne problemy matematyki wczesnych dekad XX wieku. Możemy wymienić te problemy w następujący sposób:

  1. Formalizacja teorii matematycznej. Obejmuje to wybór jego podstawowych obiektów i relacji oraz wybór aksjomatów.
  2. Dowód spójności aksjomatów.
  3. Kwestia wzajemnej niezależności i kompletności aksjomatów.
  4. Problem decyzyjny: czy istnieje metoda odpowiedzi na jakiekolwiek pytanie, które można by postawić w ramach teorii?

Jeśli chodzi o geometrię Hilberta, to próba jej sformalizowania nie dorównała ideałowi, któremu dała początek. Hilbert znalazł znacznie ważniejszą dziedzinę, do której miała zastosować jego „metamatematyka”, a mianowicie arytmetykę i analizę. Podstawą było badanie czterech podstawowych problemów w aksjomatycznych sformułowaniach czystej logiki. W ten sposób logika zdań została sformalizowana, uznana za spójną, kompletną i dającą się rozstrzygnąć. Pierwsze wyniki dotyczące logiki predykatów pochodzą z 1915 r., Kiedy Leopold Löwenheim przedstawił swoją wersję tego, co później stało się twierdzeniem Löwenheima-Skolema dla logiki predykatów (patrz wpis dotyczący logiki klasycznej). Rozwiązał również szczególne przypadki problemu decyzyjnego. Rozwój ten był niezależny od tradycji Frege-Russella, a zamiast tego opierał się na algebraicznym podejściu do logiki Ernsta Schrödera. Około 1920 rokuaksjomatyczne podejście „stylu Hilberta”, jak się je często nazywa, było znane wszystkim i zdominowało scenę logiczną; podejście algebraiczne połączyło się prawie bez zauważenia z teorią sieci. W 1928 r. W Grundzüge der theoretischen Logik Hilberta i Ackermanna przedstawiono aksjomatyczny system formalny dla logiki predykatów wraz z problemem jego kompletności. Ten ostatni rozwiązał Gödel w 1929 roku, opublikowany rok później (Gödel 1930). Czwarty podstawowy problem, problem decyzyjny dla logiki predykatów, okazał się mieć negatywne rozwiązanie w krótkim artykule Churcha w 1936 roku jako następstwo twierdzenia Gödla o niezupełności.s Grundzüge der theoretischen Logik, przedstawiono aksjomatyczny system formalny logiki predykatów wraz z problemem jego kompletności. Ten ostatni rozwiązał Gödel w 1929 roku, opublikowany rok później (Gödel 1930). Czwarty podstawowy problem, problem decyzyjny dla logiki predykatów, okazał się mieć negatywne rozwiązanie w krótkim artykule Churcha w 1936 roku jako następstwo twierdzenia Gödla o niezupełności.s Grundzüge der theoretischen Logik, przedstawiono aksjomatyczny system formalny logiki predykatów wraz z problemem jego kompletności. Ten ostatni rozwiązał Gödel w 1929 roku, opublikowany rok później (Gödel 1930). Czwarty podstawowy problem, problem decyzyjny dla logiki predykatów, okazał się mieć negatywne rozwiązanie w krótkim artykule Churcha w 1936 roku jako następstwo twierdzenia Gödla o niezupełności.

Hilbert i jego szkoła, z Bernaysem, Ackermannem i von Neumannem na czele, a także młody Herbrand we Francji, kontynuowali metamatematyczną naukę arytmetyki w drugiej połowie lat dwudziestych. Hilbert opracował metodę badania problemów ze spójnością, zwaną metodą substytucji epsilon, aby radzić sobie z kwantyfikatorami. Uważał, że pośrednie wnioskowanie z kwantyfikatorami w przypadkach z nieskończonością obiektów było kluczowym punktem dowodów zgodności i wymagało uzasadnienia. Powiedzmy, że jeśli założenie, że wszystkie liczby naturalne mają własność P, prowadzi do niemożliwości, to można wywnioskować istnienie liczby o przeciwnej własności nie-P. Centralnym problemem było zatem uzasadnienie stosowania logiki klasycznej w dowodach matematycznych, przede wszystkim arytmetycznych. Ackermann był bardzo bliski rozwiązania pod koniec lat dwudziestych XX wieku, aw szkole Hilberta panował optymizm. Potem, oczywiście, wydarzyło się nieoczekiwane, gdy Gödel udowodnił niemożność całkowitego sformalizowania elementarnej arytmetyki i, jak to wkrótce zostało zinterpretowane, niemożność udowodnienia spójności arytmetyki środkami finitarnymi, jedynymi ocenionymi jako „absolutnie wiarygodne” przez Hilberta.

3. Niesprawność spójności

Po tym, jak Gödel upublicznił niekompletność arytmetyki we wrześniu 1930 roku, von Neumann odkrył, że spójność arytmetyki należy do nieudowodnionych zdań Gödla. Niestety, Gödel dokonał tego samego odkrycia, więc von Neumann nigdy nie opublikował swojego dowodu. Jednakże, w korespondencji z Gödelem, przypuszczał, że nie da się udowodnić spójności arytmetyki, a tym samym matematyki jako całości, w pewnym sensie absolutnym. Von Neumann był kluczową postacią w recepcji wyników Gödla: Przerwał swoje wykłady na temat teorii dowodu Hilberta w Berlinie jesienią 1930 roku, aby wyjaśnić nowe odkrycia. Wydarzenia te wywołały ogromne podekscytowanie wśród matematyków, o czym świadczy zeznanie Carla Hempela:

Byłem tam na kursie u von Neumanna, który zajmował się próbą Hilberta udowodnienia spójności klasycznej matematyki za pomocą środków finitarnych. Pamiętam, że w połowie kursu von Neumann przyszedł pewnego dnia i oznajmił, że właśnie otrzymał referat od… Kurta Gödla, który pokazał, że cele, które miał na myśli Hilbert i na temat których słyszałem kurs Hilberta w Getyndze, nie mogą być w ogóle osiągnięte. Von Neumann zrezygnował zatem z pogoni za tym tematem i resztę kursu poświęcił prezentacji wyników Gödla. Odkrycie wywołało ogromne podniecenie. (Hempel 2000, s. 13)

W latach 1932–33 Gödel i Gentzen znaleźli niezależnie od siebie tłumaczenie klasycznej arytmetyki Peano na intuicjonistyczną arytmetykę Heytinga. W szczególności pokazuje, że jeśli sprzeczność można udowodnić w pierwszym, to w drugim. Wówczas spójność arytmetyki intuicjonistycznej gwarantowałaby również spójność arytmetyki klasycznej. Wynik ten był zaskoczeniem: jak wspomniano, Hilbert myślał, że „pozaskończone” dowody istnienia pośredniego będą tą częścią arytmetyki, która musi być zabezpieczona przed sprzecznością. Zgodnie z wynikiem Gödla i Gentzena, już intuicjonistyczna arytmetyka zawierała zasady, które wykraczały poza rozumowanie skończone. List, który Gentzen napisał do Heytinga 25 lutego 1933 r., Podsumowuje sytuację w następujący sposób:

Dowód konsekwencji za pomocą skończonych środków… jak dotąd się nie powiódł, więc pierwotny cel Hilberta nie został osiągnięty. Jeśli, z drugiej strony, uznamy pozycję intuicjonistyczną za bezpieczną podstawę samą w sobie, tj. Jako konsekwentną, mój wynik zapewnia spójność klasycznej arytmetyki. Gdyby ktoś chciał spełnić wymagania Hilberta, nadal pozostawałby zadanie wykazania intuicjonistycznej arytmetyki spójnej. Nie jest to jednak możliwe nawet przy zastosowaniu aparatu formalnego klasycznej arytmetyki, na podstawie wyniku Gödla w połączeniu z moim dowodem. Mimo to jestem skłonny wierzyć, że dowód spójności dla arytmetyki intuicjonistycznej z jeszcze bardziej oczywistego stanowiska jest możliwy i również pożądany. (Menzler-Trott 2007, s. 38)

Ostatnim z wymienionych był cel, który Gentzen wyznaczył sobie na początku 1932 roku, kiedy w liście do swojego starego nauczyciela Hellmutha Knesera napisał:

Postawiłem jako swoje szczególne zadanie, aby znaleźć dowód na spójność dedukcji logicznej w arytmetyce… Zadanie to staje się problemem czysto matematycznym poprzez sformalizowanie dedukcji logicznej. Dowód zgodności był do tej pory przeprowadzany tylko dla szczególnych przypadków, na przykład arytmetyki liczb całkowitych bez zasady całkowitej indukcji. W tym miejscu chciałbym przejść dalej i wyjaśnić przynajmniej arytmetykę z pełną indukcją. Pracuję nad tym od prawie roku i mam nadzieję, że wkrótce skończę, a następnie przedstawię tę pracę jako moją dysertację (z prof. Bernaysem). (Menzler-Trott 2007, s. 31)

4. Naturalna dedukcja i rachunek następczy

Realizując swój program spójności, Gentzen postawił sobie za pierwsze zadanie analizę czysto logicznej dedukcji, którą później rozszerzył na arytmetykę i analizę. W swojej rozprawie (1934–1935) Gentzen stwierdza, że postawił sobie za zadanie analizę dowodów matematycznych występujących w praktyce. Pierwsza obserwacja jest taka, że rzeczywiste dowody nie są oparte na aksjomatach wyrażonych w języku logicznym, jak w teorii dowodu aksjomatycznego Hilberta. Najbardziej typową cechą jest to, że twierdzenia twierdzą przy pewnych założeniach. Założenia są analizowane na części, a wniosek jest również analizowany na części, dopóki te dwie analizy się nie spotkają i można będzie zsyntetyzować dowód. Ta ostatnia analiza opiera się na tym, co Gentzen nazwał regułami wstępnymi: dają one warunki wystarczające do wyprowadzenia zdania o danej formie. Na przykład,aby wyprowadzić spójnik A i B, wystarczy wyprowadzić osobno spójniki A i B. Wnioskowanie formalnie jak w regule

AB &JA
A i B.

Zamiast tego założenia są analizowane pod kątem ich elementów składowych za pomocą reguł eliminacji, które w zasadzie dają natychmiastowe konsekwencje założeń. Na przykład koniunkcja używana jako założenie może zostać rozłożona na części składowe, tak jak w regułach

A i B. & E 1
ZA
A i B. & E 2
b

Gentzen opracował i badał system dedukcji naturalnej w 1932 roku i do września 1932 roku doszedł do rachunku dedukcji naturalnej (w skrócie ND), który jest dziś standardem. W tym czasie zauważył, że jeśli po wprowadzeniu, powiedzmy wyprowadzeniu A i B z A i B oddzielnie, następuje odpowiednia eliminacja, powiedzmy, wyprowadzenie A, wzór A i B stanowi lokalne maksimum, a wzgórek”, który można wyeliminować. Nazwał również takie pagórki „objazdami”, a to, co obecnie nazywa się konwersją objazdową, usuwa takie niepotrzebne pary kroków wprowadzających-eliminujących. Rezultatem etapów „normalizacji” jest wyprowadzenie w „normalnej formie”.

Implikacja jest prawdopodobnie bardziej typowa dla ND niż koniunkcja: aby wyprowadzić A ⊃ B, zakłada się tymczasowo A, a następnie próbuje wyprowadzić B. Jeśli to się powiedzie, tymczasowe założenie zostaje zamknięte lub „rozładowane”, gdy wyciągnięty zostanie wniosek do A ⊃ B, jak w schematycznym wyprowadzeniu

[A]
b ⊃I
A ⊃ B

Z drugiej strony, A ⊃ B można wyeliminować, jeśli znaleziono wyprowadzenie A, bo wtedy B można wywnioskować:

A ⊃ BA ⊃E
b

Jeśli po regule ⊃I występuje ⊃E, istnieje nienormalność, która jest usuwana przez konwersję objazdową: wyprowadzenie B (i to, co następuje po nim) jest konstruowane przez wyprowadzenie przesłanki mniejszej A reguły eliminacji i wyprowadzenie B z założenia A we wstępie. Te dwa elementy są połączone razem w wyprowadzenie B, które nie ma wzoru na objazd A ⊃ B. W tezie Gentzena wszystkie założenia są ostatecznie zamknięte wprowadzeniami implikacyjnymi, ale obecnie rozważa się także wyprowadzenia, które pozostawiają zbiór formuł jako założenia otwarte.

Patrząc na reguły koniunkcji i implikacji, można zauważyć, że przesłanki (formuły bezpośrednio nad linią wnioskowania) są podformułami wniosku w regułach I, podczas gdy w regułach E. jest odwrotnie. Gentzen zauważył, że w wyprowadzeniach normalnych ta właściwość pojedynczych kroków jest dziedziczona przez całe derywację w tym sensie, że wszystkie formuły są podformułami wniosku. Wynik ten dał jako produkt uboczny metodę decyzyjną dla intuicjonistycznej logiki zdań. Kolejnym wnioskiem był składniowy dowód spójności: jeśli można udowodnić sprzeczność, wszystko jest możliwe, ale formuła atomowa, powiedzmy, nie ma dowodu: jeśli ma dowód, ma normalny dowód, ale żadne zasady E nie mają zastosowania do formuła atomowa i żadna reguła ja również tego nie zamyka.

Pomysł Gentzena polegał na rozszerzeniu naturalnej dedukcji na system arytmetyki poprzez dodanie reguły odpowiadającej zasadzie indukcji całkowitej. Spójność wynikałaby wówczas z normalizacji wyprowadzeń i właściwości podformuły. Na początku 1933 roku Gentzen zdał sobie sprawę, że ta strategia dowodzenia nie przejdzie: reguła indukcji jest schematyczna i ma nieskończoną liczbę instancji, bez ograniczenia złożoności formuł indukcyjnych. Niemożliwe byłoby wcześniejsze ograniczenie tych formuł, a zatem żadna własność podformuły nie może być zachowana. Po tym niepowodzeniu Gentzen dosłownie wyciągnął ze swojej wczesnej pracy magisterskiej tłumaczenie z arytmetyki klasycznej na intuicjonistyczną i przedłożył go jako artykuł w marcu 1933 roku, ale wycofał artykuł po wysłuchaniu publikacji Gödla o wyniku.

Gentzen napisał, że nie był w stanie udowodnić twierdzenia o normalizacji dla klasycznego systemu ND. Dlatego wynalazł inny rachunek logiczny, który nazwał rachunkiem sekwencyjnym (Sequenzenkalkul, dosłownie „rachunek ciągów”) i uczynił go głównym tematem swojej pracy. Nazwa rachunku pochodzi od przedstawienia założeń wyprowadzenia w postaci listy. Słowo „sequent” użyte jako rzeczownik jest sugestią sformułowaną przez Kleene'a w jego „Introduction to Metamathematics” (1952: 441), przyjętym w wielu językach w postaci czysto wymyślonych słów.

Rachunek sekwencyjny, w skrócie SC, można postrzegać jako formalną reprezentację relacji wyprowadzalności w dedukcji naturalnej. Sekwencja składa się z listy Γ formuł, strzałki (w Gentzen później używano także innych znaczników) i jednej formuły jako wniosku. Lista podaje założenia, od których wniosek zależy w wyprowadzeniu, w zapisie lokalnym, gdzie w ND znajdują się w liściach drzewa pochodnego. Gentzen uogólnił również sekwencje, tak że zamiast jednego wniosku mają listę możliwych przypadków po strzałce. Ta nowość doprowadziła do pierwszego zadowalającego sformułowania systemu dowodowego dla logiki klasycznej. Reguły Gentzena dotyczące koniunkcji i implikacji są następujące, z przecinkami oddzielającymi elementy na listach:

Spójnik
Γ Δ, A Γ → Δ, B R &
Γ Δ, A i B
A, Γ Δ L & 1
A & B, Γ Δ
B, Γ Δ L & 2
A & B, Γ Δ
Implikacja
A, Γ Δ, B R⊃
Γ Δ, A ⊃ B
Γ Θ, AB, Δ Λ L⊃
A ⊃ B, Γ, Δ Θ, Λ

To nie jest miejsce na wyjaśnienie szczegółów ND i SC (ale zobacz wpis dotyczący automatycznego rozumowania). Gentzen sformułował ten ostatni, oznaczony LK, tak, że podał intuicjonistyczny rachunek, oznaczony LJ, jako przypadek szczególny, w którym konkluzja jest listą co najwyżej jednego przypadku. Następnie udowodnił analogię twierdzenia o normalizacji dla rachunku klasycznego, rachunek i dowód starannie sformułowane, tak że wynik dla rachunku intuicjonistycznego był szczególnym przypadkiem dla rachunku klasycznego. W LJ i LK L oznacza „logistykę”, termin, którym Gentzen odnosi się do aksjomatycznych rachunków logiki Frege'a, Russella, Hilberta i Bernaysa. W takich obliczeniach każda linia w wyprowadzeniu jest sama w sobie poprawna, tj. Logiczna prawda, skąd ten termin. Litery K i J pochodzą od niemieckich słów klassisch i intuitionistisch.(To ostatnie powinno więc być pisane wielką literą „I”, ale starszy niemiecki używa dużej litery „J” dla dużej litery „I”).

Gentzen nazwał analogię normalizacji niewyobrażalną nazwą Hauptsatza „głównym twierdzeniem”. Dzisiejsza standardowa terminologia to „twierdzenie o eliminacji cięcia”. Wszystkie reguły logiczne SC mają właściwość podformuły w bardzo bezpośrednim znaczeniu: każda formuła przesłanki jest formułą lub podformułą we wniosku. Reguła łączenia derywacji, analogiczna do tej wyjaśnionej powyżej w przypadku konwersji objazdów w ND, nosi nazwę „cut”. W nim formuła A pojawia się jako przypadek w pierwszym założeniu i jako założenie w drugim. Podsumowując, formuła ta zniknęła, a założenia obu przesłanek zebrały się razem:

Γ AA, Δ C Skaleczenie
Γ, Δ C

Zatem cięcie jest jedyną regułą, która sprawia, że formuła „znika” w derywacji. Gentzen wykazał, że wystąpienia reguły cięcia można wyeliminować z derywacji, permutując je w górę, aż osiągną punkty, w których zaczyna się derywacja. W ND punktem wyjścia są założenia, w SC są to „ciągi początkowe” postaci A → A, w których formuła założenia A jest jednocześnie wnioskiem. Cięcie o takiej kolejności, jak jedna przesłanka, ma drugą przesłankę równą konkluzji i dlatego może zostać usunięte.

Po dowodzie eliminacji cięcia Gentzen nie miał pożytku z dowodu normalizacji dla intuicjonistycznej naturalnej dedukcji. Pierwszą odręczną wersję swojej pracy, ze szczegółowym dowodem normalizacji (odpowiadającym około 13 wydrukowanym stronom) przekazał Bernaysowi, ale ten ostatni wydaje się nigdy nie zdawać sobie sprawy z tego, co ma w rękach. Dowód, wśród artykułów Bernays w Zurychu, został odkryty przez autora w lutym 2005 roku i jest obecnie dostępny w tłumaczeniu na język angielski (Gentzen 1933 [2008]).

5. Spójność działań arytmetycznych i analitycznych

Po pracy magisterskiej na temat ND i SC dla czystej logiki, Gentzen kontynuował swój plan udowodnienia spójności arytmetyki. Wynik był gotowy do grudnia 1934 roku. Jaki był ten pierwszy dowód, nie jest szczegółowo znany. Jednak list do Bernays z 1938 r. Wskazuje, że dowód, który Gentzen spisał do lata 1935 r., Nie był tym oryginalnym, ale drugim dowodem (patrz Menzler-Trott 2001, 79). Ten drugi dowód został skrytykowany przez Bernaysa i Gödela, którzy dyskutowali o nim podczas rejsu atlantyckiego do Princeton we wrześniu 1935 roku. Idea Gentzena w tym dowodzie była następująca: po pierwsze, weź fragment koniugacji-negacji-uniwersalnej kwantyfikacji naturalnej dedukcji jako logikę użytą w formalizacja arytmetyki. Następnie zapisz każdą instancję reguły tak, aby przesłanki i wnioski miały otwarte założenia wymienione po lewej stronie,ze strzałką oddzielającą zakończenie, więc jako sekwencje. Ten wariant ND jest teraz nazywany ND w stylu SC. Rozważmy sekwencję Γ C. Jeśli konkluzja jest formułą atomową, jest to równanie między liczbami. W najgorszym przypadku jest fałszywa, więc rozważ listę założeń. Jeśli jedno założenie jest koniunkcją, zamień je na wybrany przez siebie spójnik, jeśli jest to kwantyfikacja uniwersalna, przez instancję. Jeśli jest to negacja ¬ A, zamień wniosek na A. Jeśli na jakimkolwiek etapie tego „procesu redukcji” konkluzja sekwencji jest formułą złożoną, to jako możliwy wniosek należy wziąć pod uwagę jakikolwiek spójnik lub dowolny przykład uniwersalnej kwantyfikacji. W przypadku zaprzeczenia ¬ A jako wniosek, przenieś A do części założeniowej i zamień wniosek na 0 = 1. Gentzen pokazuje, że postępując w ten sposób przy założeniu, że dany ciąg jest dający się wyprowadzić, można znaleźć prawdziwe równanie jako wniosek lub fałszywe równanie jako założenie. A zatem,nie ma ciągów dających się wyprowadzić, przy czym wszystkie założenia są prawdziwe, a wniosek fałszywy.

Nie było jasne dla Gödla i Bernaysa, co zakładał dowód; myśleli, że przyjęło to, co w matematyce intuicjonistycznej jest znane jako twierdzenie wachlarza, ale było to fałszywe. Zakończenie procedury redukcji Gentzena można zamiast tego wykazać poprzez indukcję na dobrze ugruntowanych drzewach („indukcja słupkowa”), zasadę, którą Gentzen zastosował na podstawie intuicyjnej. W każdym razie, rezultatem krytyki było to, że Gentzen zmienił się bez dalszych ceregieli na trzeci dowód, który wykorzystuje słynną zasadę indukcji pozaskończonej aż do pierwszej liczby epsilon. Ta indukcja została przedstawiona za pomocą kodowania wykorzystującego liczby dziesiętne. Konkretny rezultat zmian w artykule Gentzena opublikowanym w 1936 roku nie był jednak dobry: rachunek logiczny został zmieniony w połowie artykułu złożonego z siedemdziesięciu kilku stron, który stał się bardzo trudny do odczytania. Dlatego Gentzen podał kolejny, według obecnych obliczeń, czwarty dowód spójności arytmetyki w 1938 r. (W archiwach Bernays w ETH w Zurychu), tym razem w oparciu o klasyczny rachunek sekwencyjny LK z 1933 r. Jak wspomniano, korespondencja z Bernays wskazuje, że w ten sposób powrócił do metody dowodowej, która doprowadziła do sukcesu w 1934 r. Zastosowanie indukcji pozaskończonej jest wyraźnie widoczne w artykule z 1938 r. za pomocą notacji porządkowej. Takie zasady indukcji w „drugiej klasie liczbowej” Cantora są szczegółowo omówione w wykładzie Hilberta „Über das Unendliche” z 1925 r. („O nieskończoności”, opublikowanym w 1926 r.), Artykule, do którego nawiązał Gentzen.tym razem na podstawie klasycznego rachunku sekwencyjnego LK z 1933 r. Jak wspomniano, korespondencja z Bernaysem wskazuje, że w ten sposób powrócił do metody dowodzenia, która doprowadziła do sukcesu w 1934 r. Użycie indukcji pozaskończonej jest wyraźnie widoczne w artykule z 1938 r. notacja porządkowa. Takie zasady indukcji w „drugiej klasie liczbowej” Cantora są szczegółowo omówione w wykładzie Hilberta „Über das Unendliche” z 1925 r. („O nieskończoności”, opublikowanym w 1926 r.), Artykule, do którego nawiązał Gentzen.tym razem na podstawie klasycznego rachunku sekwencyjnego LK z 1933 r. Jak wspomniano, korespondencja z Bernaysem wskazuje, że w ten sposób powrócił do metody dowodzenia, która doprowadziła do sukcesu w 1934 r. Użycie indukcji pozaskończonej jest wyraźnie widoczne w artykule z 1938 r. notacja porządkowa. Takie zasady indukcji w „drugiej klasie liczbowej” Cantora są szczegółowo omówione w wykładzie Hilberta „Über das Unendliche” z 1925 r. („O nieskończoności”, opublikowanym w 1926 r.), Artykule, do którego nawiązał Gentzen. Wykład z 1925 r. „Über das Unendliche” („O nieskończoności”, wyd. 1926), artykuł, do którego nawiązał Gentzen. Wykład z 1925 r. „Über das Unendliche” („O nieskończoności”, wyd. 1926), artykuł, do którego nawiązał Gentzen.

Można by pomyśleć, że to tyle, ale Gentzen miał powód, by przedstawić nawet czwarty dowód spójności arytmetyki w swoim ostatnim artykule opublikowanym w 1943 r., Ale napisanym przed wojną w 1939 r. Rozszerzył arytmetykę Peano na transfinite liczby porządkowe i stworzył Zasada indukcji pozaskończonej jest częścią tego rozszerzonego rachunku różniczkowego. Następnie wykazał bezpośrednio, że indukcja pozaskończona do pierwszej liczby epsilon ε 0 jest wyrażalna, ale nie dająca się udowodnić w systemie. Twierdzenie o niezupełności Gödla zostało więc udowodnione w zupełnie inny sposób. Idea dowodu jest, w skrócie, następująca: najpierw określono, co to znaczy wyprowadzić indukcję pozaskończoną do określonej liczby porządkowej w systemie. Po drugie, liczby porządkowe poniżej ε 0są powiązane z derywacjami. Nazywa się to „wartościami”. Następnie pokazano, że jeśli indukcja pozaskończona do liczby porządkowej daje się wyprowadzić, liczba ta nie może być większa niż wartość wyprowadzenia. Dlatego indukcji pozaskończonej do ε 0 nie można wyprowadzić.

Ponieważ zasada indukcji może być wyrażona, ale nie udowodniona w zwykłej arytmetyce, znaleziono wzór nie dający się udowodnić w arytmetyce Peano. Łatwą konsekwencją wersji Gentzena twierdzenia o niezupełności jest spójność arytmetyki Peano, ponieważ w niespójnym systemie wszystko byłoby możliwe do udowodnienia. W przeciwieństwie do „sztucznej”, niemożliwej do udowodnienia formuły Gödla, która została uzyskana poprzez kodowanie arytmetycznego predykatu możliwości udowodnienia, zasada indukcji pozaskończonej Gentzena jest zasadą „zwykłej” matematyki.

Ostatni dowód Gentzena określił „porządkową teorię dowodu” arytmetyki Peano, a mianowicie ten, który jest potrzebny do udowodnienia spójności, z właściwością, której nic mniej by nie wystarczyło. Praca ta zapoczątkowała teorię dowodu porządkowego. Było to bez wątpienia najbardziej niezwykłe podstawowe osiągnięcie arytmetyki po twierdzeniach Gödla o niekompletności, ale nadal jest w dużej mierze nieznane - można znaleźć wiele książek o twierdzeniach Gödla, w których nawet nie wspomina się o Gentzenie.

Wydaje się, że Gödel nie pomyślał o przedstawieniu dowodu spójności arytmetyki poprzez użycie nie-finitarnych, ale wciąż konstruktywnych zasad. Pod koniec lat trzydziestych, przynajmniej od 1938 roku, w odpowiedzi na dowód Gentzena rozwinął swoją własną interpretację logiki intuicjonistycznej i arytmetyki, którą nazwano interpretacją Dialectica. Używa obliczalnych funkcjonałów do interpretacji dowodów intuicjonistycznej arytmetyki. Gödel opublikował interpretację dopiero w 1958 r., Mimo że przedstawił ją na wykładach w 1941 r. Nie wiadomo, czy omawiał tę sprawę, gdy spotkał Gentzena w grudniu 1939 roku.

Na prośbę Bernays, Ackermann odtworzył dowód Gentzena w kategoriach rachunku epsilon Hilberta w 1940 roku. Artykuł Ackermanna był punktem wyjścia dla interpretacji arytmetyki Kreisela z 1951 r. „Bez kontrprzykładu”. Było zaskoczeniem, gdy publikacja zebranych dokumentów Gödla ujawniła jego „Zilsel-lecture” w Wiedniu w 1938 roku: zarysował tam tę interpretację jako przeformułowanie dowodu Gentzena z 1935 roku. (Kwestia ta jest szczegółowo omówiona w Tait (2005), który sam pracował nad interpretacją bez kontrprzykładu i jej rozszerzeniem na analizę w latach 60.).

Kolejnym oczywistym zadaniem teorii dowodu, po dowodzie spójności arytmetyki, było udowodnienie spójności analizy, czyli teorii liczb rzeczywistych. Gentzen wykonał pewną pracę w tym kierunku, ale jesienią 1939 r. Został przydzielony do służby wojskowej (obserwował i podawał typ, liczbę i kierunek samolotów przelatujących nad miastem Brunszwik, dopóki nie został trafiony załamanie na początku 1942 r.). Od 1943 r. wznowił pracę nad analizą, ale trudności związane z tematem były duże, podobnie jak praktyczne trudności życiowe spowodowane wojną. Analiza miała być sformułowana jako system arytmetyki drugiego rzędu, co oznacza, że kwantyfikacja jest rozszerzona na predykaty teorii liczb lub, równoważnie, na zbiory liczb naturalnych. Teoria liczb drugiego rzędu jest używana w ostatniej pracy Gentzena,opublikowany w 1943 r., w którym pokrótce wykazano, że zasada indukcji pozaskończonej do ε0 można wyprowadzić w teorii liczb drugiego rzędu.

Minęło ponad pół wieku bez konstruktywnego dowodu na spójność pełnej arytmetyki drugiego rzędu. Do pionierów w tej dziedzinie należeli Kurt Schütte i Gaisi Takeuti. Pierwszy stworzył w 1951 r. Nieskończony rachunek sekwencyjny, aby w przejrzysty sposób przedstawiać dowody spójności, drugi zamiast tego używał bardziej tradycyjnego rachunku w stylu Gentzena (patrz Takeuti 1987).

W aktualnych badaniach nad teorią dowodową arytmetyki drugiego rzędu bada się tak zwane podsystemy arytmetyki drugiego rzędu. Najsilniejsze wyniki na dzień dzisiejszy to, w bardzo krótkim zarysie, następujące: niech X będzie przekraczać predykaty z teorii liczb. Formuła taka jak X (x) stwierdza, że x ma właściwość wyrażoną przez X. Możemy teraz używać logiki pierwszego i drugiego rzędu do tworzenia formuł złożonych, takich jak ∀ X (X x ∨ ¬ X x). Zbiór liczb naturalnych, dla którego zachodzi taka formuła z jednym uniwersalnym kwantyfikatorem drugiego rzędu, nazywa się zbiorem Π11 (w tym przypadku całością liczb naturalnych). Bardziej ogólnie, aksjomat pojmowania ma postać ∃ X ∀ x (X x ↔ B (x)). Jeśli formuła B nie ma kwantyfikatorów drugiego rzędu, aksjomat daje to, co nazywa się rozumieniem arytmetycznym lub ACA. Jeśli B może mieć postać ∀ Y ∃ ZC (x) bez innych kwantyfikatorów drugiego rzędu, otrzymujemy specjalny przypadek zrozumienia Π12. Dowody zgodności dla podsystemu arytmetyki drugiego rzędu ze zrozumieniem Π12 zostały przedstawione przez Toshiyasu Arai i Michaela Rathjena w połowie lat 90. (patrz Rathjen 1995).

6. Późniejsze zmiany w dedukcji naturalnej

W czasie gdy Gentzen wypracował swój system dedukcji naturalnej, Stanisław Jaskowski rozwijał także logiczny system rozumowania z założeniami. Wzory w derywacjach są ułożone w sukcesję liniową, ale praca Jaskowskiego z 1934 roku pozostała fragmentaryczna i bez istotnych rezultatów, takich jak własność podformuły. Liniowy wariant naturalnej dedukcji jest stosowany w wielu pedagogicznych ekspozycjach logiki elementarnej (zwanych czasami „systemami Fitcha”). Gentzen znalazł pracę Jaskowskiego w czerwcu 1936 r., Kiedy obaj byli w Münster, i uznał liniowy układ formuł za ulepszenie, „wyzwolenie z kaftana drzewiastej formy”, na takie, które odzwierciedla „liniowość myślenia” (to pierwsze z niepublikowane notatki, ta ostatnia z pracy Gentzena).

System naturalnej dedukcji pozostawał uśpiony przez około trzydzieści lat, aż do rozprawy Daga Prawitza z 1965 r., Natural Deduction: A Proof-Theoretical Study. Kolejność, w jakiej Prawitz przedstawił twierdzenie o normalizacji, różniła się od tej we wczesnej pracy magisterskiej Gentzena. Prawitz podał najpierw twierdzenie o normalizacji i własność podformuły dla systemu naturalnej dedukcji dla logiki klasycznej. Ten system nie zawiera żadnej dysjunkcji ani istnienia. W drugim etapie rozważał intuicjonistyczną dedukcję naturalną dla pełnego języka logiki predykatów i sprowadził jej normalizację do usunięcia objazdowych konwertowalności, jak w przypadku fragmentu logiki klasycznej. Kiedy dowód Gentzena na normalizację wyszedł na jaw w 2005 roku, Prawitz powiedział w rozmowie z niniejszym autorem, że jest jasne, że Gentzen znał wynik,bo uwagi w wydrukowanej pracy są tak sugestywne.

Pod koniec lat sześćdziesiątych XX wieku problemem stała się silna normalizacja: Prawitz, korzystając z wcześniejszych prac Williama Taita i Jean-Yvesa Girarda, udowodnił w 1971 roku, że nienormalności w derywacji można przekształcić w dowolnej kolejności, z kończącym procesem normalizacji i unikalnym w rezultacie normalne wyprowadzenie. Wydaje się, że Gentzen nie zauważył tego drugiego, ale wydaje się, że uważał raczej przeciwnie, z powodu niepowodzenia tej właściwości w zakresie eliminacji cięć w kolejnych rachunkach.

Mniej więcej w tym samym czasie, gdy badano silną normalizację, pojawiła się korespondencja Curry-Howard. Curry w swojej pracy nad logiką kombinacyjną pod koniec lat pięćdziesiątych XX wieku zaobserwował analogię między eliminacją implikacji w naturalnej dedukcji a zastosowaniem funkcjonalnym (Curry i Feys 1958). Pomysł był tak stary jak logika intuicjonistyczna: przez „wyjaśnienie BHK” łączników i kwantyfikatorów (dla Brouwera-Heytinga-Kołmogorowa) formy zdań w logice intuicjonistycznej wyrażają zalecenia, jak udowodnić te zdania: koniunkcja A i B jest udowodnione przez osobne udowodnienie A i B, rozłączenie A ∨ B przez udowodnienie jednego z A i B, a implikacja A ⊃ B przez pokazanie, jak przekształcić dowolny dowód A w jakiś dowód B i tak dalej. Te wyjaśnienia są bardzo zbliżone do wprowadzających zasad dedukcji naturalnej,ale nie wiadomo, jaki był ich wpływ na myśl Gentzena.

Korespondencja Curry-Howarda z artykułu Williama Howarda z 1969 r., Ale opublikowanej dopiero w 1980 r., Opiera się na zasadzie „formuły jako typy” lub w innym żargonie, na zasadzie „propozycji jako zestawy”. Zdanie jest traktowane jako zbiór dowodów. Prawda zdania odpowiada niepustości zbioru. Dowody A ⊃ B są teraz funkcjami od (dowodów) A do (dowodów) B, a sam A ⊃ B jest zbiorem takich funkcji. Zatem, jeśli f: A ⊃ B i a: A, to aplikacja funkcjonalna daje f (a): B. Odwrotność, odpowiadająca wprowadzeniu implikacji, ujęta jest w zasadzie funkcjonalnej abstrakcji rachunku λ Alonzo Churcha.

Korespondencja Curry-Howarda uczyniła intuicjonistyczną dedukcję naturalną częścią programu nauczania informatyki: daje semantykę obliczeniową logice intuicjonistycznej, w której obliczenia, a bardziej ogólnie wykonywanie programów, odbywa się poprzez normalizację. Dowodem na implikację A ⊃ B, powiedzmy, jest program, który przekształca dane typu A na wyjście typu B. Konstrukcja obiektu (dowód, funkcja, program) f typu A ⊃ B kończy się abstrakcją. Gdy obiekt a typu A jest wprowadzany do f jako argument, wynikowe wyrażenie nie jest normalne, ale ma formę, która odpowiada wprowadzeniu, po którym następuje eliminacja. Normalizacja teraz przebiega tak samo, jak wykonanie programu f. Użycie logiki intuicjonistycznej nie jest związane z żadną intuicjonistyczną filozofią matematyki,ale jest tylko systematyczną gwarancją zakończenia wykonywania programów komputerowych.

7. Rachunek sekwencyjny: późniejsze osiągnięcia / zastosowania

Rozprawa doktorska Gentzena oznaczała narodziny teorii dowodu strukturalnego, w przeciwieństwie do starej aksjomatycznej teorii dowodu Hilberta. Niezwykły krok naprzód w rozwoju systemów rachunku sekwencyjnego zrobił Oiva Ketonen w swojej rozprawie doktorskiej z 1944 roku. Ketonen, student matematyki i filozofii w Helsinkach, wyjechał do Getyngi w 1938 roku, aby studiować teorię dowodu z Gentzenem - najbliższym studentowi, który kiedykolwiek miał. Wydaje się, że połączenie zostało ustanowione przez profesora filozofii Ketonena, Eino Kailę, który spotkał Gentzena w 1936 roku w Münster. Ketonen wspominał później, że Gentzen był „sympatycznym młodym człowiekiem o niewielu słowach”, który dał mu wprowadzenie do systemów i wyników teorii dowodu. Ketonen”Najbardziej znanym odkryciem jest rachunek sekwencyjny dla klasycznej logiki zdań, której reguły logiczne są odwracalne, co oznacza, że ilekroć ciąg ma postać zgodną z wnioskiem reguły logicznej, odpowiednie przesłanki, zdefiniowane jednoznacznie z danego ciągu a reguła jest również wyprowadzalna. Odwrotna sytuacja jest natychmiastowa (wystarczy zastosować regułę). Na przykład reguły L & i L⊃ są modyfikowane w

A, B, Γ Δ L &
A & B, Γ Δ
Γ Δ, AB, Γ Δ L⊃
A ⊃ B, Γ Δ

Jest tylko jedna lewa reguła dla koniunkcji (a podwójnie tylko jedna prawa reguła dla rozłączenia). Lewa reguła implikacji ma tak zwane „wspólne konteksty”: założenia i przypadki we wniosku, z wyjątkiem formuły z łącznikiem, są identyczne w obu przesłankach. Pomysł Ketonena polegał na zdefiniowaniu systemu wyszukiwania dowodów: zaczynamy od określonego ciągu, który ma być wyprowadzony, wybieramy w nim formułę i zapisujemy przesłanki reguły, która może zakończyć dany ciąg. Przez odwracalność kwestię wyprowadzalności zastępuje się jednym lub dwoma równoważnymi pytaniami o wyprowadzalności na prostszych ciągach. Nowe reguły są potrzebne, aby zapewnić jednoznacznie zdefiniowane przesłanki w takim rozkładzie „najpierw pierwiastek”.

Dowód odwracalności reguł logicznych jego rachunku sekwencyjnego Ketonena wykorzystywał strukturalną regułę cięcia. Później Kurt Schütte (1950) i Haskell Curry (1963) podali bezpośrednie dowody odwracalności, przy czym ta ostatnia wyraźnie wskazuje, że inwersje zachowują wysokość: jeśli dany ciąg można wyprowadzić w co najwyżej n krokach, przesłanki reguły, która może wywnioskować, że sekwencja ma również wyprowadzenie w co najwyżej n krokach.

Jak wiele prac Ketonena wywodzi się z sugestii Gentzena, pozostaje nieznane, ponieważ nie znaleziono żadnej korespondencji. Ketonen pisze we wstępie do swojej pracy, że „Dr. G. Gentzen z Getyngi skierował mnie na problematyczny obszar tej pracy”. Teza ta była jedynym oryginalnym dziełem logiki Ketonena, ocalonym od zapomnienia przez długą recenzję, którą Bernays napisał o niej dla The Journal of Symbolic Logic w 1945 roku.

Jedną osobą, która znała rachunek Ketonena pod koniec lat czterdziestych była Evert Beth. Kiedy Beth później, w 1955 roku, przedstawił swój dobrze znany rachunek tableau, wydaje się, że zapomniał o pochodzeniu rachunku tableau jako przeformułowaniu tego z Ketonen, ale zamiast tego odnosi się do wpływowego Wprowadzenia Kleene'a do metamatematyki z 1952 roku. Kleene wziął do rachunku Ketonena z recenzji Bernaysa, a także omówił intuicjonistyczny rachunek sekwencyjny, w którym odwracalność jest bardziej ograniczona niż w rachunku klasycznym. Wraz z książką Kleene, późniejsze rachunki Gentzena stały się powszechnie znane i dostępne.

Prace Kleene z wczesnych lat pięćdziesiątych XX wieku zapoczątkowały także niezwykły rozwój rachunku sekwencyjnego, a mianowicie klasycznych i intuicjonistycznych rachunków „wolnych od skurczów”, obecnie oznaczanych przez G3c i G3i. Te rachunki mają tę właściwość, że nie są potrzebne żadne z oryginalnych „reguł strukturalnych” Gentzena. Zasada „osłabienia” pozwala na dodanie zbędnych przypadków i założeń, a reguła „skrócenia” na usunięcie jednej kopii wzoru, jeśli na liście znajdują się dwa, jak w

Osłabiający Skurcz
Γ Δ Wk
A, Γ Δ
A, A, Γ Δ Ctr
A, Γ Δ

Analogiczne reguły pozwalają na osłabianie i kurczenie właściwych, następujących po sobie części sekwencji. Osłabienie staje się regułą, którą można wyeliminować, pozwalając początkowym sekwencjom mieć postać A, Γ Δ, A zamiast A → A Gentzena. Skurcze można również wyeliminować poprzez odpowiednie sformułowanie reguł. Ważne jest to, że w wyszukiwaniu dowodowym od początku nie trzeba stosować żadnych reguł, które spowodowałyby powielenie formuły w założeniu. Bez tego wyniku nie doszłoby do zakończenia poszukiwań dowodowych.

Rachunek klasyczny ma wspomnianą wyżej właściwość odwracalności reguł logicznych z zachowaniem wysokości. Albert Dragalin pod koniec lat siedemdziesiątych udoskonalił rachunek do takiego, w którym reguły strukturalne są ponadto „dopuszczalne z zachowaniem wysokości”, co oznacza, że ilekroć przesłanka takiej reguły jest wyprowadzalna, wniosek jest możliwy do wyprowadzenia bez reguły i co najwyżej z tym samym rozmiar (maksymalna liczba wystąpień reguły w gałęzi pochodnej) wyprowadzenia. Ta właściwość ma głęboki wpływ na eliminację cięć: w permutowaniu cięcia Gentzen musiał przywrócić pierwotne konteksty (Γ i Δ) poprzez osłabienia i skurcze. Przy dopuszczalności tych reguł z zachowaniem wysokości, rozmiar wyprowadzenia nie zwiększa się, gdy reguły są stosowane. Dragalin podał także intuicjonistyczny rachunek wielosekwencyjny z tym samym typem dopuszczalności reguł strukturalnych. Wreszcie Troelstra podała w podręczniku Basic Proof Theory (2000, pierwsze wydanie 1996) pojedynczy następczy rachunek intuicjonistyczny z dopuszczalnością osłabienia i skurczu z zachowaniem wysokości. Rachunki sekwencyjne bez kontrakcji są potężnymi narzędziami do analizy formalnych wyprowadzeń. Wiele trudnych wyników badań w logice staje się po prostu ćwiczeniami poprzez kontrolę nad strukturą dowodów, na którą pozwalają obliczenia G3. Rachunki sekwencyjne bez kontrakcji są potężnymi narzędziami do analizy formalnych wyprowadzeń. Wiele trudnych wyników badań w logice staje się po prostu ćwiczeniami poprzez kontrolę nad strukturą dowodów, na którą pozwalają obliczenia G3. Rachunki sekwencyjne bez kontrakcji są potężnymi narzędziami do analizy formalnych wyprowadzeń. Wiele trudnych wyników badań w logice staje się po prostu ćwiczeniami poprzez kontrolę nad strukturą dowodów, na którą pozwalają obliczenia G3.

Najwcześniejsze zastosowanie rachunku sekwencyjnego w matematyce miało miejsce w teorii dowodowej arytmetyki, w tezie Gentzena oraz w decydujący sposób w 1938 r. W dowodzie spójności arytmetyki. Troelstra wspomina o pracy Ketonena jako

wczesna analiza dowodów bez wycięć w rachunku Gentzena z aksjomatami; ale rozważa formę wyprowadzeń bez wycięć w czystym rachunku różniczkowym, gdzie aksjomaty są obecne w poprzedniku wyprowadzonych sekwencji. (Troelstra i Schwichtenberg 2000: 142)

Aksjomaty, które rozważa Ketonen, dotyczą geometrii rzutowej i afinicznej, te pierwsze zaczerpnięto z artykułu Skolema z 1920 roku, omówionego w pierwszej części powyżej. Ketonen chciał sformułować formalne reguły dowodzenia Skolema w ramach rachunku sekwencyjnego. Jednak praca Ketonena była znana głównie tylko dzięki recenzji przeprowadzonej przez Bernays i tylko część logiczna rachunku sekwencyjnego została tam szczegółowo wyjaśniona.

Drugim sposobem zastosowania rachunku sekwencyjnego jest pozwolenie sekwencjom rozpoczynającym gałęzie derywacji, oprócz sekwencji początkowych, także na postać A, w której A jest aksjomatem lub przykładem uniwersalnego aksjomatu. Teraz, dzięki „rozszerzonemu Hauptsatzowi” Gentzena, cięcia w derywacjach mogą być permutowane, aż jedna z ich przesłanek stanie się aksjomatem, ale te cięcia aksjomatów pozostają. Inną, nowszą metodą jest przekształcenie aksjomatów w dodatkowe reguły, które są dodawane do reguł logicznych rachunku sekwencyjnego, przy zachowaniu pełnej eliminacji (jak wyjaśniono w Negri i von Plato 2001, rozdział 6 oraz Troelstra i Schwichtenberg w 2000, rozdział 4.7).

8. Cele teorii dowodu

W jakim stopniu teoria dowodu osiągnęła swoje pierwotne cele? Dla Hilberta celem było całkowite wyjaśnienie podstawowych problemów poprzez ostateczne dowody spójności itp., Cele, w których teoria dowodu zawiodła. Hilbert w swoim programie nie był zainteresowany badaniem samych dowodów matematycznych, a jedynie wyjaśnieniem centralnych problemów fundamentalnych (a potem zapomnieniem o nich). Niedawno znaleziona notatka Hilberta daje inny obraz: notatka stwierdza, że Hilbert chciał dodać jako 24. i ostatni problem do swojej słynnej paryskiej listy otwartych problemów matematycznych z 1900 roku rozwój „teorii metod dowodowych w matematyce”. Było to zanim pojawił się jego metamatematyczny program rozwoju teorii dowodu.

Dla Gentzena celem, podobnie jak Hilberta, było zrozumienie struktury dowodów matematycznych. Ten program odniósł całkowity sukces, jeśli chodzi o czystą logikę i arytmetykę. Zwłaszcza metody rachunku sekwencyjnego pozwalają na analizę dowodów z głębokimi wynikami. Wielki cel teorii dowodu, dowód spójności analizy, jak w przypadku drugiego problemu paryskiego Hilberta, nie został zrealizowany, ale też nie jest wykluczony.

Pewne zrozumienie pojęcia dowodu jest konieczne dla każdego matematyka, choćby po to, aby przynajmniej przekazać wyniki matematyczne: publikacja opiera się na zrozumieniu, że dowody mogą być tak wyraźne, że można je rutynowo sprawdzać pod kątem poprawności. Jednak teoria dowodu nie stała się dotychczas praktycznym narzędziem dla pracującego matematyka; zastosowania w matematyce były raczej odosobnionymi przypadkami. Niedawne prace nad sformalizowaniem dowodów matematycznych za pomocą systemów komputerowych, zwanych edytorami dowodów, mogą stopniowo zmienić ten obraz.

Teoria dowodów stworzyła nowe cele poza tradycyjną matematyką, zwłaszcza w połączeniu z informatyką. Zagadnienia takie jak weryfikacja poprawności programów komputerowych są wyrostkiem teorii dowodu. Naturalna dedukcja doprowadziła do korespondencji Curry-Howarda i powiązań z programowaniem funkcjonalnym, a rachunek sekwencyjny jest często używany w systemach automatycznego wyszukiwania dowodów, tak jak w programowaniu logicznym.

Bibliografia

Teksty na temat teorii dowodu

  • Buss, Sam (red.), 1998, Handbook of Proof Theory, Amsterdam: Elsevier.
  • Negri, S. and J. von Plato, 2001, Structural Proof Theory, Cambridge: Cambridge University Press.
  • von Plato, J., 2013, Elements of Logical Reasoning, Cambridge: Cambridge University Press.
  • Takeuti, G., 1987, Proof Theory, Amsterdam: North-Holland, 2. wydanie.
  • Troelstra, A. and H. Schwichtenberg, 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2. wydanie.

Prace oryginalne i ich przedruki

  • Ackermann, W. 1940, „Zur Widerspruchsfreiheit der Zahlentheorie”, Mathematische Annalen, 117: 162–194.
  • Beth, E., 1955, semantyczne wynikanie i formalna wyprowadzalność (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe reeks, deel 18, nr 13), Amsterdam: North-Holland.
  • Church, A., 1936, „A Note on the Entscheidungsproblem”, Journal of Symbolic Logic, 1: 40–41.
  • Curry, H. i Feys, R., 1958. Combinatory Logic. (Studies in Logic and the Foundations of Mathematics, tom I), wydanie 1, Amsterdam: North-Holland.
  • Curry, H., 1963, Foundations of Mathematical Logic, Nowy Jork: McGraw-Hill; przedruk New York: Dover, 1977.
  • Dragalin, A., 1988, Mathematical Intuitionism: Introduction to Proof Theory, Providence, RI: American Mathematical Society.
  • Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen (Investigations into Logical Inference), Ph. D. praca magisterska, Universität Göttingen. Opublikowano w Gentzen 1969: 68–131.
  • Gentzen, G., 1938, „Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie”, Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, Neue Folge 4, S. Hrizel, 19–44. Przetłumaczone w Gentzen 1969: 252–286.
  • Gentzen, G., 1943, „Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie”, Mathematische Annalen, 119: 252–286. Przetłumaczone w Gentzen 1969: 287–308.
  • Gentzen, G., 1969, The Collected Papers of Gerhard Gentzen, wyd. M. Szabo, Amsterdam: Holandia Północna.
  • Gentzen, G., 2008, „Normalizacja derywacji”, The Bulletin of Symbolic Logic, 14 (1): 245–257.
  • Gödel, K., 1930, „Die Vollständigkeit der Axiome des logischen Funktionenkalküls”, Monatshefte für Mathematik und Physik, 37: 349–360.
  • Gödel, K., 1958, „Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”, Dialectica, 12: 280–287.
  • Gödel. K., 1986–2003, Collected Papers (tomy I – V), S. Feferman i in. (red.), Oxford: Oxford University Press.
  • van Heijenoort, J., 1967, From Frege to Gödel, Cambridge, MA: Harvard University Press.
  • Hilbert, D., 1899, Grundlagen der Geometrie, Lipsk: BG Teubner.
  • Hilbert, D., 1926, „Über das Unendliche” („O nieskończoności”), Mathematische Annalen, 95: 161–190. [Wykład wygłoszony w Münster, 4 czerwca 1925 r.]
  • Hilbert, D. i Ackermann, W., 1928, Grundzüge der theoretischen Logik, Berlin: Springer.
  • Hilbert, D., 1931, „Die Grundlegung der elementaren Zahlenlehre”, Mathematische Annalen, 104: 484–494.
  • Howard, W., 1980 [1969], „The formulas-as-types concept of construction”, w J. Seldin and J. Hindley (red.), To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Londyn, New York: Academic Press, s. 480–490.
  • Jaskowski S., 1934, „O regułach supozycji w logice formalnej”, w: S. McCall (red.), Polish Logic 1920–1939, Oxford: Clarendon Press, 1967, s. 232–258.
  • Ketonen, O., 1944, Untersuchungen zum Prädikatenkalkül, Annales Academiae scientiarum fennicae (Ser. AI 23), Helsinki.
  • Kleene, S., 1952, Introduction to Metamathematics, Amsterdam: North-Holland.
  • Kreisel, G., 1951, „O interpretacji non-finitist proofs: Part I”, The Journal of Symbolic Logic, 16 (4): 241–267.
  • Löwenheim, L., 1915, „Über Möglichkeiten im Relativkalkül”, Mathematische Annalen, 76 (4): 447–470.
  • Menzler-Trott, E., 2001, Gentzens Problem, Berlin: Birkhäuser Verlag.
  • Menzler-Trott, E., 2007, Logic's Lost Genius: The Life and Work of Gerhard Gentzen, Providence, RI: American Mathematical Society.
  • Prawitz, D., 1965, Natural Deduction: A Proof-Theoretical Study, Sztokholm: Almqvist & Wiksell; przedruk New York: Dover (z nową przedmową), 2006.
  • –––, 1971, „Idee i wyniki w teorii dowodu”, J. Fenstad (red.), Proceedings of the Second Scandinavian Logic Symposium, Amsterdam: North-Holland, s. 235–308.
  • Rathjen, M., 1995, „Ostatnie postępy w analizie porządkowej; Π 1 2 -CA and related systems,”The Bulletin of Symbolic Logic, 1 (4): 468–485.
  • Schütte, K., 1950, „Schlussweisen-Kalküle der Prädikatenlogik”, Mathematische Annalen, 122: 47–65.
  • –––, 1951, „Beweistheoretische Erfassung der unendlichen Induktion in der Zahlentheorie”, Mathematische Annalen, 122: 369–389.
  • Skolem T., 1920, „Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze, nebst einem Theoreme über dichte Mengen”, przetłumaczone i przedrukowane w: Selected Works in Logic, JE Fenstad (red.), Oslo, Universit, 1970, Oslo, Universit. s. 103–136:
  • Whitehead, AN i B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.

Literatura dodatkowa

  • Bernays, P., 1945, „Review: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul”, The Journal of Symbolic Logic, 10 (4): 127–130.
  • –––, 1965, „Betrachtungen zum Sequenzen-kalkul”, w: Contributions to Logic and Methodology in Honor of JM Bochenski, Amsterdam: North-Holland, s. 1–44.
  • –––, 1979, „O oryginalnym dowodzie spójności Gentzena dla teorii liczb”, J. Myhill et al. (red.), Intuitionism and Proof Theory, Amsterdam: North-Holland, str. 409–417.
  • Feferman, S., 2000, „Highlights in proof teorii”, w: V. Hendricks i in. (red.) 2000, 11–31.
  • Hempel, C., 2000, „Autobiografia intelektualna”. W Science, Explanation, and Rationality, wyd. J. Fetzer, str. 3–35.
  • Hendricks, V. i in. (red.), 2000, Teoria dowodu: historia i znaczenie filozoficzne, Dordrecht: Kluwer.
  • Mancosu, P., 1999, „Między Berlinem a Wiedniem: natychmiastowa recepcja twierdzeń o niezupełności Gödla”, History and Philosophy of Logic, 20: 33–45.
  • von Plato, J., 2007, „W cieniu twierdzenia Löwenheima-Skolema: wczesne analizy kombinatoryczne dowodów matematycznych”, The Bulletin of Symbolic Logic, 13 (2): 189–225.
  • –––, 2007, „From Hilbert's program to Gentzen's program”, w dodatku, Menzler-Trott 2007.
  • –––, 2009, „Gentzen's logic”, w: Handbook of the History and Philosophy of Logic (tom 5), Amsterdam: Elsevier.
  • –––, 2012, „Gentzen's proof systems: produkty uboczne w programie geniuszu”, The Bulletin of Symbolic Logic, 18 (3): 313–367.
  • Smorynski, C., 2007, „Program Hilberta”, w załączniku, Menzler-Trott 2007.
  • Tait, W., 2005, „Gödel's przeformułowanie pierwszego dowodu spójności Gentzena dla arytmetyki: interpretacja bez kontrprzykładu”, The Bulletin of Symbolic Logic, 11 (2): 225–238.
  • Troelstra, A. and Schwichtenberg, H., 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2. wydanie.

Narzędzia akademickie

człowiek ikona
człowiek ikona
Jak cytować ten wpis.
człowiek ikona
człowiek ikona
Zobacz wersję PDF tego wpisu w Friends of the SEP Society.
ikona Inpho
ikona Inpho
Poszukaj tego tematu wpisu w Internet Philosophy Ontology Project (InPhO).
ikona dokumentów phil
ikona dokumentów phil
Ulepszona bibliografia tego wpisu na PhilPapers, z linkami do jego bazy danych.

Inne zasoby internetowe

[Prosimy o kontakt z autorem z sugestiami.]

Zalecane: