Gēdela nepilnības teorēmas: nozīme, formulējums un sekas matemātikā

Gēdela nepilnības teorēmas ir nosaukums divām teorēmām (patiesiem matemātiskiem apgalvojumiem), ko 1931. gadā pierādīja Kurts Gēdels. Tās pieder matemātiskās loģikas laukam un kopš to atklāšanas būtiski ietekmējušas gan matemātikas teorētisko pamatu izpratni, gan filozofiskus uzskatus par matemātikas dabu.

Ilgu laiku matemātiķi un loģiķi cerēja, ka būs iespējams izveidot formālu aksiomu kopumu, kas būtu vienlaikus pilnīgs (t.i., katram patiesam apgalvojumam sistēmā var atrast pierādījumu) un konsekvents (t.i., sistēmā nav pretrunu — nekas nevar būt vienlaikus pierādāms un tā nē). Aksiomas ir tie pamata apgalvojumi, kurus pieņemam kā patiesus, bez pierādījuma, un no tiem ar noteiktām deduktīvām metodēm iegūstam pārējos teikumus.

Teorēmu formulējums vienkāršā valodā

Gēdela pamatideja: katra „neredzami interesanta” (netriviāla) formāla sistēma, kas spēj izteikt pietiekami daudz aritmētikas, ir pakļauta šādām ierobežojumu kategorijām:

1. Vienmēr būs apgalvojumi, kurus sistēma nespēj ne pierādīt, ne arī noliegt — tātad sistēma ir nepilnīga;
2. Sistēma pati par sevi nevar dot derīgu pierādījumu par savu konsekvenci, ja vien šo pierādījumu nebalsta spēcīgāka (ārēja) aksiomu kopa — tātad nav iespējams pierādīt sistēmas konsekvenci sistēmas paša ietvaros.

Formālāks variants (svarīgākie nosacījumi)

Precīzāk formulējot, Gēdela teorēmas prasa dažus tehniskus nosacījumus par pētāmo teoriju:

• teorija ir efektīvi aksiomatizējama (tās aksiomu kopa ir algoritmiski noteicama vai rekursīvi atpazīstama);
• teorija ir satur pietiekami daudz aritmētikas (spēj reprezentēt veselu skaitļu pamatoperācijas un rekursīvās funkcijas, piemēram, tādās teorijās kā Peano aksiomas — PA);
• teorija ir konsekventa (tai nav pierādāmu pretrunu).

Ja šie nosacījumi izpildās, pirmā nepilnības teorēma apgalvo, ka eksistē konkrēts apgalvojums G, kas ir nepierādāms gan sistēmā, gan tās konsekvenču gadījumā arī tā nespēj pierādīt G nē. Otrā nepilnības teorēma apgalvo, ka tāda sistēma nevar pierādīt savu pašu konsekvenci (parasti izsakāmi kā: ja sistēma spēj izformulēt apgalvojumu „šī sistēma ir konsekventa”, tad, ja sistēma tomēr ir konsekventa, tai nav iespējams šo apgalvojumu pierādīt).

Pierādījuma ideja — intuīcija

Gēdela pamata tehnika bija syntakses enkodēšana skaitļos: jebkuram simbolam, teikumam un pierādījumam tiek piešķirts unikāls skaitlis — tā saucamais Gēdela numurs. Tas ļauj teicienus par simboliem un pierādījumiem izteikt kā aritmētiskus apgalvojumus par skaitļiem.

Izmantojot šo enkodēšanu, Gēdels konstruktē teikumu, kas faktiski saka: "Šis teikums nav pierādāms šajā sistēmā." Tas atgādina meliņa paradoksu, bet šeit tas ir formāls teikums ar skaitļu enkodējumu. Ja sistēma spētu to pierādīt, tā kļūtu nekonsekventa (jo teikums apgalvo, ka tas nav pierādāms); ja sistēma nevar to pierādīt, tad teikums ir patiesi, bet nepierādāmi — tātad sistēma ir nepilnīga. Rossera izlabojums vēlāk samazināja dažus tehniskos pieņēmumus, padarot prasības vājākas (piem., aizstājot ω‑konsekvenci ar vienkāršu konsekvenci).

Galvenās konsekvences un nozīme

• Hilberta programmas ierobežojums: Gēdela rezultāts praktiski nozīmē, ka Hilberta programma — ideja par pilnīgu, pilnīgi drošu aksiomatizāciju visai matemātikai — nav realizējama tādā formā, kā tika cerēts.
• Atšķirība starp patiesību un pierādāmību: teorija var būt konsekventa bet nepilnīga, tāpēc pastāv apgalvojumi, kas ir patiesi (attiecībā uz naturālo skaitļu modeli), bet nav pierādāmi noteiktajā aksiomu kopā.
• Ietekme uz loģiku un datoriķību: Gēdela idejas saista ar lēmumības (decidability) rezultātiem un ved uz tādiem rezultātiem kā Tjūringa apstāšanās problēmas nepārvaramība — daudzus matemātikas jautājumus nevar automatizēti atrisināt algorimiski.
• Neatkarības rezultāti: pēc Gēdela sekoja daudzi konkrēti piemēri neatkarīgiem apgalvojumiem (piem., Kontinuma hipotēmas neatkarība no ZF(ZFC)), parādot, ka nav tikai abstrakta eksistence — ir arī reāli svarīgi apgalvojumi, kuri nav pierādāmi no dotajām aksiomām.
• Filozofiskas sekas: Gēdela rezultāti ietekmēja diskusijas starp formalismu, platonismu un intuicionismu, liekot pārvērtēt uzskatus par to, ko nozīmē „matemātiskā patiesība”.

Praktiskais skats

Gēdela teorēmas nemazina matemātikas vērtību vai kārtību praksē — lielākā daļa matemātisko teoriju, kas tiek izmantotas zinātnē un inženierijā, ir pietiekami spēcīgas un drošas. Tomēr tās liecina, ka:

• nav iespējams ar vienu aksiomu kopu atrisināt visus matemātikas jautājumus;
• dažas problēmas būs neatkarīgas no izvēlētajām aksiomām, un šādās situācijās matemātiķiem jāizvēlas, vai pieņemt jaunas aksiomas;
• konsekvences pierādījumi par spēcīgām teorijām parasti prasa vēl spēcīgāku teoriju ārpus tās.

Papildus piezīmes un ierobežojumi

• Gēdela teorēmas neattiecas uz ļoti vājām teorijām, kas nespēj izteikt elementāru aritmētiku (tādās teorijās nepilnības konstrukcija var neizdoties).
• Gēdels neapgalvoja, ka konkrētas teorijas ir nekonsekventas — viņš pierādīja, ka, ja teorija ir konsekventa un pietiekami izteiksmīga, tā būs nepilnīga.
• Otrā teorēma ir tehniskāka: tā prasa, ka teorija spēj formāli izteikt pierādāmības predikātu; tas nozīmē, ka daudzas spēcīgas teorijas (piem., PA, ZF/ZFC) nevar pierādīt savu pašu konsekvenci, ja vien tās patiesi ir konsekventas.

Svarīgi piemēri

• Peano aritmētika (PA): klasisks piemērs teorijai, uz kuru attiecas Gēdela nepilnības teorēmas — PA ir konsekventa (pārliecinoši uzskatāma par tādu) un efektīvi aksiomatizējama, tāpēc tā ir nepilnīga.
• Zermelo–Fraenkel kopu teorija (ZFC): arī ZFC, kā spēcīgs aksiomātisks pamats lielākajai daļai matemātikas, ir Gēdela ierobežojuma pakļauta — jautājumi, kas ir neatkarīgi no ZFC, pastāv.

Gēdela nepilnības teorēmas ir viens no fundamentālajiem atklājumiem 20. gadsimta matemātikā. Tās neiznīcina matemātiku, taču parāda tās robežas un mudina rūpīgāk izprast, kas matemātisks pierādījums un matemātiska patiesība īsti nozīmē.

Jautājumi un atbildes

J: Kas ir Gēdela nepilnības teorēmas?

J: Kas ir pilnīga sistēma matemātikā?

J: Kas ir nepilnīga sistēma matemātikā?

J: Kas ir konsekventa sistēma matemātikā?

J: Kas ir aksiomas matemātikā?

J: Ko Gēdelis apgalvoja par katru netriviālu formālu sistēmu?

J: Kāpēc Gēdela nepilnības teorēmas ir svarīgas matemātiķiem?

Meklēt pēc burta