Godelin epätäydellisyyslauseet

Godelin epätäydellisyyslause ja Godelin toinen lause [~ 1]  ovat kaksi matemaattisen logiikan lausetta muodollisen aritmeettisen ja sen seurauksena minkä tahansa muodollisen järjestelmän perusrajoituksista , joissa aritmeettiset peruskäsitteet voidaan määritellä: luonnolliset luvut , 0 , 1 , yhteen- ja kertolasku .

Ensimmäinen lause sanoo, että jos muodollinen aritmetiikka on johdonmukainen, se sisältää kiistämättömän ja kiistämättömän kaavan.

Toinen lause väittää, että jos muodollinen aritmetiikka on johdonmukainen, silloin jokin kaava ei ole johdettavissa siinä, mikä merkitsee tämän aritmeettisen johdonmukaisuuden.

Kurt Gödel todisti nämä molemmat lauseet vuonna 1930 (julkaistu vuonna 1931), ja ne liittyvät suoraan Hilbertin kuuluisan luettelon toiseen ongelmaan .

Historia

David Hilbert julisti jo 1900-luvun alussa tavoitteekseen koko matematiikan aksiomatisoinnin, ja tämän tehtävän suorittamiseksi jäi vielä todistaa luonnollisten lukujen aritmetiikan johdonmukaisuus ja looginen täydellisyys . 7. syyskuuta 1930 Königsbergissä pidettiin tieteellinen kongressi matematiikan perusteista , ja tässä kongressissa 24-vuotias Kurt Gödel julkaisi ensin kaksi perustavanlaatuista epätäydellisyyslausetta, jotka osoittivat, että Hilbertin ohjelmaa ei voida toteuttaa. aritmeettisten aksioomien valinnassa on lauseita, joita ei voida todistaa eikä kumota Hilbertin tarjoamilla yksinkertaisilla ( finiteillä ) keinoilla, ja aritmeettisen johdonmukaisuuden äärellinen todiste on mahdoton [6] .

Tätä puhetta ei ilmoitettu etukäteen ja sillä oli hämmästyttävä vaikutus, Gödelistä tuli heti maailmankuulu julkkis, ja Hilbertin ohjelma matematiikan perusteiden virallistamiseksi vaati pikaista tarkistusta. 23. lokakuuta 1930 Hans Hahn esitteli Gödelin tulokset Wienin tiedeakatemialle . Artikkeli, joka sisälsi molemmat lauseet (" Principia Mathematican ja siihen liittyvien järjestelmien pohjimmiltaan ratkaisemattomista väitteistä "), julkaistiin tieteellisessä kuukausilehdessä Monatshefte für Mathematik und Physik vuonna 1931. Vaikka Gödel osoitti toisen lauseen vain idean muodossa, hänen tuloksensa oli niin selkeä ja kiistaton, ettei kukaan epäillyt sitä. Hilbert ymmärsi välittömästi Gödelin löytöjen arvon; ensimmäiset täydelliset todisteet molemmista lauseista julkaistiin julkaisussa Hilbert and Bernays ' Foundations of Mathematics (1938). Toisen osan esipuheessa kirjoittajat myönsivät, että äärelliset menetelmät eivät riitä tavoitteensa saavuttamiseen, ja lisäsivät transfiniitin induktion loogisten keinojen luetteloon ; Vuonna 1936 Gerhard Gentzen onnistui todistamaan aritmeettisen johdonmukaisuuden käyttämällä tätä aksioomaa, mutta looginen täydellisyys jäi saavuttamatta [6]

Godelin epätäydellisyyslause

Alkuperäisessä muodossaan

Epätäydellisyyslauseen muotoilussaan Gödel käytti käsitettä ω-yhtenevä formaalinen järjestelmä, vahvempi ehto kuin pelkkä johdonmukaisuus. Formaalista järjestelmää kutsutaan ω-yhdenmukaiseksi , jos mille tahansa tämän järjestelmän kaavalle A ( x ) on mahdotonta johtaa samanaikaisesti kaavoja A ( 0 ), A ( 1 ), A ( 2 ), ... ja ∃ x ¬ A ( x ) (toisin sanoen siitä tosiasiasta, että jokaiselle luonnolliselle luvulle n kaava A ( n ) on johdettavissa, seuraa, että kaava ∃ x ¬ A ( x ) ei ole johdettavissa). On helppo osoittaa, että ω-yhdenmukaisuus merkitsee yksinkertaista konsistenssia (eli mikä tahansa ω-konsistentti muodollinen järjestelmä on johdonmukainen) [7] .

Lauseen todistusprosessissa muodostetaan aritmeettisen muodollisen järjestelmän S kaava A , joka [7] :

Jos muodollinen järjestelmä S on johdonmukainen, kaava A ei ole johdettavissa S :ssä ; jos järjestelmä S on ω-yhtenäinen, niin kaava ¬A ei ole johdettavissa S :ssä . Siten, jos järjestelmä S on ω-yhtenäinen, se on epätäydellinen [~ 2] ja A on esimerkki ratkaisemattomasta kaavasta.

Kaavaa A kutsutaan joskus Gödelin ratkaisemattomaksi kaavaksi [8] .

Ratkaisemattoman kaavan tulkinta

Vakiotulkinnassa [~ 3] kaava A tarkoittaa "kaavan A johtamista ei ole ", eli se väittää oman ei-johtavuutensa S:ssä. Siksi Gödelin lauseen mukaan, jos vain järjestelmä S on johdonmukainen, silloin tämä kaava ei todellakaan ole johdettavissa S:ssä ja siksi totta standarditulkinnassa. Luonnollisille luvuille kaava A on siis tosi, mutta S:ssä se ei ole johdettavissa [9] .

Rosser-puvussa

Lauseen todistusprosessissa muodostetaan aritmeettisen muodollisen järjestelmän S kaava B , joka [10] :

Jos muodollinen järjestelmä S on konsistentti, niin kaavat B ja ¬B eivät ole johdettavissa siinä; toisin sanoen, jos järjestelmä S on johdonmukainen, niin se on epätäydellinen [~ 2] ja B on esimerkki ratkaisemattomasta kaavasta.

Kaavaa B kutsutaan joskus Rosserin ratkaisemattomaksi kaavaksi [11] . Tämä kaava on hieman monimutkaisempi kuin Gödelin.

Ratkaisemattoman kaavan tulkinta

Vakiotulkinnassa [~3] kaava B tarkoittaa "jos kaavalla B on johdannainen, on kaavan ¬B johdannainen " . Mutta Gödelin lauseen mukaan Rosserin muodossa, jos muodollinen järjestelmä S on konsistentti, niin siinä oleva kaava B ei ole johdettavissa; siksi, jos järjestelmä S on johdonmukainen, niin kaava B on oikea standarditulkinnassa [12] .

Yleistetyt formulaatiot

Gödelin lauseen todistus suoritetaan yleensä tietylle muodolliselle järjestelmälle (ei välttämättä samalle), ja näin ollen lauseen väite osoittautuu todistetuksi vain tälle järjestelmälle. Niiden riittävien ehtojen tutkiminen, jotka muodollisen järjestelmän on täytettävä voidakseen todistaa epätäydellisyytensä, johtaa lauseen yleistyksiin laajaan luokkaan muodollisia järjestelmiä. Esimerkki yleistetystä formulaatiosta [13] :

Mikä tahansa riittävän vahva rekursiivisesti aksiomatisoitava johdonmukainen ensimmäisen asteen teoria on epätäydellinen.

Erityisesti Gödelin lause pätee jokaiselle aritmeettisen muodollisen järjestelmän S johdonmukaiselle, äärellisesti aksiomatisoitavalle laajennukselle.

Polynomimuoto

Kun Juri Matiyasevitš osoitti , että mikä tahansa tehokkaasti numeroitava joukko on diofantiini , ja esimerkkejä universaaleista diofantiiniyhtälöistä löydettiin , tuli mahdolliseksi muotoilla epätäydellisyyslause polynomi- (tai diofantiini-) muodossa [14] [15] [16] [17] :

Kullekin johdonmukaiselle teorialle T voidaan määrittää parametrin K kokonaislukuarvo siten, että yhtälö ei ole ratkaisuja ei-negatiivisissa kokonaisluvuissa, mutta tätä tosiasiaa ei voida todistaa teoriassa T . Lisäksi jokaisessa johdonmukaisessa teoriassa parametrin K arvojen joukko, jolla on tämä ominaisuus, on ääretön ja algoritmisesti numeroimaton .

Tämän yhtälön aste voidaan pienentää 4:ään muuttujien lukumäärän lisäämisen kustannuksella.

Luonnos todisteesta

Kirjoituksessaan Gödel esittää pääpiirteet todisteen pääajatuksista [18] , joka esitetään jäljempänä pienin muutoksin.

Jokin muodollisen järjestelmän [~ 4] S jokainen primitiivinen symboli, lauseke ja lausekesarja liitetään tiettyyn luonnolliseen lukuun [~ 5] . Matemaattisista käsitteistä ja väitteistä tulee siten luonnollisia lukuja koskevia käsitteitä ja väitteitä, ja siksi ne voidaan ilmaista itse järjestelmän S symboliikassa. Voidaan osoittaa erityisesti, että käsitteet "kaava", "derivaatio", "johdannainen" kaava" ovat määritettävissä järjestelmän S sisällä, eli on mahdollista palauttaa esimerkiksi kaava F ( v ) S:ssä yhdellä vapaalla luonnollisella lukumuuttujalla v siten, että F ( v ) tarkoittaa intuitiivisessa tulkinnassa: v  on johdettavissa oleva kaava. Muodostetaan nyt järjestelmän S ratkaisematon lause, toisin sanoen lause A , jolle A tai not-A ei ole ei- johdettavissa, seuraavasti:

S:n kaavaa, jossa on täsmälleen yksi vapaa luonnollinen lukumuuttuja, kutsutaan luokkalausekkeeksi . Järjestetään luokkalausekkeet jollakin tavalla sekvenssiksi, merkitään n : nneksi R :llä ( n ), ja huomioidaan, että "luokkalausekkeen" käsite, samoin kuin järjestysrelaatio R , voidaan määritellä järjestelmässä S. Olkoon a on mielivaltainen luokkalausekelauseke; kautta [α; n ] tarkoittaa kaavaa, joka muodostetaan luokkalausekkeesta α korvaamalla vapaa muuttuja luonnollisen luvun n symbolilla . Kolmiosainen relaatio x = [ y ; z ] osoittautuu myös määriteltäväksi S:ssä. Nyt määritellään luonnollisten lukujen luokka K seuraavasti:

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

(jossa Bew x tarkoittaa: x  on johdettu kaava [~ 6] ). Koska kaikki tämän määritelmän määrittävät käsitteet voidaan ilmaista S:llä, sama pätee käsitteeseen K , joka on rakennettu niistä, eli on olemassa sellainen luokkalauseke C , että kaava [ C ; n ], joka on intuitiivisesti tulkittu, tarkoittaa, että luonnollinen luku n kuuluu K :hen . Luokkalausekkeena C on identtinen jonkin tietyn R ( q ) kanssa luettelossamme, ts.

C = R ( q )

pätee jollekin määrätylle luonnolliselle luvulle q . Osoitetaan nyt, että lause [ R ( q ); q ] on ratkaisematon S:ssä. Jos siis lause [ R ( q ); q ] oletetaan johdettavissa olevaksi, niin se osoittautuu todeksi, eli yllä olevan mukaan q tulee kuulumaan K :lle , eli (*), ¬Bew[ R ( q ); q ], mikä on ristiriidassa oletuksemme kanssa. Toisaalta, jos oletetaan, että negaatio on johdettavissa [ R ( q ); q ], silloin ¬ q ∈ K tapahtuu , eli Bew[ R ( q ); q ] on totta. Siksi [ R ( q ); q ] yhdessä sen negatiivisen kanssa on johdettavissa, mikä taas on mahdotonta.

Yhteys paradokseihin

Normaalissa tulkinnassa [~3] Gödelin ratkaisematon kaava A tarkoittaa "kaavaa A ei ole johdettu ", eli se väittää oman ei-johtavuutensa järjestelmässä S. Siten A on valehtelun paradoksin analogi . Gödelin päättely on pitkälti hyvin samanlainen kuin Richardin paradoksi . Lisäksi mitä tahansa semanttista paradoksia voidaan käyttää todistamaan ei-johdannaisten väitteiden olemassaolo [19] .

On huomattava, että kaavalla A ilmaistu väite ei sisällä noidankehää, koska aluksi väitetään vain, että jokin tietty kaava, jonka eksplisiittinen ilmaisu on helppo (vaikkakin hankala), on todistamaton. "Vasta myöhemmin (ja niin sanotusti sattumalta) käy ilmi, että tämä kaava on juuri se, joka ilmaisee itse tämän väitteen" [19] .

Gödelin toinen lause

Formaalaritmeettisessa S:ssä voidaan rakentaa kaava, joka standarditulkinnassa [~ 3] on tosi, jos ja vain jos teoria S on johdonmukainen. Tälle kaavalle Gödelin toisen lauseen väite on totta:

Jos muodollinen aritmetiikka S on johdonmukainen, siinä ei ole johdettavissa olevaa kaavaa, joka merkitsee S :n konsistenssia .

Toisin sanoen muodollisen aritmetiikan johdonmukaisuutta ei voida todistaa tällä teorialla. Formaalisen aritmeettisen johdonmukaisuudesta voi kuitenkin olla todisteita siinä sanoin kuvailemattomilla keinoilla.

Luonnos todisteesta

Ensin muodostetaan kaava Con , joka ilmaisee mielekkäästi minkä tahansa teorian S kaavan johtamisen mahdottomuuden sekä sen negatiivisen. Sitten Gödelin ensimmäisen lauseen väite ilmaistaan ​​kaavalla Con ⊃ G , jossa G  on Gödelin ratkaisematon kaava. Kaikki ensimmäisen lauseen todistuksen argumentit voidaan ilmaista ja suorittaa S:n avulla, eli kaava Con ⊃ G on johdettavissa S :stä. Näin ollen, jos Con on johdettavissa S:ssä , niin G on myös johdettavissa siinä . Kuitenkin Gödelin ensimmäisen lauseen mukaan, jos S on johdonmukainen, niin G on siinä ei-johdannainen. Siksi, jos S on johdonmukainen, niin kaava Con ei myöskään ole johdettavissa siinä .

Historiallinen vaikutus

Asiantuntijat antavat hyvin erilaisia, joskus jopa polaarisia arvioita Gödelin lauseiden historiallisesta merkityksestä. Jotkut tutkijat uskovat, että nämä teoreemat "käänsivät" matematiikan tai jopa koko tietoteorian perusteet , ja Gödelin loistavan löydön merkitys paljastuu vähitellen vielä pitkään [20] . Toiset (esim. Bertrand Russell ) kehottavat olemaan liioittelematta, koska lauseet perustuvat Hilbertin äärelliseen formalismiin [21] [22] .

Vastoin yleistä väärinkäsitystä, Gödelin epätäydellisyyslauseet eivät tarkoita, että joitain totuuksia ei koskaan tiedetä ikuisesti. Lisäksi näistä teoreemoista ei seuraa, että ihmisen kognitiokyky olisi jotenkin rajoitettu. Ei, lauseet osoittavat vain muodollisten järjestelmien heikkoudet ja puutteet [23] .

Tarkastellaan esimerkiksi seuraavaa todistetta aritmeettisen johdonmukaisuudesta [24] .

Oletetaan, että Peanon aritmetiikkaa koskeva aksiomatiikka on epäjohdonmukainen. Siitä voidaan sitten päätellä mikä tahansa väite, myös väärä. Kaikki Peanon aksioomit ovat kuitenkin ilmeisen totta, eikä oikeista väitteistä voi seurata väärää johtopäätöstä - saamme ristiriidan. Siksi aritmetiikka on johdonmukainen.

Arkipäivän inhimillisen logiikan näkökulmasta tämä todiste on hyväksyttävä ja vakuuttava. Mutta sitä ei voida kirjoittaa Hilbertin todistusteorian sääntöjen mukaan, koska näissä säännöissä semantiikka on korvattu syntaksilla ja totuus korvataan "pääteltävissä" [24] . Joka tapauksessa Gödelin lauseet nostivat matematiikan filosofian uudelle tasolle.

Katso myös

Muistiinpanot

Kommentit
  1. ↑ Joskus viitataan Gödelin toiseksi lauseeksi "yhdenmukaisuuden todisteista" [1] , "epätäydellisyydestä" [2] [3] [4] , "aritmetiikan epätäydellisyydestä" [5] .
  2. ↑ 1 2 Formaalista järjestelmää, joka sisältää ratkaisemattoman, toisin sanoen ei-johdannaisen ja kiistämättömän kaavan, kutsutaan epätäydelliseksi.
  3. ↑ 1 2 3 4 Teorian S kaavojen tulkintaa kutsutaan standardiksi, jos sen alue on ei-negatiivisten kokonaislukujen joukko, symboli 0 tulkitaan numerolla 0, funktiokirjaimet ', +, • tulkitaan yhteenlasku, yhteen- ja kertolasku, predikaattikirjain = tulkitaan identiteettirelaatiolla.
  4. ↑ Gödel käytti Whiteheadin ja Russellin Principia Mathematicaa sillä ehdolla, että päättely koskee laajaa muodollisten järjestelmien luokkaa.
  5. ↑ Tällaista kaavojen ja luonnollisten lukujen vertailua kutsutaan matematiikan aritmetisoinniksi ja Gödel teki sen ensimmäistä kertaa. Tästä ideasta tuli myöhemmin avain monien tärkeiden matemaattisen logiikan ongelmien ratkaisemiseen. Katso Gödel-numerointi
  6. ↑ "Bew" lyhenne häneltä. "Beweisbar" - todistettavissa , pääteltävissä
Lähteet
  1. ↑ Kleene 1957 s. 513
  2. ↑ vastaava jäsen RAS Lev Dmitrievich Beklemishev kirjassa "Johdatus matemaattiseen logiikkaan" . Käyttöpäivä: 7. tammikuuta 2010. Arkistoitu alkuperäisestä 21. maaliskuuta 2009.
  3. ↑ Tietojenkäsittelyjärjestelmien selittävä sanakirja - sivu 205
  4. ↑ Neuvostoliiton tiedeakatemian raportit, osa 262 - sivu 799 (1982)
  5. ↑ Neuvostoliiton tiedeakatemian julkaisut, osa 50 - sivu 1140 (1986)
  6. ↑ 1 2 Pinheiro, 2015 , s. 13, 48-49, 66, 89-90.
  7. ↑ 1 2 Kleene 1957 s. 187
  8. ↑ Mendelssohn 1971 s. 165
  9. ↑ Tämä päättely on otettu Mendelssohn 1971, s. 160
  10. ↑ Katso esimerkiksi Kleene 1957 s. 188
  11. ↑ Mendelssohn 1971 s. 162
  12. ↑ Mendelssohn 1971 s. 162-163
  13. ↑ Mendelssohn 1971 s. 176
  14. ↑ Jones JP, Ratkaisemattomat diofantiiniyhtälöt
  15. ↑ Martin Davis, Diophantine Equations & Computation (linkki ei ole käytettävissä) . Haettu 17. marraskuuta 2009. Arkistoitu alkuperäisestä 24. toukokuuta 2010. 
  16. ↑ Martin Davis, Epätäydellisyyslause . Haettu 30. marraskuuta 2011. Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
  17. ↑ K. Podnieks, Gödelin lause diofantinisessa muodossa . Haettu 17. marraskuuta 2009. Arkistoitu alkuperäisestä 10. syyskuuta 2017.
  18. ↑ Godel, Kurt. Principia Mathematican ja siihen liittyvien järjestelmien muodollisesti ratkaisemattomista ehdotuksista. I. - 1931 , Davis, Martin (toim.). Ratkaisematon: Peruspaperit ratkaisemattomista ehdotuksista, ratkaisemattomista ongelmista ja laskettavissa olevista funktioista . - New York: Raven Press, 1965. - S.  6 -8.
  19. ↑ 1 2 Gödel 1931
  20. ↑ Stephen Hawking . Godel ja universumin loppu (linkki ei saatavilla) . Haettu 8. huhtikuuta 2018. Arkistoitu alkuperäisestä 29. toukokuuta 2020. 
  21. ↑ Mikhailova N.V. Nykyaikaisen matematiikan perustelemisen ongelma uusien filosofisten ja metodologisten kriisien yhteydessä // Matematiikan filosofia: todelliset ongelmat. Matematiikka ja todellisuus. Kolmannen koko Venäjän tieteellisen konferenssin tiivistelmät; 27.-28.9.2013 . - M . : Center for Strategic Conjuncture, 2013. - S. 187. - 270 s. - ISBN 978-5-906233-39-4 . Arkistoitu 16. joulukuuta 2017 Wayback Machineen
  22. ↑ Muusikko A. .
  23. ↑ Livio, Mario. Oliko Jumala matemaatikko? Luku "Totuus epätäydellisyydessä". - M. : AST, 2016. - 384 s. — (Tieteen kultainen rahasto). - ISBN 978-5-17-095136-9 .
  24. ↑ 1 2 Pinheiro, 2015 , s. 155-162.

Kirjallisuus

Linkit

Bibliografia - Gödelin artikkelit

  • 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. ja Principia Mathematican ja siihen liittyvien järjestelmien I muodollisesti ratkaisemattomista ehdotuksista julkaisussa Solomon Feferman , toim., 1986. Kurt Gödel Kootut teokset, Voi. minä. _ Oxford University Press: 144-195. - Alkuperäinen saksankielinen teksti rinnakkain englanninkielisellä käännöksellä, jonka alkeellisen johdannon on kirjoittanut Stephen Kleene .
  • Hirzel, Martin, 2000, Principia Mathematican ja siihen liittyvien järjestelmien muodollisesti ratkaisemattomista ehdotuksista I. . - Marina Herzelin moderni käännös.
  • 1951, Jotkut peruslauseet matematiikan perusteista ja niiden vaikutuksista teoksessa Solomon Feferman , toim., 1995. Kurt Gödel Collected works, Voi. III . Oxford University Press: 304-323.