Mikä tahansa matemaattisten aksioomien järjestelmä, joka alkaa tietystä monimutkaisuustasosta, on joko sisäisesti epäjohdonmukainen tai epätäydellinen.

Vuonna 1900 Pariisissa pidettiin matemaatikoiden maailmankonferenssi, jossa David Hilbert (1862–1943) esitteli tiivistelmien muodossa 23 hänen mielestään tärkeintä muotoilemaansa ongelmaa, jotka teoreettisten tutkijoiden oli määrä ratkaista. tulevalta 1900-luvulta. Hänen luettelonsa numero kaksi oli yksi niistä yksinkertaisista ongelmista, jotka näyttävät ilmeisiltä, ​​kunnes kaivaa hieman syvemmälle. Nykyajan termein se oli kysymys: riittääkö matematiikka yksinään? Hilbertin toinen tehtävä rajoittui tarpeeseen todistaa tiukasti, että aksioomijärjestelmä – matematiikan peruslausekkeet ilman todisteita – on täydellinen ja täydellinen, eli se mahdollistaa kaiken olemassa olevan matemaattisen kuvauksen. Oli tarpeen todistaa, että on mahdollista asettaa sellainen aksioomijärjestelmä, että ensinnäkin ne ovat keskenään johdonmukaisia, ja toiseksi niistä voidaan tehdä johtopäätös minkä tahansa väitteen totuudesta tai virheellisyydestä.

Otetaan esimerkki koulun geometriasta. Tavallisessa euklidisessa planimetriassa (geometria tasossa) voidaan ehdottoman todistaa, että väite "kolmion kulmien summa on 180°" on totta, ja väite "kolmion kulmien summa on 137° "on väärä. Pohjimmiltaan euklidisessa geometriassa mikä tahansa väite on joko epätosi tai tosi, ja kolmatta ei anneta. Ja 1900-luvun alussa matemaatikot uskoivat naiivisti, että sama tilanne tulisi havaita missä tahansa loogisesti johdonmukaisessa järjestelmässä.

Ja sitten vuonna 1931 joku wieniläinen silmälasimatemaatikko Kurt Godel otti ja julkaisi lyhyen artikkelin, joka yksinkertaisesti kaatoi koko niin kutsutun "matemaattisen logiikan" maailman. Pitkien ja monimutkaisten matemaattisten ja teoreettisten alustojen jälkeen hän kirjaimellisesti totesi seuraavan. Otetaan mikä tahansa väite, kuten: "Oletus #247 on loogisesti todistamaton tässä aksioomajärjestelmässä" ja kutsutaan sitä "väittämäksi A". Joten Gödel yksinkertaisesti todisti minkä tahansa aksioomijärjestelmän seuraavan hämmästyttävän ominaisuuden:

"Jos väite A voidaan todistaa, niin ei-A-väite voidaan todistaa."

Toisin sanoen, jos on mahdollista todistaa väitteen "Oletus 247 ei ole todistettavissa" pätevyys, niin on mahdollista todistaa väitteen "Oletus 247 todistettavissa oleva" pätevyys. Toisin sanoen, kun palataan toisen Hilbert-tehtävän muotoiluun, jos aksioomijärjestelmä on täydellinen (eli mikä tahansa väite siinä voidaan todistaa), niin se on epäjohdonmukainen.

Ainoa tie ulos tästä tilanteesta on hyväksyä epätäydellinen aksioomijärjestelmä. Toisin sanoen meidän on siedettävä sitä tosiasiaa, että minkä tahansa loogisen järjestelmän yhteydessä meillä on edelleen "tyypin A" väitteitä, jotka ovat ilmeisen tosia tai vääriä - ja voimme arvioida niiden totuuden vain olemassa olevan aksiomaatiikan ulkopuolella. hyväksytty. Jos tällaisia ​​väitteitä ei ole, aksiomatiikkamme on ristiriitaista, ja sen puitteissa tulee väistämättä olemaan muotoiluja, jotka voidaan sekä todistaa että kumota.

Joten Gödelin ensimmäisen eli heikon epätäydellisyyden lauseen muotoilu on: "Mikä tahansa muodollinen aksioomijärjestelmä sisältää ratkaisemattomia oletuksia." Mutta Gödel ei pysähtynyt tähän vaan muotoili ja todistaa Gödelin toisen eli vahvan epätäydellisyyslauseen: "Minkään aksioomajärjestelmän loogista täydellisyyttä (tai epätäydellisyyttä) ei voida todistaa tämän järjestelmän puitteissa. Sen todistamiseksi tai kumoamiseksi tarvitaan lisäaksioomia (järjestelmän vahvistaminen).

Olisi turvallisempaa ajatella, että Godelin lauseet ovat abstrakteja eivätkä koske meitä, vaan vain ylevän matemaattisen logiikan alueita, mutta itse asiassa kävi ilmi, että ne liittyvät suoraan ihmisen aivojen rakenteeseen. Englantilainen matemaatikko ja fyysikko Roger Penrose (s. 1931) osoitti, että Gödelin lauseita voidaan käyttää todistamaan perustavanlaatuiset erot ihmisaivojen ja tietokoneen välillä. Hänen perustelunsa pointti on yksinkertainen. Tietokone toimii tiukasti loogisesti eikä pysty määrittämään, onko väite A tosi vai epätosi, jos se ylittää aksiomaatiikan, ja tällaisia ​​väitteitä Gödelin lauseen mukaan on väistämättä olemassa. Ihminen, joka kohtaa tällaisen loogisesti todistamattoman ja kiistämättömän väitteen A, pystyy aina määrittämään sen totuuden tai valheellisuuden - jokapäiväisen kokemuksen perusteella. Ainakin tässä ihmisen aivot ovat parempia kuin puhtaiden loogisten piirien kahlittu tietokone. Ihmisaivot pystyvät ymmärtämään Gödelin lauseiden sisältämän totuuden täyden syvyyden, mutta tietokone ei koskaan. Siksi ihmisen aivot ovat kaikkea muuta kuin tietokone. Hän pystyy tekemään päätöksiä, ja Turingin testi menee läpi.

Mietin, oliko Hilbertillä aavistustakaan, kuinka pitkälle hänen kysymyksensä vievät meidät?

Kurt GOEDEL
Kurt Godel, 1906-78

Itävaltalainen, sitten amerikkalainen matemaatikko. Syntynyt Brünnissä (Brünn, nykyään Brno, Tšekki). Hän valmistui Wienin yliopistosta, jossa hän pysyi opettajana matematiikan laitoksella (vuodesta 1930 - professori). Vuonna 1931 hän julkaisi lauseen, joka myöhemmin sai nimensä. Puhtaasti apoliittisena ihmisenä hän selvisi äärimmäisen vaikeasti natsi-opiskelijan tekemästä ystävänsä ja osastotyöntekijänsä murhasta ja vaipui syvään masennukseen, jonka paheneminen ahdisti häntä elämänsä loppuun asti. 1930-luvulla hän muutti Yhdysvaltoihin, mutta palasi kotimaahansa Itävaltaan ja meni naimisiin. Vuonna 1940, sodan huipulla, hänet pakotettiin pakenemaan Amerikkaan Neuvostoliiton ja Japanin kautta. Jonkin aikaa hän työskenteli Princeton Institute for Advanced Studyssa. Valitettavasti tiedemiehen psyyke ei kestänyt sitä, ja hän kuoli nälkään psykiatrisella klinikalla kieltäytyen syömästä, koska hän oli vakuuttunut siitä, että he aikoivat myrkyttää hänet.

Kommentit: 0

Miten tieteellinen malli kehittyy luonnontieteissä? Jokapäiväinen tai tieteellinen kokemus kertyy, sen virstanpylväät on muotoiltu siististi postulaattien muodossa ja muodostavat mallin perustan: joukko väitteitä, jotka kaikki tässä mallissa työskentelevät hyväksyvät.

Anatoli Wasserman

Vuonna 1930 Kurt Gödel todisti kaksi lausetta, jotka käännettynä matemaattisesta kielestä ihmisten kielelle tarkoittavat jotain tällaista: Mikä tahansa aksioomijärjestelmä, joka on riittävän rikas käytettäväksi aritmeettisen määrittelyssä, on joko epätäydellinen tai epäjohdonmukainen. Epätäydellinen järjestelmä tarkoittaa, että järjestelmässä voidaan muotoilla väite, jota ei voida todistaa eikä kumota tämän järjestelmän avulla. Mutta määritelmän mukaan Jumala on kaikkien syiden perimmäinen syy. Matemaattisesti tämä tarkoittaa, että Jumalaa koskevan aksiooman käyttöönotto tekee koko aksioomistamme täydellisen. Jos Jumala on olemassa, niin mikä tahansa väite voidaan joko todistaa tai kumota, viitaten tavalla tai toisella Jumalaan. Mutta Gödelin mukaan täydellinen aksioomijärjestelmä on väistämättä ristiriitainen. Eli jos uskomme, että Jumala on olemassa, meidän on pakko tulla siihen johtopäätökseen, että ristiriidat ovat mahdollisia luonnossa. Ja koska ristiriitoja ei ole, muuten koko maailmamme murentuisi näistä ristiriitaisuuksista, on päädyttävä siihen johtopäätökseen, että Jumalan olemassaolo on ristiriidassa luonnon olemassaolon kanssa.

Sosinsky A. B.

Gödelin lausetta sekä suhteellisuusteorian, kvanttimekaniikan ja DNA:n löytöä pidetään yleisesti 1900-luvun suurimpana tieteellisenä saavutuksena. Miksi? Mikä on sen olemus? Mikä sen merkitys on? Aleksei Bronislavovich Sosinsky, matemaatikko, itsenäisen Moskovan yliopiston professori, Ranskan tasavallan akateemisten palmujen ritarikunnan upseeri, RF:n hallituksen koulutusalan palkinnon saaja vuonna 2012, paljastaa nämä kysymykset luentonsa puitteissa. Polit.ru Public Lectures -projekti. Erityisesti siitä annettiin useita erilaisia ​​muotoja, kuvattiin kolme lähestymistapaa sen todistamiseen (Kolmogorov, Chaitin ja Gödel itse) ja selitettiin sen merkitys matematiikan, fysiikan, tietojenkäsittelytieteen ja filosofian kannalta.

Uspensky V. A.

Luento on omistettu Gödelin epätäydellisyyslauseen syntaktiselle versiolle. Gödel itse todisti syntaktisen version käyttämällä johdonmukaisuutta vahvempaa oletusta, nimittäin niin sanottua omega-konsistenssia.

Uspensky V. A.

Kesäkoulun "Modern Mathematics" luennot, Dubna.

Godelin epätäydellisyyslause

Uspensky V.A.

Ehkä Gödelin epätäydellisyyslause on todella ainutlaatuinen. Ainutlaatuista siinä, että he viittaavat siihen, kun he haluavat todistaa "kaiken maailmassa" - jumalien läsnäolosta järjen puuttumiseen. Olen aina ollut kiinnostunut "ensisijaisemmasta kysymyksestä" - ja kuka epätäydellisyyslauseeseen viittaavista ei voinut vain muotoilla sitä, vaan myös todistaa sen? Julkaisen tämän artikkelin siitä syystä, että se esittelee Gödelin lauseen hyvin helposti saatavilla olevan muotoilun. Suosittelen, että luet ensin Tullio Regge Kurt Gödelin artikkelin ja hänen kuuluisan lauseensa

Johtopäätös yleisen totuuskriteerin mahdottomuudesta on suora seuraus tuloksesta, jonka Tarski sai yhdistämällä Gödelin päättämättömyyslauseen omaan totuusteoriaansa, jonka mukaan ei voi olla universaalia totuuskriteeriä edes suhteellisen kapealle alueelle. lukuteoriasta ja siten kaikille aritmetiikkaa käyttäville tieteille. Tämä tulos pätee luonnollisesti sitäkin suuremmalla syyllä totuuden käsitteeseen kaikilla ei-matemaattisilla tiedon aloilla, joilla aritmetiikkaa käytetään laajalti.

Karl Popper

Uspensky Vladimir Andreevich syntyi 27. marraskuuta 1930 Moskovassa. Valmistunut Moskovan valtionyliopiston mekaniikan ja matematiikan tiedekunnasta (1952). Fysikaalisten ja matemaattisten tieteiden tohtori (1964). Professori, mekaniikan ja matematiikan tiedekunnan matemaattisen logiikan ja algoritmien teorian laitoksen johtaja (1966). Lukee luentokursseja "Johdatus matemaattiseen logiikkaan", "Laskennettavat funktiot", "Gödelin täydellisyyslause". Valmisteli 25 kandidaattia ja 2 tohtoria

1. Ongelman kuvaus

Epätäydellisyyslause, jonka tarkan sanamuodon annamme tämän luvun lopussa ja ehkä myöhemmin (jos lukijaa kiinnostaa tämä) ja todistusaineistossa, sanoo suunnilleen seuraavaa: Tietyissä olosuhteissa missä tahansa kielessä on totta, mutta todistamattomia väitteitä.

Kun muotoilemme lauseen tällä tavalla, melkein jokainen sana vaatii selityksen. Siksi aloitamme selittämällä tässä sanamuodossa käyttämiemme sanojen merkityksen.

1.1. Kieli

Emme anna kielen yleisintä mahdollista määritelmää, vaan rajoitamme mieluummin niihin kielikäsitteisiin, joita tarvitsemme myöhemmin. Tällaisia ​​käsitteitä on kaksi: "kielen aakkoset" ja "kielen tosilauseiden joukko".

1.1.1. Aakkoset

Aakkosilla tarkoitamme rajallista joukkoa alkeismerkkejä (eli asioita, joita ei voida jakaa osiin). Näitä merkkejä kutsutaan aakkosten kirjaimiksi. Aakkosten sanalla tarkoitamme äärellistä kirjainsarjaa. Esimerkiksi englanninkieliset tavalliset sanat (mukaan lukien erisnimet) ovat 54-kirjaimisen aakkosten sanoja (26 pientä kirjainta, 26 isoa kirjainta, viiva ja heittomerkki). Toinen esimerkki - luonnolliset luvut desimaalimuodossa ovat 10-kirjaimien aakkosten sanoja, joiden kirjaimet ovat merkkejä: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Käytämme tavallisia isoja kirjaimia merkitsemään aakkoset. Jos L on aakkoset, niin L? tarkoittaa aakkosten L kaikkien sanojen joukkoa, - sen kirjaimista muodostetut sanat. Oletetaan, että millä tahansa kielellä on oma aakkostonsa, joten kaikki tämän kielen ilmaisut (eli - eri objektien nimet, lausekkeet näistä objekteista jne.) ovat tämän aakkoston sanoja. Esimerkiksi mitä tahansa englanninkielistä lausetta sekä mitä tahansa englanniksi kirjoitettua tekstiä voidaan pitää laajennetun 54-kirjaimen aakkoston sanana, joka sisältää myös välimerkit, välilyönnit, punaviivamerkin ja mahdollisesti jotain muuta. hyödyllisiä hahmoja. Olettaen, että kielen ilmaisut ovat jonkin aakkoston sanoja, jätämme huomioimatta "monikerroksiset" lausekkeet, kuten ???f(x)dx. Tämä rajoitus ei kuitenkaan ole liian merkittävä, koska mikä tahansa tällainen ilmaisu voidaan sopivia käytäntöjä käyttäen "venyttää" lineaariseen muotoon. Onko L:ssä jokin joukko M? kutsutaan aakkosten L sanajoukoksi. Jos sanomme yksinkertaisesti, että M on sanajoukko, tarkoitamme, että se on jonkin aakkoston sana. Nyt yllä oleva kielioletus voidaan muotoilla uudelleen seuraavasti: millä tahansa kielellä mikä tahansa ilmaisujoukko on sanajoukko.

1.1.2. Paljon oikeita väitteitä

Oletetaan, että meille annetaan osajoukko T joukosta L? (jossa L on jonkin tarkastelemamme kielen aakkoset), jota kutsutaan "toden väittämien" (tai yksinkertaisesti "totuuksien") joukkoksi. Siirryttäessä suoraan osajoukkoon T, jätämme pois seuraavat päättelyn välivaiheet: ensinnäkin mitkä aakkosten L sanat ovat hyvin muotoiltuja kielen ilmaisuja, eli niillä on tietty merkitys tulkinnassamme tästä kielestä (esim. , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 ovat hyvin muotoiltuja lausekkeita, kun taas lausekkeet kuten +=x eivät ole); toiseksi, mitkä lausekkeet ovat kaavoja, ts. voi riippua parametrista (esim. x=3, x=y, 2=3, 2=2); kolmanneksi, mitkä kaavoista ovat suljettuja kaavoja, ts. lausekkeet, jotka eivät riipu parametreista (esimerkiksi 2=3, 2=2); ja lopuksi, mitkä suljetut kaavat ovat tosi lauseita (esimerkiksi 2=2).

1.1.3. Peruskielipari

1.2. "Todistamaton"

"Todistamaton" tarkoittaa, ettei todisteita ole.

1.3. Todiste

Huolimatta siitä, että termi "todistus" on ehkä yksi tärkeimmistä matematiikassa (bourbakit aloittavat kirjansa "Matematiikan perusteet" sanoilla: "Muinaisten kreikkalaisten ajoista lähtien sanonta "matematiikka" merkitsi samaa kuin sanomalla "todiste"), hänellä ei ole tarkkaa määritelmää. Yleisesti ottaen todisteen käsite kaikkine semanttisine haaroihinsa kuuluu pikemminkin psykologian kuin matematiikan alaan. Mutta olipa kuinka tahansa, todiste on yksinkertaisesti argumentti, jonka me itse pidämme varsin vakuuttavana vakuuttaaksemme kaikki muut.

Kun todistus on kirjoitettu ylös, siitä tulee sana jossain aakkostossa P, aivan kuten mikä tahansa englanninkielinen teksti on sana aakkosissa L, josta esimerkki on annettu edellä. Kaikkien todisteiden joukko muodostaa joukon P? osajoukon (ja melko suuren osajoukon). Emme yritä antaa tarkkaa määritelmää tälle sekä "naiiville" että "absoluuttiselle" todisteen käsitteelle tai - mikä on ekvivalentti - määritellä P?:n vastaavaa osajoukkoa. Sen sijaan harkitsemme tämän epämääräisen käsitteen muodollista analogia, josta käytämme edelleen termiä "todiste" seuraavassa. Tällä analogilla on kaksi erittäin tärkeää ominaisuutta, jotka erottavat sen intuitiivisesta käsitteestä (vaikka todisteen intuitiivinen idea heijastaa edelleen näitä ominaisuuksia jossain määrin). Ensinnäkin oletetaan, että todisteilla on erilaisia ​​käsitteitä, toisin sanoen P?:n eri osajoukot todisteet ovat sallittuja, ja vielä enemmän: itse asiassa oletetaan, että itse P:n todisteiden aakkoset voivat muuttua. . Seuraavassa edellytämme, että jokaiselle tällaiselle todistuskäsitykselle on olemassa tehokas menetelmä, toisin sanoen algoritmi, joka välttämättä määrittäisi, onko tietty aakkosten P sana todiste vai ei. Oletetaan myös, että on olemassa algoritmi, jonka avulla voidaan aina määrittää, minkä väitteen annettu todiste todistaa. (Monissa tilanteissa todistettava väite on yksinkertaisesti viimeinen lause siinä vaihesarjassa, joka muodostaa todisteen.)

Näin ollen määritelmämme lopullinen sanamuoto on seuraava:

(1) Meillä on aakkoset L (kielen aakkoset) ja aakkoset P (todistuksen aakkoset).

(2) Meille annetaan joukko P, joka on P?:n osajoukko ja jonka alkioita kutsutaan "todistuksiksi". Jatkossa oletetaan, että meillä on myös algoritmi, jonka avulla voimme määrittää, onko aakkosten P mielivaltainen sana joukon P elementti eli todiste vai ei.

(3) Onko meillä myös toiminto? (jota löytääkseen tarkalleen, mikä on todistettu), kenen verkkotunnus on? täyttää ehdon P???P?, ja jonka alue on P?:ssä. Oletetaan, että meillä on algoritmi, joka laskee tämän funktion (sanojen "algoritmi laskee funktion" tarkka merkitys on seuraava: funktion arvot saadaan käyttämällä tätä algoritmia - joukko erityisiä muunnossääntöjä). Sanomme, että elementti p? P on todiste aakkosten L sanasta?(p).

Troikka<Р, Р, ?>, ehtojen (1)-(3) täyttymistä kutsutaan deduktiiviseksi järjestelmäksi aakkosten L yli.

Lukijalle, joka tuntee tavanomaisen tavan määritellä "todistus" termeillä "aksiooma" ja "päätelmäsääntö", selitämme nyt, kuinka tätä menetelmää voidaan pitää luvussa 1.3.2 annetun määritelmän erikoistapauksena. Toisin sanoen todistus määritellään yleensä tällaisten kielilausekkeiden sarjaksi, joista jokainen on joko aksiooma tai saatu aiemmin jo olemassa olevista lauseista käyttämällä yhtä päättelysääntöä. Jos lisäämme kielemme aakkosiin uuden sanan *, voimme kirjoittaa sellaisen todistuksen sanaksi, joka on muodostettu tuloksena olevasta aakkosesta: lausekkeiden sarjasta tulee sana C1*C2*...*Cn. Tässä tapauksessa funktiolla, joka määrittää, mitä tarkalleen on todistettu, on arvonsa tämän sanan osassa, joka seuraa välittömästi sekvenssin viimeistä *-kirjainta. Algoritmi, jonka olemassaolo vaaditaan kohdassa 1.3.2. määritelmät, voidaan helposti rakentaa, kun olemme määrittäneet tarkasti minkä tahansa sanojen "aksiooma" ja "päätelmäsääntö" hyväksytyistä merkityksistä.

1.4 Yrittää muotoilla epätäydellisyyslauseen tarkasti

1.4.1. Ensimmäinen yritys

"Tietyin ehdoin aakkosten L ja deduktiivisen järjestelmän kielen perusparille<Р, Р, ?>L:n yläpuolella T:ssä on aina sana, jolla ei ole todisteita. Tämä vaihtoehto näyttää edelleen epämääräiseltä. Erityisesti voisimme helposti keksiä niin monta deduktiivista järjestelmää kuin haluamme, joissa on hyvin vähän todistettavia sanoja. ?) Ei ole sanoja jollain olisi todisteita.

1.4.2. Toinen yritys

On olemassa toinen, luonnollisempi lähestymistapa. Oletetaan, että meille annetaan kieli - siinä mielessä, että meille annetaan tämän kielen peruspari. Nyt etsitään sellaista deduktiivista järjestelmää L:n yli (intuitiivisesti etsitään todistustekniikkaa), jolla voisimme todistaa mahdollisimman monta sanaa T:stä, rajassa kaikki sanat T. Gödelin lauseesta kuvaavat tilannetta, jossa tällaista deduktiivista järjestelmää (jolla jokainen T:n sana olisi todistettavissa) ei ole olemassa. Siksi haluamme muotoilla seuraavan lausunnon:

"Tietyissä perusparin olosuhteissa ei ole sellaista deduktiivista järjestelmää, jossa jokaisella T:n sanalla olisi todiste."

Tällainen väite on kuitenkin ilmeisen väärä, koska on tarpeen ottaa vain deduktiivinen järjestelmä, jossa P = L, P = P? ja?(p) = p kaikille p:lle P2:ssa; sitten jokainen sana L:stä? on triviaalisti todistettavissa. Siksi meidän on hyväksyttävä joitain rajoituksia sille, mitä deduktiivisia järjestelmiä käytämme.

1.5. Johdonmukaisuus

Olisi aivan luonnollista vaatia, että vain "oikeat väitteet" eli vain sanat T:stä voidaan todistaa. Sanomme, että deduktiivinen järjestelmä<Р, Р, ?>on yhdenmukainen perusparin suhteen if?(P)?T. Kaikessa myöhemmässä päättelyssä olemme kiinnostuneita vain sellaisista johdonmukaisista deduktiivisista järjestelmistä. Jos meille annetaan kieli, olisi äärimmäisen houkuttelevaa löytää sellainen johdonmukainen deduktiivinen järjestelmä, jossa jokaisella oikealla väitteellä olisi todiste. Meitä kiinnostava Gödelin lauseen muunnelma sanoo tarkalleen, että tietyin edellytyksin perusparin suhteen on mahdotonta löytää tällaista deduktiivista järjestelmää.

1.6. täydellisyyttä

Sanotaan, että deduktiivinen järjestelmä<Р,Р,?>on täydellinen perusparin suhteen edellyttäen, että?(P)?T. Sitten epätäydellisyyslauseen muotoilumme saa seuraavan muodon:

Tietyissä perusparin olosuhteissa tällaista deduktiivista järjestelmää ei ole<Р,Р,?>yli L, joka olisi sekä täydellinen että suhteellisen johdonmukainen.

Bibliografia

Tämän työn valmisteluun käytettiin materiaalia sivustolta http://filosof.historic.ru.

09sen

Mikä tahansa matemaattisten aksioomien järjestelmä, joka alkaa tietystä monimutkaisuustasosta, on joko sisäisesti epäjohdonmukainen tai epätäydellinen.

Vuonna 1900 matemaatikoiden maailmankonferenssi pidettiin Pariisissa, jossa David Gilbert(David Hilbert, 1862–1943) hahmotteli teesien muodossa 23 hänen mielestään tärkeintä tehtävää, jotka tulevan 1900-luvun teoreetikoiden oli ratkaistava. Hänen luettelonsa numero kaksi oli yksi niistä yksinkertaisista ongelmista, jotka näyttävät ilmeisiltä, ​​kunnes kaivaa hieman syvemmälle. Nykyajan termein se oli kysymys: riittääkö matematiikka yksinään? Hilbertin toinen tehtävä rajoittui tarpeeseen todistaa tiukasti, että aksioomijärjestelmä – matematiikan peruslausekkeet ilman todisteita – on täydellinen ja täydellinen, eli se mahdollistaa kaiken olemassa olevan matemaattisen kuvauksen. Oli tarpeen todistaa, että on mahdollista asettaa sellainen aksioomijärjestelmä, että ensinnäkin ne ovat keskenään johdonmukaisia, ja toiseksi niistä voidaan tehdä johtopäätös minkä tahansa väitteen totuudesta tai virheellisyydestä.

Otetaan esimerkki koulun geometriasta. Tavallisessa euklidisessa planimetriassa (geometria tasossa) voidaan ehdottoman todistaa, että väite "kolmion kulmien summa on 180°" on totta, ja väite "kolmion kulmien summa on 137° "on väärä. Pohjimmiltaan euklidisessa geometriassa mikä tahansa väite on joko epätosi tai tosi, ja kolmatta ei anneta. Ja 1900-luvun alussa matemaatikot uskoivat naiivisti, että sama tilanne tulisi havaita missä tahansa loogisesti johdonmukaisessa järjestelmässä.

Ja sitten vuonna 1931 joku wieniläinen silmälasimatemaatikko Kurt Gödel- otti ja julkaisi lyhyen artikkelin, joka yksinkertaisesti kaatoi koko niin sanotun "matemaattisen logiikan" maailman. Pitkien ja monimutkaisten matemaattisten ja teoreettisten alustojen jälkeen hän kirjaimellisesti totesi seuraavan. Otetaan mikä tahansa väite, kuten: "Oletus #247 on loogisesti todistamaton tässä aksioomajärjestelmässä" ja kutsutaan sitä "väittämäksi A". Joten Gödel yksinkertaisesti todisti minkä tahansa aksioomijärjestelmän seuraavan hämmästyttävän ominaisuuden:

"Jos väite A voidaan todistaa, niin ei-A-väite voidaan todistaa."

Toisin sanoen, jos on mahdollista todistaa väitteen "Oletus 247 ei ole todistettavissa" pätevyys, niin on mahdollista todistaa väitteen "Oletus 247 todistettavissa oleva" pätevyys. Toisin sanoen, kun palataan toisen Hilbert-tehtävän muotoiluun, jos aksioomijärjestelmä on täydellinen (eli mikä tahansa väite siinä voidaan todistaa), niin se on epäjohdonmukainen.

Ainoa tie ulos tästä tilanteesta on hyväksyä epätäydellinen aksioomijärjestelmä. Toisin sanoen meidän on siedettävä sitä tosiasiaa, että minkä tahansa loogisen järjestelmän yhteydessä meillä on edelleen "tyypin A" väitteitä, jotka ovat ilmeisen tosia tai vääriä, ja voimme arvioida niiden totuuden vain olemassa olevan aksiomaatiikan ulkopuolella. hyväksytty. Jos tällaisia ​​väitteitä ei ole, aksiomatiikkamme on ristiriitaista, ja sen puitteissa tulee väistämättä olemaan muotoiluja, jotka voidaan sekä todistaa että kumota.

Joten Gödelin ensimmäisen eli heikon epätäydellisyyslauseen muotoilu on: "Mikä tahansa muodollinen aksioomijärjestelmä sisältää ratkaisemattomia oletuksia". Mutta Gödel ei pysähtynyt tähän vaan muotoili ja todistaa Gödelin toisen eli vahvan epätäydellisyyslauseen: "Minkään aksioomajärjestelmän loogista täydellisyyttä (tai epätäydellisyyttä) ei voida todistaa tämän järjestelmän puitteissa. Sen todistamiseksi tai kumoamiseksi tarvitaan lisäaksioomia (järjestelmän vahvistaminen).

Olisi turvallisempaa ajatella, että Godelin lauseet ovat abstrakteja eivätkä koske meitä, vaan vain ylevän matemaattisen logiikan alueita, mutta itse asiassa kävi ilmi, että ne liittyvät suoraan ihmisen aivojen rakenteeseen. Englantilainen matemaatikko ja fyysikko Roger Penrose (s. 1931) osoitti, että Gödelin lauseet voidaan käyttää todistamaan perustavanlaatuisten erojen olemassaolo ihmisaivojen ja tietokoneen välillä. Hänen perustelunsa pointti on yksinkertainen. Tietokone toimii tiukasti loogisesti eikä pysty määrittämään, onko väite A tosi vai epätosi, jos se ylittää aksiomaatiikan, ja tällaisia ​​väitteitä Gödelin lauseen mukaan on väistämättä olemassa. Ihminen, joka kohtaa tällaisen loogisesti todistamattoman ja kiistämättömän väitteen A, pystyy aina määrittämään sen totuuden tai valheellisuuden - jokapäiväisen kokemuksen perusteella. Ainakin tässä ihmisen aivot ovat parempia kuin puhtaiden loogisten piirien kahlittu tietokone. Ihmisaivot pystyvät ymmärtämään Gödelin lauseiden sisältämän totuuden täyden syvyyden, mutta tietokone ei koskaan. Siksi ihmisen aivot ovat kaikkea muuta kuin tietokone. Hän pystyy tekemään päätöksiä, ja Turingin testi menee läpi.

Godelin epätäydellisyyslauseet

Godelin epätäydellisyyslauseet

Godelin epätäydellisyyslauseet- kaksi matemaattisen logiikan lausetta muodollisen aritmeettisen ja sen seurauksena minkä tahansa riittävän vahvan ensimmäisen asteen teorian perusrajoituksista.

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 sanoo, että jos muodollinen aritmetiikka on johdonmukainen, niin jokin kaava on siinä ei-johdettavissa, mikä merkitsee tämän teorian johdonmukaisuutta.

Gödelin ensimmäinen epätäydellisyyslause

Gödelin ensimmäisen epätäydellisyyslauseen väite voidaan esittää seuraavasti:

Jos muodollinen aritmeettinen S on johdonmukainen, silloin se sisältää suljetun kaavan G siten, että G tai sen negaatio ¬G eivät ole johdettavissa S .

Todistaessaan lauseen Gödel rakensi kaavan G nimenomaisesti, joskus sitä kutsutaan Gödelin ratkaisemattomaksi kaavaksi. Normaalissa tulkinnassa lause G väittää oman ei-johdettavuutensa S:ssä. Siksi Gödelin lauseen mukaan, jos teoria S on johdonmukainen, tämä kaava on todellakin ei-johdettavissa S:ssä ja siksi totta standarditulkinnassa. Luonnollisille luvuille siis kaava G on totta, mutta se ei ole pääteltävissä S:ssä.

Gödelin todistus voidaan suorittaa myös mille tahansa S:stä saadulle teorialle lisäämällä uusia aksioomia, esimerkiksi kaava G aksioomana. Siksi mikä tahansa johdonmukainen teoria, joka on muodollisen aritmeettisen laajennus, on epätäydellinen.

Todistaakseen ensimmäisen epätäydellisyyslauseen Gödel antoi tietyn numeron jokaiselle symbolille, lausekkeelle ja lausekesarjalle muodollisessa aritmetiikassa. Koska kaavat ja lauseet ovat aritmeettisia lauseita ja lauseiden muodolliset johdannaiset ovat kaavojen sarjoja, tuli mahdolliseksi puhua lauseista ja todisteista luonnollisten lukujen perusteella. Olkoon esimerkiksi Gödelin ratkaisematon kaava G on numero m, niin se vastaa seuraavaa lausetta aritmeettisella kielellä: "ei ole olemassa sellaista luonnollista lukua n, Mitä n on kaavan johtamisluku numeron kanssa m Tällaista kaavojen ja luonnollisten lukujen vertailua kutsutaan matematiikan aritmetisoinniksi, ja Gödel toteutti sen ensimmäistä kertaa. Tästä ideasta tuli myöhemmin avain monien tärkeiden matemaattisen logiikan ongelmien ratkaisemiseen.

todisteluonnos

Korjataan joku muodollinen järjestelmä PM, jossa alkeismatemaattiset käsitteet voidaan esittää.

Formaalisen järjestelmän lausekkeet ovat ulkopuolelta katsottuna äärellisiä primitiivisten symbolien sarjoja (muuttujia, loogisia vakioita ja hakasulkuja tai pisteitä), ja ei ole vaikea määritellä tarkasti mitkä primitiivisten symbolien sekvenssit ovat kaavoja ja mitkä eivät. Vastaavasti muodollisesta näkökulmasta todistukset ovat vain äärellisiä kaavojen sarjoja (joilla on tiukasti määritellyt ominaisuudet). Matemaattisesti ei ole väliä mitkä objektit otetaan primitiivisiksi symboleiksi, ja päätämme käyttää luonnollisia lukuja näihin tarkoituksiin. Vastaavasti kaava on luonnollisten lukujen äärellinen sarja, kaavan johdannainen on luonnollisten lukujen äärellinen sarja. Matemaattisista käsitteistä (lausekkeista) tulee näin ollen käsitteitä (lauseita) luonnollisista lukuista tai niiden sarjoista, ja siksi ne voidaan ilmaista itse PM-järjestelmän symboliikassa (ainakin osittain). Voidaan osoittaa erityisesti, että käsitteet "kaava", "johdannainen", "johdannainen kaava" ovat määriteltävissä PM-järjestelmässä, eli voidaan palauttaa esimerkiksi kaava. F(v) PM:ssä yhdellä vapaalla muuttujalla v(jonka tyyppi on numeerinen sarja) siten, että F(v), tarkoittaa intuitiivisessa tulkinnassa: v- johdettavissa oleva kaava. Rakentakaamme nyt PM-järjestelmän ratkaisematon lause, eli lause A, jolle ei kumpikaan A, ei myöskään ei-A ei ole pääteltävissä seuraavasti:

Kaavaa PM:ssä, jossa on täsmälleen yksi vapaa muuttuja, jonka tyyppi on luonnollinen luku (luokkien luokka), kutsutaan lausekeluokaksi. Järjestetään luokkalausekkeet jollain tavalla järjestykseen, denot n-e läpi R(n), ja huomaa, että käsite "luokka-ilmaus" sekä järjestyssuhde R voidaan määrittää PM-järjestelmässä. Olkoon α mielivaltainen luokkalauseke; kautta [α; n] tarkoittaa kaavaa, joka muodostetaan luokkalausekkeesta α korvaamalla vapaa muuttuja luonnollisen luvun symbolilla n. Kolmiosainen suhde x = [y;z] osoittautuu myös määriteltävissä PM:ssä. Nyt määrittelemme luokan K luonnolliset luvut seuraavasti:

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

(missä Bew x tarkoittaa: x- johdettava kaava). Koska kaikki tässä määritelmässä esiintyvät käsitteet voidaan ilmaista PM:nä, sama pätee käsitteeseen K, joka on rakennettu niistä, eli on olemassa sellainen luokka-ilmaus S että kaava [ S;n], joka on intuitiivisesti tulkittu, tarkoittaa, että luonnollinen luku n kuuluu K. Luokkailmaisuna, S identtinen joidenkin tiettyjen kanssa R(q) numerointissamme, eli

S = R(q)

pätee jollekin selvälle luonnolliselle luvulle q. Osoittakaamme nyt, että lause [ R(q);q] on ratkaisematon PM:ssä. Joten jos lause [ R(q);q] oletetaan johdettavissa olevaksi, niin se osoittautuu todeksi, toisin sanoen edellä sanotun mukaisesti, q tulee kuulumaan K, eli (*) mukaan ¬Bew[ R(q);q] täyttyy, mikä on ristiriidassa oletuksemme kanssa. Toisaalta, jos kielto [ R(q);q] oli johdettavissa, sitten ¬ n ∈ K, eli Bew[ R(q);q] on totta. Siksi [ R(q);q] yhdessä sen negatiivisen kanssa on johdettavissa, mikä taas on mahdotonta.

Polynomimuoto

Jokaiselle johdonmukaiselle teorialle T parametrille K voidaan määrittää sellainen kokonaisluku, että yhtälö (θ + 2 z − b 5) 2 + (u + tθ − l) 2 + (y + mθ − e) 2 + (n − q 16) 2 + ((g + eq 3 + lq 5 + (2(e − zλ)(1 + g) 4 + λ b 5+λ b 5 q 4)q 4)(n 2 − n) + (q 3 − bl + l + θλ q 3 + (b 5 − 2)q 5)(n 2 − 1) − r) 2 + (s − 2ws 2 r 2 n 2) 2 + (s 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − ksn 2) 2 + η − k 2) 2 + (r + 1 + hs − h − k) 2 + (a − (wn 2 + 1)rsn 2) 2 + (2r+ 1 + φ − c) 2 + (bw + ca − 2c+ 4αγ − 5γ − d) 2 + ((a 2 − 1)c 2 + 1 − d 2) 2 + ((a 2 − 1)i 2 c 4 + 1 − f 2) 2 + (((a + f 2 (d 2 − a)) 2 − 1)(2r + 1 + jc) 2 + 1 − (d + of) 2) 2 + (((z + u + y) 2 + u) 2 + y − K) 2 = 0 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 ei-numeroitavissa.

Gödelin toinen epätäydellisyyslause

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

Jos muodollinen aritmeettinen S on johdonmukainen, se sisältää ei-johdannaisen kaavan, joka vakuuttaa olennaisesti johdonmukaisuuden S .

Toisin sanoen muodollisen aritmetiikan johdonmukaisuutta ei voida todistaa tällä teorialla. On kuitenkin olemassa todisteita muodollisen aritmeettisen johdonmukaisuudesta käyttämällä siinä sanomattomia keinoja.

todisteluonnos

Ensin rakennetaan kaava Con, ilmaisee mielekkäästi sen, että teoriassa S on mahdotonta johtaa mikä tahansa kaava yhdessä sen negatiivisuuden kanssa. Sitten Gödelin ensimmäisen lauseen väite ilmaistaan ​​kaavalla Con ⊃ G, Missä G- Gödelin ratkaisematon kaava. Kaikki argumentit ensimmäisen lauseen todistukselle voidaan ilmaista ja suorittaa S:n avulla, eli S:ssä kaava on johdettavissa Con ⊃ G. Näin ollen, jos S on johdettavissa Con, niin johdamme siitä ja G. Kuitenkin Gödelin ensimmäisen lauseen mukaan, jos S on johdonmukainen, niin G siinä ei ole pääteltävissä. Siksi, jos S on johdonmukainen, niin kaava Con.

Huomautuksia

Katso myös

Linkit

• V. A. Uspensky Godelin epätäydellisyyslause. - M.: Nauka, 1982. - 110 s. - (Suosittuja matematiikan luentoja).
• Akateemikko Yu. L. Ershov "Matematiikan todisteet", A. Gordonin ohjelma 16. kesäkuuta 2003
• A. B. Sosinsky Gödelin lause // kesäkoulu "Moderni matematiikka". - Dubai: 2006.
• P. J. Cohen Joukkoteorian perusteilla // Matemaattisten tieteiden edistyminen. - 1974. - T. 29. - Nro 5 (179). - S. 169–176.
• M. Kordonsky Totuuden loppu. - ISBN 5-946448-001-04
• V. A. Uspensky Gödelin epätäydellisyyslause ja neljä siihen johtavaa tietä // kesäkoulu "Moderni matematiikka". - Dubai: 2007.
• Zenkin A. A. Aikajakoperiaate ja yhden lähes äärellisen uskottavan päättelyn luokan analyysi (G. Kantorin laskemattomuuslauseen esimerkissä) // DAN. - 1997. - T. 356. - Nro 6. - S. 733-735.
• Chechulin V.L. Lyhyestä versiosta Gödelin lauseiden todistuksesta // "Matematiikan ja tietotieteiden perusongelmat", akateemikko E.V. nimetyn XXXIV Far Eastern Mathematical School -seminaarin materiaalit. Zolotova. - Habarovsk, Venäjä: 2009. - S. 60-61.

Wikimedia Foundation. 2010 .

Katso, mitä "Gödelin epätäydellisyyslauseet" ovat muissa sanakirjoissa:

Tällä termillä on muita merkityksiä, katso Gödelin lause. Gödelin epätäydellisyyslause ja Gödelin toinen lause [1] ovat kaksi matemaattisen logiikan lausetta, jotka koskevat muodollisen aritmeettisen perusrajoituksen ja sen seurauksena kaikkia ... ... Wikipedia

Gödelin epätäydellisyyslauseet ovat kaksi matemaattisen logiikan lausetta tietyntyyppisten muodollisten järjestelmien epätäydellisyydestä. Sisältö 1 Gödelin ensimmäinen epätäydellisyyslause 2 Gödelin toinen epätäydellisyyslause ... Wikipedia

Tällä termillä on muita merkityksiä, katso Gödelin lause. Gödelin lause predikaattilaskennan täydellisyydestä on yksi matemaattisen logiikan peruslauseista: se muodostaa yksiselitteisen suhteen loogisen totuuden välille ... ... Wikipedia

Yhteinen nimi kahdelle K. Gödelin laatimalle lauseelle. Ensimmäinen G. t. noin n. väittää, että missä tahansa johdonmukaisessa muodollisessa järjestelmässä, joka sisältää vähimmäismäärän aritmetiikkaa (merkit ja tavanomaiset säännöt niiden käsittelemiseksi), on muodollisesti ratkaisematon ... ... Matemaattinen tietosanakirja

aiheesta: "Jumalan LAUSE"

Kurt Gödel

Kurt Gödel - suurin matemaattisen logiikan asiantuntija - syntyi 28. huhtikuuta 1906 Brunnissa (nykyisin Brno, Tšekin tasavalta). Hän valmistui Wienin yliopistosta, jossa hän puolusti väitöskirjaansa, oli apulaisprofessori vuosina 1933–1938. Anschlussin jälkeen hän muutti Yhdysvaltoihin. Vuodesta 1940 vuoteen 1963 Gödel työskenteli Princeton Institute for Advanced Studyssa. Gödel on Yalen ja Harvardin yliopistojen kunniatohtori, Yhdysvaltain kansallisen tiedeakatemian ja American Philosophical Societyn jäsen.

Vuonna 1951 Kurt Gödel sai Yhdysvaltain korkeimman tieteellisen palkinnon, Einstein-palkinnon. Tälle tapahtumalle omistetussa artikkelissa toinen aikamme suurimmista matemaatikoista, John von Neumann, kirjoitti: "Kurt Gödelin panos moderniin logiikkaan on todella monumentaalinen. Tämä on enemmän kuin pelkkä monumentti. Tämä on virstanpylväs, joka erottaa kaksi aikakautta... Voidaan liioittelematta sanoa, että Gödelin työ muutti pohjimmiltaan logiikan aihetta tieteenä.

Itse asiassa jopa kuiva lista Gödelin saavutuksista matemaattisen logiikan alalla osoittaa, että niiden kirjoittaja loi perustan tämän tieteen kokonaisille osille: mallien teorialle (1930; ns. teoreema kapean predikaattilaskennan täydellisyydestä, joka osoittaa, karkeasti sanottuna "muodollisen logiikan" välineiden riittävyys todistaa kaikki sen kielellä ilmaistut todelliset lauseet), konstruktiivinen logiikka (1932–1933; tulokset mahdollisuudesta pelkistää joitain klassisen logiikan lauseluokkia niiden intuitionistisiksi vastineiksi). perusta systemaattiselle "upotusoperaatioille", jotka mahdollistavat erilaisten loogisten järjestelmien pelkistämisen toisiinsa), muodollinen aritmetiikka (1932–1933; tulokset mahdollisuudesta pelkistää klassinen aritmetiikka intuitionistiseksi aritmetiikaksi, mikä osoittaa tietyssä mielessä johdonmukaisuuden ensimmäisestä suhteessa toiseen), algoritmien ja rekursiivisten funktioiden teoria (1934; yleisen rekursiivisen funktion käsitteen määritelmä, jolla oli ratkaiseva rooli useiden matematiikan tärkeiden ongelmien algoritmisen ratkaisemattomuuden määrittämisessä). toisaalta. Ja loogisten ja matemaattisten ongelmien toteuttamisessa elektronisissa tietokoneissa - toisaalta aksiomaattinen joukkoteoria (1938; todiste valinnan aksiooman ja Cantorin jatkumohypoteesin suhteellisesta johdonmukaisuudesta joukkoteorian aksioomeista, mikä merkitsi alkua sarja tärkeitä tuloksia suhteellisen johdonmukaisuuden ja riippumattomuuden joukkoteoreettisista periaatteista).

Godelin epätäydellisyyslause

Johdanto

Vuonna 1931 eräässä saksalaisessa tieteellisessä lehdessä ilmestyi suhteellisen pieni artikkeli melko pelottavalla otsikolla "Principia Mathematican ja siihen liittyvien järjestelmien muodollisesti ratkaisemattomista ehdotuksista". Sen kirjoittaja oli 25-vuotias matemaatikko Wienin yliopistosta Kurt Gödel, joka työskenteli myöhemmin Princeton Institute for Advanced Studyssa. Tällä teoksella oli ratkaiseva rooli logiikan ja matematiikan historiassa. Harvardin yliopiston päätöksessä myöntää Gödelille kunniatohtorin arvo (1952) sitä luonnehdittiin yhdeksi modernin logiikan suurimmista saavutuksista.

Julkaisuhetkellä Gödelin teokselle ei kuitenkaan ollut nimeä. Sen sisältö ei myöskään sanonut mitään useimmille matemaatikoille. Nimessään mainittu Principia Mathematica on Alfred North Whiteheadin ja Bertrand Russellin monumentaalinen kolmiosainen tutkielma matemaattisesta logiikasta ja matematiikan perusteista; tutkielman tuntemus ei suinkaan ollut välttämätön edellytys onnistuneelle työlle useimmilla matematiikan aloilla. Kiinnostus Gödelin työssä käsiteltyihin kysymyksiin on aina ollut hyvin pienelle tiedemiehelle. Samaan aikaan Gödelin todisteissaan esittämät perustelut olivat aikansa epätavallisia. Se, että niiden täydellinen ymmärtäminen edellytti erityistä tietoa aiheesta ja perehtymistä näihin hyvin erityisiin ongelmiin omistetun kirjallisuuden kanssa.

Ensimmäinen epätäydellisyyslause

Gödelin ensimmäinen epätäydellisyyslause näyttää olevan matemaattisen logiikan merkittävin tulos. Se kuulostaa tältä:

Mielivaltaiselle johdonmukaiselle muodolliselle ja laskettavalle teorialle, jossa aritmeettiset peruslauseet voidaan todistaa, voidaan rakentaa todellinen aritmeettinen lause, jonka totuutta ei voida todistaa teorian puitteissa. Toisin sanoen mikään täysin hyödyllinen teoria, joka riittää edustamaan aritmetiikkaa, ei voi olla sekä johdonmukainen että täydellinen.

Tässä sana "teoria" tarkoittaa "ääretöntä joukkoa" väitteitä, joista joidenkin oletetaan olevan tosia ilman todisteita (sellaisia ​​väitteitä kutsutaan aksioomeiksi), kun taas toiset (lauseet) voidaan päätellä aksioomista ja siksi oletetaan ( osoittautui) todeksi. Ilmaisu "teoriassa todistettavissa oleva" tarkoittaa "pääteltyä teorian aksioomeista ja primitiivisistä (aakkosten vakiosymboleista) käyttämällä tavallista (ensimmäisen asteen) logiikkaa". Teoria on johdonmukainen, jos siinä on mahdotonta todistaa ristiriitaista väitettä. Ilmaisu "voidaan rakentaa" tarkoittaa, että on olemassa jokin mekaaninen menettely (algoritmi), joka voi rakentaa lausunnon aksioomien, primitiivien ja ensimmäisen kertaluvun logiikan perusteella. "Alkuaritmetiikka" on luonnollisten lukujen yhteen- ja kertolaskuoperaatioiden läsnäolo. Tuloksena olevaa oikeaa, mutta todistamatonta väitettä kutsutaan usein tietylle teorialle "Gödel-sekvenssiksi", mutta teoriassa on ääretön määrä muita väitteitä, joilla on sama ominaisuus olla todistamattomia teorian sisällä.

Oletus, että teoria on laskettavissa, tarkoittaa, että periaatteessa on mahdollista toteuttaa tietokonealgoritmi (tietokoneohjelma), joka (jos sallitaan mielivaltaisen pitkiä aikoja, äärettömään asti) laskee listan kaikista teorian teoreemista. Itse asiassa riittää, että lasketaan vain luettelo aksioomista, ja kaikki lauseet voidaan johtaa tehokkaasti tällaisesta luettelosta.

Ensimmäinen epätäydellisyyslause oli nimeltään "Lause VI" Gödelin vuoden 1931 artikkelissa. Muodollisesti ratkaisemattomista väitteistä Principia Mathematicassa ja siihen liittyvissä järjestelmissä I. Gödelin alkuperäisessä tallenteessa se kuulosti tältä:

"Yleinen johtopäätös ratkaisemattomien ehdotusten olemassaolosta on seuraava:

Lause VI .

Jokaiselle ω-konsistentille rekursiiviselle luokalle k KAAVA on rekursiivisia MERKIT r sellainen, ettei kumpikaan (v Gen r), ei myöskään ¬( v Gen r)eivät kuulu Flg (k)(missä v on ILMAINEN MUUTTUJA r ) ».

Nimitys Flg tulee häneltä. Folgerungsmenge- sarja sarjoja, Gen tulee häneltä. yleistys- yleistäminen.

Karkeasti sanottuna Gödelin lausunto G väittää: "totuus G ei voida todistaa." Jos G voitaisiin todistaa teorian puitteissa, silloin teoria sisältäisi lauseen, joka on ristiriidassa itsensä kanssa, ja siksi teoria olisi epäjohdonmukainen. Mutta jos G todistamaton, niin se on totta, ja siksi teoria on epätäydellinen (väite G ei ole pääteltävissä siitä).

Tämä selitys on tavallisella luonnollisella kielellä, eikä siksi aivan matemaattisesti tiukka. Tarkan todisteen saamiseksi Gödel numeroi väitteet luonnollisilla luvuilla. Tässä tapauksessa myös lukuja kuvaava teoria kuuluu lauseiden joukkoon. Lausekkeiden todistettavuutta koskevat kysymykset voidaan tässä tapauksessa esittää luonnollisten lukujen ominaisuuksia koskevien kysymysten muodossa, joiden on oltava laskettavissa, jos teoria on valmis. Näillä termeillä Gödelin lausunto sanoo, ettei ole olemassa lukua jolla on jokin tietty ominaisuus. Numero, jolla on tämä ominaisuus, on todiste teorian epäjohdonmukaisuudesta. Jos tällainen luku on olemassa, teoria on epäjohdonmukainen, toisin kuin alkuperäinen oletus. Joten olettaen, että teoria on johdonmukainen (kuten lauseen lähtökohta ehdottaa), käy ilmi, että sellaista lukua ei ole, ja Gödelin väite on totta, mutta tätä ei voida todistaa teorian puitteissa (siis teoria on epätäydellinen) . Tärkeä käsitteellinen huomautus on, että on oletettava, että teoria on johdonmukainen, jotta Gödelin väite voidaan julistaa todeksi.

Gödelin toinen epätäydellisyyslause

Gödelin toinen epätäydellisyyslause kuuluu seuraavasti:

Jokaiselle muodollisesti rekursiivisesti numeroitavalle (eli tehokkaasti generoidulle) teorialle T, mukaan lukien perusaritmeettiset totuuslausunnot ja tietyt muodolliset todistettavuuslausekkeet, tietty teoria T sisältää lausuman sen johdonmukaisuudesta, jos ja vain jos teoria T on epäjohdonmukainen.

Toisin sanoen riittävän rikkaan teorian johdonmukaisuutta ei voida todistaa tällä teorialla. Voi kuitenkin hyvinkin käydä ilmi, että tietyn teorian johdonmukaisuus voidaan todeta toisen, tehokkaamman muodollisen teorian avulla. Mutta sitten herää kysymys tämän toisen teorian johdonmukaisuudesta ja niin edelleen.

Monet ovat yrittäneet käyttää tätä lausetta todistaakseen, että älyllistä toimintaa ei voida pelkistää laskelmiin. Esimerkiksi vuonna 1961 kuuluisa logiikka John Lucas keksi samanlaisen ohjelman. Hänen päättelynsä osoittautui varsin haavoittuvaiseksi - hän asetti tehtävän kuitenkin laajemmin. Roger Penrose ottaa hieman erilaisen lähestymistavan, joka esitetään kirjassa kokonaan, "tyhjästä".

Keskustelut

Lauseen seuraukset vaikuttavat matematiikan filosofiaan, erityisesti niihin formalismiin, jotka käyttävät muodollista logiikkaa periaatteiden määrittelemiseen. Ensimmäinen epätäydellisyyslause voidaan muotoilla uudelleen seuraavasti: on mahdotonta löytää kattavaa aksioomijärjestelmää, joka voitaisiin todistaa Kaikki matemaattisia totuuksia, eikä yhtäkään valhetta". Toisaalta tiukan muodollisuuden näkökulmasta tässä uudelleenmuotoilussa ei ole juurikaan järkeä, koska siinä oletetaan, että käsitteet "tosi" ja "epätosi" määritellään absoluuttisessa merkityksessä eikä suhteellisessa merkityksessä. jokaiseen erityiseen järjestelmään.