Gödeli mittetäielikkuse teoreemid on nimetus, mis on antud kahele teoreemile (tõele matemaatilisele väitele), mida Kurt Gödel tõestas 1931. aastal. Need on matemaatilise loogika teoreemid. Need tõestused muutsid 20. sajandi matemaatika ja filosoofia arusaama selle kohta, mida formaalne ehk aksioomide põhine süsteem suudab teha.

Matemaatikud arvasid kunagi, et kõigel, mis on tõsi, on matemaatiline tõestus. Süsteemi, millel on see omadus, nimetatakse täielikuks; süsteemi, millel seda ei ole, nimetatakse mittetäielikuks. Samuti ei tohiks matemaatilistel ideedel olla vastuolusid. See tähendab, et nad ei tohiks olla samaaegselt tõesed ja valed. Süsteemi, mis ei sisalda vastuolusid, nimetatakse järjepidevaks. Need süsteemid põhinevad aksioomide kogumitel. Aksioomid on väited, mida aktsepteeritakse tõena ja mis ei vaja tõestamist.

Gödel ütles, et iga mittetriviaalne (huvitav) formaalne süsteem on kas mittetäielik või ebajärjekindel:

  1. Alati on küsimusi, millele ei saa vastata, kasutades teatud aksioomide kogumit;
  2. Te ei saa tõestada, et aksioomide süsteem on järjepidev, kui te ei kasuta teistsugust aksioomide kogumit.

Mis täpselt on Gödeliga tõestatud?

Gödeli originaalväide jaguneb tavaliselt kaheks teoreemiks:

  • Esimene mittetäielikkuse teoreem: Kui formaalne süsteem on piisavalt tugev, et selles saab vormistada lihtsat aritmeetikat (näiteks Peano aritmeetika) ja kui see süsteem on järjepidev ning tema aksiomide ja tõestusreeglite hulk on mehaaniliselt (rekursiivselt) loetav, siis leidub selles süsteemis lauseid, mis on tõelised (tõesus tavalises aritmeetilise mudeelis) ent mida süsteem ise ei suuda tõestada. Teisisõnu: süsteem on mittetäielik.
  • Teine mittetäielikkuse teoreem: Sama laadi süsteem ei saa omaenda järjepidevust tõestada (st kui süsteem on tõepoolest järjepidev, siis ei saa selles süsteemis leiduvatest reeglitest ja aksiomidest lähtudes tuletada väidet „see süsteem on järjepidev”). See tähendab, et järjepidevuse avastamine nõuab tihti vastava süsteemi väliselt informatsiooni või tugevamaid aksiome.

Kuidas see töötab (kuivõrd lihtsustatud selgitus)

Gödeli argument kasutab kahte põhilist ideed:

  • Gödelite arvustamine (Gödel numbering): kõiki sümboleid, valemeid ja tõestusi kodeeritakse täisarvudeks. Sel viisil saavad loogilised laused ja tõestused olla objektid aritmeetikas.
  • Diagonalisatsioon ja enesereferents: konstrueeritakse lause G, mis „räägib” endast läbi oma Gödel-numbri. Selle G sisu on vabasõnaliselt: „Seda lauset ei saa selles süsteemis tõestada.” Kui süsteem suudaks G tõestada, tekiks vastuolu (sest G väidab, et see ei ole tõestatav); kui süsteem ei suuda G tõestada, siis G on tegelikult tõene (võimalikus tavakeeles) aga mittetõestatud — seega mittetäielik.

Mõned olulised mõisted ja täpsustused

  • Sõnas „tõene” ja „tõestatud” vahe: „Tõene” viitab tavaliselt semantilisele tõele kindlas mudelis (näiteks tavalistes täisarvudes aritmeetika kohta), „tõestatud” tähendab sünteetilist ehk formaalset järeldust aksiomide ja reeglite alusel.
  • „Piisavalt tugev” süsteem: ei tähenda kõikehõlmavat süsteemi, vaid süsteemi, milles saab kodeerida põhilisi aritmeetilisi tehteid ja mingit elementaarset metaaritmeetikat. Näiteks Peano aritmeetika on piisavalt tugev, samas väga lihtsad loogilised süsteemid seda ei ole.
  • Mehaaniliselt loetav (rekursiivne) hulga nõue: Gödel eeldas, et tõestusprotsess on formaliseeritav nii, et on olemas algoritm, mis suudaks nimekirja teha kõigist lubatud tõestustest — see eristab tema tulemust juhuslikest, mitte-mehaanilistest aksiomistikest.

Miks see on oluline?

  • Piirangud formaalsetele süsteemidele: Gödel näitas, et lootus saada üks olemuslikult lõpuni viidud ja täielik akadeemiline teoria kõigi matemaatiliste tõdede kohta (nagu Hilberti programm soovitas) ei saa teoks — vähemalt mitte ilma omaenda järjepidevuse väitmiseta teisest, tugevamast süsteemist.
  • Mõju filosoofiale: Gödel ei tõestanud, et inimintellekt on „müstiliselt” võimekam kui masin, kuid tema teoreemid on andnud tugeva aluse debatile inimloogika, formaalse mõtlemise ja mehaanilise arvutamise piiridest.
  • Seos arvutiteadusega: mittetäielikkuse ideed ja Gödelile järgnenud töö (nt Turingi Turingi masin ja otsustamatuse tulemused) aitasid selgitada, millised probleemid on algoritmiliselt lahendatavad ja millised mitte.

Näited ja intuitsioon

Intuitiivselt sarnaneb Gödelite argument vanale „äänsest paradoksile” (nt „see lause on vale”), kuid Gödel kasutab selle asemel aritmeetikasse kodeeritud väidet, nii et paradoksi ohtlik semantiline ring ei tekita loogilist vastuolu — ta jääb formaalselt korrektseks. Tulemus on pigem konstruktiivne: Gödel näitab, kuidas ühe konkreetse lause olemasolu ühes süsteemis tekitab valiku, mis ei lahendu süsteemi sisemiste vahenditega.

Piirangud ja sageli valesti mõistetud aspektid

  • Gödel ei väitnud, et matemaatika on „mõttetu” või „katkine” — ta näitas pigem, et iga rikas formaalne süsteem lõikab endale haiguse: kas see jätab välja tõsi väiteid või suudab teha sisemisi vasturääkivusi, kui see pole järjepidev.
  • Teoreetiliselt on võimalik lisada uusi aksiome ja teha süsteemi „täiustatumaks”, kuid iga kord kui süsteemi jõulisust suurendatakse, tekivad taas uued, samasugused piiriülesed väited.
  • Teine teoreem ei ütle, et süsteem ei suuda tõestada ühtegi oma järjepidevuse vormi — ainult seda, et see ei suuda tõestada omaenda järjepidevust, kasutades vaid omaenda aksiome ja reegleid (eeldusel, et süsteem on järjepidev ja piisavalt tugev).

Kokkuvõte

Gödeli mittetäielikkuse teoreemid näitavad, et mis tahes piisavalt võimas ja mehaaniliselt defineeritav formaalne süsteem ei saa korraga olla täielik ja tõestada omaenda järjepidevust. See tulemus seadis piiri Hilberti programmile ja muutis põhjalikult arusaama matemaatika aluste ning formaalse tõestamise võimalustest. Teoreemidel on sügav mõju nii matemaatikafilosoofiale kui ka arvutiteadusele ja loogikale.