Drugi problem Hilberta

W matematyce drugi problem Hilberta został postawiony przez Davida Hilberta w 1900 roku jako jeden z jego 23 problemów . Prosi o dowód, że arytmetyka jest spójna – wolna od jakichkolwiek wewnętrznych sprzeczności. Hilbert stwierdził, że aksjomaty, które rozważał dla arytmetyki, to te podane w Hilbert (1900) , które obejmują aksjomat kompletności drugiego rzędu.

W latach trzydziestych XX wieku Kurt Gödel i Gerhard Gentzen udowodnili wyniki, które rzucają nowe światło na problem. Niektórzy uważają, że twierdzenia Gödla dają negatywne rozwiązanie problemu, podczas gdy inni uważają dowód Gentzena za częściowe rozwiązanie pozytywne.

Problem Hilberta i jego interpretacja

W jednym tłumaczeniu na język angielski Hilbert pyta:

„Kiedy zajmujemy się badaniem podstaw nauki, musimy ustanowić system aksjomatów, który zawiera dokładny i pełny opis relacji zachodzących między elementarnymi ideami tej nauki. ... Ale przede wszystkim chcę wyznaczyć spośród licznych pytań, które można postawić w odniesieniu do aksjomatów, najważniejsze jest następujące: udowodnić, że nie są one sprzeczne, to znaczy, że określona liczba kroków logicznych opartych na nich nie może nigdy prowadzić do sprzecznych wyników. , dowód zgodności aksjomatów można przeprowadzić konstruując odpowiednie pole liczb, tak aby analogiczne relacje między liczbami tego ciała odpowiadały aksjomatom geometrycznym. ... Z drugiej strony potrzebna jest metoda bezpośrednia dla dowód zgodności aksjomatów arytmetycznych”.

Stwierdzenie Hilberta jest czasami źle rozumiane, ponieważ przez „aksjomaty arytmetyczne” miał na myśli nie system równoważny arytmetyce Peano, ale mocniejszy system z aksjomatem zupełności drugiego rzędu. System, którego dowód kompletności zażądał Hilbert, bardziej przypomina arytmetykę drugiego rzędu niż arytmetykę Peano pierwszego rzędu.

Jako powszechna obecnie interpretacja, pozytywne rozwiązanie drugiego pytania Hilberta dostarczyłoby w szczególności dowodu, że arytmetyka Peano jest spójna.

Istnieje wiele znanych dowodów na to, że arytmetyka Peano jest spójna, które można przeprowadzić w silnych systemach, takich jak teoria mnogości Zermelo – Fraenkla . Nie dają one jednak rozwiązania drugiego pytania Hilberta, ponieważ jest mało prawdopodobne, aby ktoś, kto wątpi w spójność arytmetyki Peano, zaakceptował aksjomaty teorii mnogości (która jest znacznie silniejsza), aby udowodnić jej spójność. Tak więc satysfakcjonujące rozwiązanie problemu Hilberta musi zostać przeprowadzone przy użyciu zasad, które byłyby do przyjęcia dla kogoś, kto nie wierzy już, że PA jest spójne. Takie zasady są często nazywane finitystycznymi ponieważ są one całkowicie konstruktywne i nie zakładają skończonej nieskończoności liczb naturalnych. Drugie twierdzenie Gödla o niezupełności (patrz twierdzenia Gödla o niezupełności ) nakłada surowe ograniczenie na to, jak słaby może być system finitystyczny, jednocześnie udowadniając spójność arytmetyki Peano.

Twierdzenie Gödla o niezupełności

Drugie twierdzenie Gödla o niezupełności pokazuje, że nie jest możliwe, aby jakikolwiek dowód na to, że arytmetyka Peano była spójna, mógł zostać przeprowadzony w ramach samej arytmetyki Peano. To twierdzenie pokazuje, że jeśli jedynymi akceptowalnymi procedurami dowodowymi są te, które można sformalizować w ramach arytmetyki, to nie można odpowiedzieć na wezwanie Hilberta do dowodu spójności. Jednak, jak wyjaśniają Nagel i Newman (1958: 96–99), wciąż jest miejsce na dowód, którego nie można sformalizować w arytmetyce:

„Tego imponującego wyniku analizy Godla nie należy źle rozumieć: nie wyklucza on metamatematycznego dowodu spójności arytmetyki. Wyklucza dowód spójności, który można odzwierciedlić w formalnych dedukcjach arytmetycznych. Dowody meta-matematyczne konsystencji arytmetyki zostały w rzeczywistości skonstruowane, zwłaszcza przez Gerharda Gentzena , członek szkoły Hilberta, w 1936 roku i od tego czasu przez innych. ... Ale tych metamatematycznych dowodów nie można przedstawić w rachunku arytmetycznym; a ponieważ nie są finitystyczne, nie osiągają ogłoszonych celów pierwotnego programu Hilberta. ... Wyniki Gödla nie wykluczają możliwości skonstruowania finitystycznego absolutnego dowodu zgodności dla arytmetyki. Gödel wykazał, że żaden taki dowód nie jest możliwy, który można przedstawić w ramach arytmetyki. Jego argumentacja nie eliminuje możliwości ściśle skończonych dowodów, których nie można przedstawić w arytmetyce. Wydaje się jednak, że nikt dzisiaj nie ma jasnego pojęcia, jak wyglądałby dowód finitystyczny, którego nie da się sformułować w ramach arytmetyki”.

Dowód konsystencji Gentzena

W 1936 roku Gentzen opublikował dowód na to, że arytmetyka Peano jest spójna. Wynik Gentzena pokazuje, że dowód spójności można uzyskać w systemie, który jest znacznie słabszy niż teoria mnogości.

Dowód Gentzena przebiega poprzez przypisanie każdemu dowodowi w arytmetyce Peano liczby porządkowej , na podstawie struktury dowodu, przy czym każda z tych liczb porządkowych jest mniejsza niż ε ₀ . Następnie udowadnia za pomocą indukcji pozaskończonej na tych liczbach porządkowych, że żaden dowód nie może zakończyć się sprzecznością. Metodę zastosowaną w tym dowodzie można również wykorzystać do udowodnienia eliminacji cięcia dla arytmetyki Peano w logice silniejszej niż logika pierwszego rzędu, ale sam dowód spójności można przeprowadzić w zwykłej logice pierwszego rzędu przy użyciu aksjomatów prymitywna arytmetyka rekurencyjna i zasada indukcji pozaskończonej. Tait (2005) przedstawia teoretyczną interpretację metody Gentzena.

Dowód spójności Gentzena zapoczątkował program analizy porządkowej w teorii dowodu. W tym programie formalnym teoriom arytmetyki lub teorii mnogości przypisuje się liczby porządkowe , które mierzą siłę spójności teorii. Teoria nie będzie w stanie udowodnić spójności innej teorii z wyższą teorią porządkową dowodu.

Współczesne poglądy na stan problemu

Chociaż twierdzenia Gödla i Gentzena są obecnie dobrze rozumiane przez społeczność logiki matematycznej, nie osiągnięto konsensusu co do tego, czy (lub w jaki sposób) te twierdzenia odpowiadają na drugi problem Hilberta. Simpson (1988: rozdz. 3) argumentuje, że twierdzenie Gödla o niezupełności pokazuje, że nie jest możliwe przedstawienie finitystycznych dowodów spójności silnych teorii. Kreisel (1976) stwierdza, że chociaż wyniki Gödla sugerują, że nie można uzyskać żadnego finitystycznego dowodu spójności składniowej, semantyczny (w szczególności drugiego rzędu ) można użyć argumentów, aby przedstawić przekonujące dowody spójności. Detlefsen (1990: s. 65) argumentuje, że twierdzenie Gödla nie uniemożliwia dowodu spójności, ponieważ jego hipotezy mogą nie mieć zastosowania do wszystkich systemów, w których można przeprowadzić dowód spójności. Dawson (2006: sek. 2) nazywa przekonanie, że twierdzenie Gödla eliminuje możliwość przekonującego dowodu spójności „błędnym”, powołując się na dowód spójności podany przez Gentzena i późniejszy dowód podany przez Gödla w 1958 roku.

Zobacz też

Przypuszczenie Takeutiego

Notatki

Dawson, John W. (2006) „Wstrząśnięte fundamenty czy przełomowa zmiana? Stuletnia ocena wpływu Kurta Gödla na logikę, matematykę i informatykę”. 2006 21. doroczne sympozjum IEEE na temat logiki w informatyce , IEEE, s. 339–341. ISBN 0-7695-2631-4 do : 10.1109/LICS.2006.47
Michaela Detlefsena (1990). „O rzekomym obaleniu programu Hilberta przy użyciu pierwszego twierdzenia Gödla o niezupełności”. Dziennik logiki filozoficznej . Skoczek. 19 (4): 343–377. doi : 10.1007/BF00263316 . S2CID 44736805 .
Torkel Franzen (2005), twierdzenie Godla: niekompletny przewodnik po jego użyciu i nadużywaniu , AK Peters, Wellesley MA. ISBN 1-56881-238-8
Gerharda Gentzena (1936). „Die Widerpruchsfreiheit der reinen Zahlenteorie”. Mathematische Annalen , t. 112, s. 493–565.
Gödel, Kurt (1931). „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I” . Monatshefte für Mathematik und Physik . 38 : 173–98. doi : 10.1007/BF01700692 . S2CID 197663120 . Zarchiwizowane od oryginału w dniu 2006-07-05. Przetłumaczone w Jean van Heijenoort , 1967. Od Fregego do Gödla: książka źródłowa o logice matematycznej . Harvard University Press: 596-616.
Hilbert, David (1900), "Über den Zahlbegriff" , Jahresbericht der Deutschen Mathematiker-Vereinigung , 8 : 180–184
David Hilbert [1900] (1901) „Mathematische Probleme”. Archiv der Mathematik und Physik , t. 3 n. 1, s. 44–63 i 213–237. Tłumaczenie angielskie, Maby Winton, Biuletyn Amerykańskiego Towarzystwa Matematycznego 8 (1902), 437–479. Dostępne w Internecie pod adresem http://aleph0.clarku.edu/~djoyce/hilbert/problems.html .
George'a Kreisela (1976). „Czego nauczyliśmy się z drugiego problemu Hilberta?”. Rozwój matematyczny wynikający z problemów Hilberta (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill.,) . Providence, RI: Amer. Matematyka soc. s. 93–130. ISBN 0-8218-1428-1 .
Nagel, Ernest i Newman, James R., Dowód Godla , New York University Press, 1958.
Stephena G. Simpsona (1988). „Częściowe realizacje programu Hilberta”. Dziennik logiki symbolicznej . 53 (2): 349–363. CiteSeerX 10.1.1.79.5808 . doi : 10.2307/2274508 . ISSN 0022-4812 . JSTOR 2274508 . Dostępne w Internecie pod adresem http://www.math.psu.edu/simpson/papers/hilbert.pdf .
William W. Tait (2005). „Przeformułowanie przez Gödla pierwszego dowodu spójności Gentzena arytmetyki: interpretacja bez kontrprzykładów”. Biuletyn Logiki Symbolicznej t. 11 n. 2, s. 225–238.

Linki zewnętrzne