Godel befejezetlenségi tételei

Godel befejezetlenségi tétele és Godel második tétele [~ 1] a matematikai logika  két tétele a formális aritmetika , és ennek következtében minden olyan formális rendszer alapvető korlátairól , amelyben az alapvető számtani fogalmak definiálhatók: természetes számok , 0 , 1 , összeadás és szorzás .

Az első tétel kimondja, hogy ha a formális aritmetika konzisztens, akkor tartalmaz egy cáfolhatatlan és megcáfolhatatlan formulát.

A második tétel azt állítja, hogy ha egy formális aritmetika konzisztens, akkor valamilyen képlet nem levezethető benne, amely értelmesen kijelenti ennek az aritmetikának a következetességét.

Mindkét tételt Kurt Gödel bizonyította 1930-ban (1931-ben jelent meg), és közvetlenül kapcsolódnak Hilbert híres listáján szereplő második problémához .

Történelem

David Hilbert még a 20. század elején meghirdette az egész matematika axiomatizálásának célját, és e feladat elvégzéséhez a természetes számok aritmetikája következetességének és logikai teljességének bizonyítása maradt . 1930. szeptember 7-én Königsbergben tartottak egy tudományos kongresszust a matematika alapjairól , és ezen a kongresszuson a 24 éves Kurt Gödel először publikált két alapvető hiányos tételt, amelyek megmutatták, hogy Hilbert programja nem valósítható meg. Az aritmetika axiómáinak megválasztása, vannak olyan tételek, amelyeket nem lehet sem bizonyítani, sem megcáfolni Hilbert által megadott egyszerű ( véges ) eszközökkel, és lehetetlen az aritmetika következetességének véges bizonyítása [6] .

Ezt a beszédet nem jelentették be előre, és lenyűgöző hatása volt, Gödel azonnal világhírességgé vált, Hilbert matematika alapjainak formalizálására irányuló programja pedig sürgős átdolgozást igényelt. 1930. október 23-án Hans Hahn bemutatta Gödel eredményeit a Bécsi Tudományos Akadémiának . A Monatshefte für Mathematik und Physik tudományos havilapban 1931- ben megjelent egy cikk mindkét tétellel (" A Principia Mathematica és a kapcsolódó rendszerek alapvetően eldönthetetlen állításairól "). Bár Gödel a második tétel bizonyítását csak ötlet formájában adta meg, eredménye annyira egyértelmű és tagadhatatlan volt, hogy senki sem kételkedett benne. Hilbert azonnal felismerte Gödel felfedezésének értékét; mindkét tétel első teljes bizonyítását Hilbert és Bernays Mathematics alapjai (1938) publikálták. A második kötet előszavában a szerzők elismerték, hogy a véges módszerek nem elegendőek céljuk eléréséhez, és a transzfinit indukcióval egészítették ki a logikai eszközök listáját ; 1936-ban Gerhard Gentzennek ezzel az axiómával sikerült igazolnia az aritmetika következetességét, de a logikai teljesség elérhetetlen maradt [6].

Godel befejezetlenségi tétele

Eredeti formájában

Gödel a befejezetlenségi tétel megfogalmazásában az ω-konzisztens formális rendszer fogalmát használta, ami erősebb feltétel, mint a puszta konzisztencia. Egy formális rendszert ω-konzisztensnek nevezünk, ha ennek a rendszernek bármely A ( x ) képletére lehetetlen egyidejűleg levezetni az A ( 0 ), A ( 1 ), A ( 2 ), ... és ∃ x ¬ A képleteket. ( x ) (más szóval abból, hogy minden n természetes számra levezethető az A ( n ) képlet , ebből következik, hogy az ∃ x ¬ A ( x ) képlet nem származtatható). Könnyen kimutatható, hogy az ω-konzisztencia egyszerű konzisztenciát jelent (vagyis bármely ω-konzisztens formális rendszer konzisztens) [7] .

A tétel bizonyítása során egy olyan S aritmetikai formális rendszer A képletét állítjuk elő, amely [7] :

Ha az S formális rendszer konzisztens, akkor az A képlet nem származtatható S -ben ; ha az S rendszer ω-konzisztens, akkor a ¬A képlet S -ben nem származtatható . Így, ha egy S rendszer ω-konzisztens, akkor nem teljes [~ 2] , és A egy példa egy feloldhatatlan képletre.

Az A képletet néha Gödel feloldhatatlan formulának is nevezik [8] .

A feloldhatatlan képlet értelmezése

A szabványos értelmezésben [~ 3] az A képlet azt jelenti, hogy "nincs levezetése az A képletnek " , vagyis saját levezethetetlenségét állítja S-ben. Ezért Gödel tétele szerint, ha csak az S rendszer konzisztens, akkor ez a képlet valóban nem levezethető S-ben, és ezért igaz a standard értelmezésben. Így természetes számokra az A képlet igaz, de S-ben nem származtatható [9] .

Rosser egyenruhában

A tétel bizonyítása során egy S aritmetikai formális rendszer B képletét állítjuk össze, amely [10] :

Ha egy S formális rendszer konzisztens, akkor a B és a ¬B képlet sem származtatható benne; más szóval, ha az S rendszer konzisztens, akkor nem teljes [~ 2] , és B egy feloldhatatlan képlet példája.

A B képletet néha Rosser feloldhatatlan formulának is nevezik [11] . Ez a képlet kicsit bonyolultabb, mint Gödel.

A feloldhatatlan képlet értelmezése

A standard értelmezésben [~3] a B képlet azt jelenti, hogy "ha van B képlet származéka , akkor van ¬B képlet származéka " . De Gödel Rosser-féle tétele szerint, ha egy S formális rendszer konzisztens, akkor a benne lévő B képlet nem levezethető; tehát ha az S rendszer konzisztens, akkor a standard értelmezésben a B képlet helyes [12] .

Általánosított megfogalmazások

A Gödel-tétel bizonyítását általában egy meghatározott formális rendszerre (nem feltétlenül ugyanarra) hajtják végre, és ennek megfelelően a tétel állítása csak erre a rendszerre válik bizonyítottnak. Az elegendő feltétel tanulmányozása, amelyet egy formális rendszernek teljesítenie kell ahhoz, hogy bizonyítani tudja hiányosságát, a tétel általánosításokhoz vezet a formális rendszerek széles osztályára. Példa egy általánosított megfogalmazásra [13] :

Minden kellően erős, rekurzívan axiomatizálható konzisztens elsőrendű elmélet hiányos.

Különösen Gödel tétele érvényes egy S aritmetikai formális rendszer minden következetes, véges axiomatizálható kiterjesztésére.

Polinom alak

Miután Jurij Matijasevics bebizonyította , hogy bármely hatékonyan megszámlálható halmaz diofantin , és példákat találtak univerzális diofantin egyenletekre , lehetővé vált a hiányossági tétel polinomiális (vagy diofantin) formában történő megfogalmazása [14] [15] [16] [17] :

Minden konzisztens T elmélethez megadható a K paraméter egész értéke úgy, hogy az egyenlet nincs megoldása nemnegatív egész számokban, de ez a tény a T elméletben nem bizonyítható . Ezenkívül minden konzisztens elmélet esetében a K paraméter értékeinek halmaza, amely rendelkezik ezzel a tulajdonsággal, végtelen és algoritmikusan nem megszámlálható .

Ennek az egyenletnek a mértéke 4-re csökkenthető a változók számának növelése árán.

A bizonyítás vázlata

Gödel dolgozatában felvázolja a bizonyítás fő gondolatait [18] , amelyet az alábbiakban kisebb módosításokkal közölünk.

Valamely formális rendszer [~ 4] S minden primitív szimbóluma, kifejezése és kifejezéssorozata egy bizonyos természetes számhoz [~ 5] lesz társítva . A matematikai fogalmak és állítások így a természetes számokra vonatkozó fogalmakká és állításokká válnak, és ezért önmagukban is kifejezhetők az S rendszer szimbolikájában. Különösen kimutatható, hogy a „képlet”, „származtatás”, „származtatható” fogalmak. formula" az S rendszeren belül definiálható, azaz lehetséges például egy F ( v ) képlet S-ben egy szabad v természetes számváltozóval visszaállítani úgy, hogy F ( v ) intuitív értelmezésben azt jelenti: v  egy levezethető képlet. Most konstruáljuk meg az S rendszer egy eldönthetetlen mondatát, azaz egy olyan A mondatot , amelyre sem A , sem nem-A nem származtatható, a következőképpen:

A pontosan egy szabad természetes számváltozóval rendelkező S-beli képletet osztálykifejezésnek nevezzük . Az osztálykifejezéseket rendezzük valamilyen módon sorozatba, jelöljük az n - edik R -vel ( n ), és vegyük észre, hogy az „osztálykifejezés” fogalma, valamint az R rendezési reláció definiálható az S rendszerben. α egy tetszőleges osztálykifejezés kifejezés; keresztül [α; n ] jelöli azt a képletet, amely az α osztálykifejezésből keletkezik úgy, hogy a szabad változót egy n természetes szám szimbólumával helyettesítjük . Terner reláció x = [ y ; z ] S-ben is definiálhatónak bizonyul. Most a természetes számok K osztályát a következőképpen definiáljuk:

n ∈ K ≡ ¬Bew[ R ( n ); n ] (*)

(ahol a Bew x jelentése: x  a származtatott képlet [~ 6] ). Mivel ebből a definícióból az összes meghatározó fogalom kifejezhető S-ben, ugyanez igaz a belőlük felépülő K fogalomra is, vagyis van olyan C osztálykifejezés , hogy a [ C ; n ], amelyet intuitív módon értelmezünk, azt jelenti, hogy egy n természetes szám K -hez tartozik . Osztálykifejezésként C azonos a felsorolásunkban szereplő bizonyos R ( q )-vel, azaz.

C = R ( q )

teljesül valamilyen határozott q természetes számra . Mutassuk meg most, hogy a [ R ( q ); q ] S-ben eldönthetetlen. Így ha a mondat [ R ( q ); q ]-t származtathatónak tételezzük fel, akkor igaznak bizonyul, vagyis a fentiek szerint q K -hoz fog tartozni , azaz (*) szerint ¬Bew[ R ( q ); q ], ami ellentmond feltételezésünknek. Másrészt, ha a negációt származtathatónak tételezzük fel [ R ( q ); q ], akkor ¬ q ∈ K fog bekövetkezni , azaz Bew[ R ( q ); q ] igaz lesz. Ezért [ R ( q ); q ] tagadásával együtt levezethető lesz, ami megint csak lehetetlen.

Kapcsolat paradoxonokkal

A standard értelmezésben [~3] Gödel eldönthetetlen A formulája azt jelenti, hogy "nincs levezetése az A képletnek " , azaz saját levezethetetlenségét állítja az S rendszerben. Így A a hazug paradoxon analógja . Gödel érvelése nagyjából hasonló Richard paradoxonjához . Sőt, bármely szemantikai paradoxon felhasználható a nem levezethető állítások létezésének bizonyítására [19] .

Meg kell jegyezni, hogy az A formulával kifejezett állítás nem tartalmaz ördögi kört, mivel kezdetben csak azt állítják, hogy bizonyos képlet, amelynek kifejezett kifejezése könnyű (bár nehézkes), nem bizonyítható. „Csak később (és úgymond véletlenül) derül ki, hogy pontosan ez a képlet fejezi ki magát ezt az állítást” [19] .

Gödel második tétele

Az S formális aritmetikában megalkotható egy képlet, amely a standard értelmezésben [~ 3] akkor és csak akkor igaz, ha az S elmélet konzisztens. Erre a képletre igaz Gödel második tételének állítása:

Ha egy S formális aritmetika konzisztens, akkor nincs benne olyan levezethető képlet, amely értelmesen állítaná S konzisztenciáját .

Más szóval, a formális aritmetika következetessége ezzel az elmélettel nem igazolható. A formális aritmetika konzisztenciájának azonban lehetnek olyan bizonyításai, amelyek kifejezhetetlenek benne.

A bizonyítás vázlata

Először egy Con formulát állítunk össze , amely értelmesen kifejezi az S elméletben szereplő bármely képlet levezetésének lehetetlenségét, annak tagadásával együtt. Ekkor Gödel első tételének állítása a Con ⊃ G formulával fejeződik ki , ahol G  egy Gödel-feloldhatatlan formula. Az első tétel bizonyítására vonatkozó összes érv kifejezhető és végrehajtható S segítségével, vagyis a Con ⊃ G képlet S -ből származtatható. Ezért ha Con származtatható S -ben , akkor G is származtatható benne . Gödel első tétele szerint azonban, ha S konzisztens, akkor G nem levezethető benne. Ezért ha S konzisztens, akkor a Con formula sem származtatható benne .

Történelmi hatás

Gödel tételeinek történeti jelentőségéről a szakemberek nagyon eltérő, olykor sarkos értékeléseket adnak. Egyes tudósok úgy vélik, hogy ezek a tételek „megfordították” a matematika vagy akár az egész tudáselmélet alapjait , és Gödel zseniális felfedezésének jelentősége fokozatosan, még hosszú időn keresztül feltárul [20] . Mások (például Bertrand Russell ) arra buzdítanak, hogy ne vigyük túlzásba, mivel a tételek Hilbert véges formalizmusán alapulnak [21] [22] .

A közkeletű tévhittel ellentétben Gödel hiányossági tételei nem jelentik azt, hogy bizonyos igazságokat soha nem ismerjük meg örökké. Ráadásul ezekből a tételekből nem következik, hogy az emberi megismerési képesség valamiképpen korlátozott lenne. Nem, a tételek csak a formális rendszerek gyengeségeit és hiányosságait mutatják be [23] .

Tekintsük például az aritmetika következetességének következő bizonyítását [24] .

Tegyük fel, hogy Peano aritmetikai axiomatikája inkonzisztens. Akkor bármilyen állítás levezethető belőle, beleértve a hamisat is. Azonban minden Peano-axióma nyilvánvalóan igaz, és az igaz állításokból nem következhet hamis következtetés – ellentmondást kapunk. Ezért az aritmetika következetes.

A mindennapi emberi logika szempontjából ez a bizonyíték elfogadható és meggyőző. De nem írható fel Hilbert bizonyítási elméletének szabályai szerint, hiszen ezekben a szabályokban a szemantika helyébe a szintaxis, az igazság helyébe pedig a „levezethetőség” [24] . Mindenesetre Gödel tételei új szintre emelték a matematika filozófiáját.

Lásd még

Jegyzetek

Hozzászólások
  1. ↑ Néha Gödel második tételeként emlegetik „a konzisztencia bizonyításáról” [1] , „a hiányosságról” [2] [3] [4] , „az aritmetika hiányosságáról” [5] .
  2. ↑ 1 2 Az olyan formális rendszert, amely egy eldönthetetlen, azaz nem levezethető és megcáfolhatatlan formulát tartalmaz, hiányosnak nevezzük.
  3. ↑ 1 2 3 4 Egy S elmélet képleteinek értelmezését standardnak nevezzük, ha a tartománya nemnegatív egész számok halmaza, a 0 szimbólumot a 0, a ', +, • függvénybetűket pedig egyet összeadva, összeadáskor és szorzáskor az = állítmányt az azonossági reláció értelmezi.
  4. ↑ Gödel Whitehead és Russell Principia Mathematica című művét használta , azzal a feltétellel, hogy az érvelés a formális rendszerek széles osztályára vonatkozik.
  5. ↑ A képletek és a természetes számok ilyen összehasonlítását a matematika aritmetizálásának nevezik, és Gödel végezte el először. Ez az ötlet később a matematikai logikai számos fontos probléma megoldásának kulcsa lett. Lásd Gödel számozás
  6. ↑ "Bew" röv. tőle. "Beweisbar" - bizonyítható , levezethető
Források
  1. ↑ Kleene 1957 513. o
  2. ↑ levelező tag RAS Lev Dmitrievich Beklemishev a "Bevezetés a matematikai logikába" című könyvében . Hozzáférés dátuma: 2010. január 7. Az eredetiből archiválva : 2009. március 21..
  3. ↑ Számítástechnikai rendszerek magyarázó szótára - 205. oldal
  4. ↑ A Szovjetunió Tudományos Akadémiájának jelentései, 262. kötet - 799. oldal (1982)
  5. ↑ A Szovjetunió Tudományos Akadémiájának közleménye, 50. kötet – 1140. oldal (1986)
  6. ↑ 1 2 Pinheiro, 2015 , p. 13, 48-49, 66, 89-90.
  7. ↑ 1 2 Kleene 1957 187. o
  8. ↑ Mendelssohn 1971 165. o
  9. ↑ Ez az érvelés Mendelssohn 1971 160. o.-ból származik
  10. ↑ Lásd például Kleene 1957 188. o
  11. ↑ Mendelssohn 1971 162. o
  12. ↑ Mendelssohn 1971, 162-163
  13. ↑ Mendelssohn 1971 176. o
  14. ↑ Jones JP, Megdönthetetlen diofantin egyenletek
  15. ↑ Martin Davis, Diophantine Equations & Computation (hivatkozás nem érhető el) . Letöltve: 2009. november 17. Az eredetiből archiválva : 2010. május 24.. 
  16. ↑ Martin Davis, A befejezetlenségi tétel . Letöltve: 2011. november 30. Az eredetiből archiválva : 2016. március 4..
  17. ↑ K. Podnieks, Gödel-tétel diofantin formában . Letöltve: 2009. november 17. Az eredetiből archiválva : 2017. szeptember 10..
  18. ↑ Godel, Kurt. A Principia Mathematica és a kapcsolódó rendszerek formailag eldönthetetlen állításairól. I. - 1931. in Davis, Martin (szerk.). Az eldönthetetlen: Alapvető tanulmányok eldönthetetlen állításokról, megoldhatatlan problémákról és kiszámítható függvényekről . - New York: Raven Press, 1965. - S.  6 -8.
  19. ↑ 1 2 Gödel 1931
  20. ↑ Stephen Hawking . Godel és az Univerzum vége (nem elérhető link) . Letöltve: 2018. április 8. Az eredetiből archiválva : 2020. május 29. 
  21. ↑ Mikhailova N.V. A modern matematika alátámasztásának problémája új filozófiai és módszertani válságok összefüggésében // Matematika filozófiája: Aktuális problémák. Matematika és valóság. A Harmadik Össz-Oroszországi Tudományos Konferencia absztraktjai; 2013. szeptember 27-28 . - M . : Stratégiai Konjunktúra Központja, 2013. - P. 187. - 270 p. - ISBN 978-5-906233-39-4 . Archiválva : 2017. december 16. a Wayback Machine -nál
  22. ↑ Zenész A. .
  23. ↑ Livio, Mario. Isten matematikus volt? "Igazság a befejezetlenségben" fejezet. - M. : AST, 2016. - 384 p. — (A tudomány aranyalapja). - ISBN 978-5-17-095136-9 .
  24. ↑ 1 2 Pinheiro, 2015 , p. 155-162.

Irodalom

Linkek

Bibliográfia - Gödel cikkei

  • 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38 :173-198.
  • 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. és A Principia Mathematica és a kapcsolódó rendszerek formálisan eldönthetetlen javaslatairól I in Solomon Feferman , ed., 1986. Kurt Gödel Collected works, Vol. I. _ Oxford University Press: 144-195. - Eredeti német szöveg párhuzamos angol fordítással, Stephen Kleene kezdetleges bevezetőjével .
  • Hirzel, Martin, 2000, A Principia Mathematica és a kapcsolódó rendszerek formálisan eldönthetetlen tételeiről I. . - Marina Herzel modern fordítása.
  • 1951, Néhány alapvető tétel a matematika alapjairól és azok következményeiről : Solomon Feferman , szerk., 1995. Kurt Gödel Collected works, Vol. III . Oxford University Press: 304-323.