Filozofia e teoremës së paplotësisë së Gödel. Fakte interesante dhe këshilla të dobishme

Teorema e paplotesise se Gödel

Uspensky V.A.

Ndoshta teorema e paplotësisë së Gödel-it është vërtet unike. Është unike në atë që i referohet kur duan të provojnë "çdo gjë në botë" - nga prania e perëndive deri te mungesa e inteligjencës. Gjithmonë kam qenë i interesuar për një "pyetje primare" - cili nga ata që i referohen teoremës së paplotësisë jo vetëm që mund ta formulonte atë, por edhe ta vërtetonte? Po e botoj këtë artikull për arsye se ai paraqet një formulim plotësisht të arritshëm të teoremës së Gödel. Unë ju rekomandoj që së pari të lexoni artikullin e Tullio Regge Kurt Gödel dhe teoremën e tij të famshme

Përfundimi për pamundësinë e një kriteri universal të së vërtetës është pasojë e drejtpërdrejtë e rezultatit të marrë nga Tarski duke kombinuar teoremën e Gödel mbi pavendosmërinë me teorinë e tij të së vërtetës, sipas së cilës nuk mund të ketë një kriter universal të së vërtetës edhe për atë relativisht të ngushtë. fushën e teorisë së numrave, dhe për këtë arsye për çdo shkencë që përdor aritmetikën. Natyrisht, ky rezultat zbatohet një fortiori për konceptin e së vërtetës në çdo fushë jo-matematikore të njohurive në të cilën aritmetika përdoret gjerësisht.

Karl Popper

Uspensky Vladimir Andreevich lindi në 27 nëntor 1930 në Moskë. U diplomua në Fakultetin e Mekanikës dhe Matematikës të Universitetit Shtetëror të Moskës (1952). Doktor i Shkencave Fizike dhe Matematikore (1964). Profesor, Shef i Departamentit të Logjikës Matematikore dhe Teorisë së Algoritmeve, Fakulteti i Mekanikës dhe Matematikës (1966). Jep kurse leksionesh "Hyrje në logjikën matematikore", "Funksionet e llogaritshme", "Teorema e Gödel mbi plotësinë". Përgatitën 25 kandidatë dhe 2 doktorë shkencash

1. Deklarata e problemit

Teorema e paplotesise, formulimin e sakte te se ciles do ta japim ne fund te ketij kapitulli dhe ndoshta me vone (nese lexuesit i intereson kjo) dhe prova, thekson afersisht sa me poshte: ne kushte te caktuara ne cdo gjuhe ka te verteta por deklarata të paprovueshme.

Kur e formulojmë teoremën në këtë mënyrë, pothuajse çdo fjalë kërkon një shpjegim. Prandaj do të fillojmë duke shpjeguar kuptimin e fjalëve që përdorim në këtë formulim.

1.1. Gjuha

Ne nuk do të japim përkufizimin më të përgjithshëm të mundshëm të gjuhës, duke preferuar të kufizohemi në ato koncepte gjuhësore që do të na duhen më vonë. Ekzistojnë dy koncepte të tilla: "alfabeti i një gjuhe" dhe "bashkësia e pohimeve të vërteta të një gjuhe".

1.1.1. Alfabeti

Me alfabet nënkuptojmë një grup të kufizuar shenjash elementare (d.m.th., gjëra që nuk mund të ndahen në pjesët përbërëse të tyre). Këto shenja quhen shkronja të alfabetit. Me një fjalë të alfabetit nënkuptojmë një sekuencë të fundme shkronjash. Për shembull, fjalët e zakonshme në anglisht (përfshirë emrat e duhur) janë fjalë të alfabetit me 54 shkronja (26 shkronja të vogla, 26 shkronja të mëdha, një vizë dhe një apostrof). Një shembull tjetër është se numrat natyrorë në shënimet dhjetore janë fjalë të një alfabeti me 10 shkronja, shkronjat e të cilit janë shenja: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Për të treguar alfabetet, ne do të përdorim shkronja të zakonshme të mëdha. Nëse L është një alfabet, atëherë L? do të shënojë grupin e të gjitha fjalëve të alfabetit L - fjalë të formuara nga shkronjat e tij. Do të supozojmë se çdo gjuhë ka alfabetin e vet, kështu që të gjitha shprehjet e kësaj gjuhe (d.m.th. - emrat e objekteve të ndryshme, deklaratat në lidhje me këto objekte, etj.) janë fjalë të këtij alfabeti. Për shembull, çdo fjali në anglisht, si dhe çdo tekst i shkruar në anglisht, mund të konsiderohet një fjalë në një alfabet të zgjeruar prej 54 shkronjash, i cili përfshin gjithashtu shenja pikësimi, hapësirën e ndërfjalës, një shenjë të vijës së kuqe dhe ndoshta disa karaktere të tjera të dobishme. . Duke supozuar se shprehjet e gjuhës janë fjalë të ndonjë alfabeti, ne kështu përjashtojmë nga shqyrtimi shprehjet "shumështresore" si ???f(x)dx. Megjithatë, ky kufizim nuk është shumë domethënës, pasi çdo shprehje e tillë, duke përdorur konventa të përshtatshme, mund të "shtrihet" në një formë lineare. Ndonjë grup M i përfshirë në L? quhet një grup fjalësh i alfabetit L. Nëse themi thjesht se M është një grup fjalësh, atëherë nënkuptojmë se është një fjalë e ndonjë alfabeti. Tani supozimi i mësipërm për gjuhën mund të riformulohet si vijon: në çdo gjuhë, çdo grup shprehjesh është një grup fjalësh.

1.1.2. Shumë deklarata të vërteta

Supozojmë se na është dhënë një nënbashkësi T e bashkësisë L? (ku L është alfabeti i një gjuhe që po shqyrtojmë), i cili quhet grupi i "thënieve të vërteta" (ose thjesht "të vërtetat"). Duke lëvizur drejtpërdrejt në nëngrupin T, ne lëmë hapat e mëposhtëm të ndërmjetëm të arsyetimit: së pari, cilat fjalë të alfabetit L janë shprehje të formuara saktë të gjuhës, domethënë kanë një kuptim të caktuar në interpretimin tonë të kësaj gjuhe (për shembull, 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 janë shprehje të mirëformuara, ndërsa shprehjet si +=x jo); së dyti, cilat shprehje janë formula, d.m.th. mund të varet nga parametri (për shembull, x=3, x=y, 2=3, 2=2); së treti, cilat nga formulat janë formula të mbyllura, d.m.th. deklarata që nuk varen nga parametrat (për shembull, 2=3, 2=2); dhe së fundi, cilat formula të mbyllura janë pohime të vërteta (për shembull, 2=2).

1.1.3. Çifti themelor i gjuhës

1.2. "E paprovueshme"

“E paprovueshme” do të thotë pa prova.

1.3. Dëshmi

Megjithëse termi "provë" është ndoshta një nga më të rëndësishmit në matematikë (Bourbakis e fillojnë librin e tyre "Themelet e Matematikës" me fjalët: "Që nga koha e grekëve të lashtë, të thuash "matematikë" do të thoshte njësoj si të thuaj 'provë'"), nuk ka përkufizimin e vet të saktë. Në përgjithësi, koncepti i provës me të gjitha degët e tij semantike i përket më tepër fushës së psikologjisë sesa matematikës. Por sido që të jetë, prova është thjesht një argument që neve na duket mjaft bindës për të bindur të gjithë të tjerët.

Pasi të shkruhet, një provë bëhet fjalë në ndonjë alfabet P, ashtu si çdo tekst në anglisht është një fjalë në alfabetin L, një shembull i së cilës u dha më sipër. Bashkësia e të gjitha provave formon një nënbashkësi (dhe një nëngrup mjaft të gjerë) të grupit P?. Ne nuk do të përpiqemi të japim një përkufizim të saktë të këtij koncepti njëkohësisht "naiv" dhe "absolut" të provës, ose - çfarë është ekuivalente - të japim një përkufizim të nëngrupit përkatës të P?. Në vend të kësaj, ne do të shqyrtojmë një analog formal të këtij koncepti të paqartë, për të cilin në të ardhmen do të përdorim ende termin "provë". Ky analog ka dy veçori shumë të rëndësishme që e dallojnë atë nga koncepti intuitiv (edhe pse ideja intuitive e provës ende i pasqyron këto veçori në një farë mase). Para së gjithash, ne do të pranojmë se ekzistojnë koncepte të ndryshme të provës, domethënë, nëngrupe të ndryshme provash në P janë të pranueshme, madje edhe më shumë se kaq: ne, në fakt, do të pranojmë se vetë alfabeti i provave P mund të ndryshojë? . Më tej do të kërkojmë që për çdo koncept të tillë të provës të ekzistojë një metodë efikase, me fjalë të tjera, një algoritëm, i cili do të përcaktonte domosdoshmërisht nëse një fjalë e dhënë e alfabetit P është një provë apo jo. Ne gjithashtu do të supozojmë se ekziston një algoritëm që gjithmonë mund të përcaktojë se cilin pohim vërteton një provë e dhënë. (Në shumë situata, pohimi që provohet është thjesht pohimi i fundit në sekuencën e hapave që përbën provën.)

Kështu, përkufizimi ynë përfundimtar është si më poshtë:

(1) Kemi një alfabet L (alfabet i gjuhës) dhe një alfabet P (alfabet vërtetues).

(2) Na jepet një bashkësi P, e cila është një nëngrup i P?, dhe elementët e së cilës quhen "prova". Në të ardhmen, do të supozojmë se kemi gjithashtu një algoritëm që na lejon të përcaktojmë nëse një fjalë arbitrare e alfabetit P është një element i grupit P, domethënë një provë, apo jo.

(3) Gjithashtu a kemi një funksion? (për të gjetur se çfarë është vërtetuar saktësisht), domeni i cilës përkufizim? plotëson kushtin P???P?, dhe diapazoni i vlerave të të cilit është në P?. Supozojmë se kemi një algoritëm që llogarit këtë funksion (kuptimi i saktë i fjalëve "një algoritëm llogarit një funksion" është: vlerat e funksionit merren duke përdorur këtë algoritëm - një grup rregullash të veçanta transformimi). Do të themi se elementi p? P është një provë e fjalës?(p) e alfabetit L.

Trojka<Р, Р, ?>, kushtet e kënaqshme (1)-(3) quhet një sistem deduktiv mbi alfabetin L.

Për lexuesin e njohur me mënyrën e zakonshme të përcaktimit të "provës" në termat e "aksiomës" dhe "rregullit të konkluzionit", tani do të shpjegojmë se si kjo metodë mund të konsiderohet si një rast i veçantë i përkufizimit të dhënë në seksionin 1.3.2. Kjo do të thotë, një provë zakonisht përkufizohet si një sekuencë e shprehjeve të tilla gjuhësore, secila prej të cilave është ose një aksiomë ose e marrë më parë nga deklaratat tashmë ekzistuese duke përdorur një nga rregullat e konkluzionit. Nëse shtojmë një fjalë të re * në alfabetin e gjuhës sonë, atëherë mund të shkruajmë një provë të tillë në formën e një fjale të kompozuar duke përdorur modifikimin e alfabetit që rezulton: sekuenca e shprehjeve bëhet fjala C1*C2*...*Cn . Në këtë rast, funksioni që përcakton se çfarë saktësisht është vërtetuar ka kuptimin e tij në pjesën e kësaj fjale menjëherë pas shkronjës së fundit * në sekuencë. Një algoritëm ekzistenca e të cilit kërkohet në pjesën 1.3.2. përkufizimi, mund të ndërtohet lehtësisht pasi të kemi përcaktuar saktësisht ndonjë nga kuptimet e pranuara të fjalëve "aksiomë" dhe "rregullat e përfundimit".

1.4 Përpjekjet për të formuluar me saktësi teoremën e paplotësimit

1.4.1. Së pari provoni

“Në kushte të caktuara për çiftin themelor të gjuhës alfabetike L dhe sistemin deduktiv<Р, Р, ?>mbi L - ka gjithmonë një fjalë në T që nuk ka prova." Ky opsion duket ende i paqartë. Në veçanti, ne mund të dalim lehtësisht me çdo numër sistemesh deduktive që kanë shumë pak fjalë të provueshme. Për shembull, në deduktivin bosh sistemi (ku P = ?) nuk ka fare fjalë që të kenë prova.

1.4.2. Prova e dytë

Ekziston një qasje tjetër, më e natyrshme. Supozoni se na është dhënë një gjuhë - në kuptimin që na jepet një çift themelor i kësaj gjuhe. Tani do të kërkojmë një sistem të tillë deduktiv mbi L (në mënyrë intuitive, ne po kërkojmë një teknikë vërtetimi) me ndihmën e së cilës mund të vërtetojmë sa më shumë fjalë nga T, në kufirin e të gjitha fjalëve nga teorema e T. Gödel përshkruan situatë në të cilën një sistem i tillë deduktiv (me anë të të cilit çdo fjalë në T do të ishte e vërtetueshme) nuk ekziston. Kështu, ne dëshirojmë të formulojmë deklaratën e mëposhtme:

"Në kushte të caktuara në lidhje me çiftin themelor, nuk ekziston një sistem deduktiv në të cilin çdo fjalë nga T ka një provë."

Sidoqoftë, një deklaratë e tillë është padyshim e rreme, pasi është e nevojshme vetëm të merret një sistem deduktiv në të cilin P = L, P = P? u?(p) = p për të gjitha p nga P?; pastaj çdo fjalë nga L? është i parëndësishëm i vërtetueshëm. Prandaj, ne duhet të pranojmë disa kufizime se cilat sisteme deduktive përdorim.

1.5. Konsistenca

Do të ishte krejt e natyrshme të kërkohej që të vërtetohen vetëm "thëniet e vërteta", pra vetëm fjalët nga T. Do të themi se sistemi deduktiv<Р, Р, ?>është konsistente në lidhje me çiftin themelor nëse?(P)?T. Në të gjitha diskutimet e mëvonshme do të jemi të interesuar vetëm për sisteme të tilla deduktive konsistente. Nëse na jepet një gjuhë, atëherë do të ishte jashtëzakonisht joshëse të gjejmë një sistem deduktiv të qëndrueshëm në të cilin çdo deklaratë e vërtetë do të kishte një provë. Versioni i teoremës së Gödel-it që na intereson pohon saktësisht se në kushte të caktuara në lidhje me çiftin themelor, është e pamundur të gjendet një sistem i tillë deduktiv.

1.6. Plotësia

Thuhet se sistemi deduktiv<Р,Р,?>është i plotë në lidhje me çiftin themelor, me kusht që?(P)?T. Atëherë formulimi ynë i teoremës së paplotësisë merr formën e mëposhtme:

Në kushte të caktuara në lidhje me çiftin themelor, nuk ekziston një sistem i tillë deduktiv<Р,Р,?>mbi L, i cili do të ishte i plotë dhe relativisht i qëndrueshëm.

Referencat

Për të përgatitur këtë punë, u përdorën materiale nga faqja http://filosof.historic.ru

Një nga teoremat më të famshme në logjikën matematikore është fat dhe pafat në të njëjtën kohë. Në këtë është e ngjashme me teorinë speciale të relativitetit të Ajnshtajnit. Nga njëra anë, pothuajse të gjithë kanë dëgjuar diçka për ta. Nga ana tjetër, në interpretimin popullor, teoria e Ajnshtajnit, siç dihet, "Thotë se gjithçka në botë është relative". Dhe teorema e Gödel-it mbi paplotësinë (në tekstin e mëtejmë thjesht TGN), afërsisht në të njëjtin formulim të lirë popullor, "dëshmon se ka gjëra të pakuptueshme për mendjen njerëzore". Dhe kështu disa përpiqen ta përshtatin atë si një argument kundër materializmit, ndërsa të tjerët, përkundrazi, vërtetojnë me ndihmën e tij se nuk ka Zot. Gjëja qesharake nuk është vetëm se të dyja palët nuk mund të kenë të drejtë në të njëjtën kohë, por edhe se asnjëra dhe as tjetra nuk shqetësohen të kuptojnë se çfarë thotë në të vërtetë kjo teoremë.

Pra, çfarë? Më poshtë do të përpiqem t'ju tregoj për të "në gishta". Prezantimi im, natyrisht, do të jetë jo rigoroz dhe intuitiv, por do t'u kërkoj matematikanëve të mos më gjykojnë rreptësisht. Është e mundur që për jo-matematicienët (nga të cilët, në fakt, unë jam një), do të ketë diçka të re dhe të dobishme në atë që përshkruhet më poshtë.

Logjika matematikore është me të vërtetë një shkencë mjaft komplekse, dhe më e rëndësishmja, jo shumë e njohur. Kërkon manovra të kujdesshme dhe strikte, në të cilat është e rëndësishme të mos ngatërrohet ajo që është vërtetuar në të vërtetë me atë që është "tashmë e qartë". Megjithatë, shpresoj që për të kuptuar "përvijimin e një prove të TGN" në vijim lexuesit do t'i nevojiten vetëm njohuri të matematikës/shkencës kompjuterike të shkollës së mesme, aftësi të të menduarit logjik dhe 15-20 minuta kohë.

Duke e thjeshtuar disi, TGN pohon se në gjuhë mjaft komplekse ka deklarata të paprovueshme. Por në këtë frazë pothuajse çdo fjalë ka nevojë për shpjegim.

Le të fillojmë duke u përpjekur të kuptojmë se çfarë është një provë. Le të marrim një problem aritmetik shkollor. Për shembull, supozoni se duhet të provoni korrektësinë e formulës së mëposhtme të thjeshtë: " " (më lejoni t'ju kujtoj se simboli lexon "për cilindo" dhe quhet "kuantifikues universal"). Ju mund ta vërtetoni atë duke e transformuar në mënyrë identike, të themi, si kjo:

Kalimi nga një formulë në tjetrën ndodh sipas disa rregullave të njohura. Kalimi nga formula e 4-të në të 5-tën ndodhi, le të themi, sepse çdo numër është i barabartë me vetveten - kjo është një aksiomë e aritmetikës. Dhe e gjithë procedura e provës, kështu, e përkthen formulën në vlerën Boolean TRUE. Rezultati mund të jetë gjithashtu një gënjeshtër - nëse do të hedhim poshtë ndonjë formulë. Në këtë rast, ne do të vërtetonim mohimin e saj. Mund të imagjinohet një program (dhe programe të tilla në fakt janë shkruar) që do të provonte deklarata të ngjashme (dhe më komplekse) pa ndërhyrjen njerëzore.

Le të themi të njëjtën gjë pak më formalisht. Supozoni se kemi një grup të përbërë nga vargje karakteresh të ndonjë alfabeti, dhe ka rregulla me të cilat nga këto vargje mund të zgjedhim një nëngrup të të ashtuquajturave deklaratat- domethënë fraza me kuptim gramatikor, secila prej të cilave është e vërtetë ose e rreme. Mund të themi se ekziston një funksion që lidh deklaratat me njërën nga dy vlerat: TRUE ose FALSE (d.m.th., duke i paraqitur ato në një grup Boolean prej dy elementësh).

Le ta quajmë një çift të tillë - një grup deklaratash dhe një funksion nga në - "gjuha e deklaratave". Vini re se në kuptimin e përditshëm koncepti i gjuhës është disi më i gjerë. Për shembull, fraza ruse "Ejani këtu!" as e vërtetë as e rreme, pra nga pikëpamja e logjikës matematikore nuk është pohim.

Për sa vijon, ne kemi nevojë për konceptin e një algoritmi. Unë nuk do të jap një përkufizim zyrtar të tij këtu - kjo do të na çonte shumë larg. Unë do të kufizohem në informale: "algoritmi"është një sekuencë udhëzimesh të paqarta (“program”) që në një numër të kufizuar hapash konverton të dhënat burimore në rezultate. Ajo që është në kursive është thelbësisht e rëndësishme - nëse programi lidhet me disa të dhëna fillestare, atëherë ai nuk e përshkruan algoritmin. Për thjeshtësi dhe zbatim në rastin tonë, lexuesi mund të konsiderojë se një algoritëm është një program i shkruar në çdo gjuhë programimi të njohur për të, i cili, për çdo të dhënë hyrëse nga një klasë e caktuar, është e garantuar të përfundojë punën e tij duke prodhuar një rezultat Boolean.

Le të pyesim veten: për çdo funksion ekziston një "algoritëm vërtetues" (ose shkurtimisht, "deduktive"), ekuivalente me këtë funksion, domethënë, duke e transformuar çdo deklaratë në të njëjtën vlerë Boolean si ajo? E njëjta pyetje mund të formulohet më shkurt si më poshtë: është çdo funksion mbi një grup pohimesh të llogaritshme? Siç e keni marrë me mend tashmë, nga vlefshmëria e TGN rrjedh se jo, jo çdo funksion - ka funksione të pallogaritshme të këtij lloji. Me fjalë të tjera, jo çdo deklaratë e vërtetë mund të provohet.

Ka shumë mundësi që kjo deklaratë të shkaktojë një protestë të brendshme tek ju. Kjo është për shkak të disa rrethanave. Së pari, kur na mësohet matematika shkollore, ndonjëherë kemi përshtypjen e gabuar se frazat "teorema është e vërtetë" dhe "teorema mund të vërtetohet ose verifikohet" janë pothuajse plotësisht identike. Por, nëse mendoni për këtë, kjo nuk është aspak e qartë. Disa teorema vërtetohen mjaft thjesht (për shembull, duke provuar një numër të vogël opsionesh), ndërsa të tjerat janë shumë të vështira. Merrni, për shembull, teoremën e famshme të fundit të Fermatit:

prova e së cilës u gjet vetëm tre shekuj e gjysmë pas formulimit të parë (dhe është larg të qenit elementar). Është e nevojshme të bëhet dallimi midis vërtetësisë së një deklarate dhe vërtetueshmërisë së tij. Nga askund nuk rezulton se nuk ka deklarata të vërteta, por të paprovueshme (dhe jo plotësisht të verifikueshme).

Argumenti i dytë intuitiv kundër TGN është më delikate. Le të themi se kemi një deklaratë të paprovueshme (në kuadër të kësaj deduktive). Çfarë na pengon ta pranojmë atë si një aksiomë të re? Kështu, ne do ta komplikojmë pak sistemin tonë të provave, por kjo nuk është e frikshme. Ky argument do të ishte plotësisht i saktë nëse do të kishte një numër të kufizuar pohimesh të paprovueshme. Në praktikë, mund të ndodhë sa vijon: pasi të postulosh një aksiomë të re, ndeshesh me një deklaratë të re të paprovueshme. Nëse e pranoni si një aksiomë tjetër, do të pengoheni te e treta. Dhe kështu me radhë ad infinitum. Ata thonë se zbritja do të mbetet jo të plota. Ne gjithashtu mund ta detyrojmë algoritmin e vërtetimit të përfundojë në një numër të caktuar hapash me një rezultat për çdo shqiptim të gjuhës. Por në të njëjtën kohë, ai do të fillojë të gënjejë - duke çuar në të vërtetën për deklarata të pasakta, ose në një gënjeshtër - për besimtarët. Në raste të tilla thonë se zbritja kontradiktore. Kështu, një formulim tjetër i TGN tingëllon kështu: "Ka gjuhë propozicionale për të cilat deduktiviteti i plotë i qëndrueshëm është i pamundur" - prandaj emri i teoremës.

Nganjëherë quhet "teorema e Gödel", pohimi është se çdo teori përmban probleme që nuk mund të zgjidhen brenda vetë teorisë dhe kërkojnë përgjithësimin e saj. Në një farë kuptimi kjo është e vërtetë, megjithëse ky formulim tenton të errësojë çështjen në vend që ta sqarojë atë.

Do të vërej gjithashtu se nëse do të flisnim për funksione të njohura që hartojnë një grup numrash realë në të, atëherë "mosllogaritshmëria" e funksionit nuk do të befasonte askënd (thjesht mos ngatërroni "funksionet e llogaritshme" dhe "numrat e llogaritshëm" ” - këto janë gjëra të ndryshme). Çdo nxënës shkolle e di që, le të themi, në rastin e një funksioni, duhet të kesh shumë fat me argumentin, në mënyrë që procesi i llogaritjes së paraqitjes së saktë dhjetore të vlerës së këtij funksioni të përfundojë në një numër të kufizuar hapash. Por ka shumë të ngjarë që ju do ta llogaritni atë duke përdorur një seri të pafundme, dhe kjo llogaritje nuk do të çojë kurrë në një rezultat të saktë, megjithëse mund të afrohet sa të doni - thjesht sepse vlera e sinusit të shumicës së argumenteve është irracionale. TGN thjesht na tregon se edhe midis funksioneve, argumentet e të cilëve janë vargje dhe vlerat e të cilave janë zero ose një, ka edhe funksione jo të llogaritshme, megjithëse ato janë të strukturuara në një mënyrë krejtësisht të ndryshme.

Për qëllime të mëtejshme, ne do të përshkruajmë "gjuhën e aritmetikës formale". Konsideroni një klasë vargjesh teksti me gjatësi të kufizuar, të përbërë nga numra arabë, variabla (gërma të alfabetit latin) që marrin vlera natyrore, hapësira, shenja aritmetike, barazi dhe pabarazi, kuantifikues ("ekziston") dhe ("për çdo") dhe , ndoshta , disa simbole të tjera (numri dhe përbërja e tyre e saktë janë të parëndësishme për ne). Është e qartë se jo të gjitha rreshtat e tillë janë kuptimplotë (për shembull, " " është e pakuptimtë). Nëngrupi i shprehjeve kuptimplote nga kjo klasë (d.m.th., vargjet që janë të vërteta ose të rreme nga pikëpamja e aritmetikës së zakonshme) do të jetë grupi ynë i pohimeve.

Shembuj të deklaratave aritmetike formale:

etj. Tani le të quajmë një "formulë me një parametër të lirë" (FSP) një varg që bëhet një deklaratë nëse një numër natyror zëvendësohet në të si ky parametër. Shembuj të FSP (me parametër):

etj. Me fjalë të tjera, FSP-të janë ekuivalente me funksionet e argumentit natyror me vlera Boolean.

Le të shënojmë grupin e të gjitha FSP-ve me shkronjën . Është e qartë se mund të renditet (për shembull, fillimisht shkruajmë formulat me një shkronja të renditura sipas alfabetit, të ndjekura nga formulat me dy shkronja etj.; për ne nuk është e rëndësishme se në cilin alfabet do të bëhet renditja). Kështu, çdo FSP korrespondon me numrin e tij në listën e renditur, dhe ne do ta shënojmë atë.

Le të kalojmë tani në një skicë të provës së TGN në formulimin e mëposhtëm:

Për gjuhën propozicionale të aritmetikës formale nuk ka një sistem të plotë deduktiv të qëndrueshëm.

Do ta vërtetojmë me kontradiktë.

Pra, le të supozojmë se ekziston një sistem i tillë deduktiv. Le të përshkruajmë algoritmin e mëposhtëm ndihmës, i cili i cakton një vlerë Boolean një numri natyror si më poshtë:

E thënë thjesht, algoritmi rezulton në vlerën TRUE nëse dhe vetëm nëse rezultati i zëvendësimit të numrit të tij në FSP në listën tonë jep një deklaratë të rreme.

Këtu kemi ardhur në të vetmin vend ku do t'i kërkoj lexuesit të mbajë fjalën time për këtë.

Është e qartë se, sipas supozimit të bërë më sipër, çdo FSP mund të krahasohet me një algoritëm që përmban një numër natyror në hyrje dhe një vlerë Boolean në dalje. E kundërta është më pak e dukshme:

Vërtetimi i kësaj leme do të kërkonte, së paku, një përkufizim formal dhe jo intuitiv të konceptit të një algoritmi. Megjithatë, nëse e mendoni pak, është mjaft e besueshme. Në fakt, algoritmet janë shkruar në gjuhë algoritmike, ndër të cilat ka të tilla ekzotike si, për shembull, Brainfuck, i përbërë nga tetë fjalë me një karakter, në të cilat, megjithatë, mund të zbatohet çdo algoritëm. Do të ishte e çuditshme nëse gjuha më e pasur e formulave të aritmetikës formale që përshkruam do të ishte më e varfër - megjithëse, pa dyshim, nuk është shumë e përshtatshme për programim të zakonshëm.

Pasi kaluam këtë vend të rrëshqitshëm, arrijmë shpejt në fund.

Pra, më lart përshkruam algoritmin. Sipas lemës që ju kërkova të besoni, ekziston një FSP ekuivalente. Ka një numër në listë - le të themi, . Le të pyesim veten, me çfarë është e barabartë? Le të jetë kjo E VËRTETA. Pastaj, sipas konstruksionit të algoritmit (dhe rrjedhimisht funksionit ekuivalent me të), kjo do të thotë se rezultati i zëvendësimit të një numri në funksion është FALSE. E kundërta kontrollohet në të njëjtën mënyrë: nga FALSE vijon TRUE. Kemi arritur në një kontradiktë, që do të thotë se supozimi fillestar është i pasaktë. Kështu, nuk ka një sistem të plotë deduktiv të qëndrueshëm për aritmetikën formale. Q.E.D.

Këtu është me vend të kujtojmë Epimenidin (shih portretin në titull), i cili, siç dihet, deklaroi se të gjithë Kretasit janë gënjeshtarë, duke qenë vetë Kretan. Në një formulim më të përmbledhur, deklarata e tij (e njohur si "paradoksi i gënjeshtarit") mund të thuhet si më poshtë: "Po gënjej". Pikërisht këtë lloj deklarate, që vetë shpall falsitetin e saj, ne përdorëm për provë.

Si përfundim, dua të vërej se TGN nuk pretendon asgjë veçanërisht befasuese. Në fund të fundit, të gjithë janë mësuar prej kohësh me faktin se jo të gjithë numrat mund të përfaqësohen si një raport prej dy numrash të plotë (mos harroni, kjo deklaratë ka një provë shumë elegante që është më shumë se dy mijë vjet e vjetër?). Dhe jo të gjithë numrat janë rrënjë polinomesh me koeficientë racionalë. Dhe tani rezulton se jo të gjitha funksionet e një argumenti natyror janë të llogaritshëm.

Skica e provës së dhënë ishte për aritmetikën formale, por është e lehtë të shihet se TGN është e zbatueshme për shumë gjuhë të tjera propozicionale. Sigurisht, jo të gjitha gjuhët janë të tilla. Për shembull, le të përcaktojmë një gjuhë si më poshtë:

"Çdo frazë në gjuhën kineze është një deklaratë e vërtetë nëse gjendet në librin e citimeve të shokut Mao Ce Dun dhe e pasaktë nëse nuk përmbahet."

Pastaj algoritmi përkatës i plotë dhe i qëndrueshëm i vërtetimit (dikush mund ta quajë atë "deduktiv dogmatik") duket diçka si kjo:

“Shfletoni librin e citimeve të shokut Mao Ce Dun derisa të gjeni thënien që po kërkoni. Nëse gjendet, atëherë është e vërtetë, por nëse libri i citateve ka mbaruar dhe deklarata nuk gjendet, atëherë është e pasaktë.”

Ajo që na shpëton këtu është se çdo libër citate është padyshim i fundëm, kështu që procesi i "provës" do të përfundojë në mënyrë të pashmangshme. Kështu, TGN nuk është e zbatueshme për gjuhën e deklaratave dogmatike. Por ne po flisnim për gjuhë komplekse, apo jo?

Çdo sistem aksiomash matematikore, duke filluar nga një nivel i caktuar kompleksiteti, është ose kontradiktor i brendshëm ose i paplotë.

Në vitin 1900, në Paris u mbajt Konferenca Botërore e Matematikanëve, në të cilën David Hilbert (1862–1943) paraqiti në formën e tezave 23 problemet më të rëndësishme, sipas mendimit të tij, që teoricienët e shekullit të XX-të që po vinte duhej të zgjidhnin. Numri dy në listën e tij ishte një nga ato probleme të thjeshta, përgjigja e të cilave duket e qartë derisa të gërmoni pak më thellë. Në terma moderne, kjo ishte pyetja: a është matematika e vetë-mjaftueshme? Detyra e dytë e Hilbertit përbëhej nga nevoja për të vërtetuar rreptësisht se sistemi i aksiomave - pohime themelore të pranuara në matematikë si bazë pa prova - është i përsosur dhe i plotë, domethënë, ai lejon që dikush të përshkruajë matematikisht gjithçka që ekziston. Ishte e nevojshme të vërtetohej se ishte e mundur të përcaktohej një sistem i tillë aksiomash që ato, së pari, të ishin të qëndrueshme reciproke, dhe së dyti, prej tyre mund të nxirret një përfundim në lidhje me vërtetësinë ose falsitetin e çdo deklarate.

Le të marrim një shembull nga gjeometria e shkollës. Në planimetrinë standarde Euklidiane (gjeometria në një plan), mund të vërtetohet pa dyshim se pohimi "shuma e këndeve të një trekëndëshi është 180°" është i vërtetë, dhe pohimi "shuma e këndeve të një trekëndëshi është 137". °” është e rreme. Duke folur në thelb, në gjeometrinë Euklidiane çdo deklaratë është ose e rreme ose e vërtetë, dhe nuk ka asnjë opsion të tretë. Dhe në fillim të shekullit të njëzetë, matematikanët besonin me naivitet se e njëjta situatë duhet të vëzhgohej në çdo sistem logjikisht të qëndrueshëm.

Dhe më pas, në vitin 1931, një matematikan vjenez me syze Kurt Gödel botoi një artikull të shkurtër që thjesht tronditi të gjithë botën e të ashtuquajturës "logjikë matematikore". Pas preambulave të gjata dhe komplekse matematikore dhe teorike, ai vendosi fjalë për fjalë sa vijon. Le të marrim çdo deklaratë si: "Supozimi nr. 247 në këtë sistem aksiomash është logjikisht i paprovueshëm" dhe ta quajmë atë "pohim A". Pra, Gödel thjesht vërtetoi vetinë e mahnitshme të mëposhtme të çdo sistemi aksiomash:

"Nëse pohimi A mund të provohet, atëherë deklarata jo-A mund të provohet."

Me fjalë të tjera, nëse mund të vërtetohet vlefshmëria e pohimit “Supozimi 247 është i paprovueshëm”, atëherë mund të vërtetohet edhe vlefshmëria e pohimit “Supozimi 247 është i provueshëm”. Kjo do të thotë, duke u kthyer në formulimin e problemit të dytë të Hilbertit, nëse një sistem aksiomash është i plotë (d.m.th., çdo deklaratë në të mund të vërtetohet), atëherë është kontradiktore.

E vetmja rrugëdalje nga kjo situatë është pranimi i një sistemi jo të plotë aksiomash. Kjo do të thotë, ne duhet të durojmë faktin se në kontekstin e çdo sistemi logjik do të kemi ende pohime të tipit A që janë dukshëm të vërteta ose të rreme - dhe të vërtetën e tyre mund ta gjykojmë vetëm jashtë kornizës së aksiomatikës që kemi. pranuar. Nëse nuk ka pohime të tilla, atëherë aksiomatika jonë është kontradiktore dhe në kuadrin e saj do të ketë pashmangshmërisht formulime që mund të vërtetohen dhe të kundërshtohen.

Pra, formulimi i teoremës së parë, ose të dobët, të paplotësisë së Gödel: "Çdo sistem formal aksiomash përmban supozime të pazgjidhura." Por Gödel nuk u ndal me kaq, duke formuluar dhe vërtetuar teoremën e dytë, ose të fortë, të paplotësisë së Gödel-it: “Plotësia (ose paplotësia) logjike e çdo sistemi aksiomash nuk mund të vërtetohet brenda kornizës së këtij sistemi. Për ta vërtetuar ose hedhur poshtë, kërkohen aksioma shtesë (forcimi i sistemit).

Do të ishte më e sigurt të mendohej se teoremat e Gödel janë abstrakte në natyrë dhe nuk na shqetësojnë ne, por vetëm fusha të logjikës sublime matematikore, por në fakt doli se ato lidhen drejtpërdrejt me strukturën e trurit të njeriut. Matematikani dhe fizikani anglez Roger Penrose (l. 1931) tregoi se teoremat e Gödel-it mund të përdoren për të vërtetuar ekzistencën e dallimeve themelore midis trurit të njeriut dhe një kompjuteri. Kuptimi i arsyetimit të tij është i thjeshtë. Kompjuteri vepron në mënyrë strikte logjike dhe nuk është në gjendje të përcaktojë nëse pohimi A është i vërtetë apo i rremë nëse shkon përtej aksiomatikës, dhe deklarata të tilla, sipas teoremës së Gödel, ekzistojnë në mënyrë të pashmangshme. Një person, i përballur me një deklaratë të tillë logjikisht të paprovueshme dhe të pakundërshtueshme A, është gjithmonë në gjendje të përcaktojë të vërtetën ose falsitetin e saj - bazuar në përvojën e përditshme. Të paktën në këtë aspekt truri i njeriut është superior ndaj një kompjuteri të kufizuar nga qarqe të pastra logjike. Truri i njeriut është i aftë të kuptojë thellësinë e plotë të së vërtetës që përmban teoremat e Gödel-it, por truri kompjuterik nuk mundet kurrë. Prandaj, truri i njeriut është gjithçka tjetër veçse një kompjuter. Ai është i aftë të marrë vendime dhe do të kalojë testin Turing.

Pyes veten nëse Hilberti kishte ndonjë ide se sa larg do të na çonin pyetjet e tij?

Kurt GÖDEL
Kurt Godel, 1906–78

Matematikan austriak, më pas amerikan. Lindur në Brünn (tani Brno, Republika Çeke). U diplomua në Universitetin e Vjenës, ku mbeti mësues në departamentin e matematikës (që nga viti 1930 - profesor). Në vitin 1931 ai botoi një teoremë që më vonë mori emrin e tij. Duke qenë një person thjesht apolitik, ai e kaloi një kohë jashtëzakonisht të vështirë me vrasjen e shokut dhe kolegut të tij nga një student nazist dhe ra në një depresion të thellë, rikthimet e të cilit e ndoqën atë gjatë gjithë jetës së tij. Në vitet 1930 emigroi në SHBA, por u kthye në vendlindjen e tij në Austri dhe u martua. Në vitin 1940, në kulmin e luftës, ai u detyrua të ikte në Amerikë me tranzit përmes BRSS dhe Japonisë. Ai punoi për disa kohë në Institutin për Studime të Avancuara në Princeton. Fatkeqësisht, psikika e shkencëtarit nuk mund ta duronte dhe ai vdiq në një klinikë psikiatrike nga uria, duke refuzuar të hante, sepse ishte i bindur se do ta helmonin.

Komentet: 0

Si zhvillohet një model shkencor në shkencat natyrore? Përvoja e përditshme ose shkencore është akumuluar, piketa e saj formulohen me kujdes në formën e postulateve dhe përbëjnë bazën e modelit: një grup pohimesh të pranuara nga të gjithë ata që punojnë në kuadrin e këtij modeli.

Anatoly Wasserman

Në vitin 1930, Kurt Gödel vërtetoi dy teorema që, të përkthyera nga gjuha matematikore në gjuhën njerëzore, do të thotë afërsisht sa vijon: Çdo sistem aksiomash mjaft i pasur për t'u përdorur për të përcaktuar aritmetikën do të jetë ose i paplotë ose kontradiktor. Jo një sistem i plotë - kjo do të thotë se në sistem mund të formulohet një deklaratë, e cila me anë të këtij sistemi nuk mund të provohet dhe as të hidhet poshtë. Por Zoti, sipas përkufizimit, është shkaku përfundimtar i të gjitha shkaqeve. Nga pikëpamja e matematikës, kjo do të thotë se futja e aksiomës për Zotin e bën të plotë aksiomatikën tonë. Nëse ekziston një Zot, atëherë çdo deklaratë ose mund të provohet ose të kundërshtohet, duke iu referuar, në një mënyrë ose në një tjetër, Zotit. Por sipas Gödel, sistemi i plotë i aksiomave është në mënyrë të pashmangshme kontradiktor. Kjo do të thotë, nëse besojmë se Zoti ekziston, atëherë jemi të detyruar të arrijmë në përfundimin se kontradiktat janë të mundshme në natyrë. Dhe duke qenë se nuk ka kontradikta, përndryshe e gjithë bota jonë do të shkërmoqej nga këto kontradikta, ne duhet të arrijmë në përfundimin se ekzistenca e Zotit është e papajtueshme me ekzistencën e natyrës.

Sosinsky A.B.

Teorema e Gödel, së bashku me zbulimet e relativitetit, mekanikës kuantike dhe ADN-së, konsiderohet përgjithësisht si arritja më e madhe shkencore e shekullit të 20-të. Pse? Cili është thelbi i tij? Cila është rëndësia e saj? Këto pyetje janë adresuar në leksionin e tij në kuadër të projektit "Leksione publike "Polit.ru" nga Alexey Bronislavovich Sosinsky, matematikan, profesor në Universitetin e Pavarur të Moskës, oficer i Urdhrit të Palmave Akademike të Republikës Franceze, laureat i Çmimi i Qeverisë Ruse në fushën e arsimit në 2012. Në veçanti, u dhanë disa formulime të ndryshme të tij, u përshkruan tre qasje për vërtetimin e tij (Kolmogorov, Chaitin dhe vetë Gödel) dhe u shpjegua rëndësia e tij për matematikën, fizikën, shkencat kompjuterike dhe filozofinë.

Uspensky V. A.

Leksioni i kushtohet versionit sintaksor të Teoremës së Paplotësisë së Gödel-it. Vetë Gödel vërtetoi versionin sintaksor duke përdorur një supozim më të fortë se konsistenca, domethënë të ashtuquajturën konsistencë omega.

Uspensky V. A.

Ligjërata në shkollën verore “Matematika moderne”, Dubna.

Teoremat e paplotesise se Gödel

Teoremat e paplotesise se Gödel- dy teorema të logjikës matematikore në lidhje me kufizimet themelore të aritmetikës formale dhe, si pasojë, të çdo teorie mjaftueshëm të fortë të rendit të parë.

Teorema e parë thotë se nëse aritmetika formale është konsistente, atëherë ajo përmban një formulë të pareduktueshme dhe të pakundërshtueshme.

Teorema e dytë thotë se nëse aritmetika formale është konsistente, atëherë ajo përmban një formulë jo të derivueshme që në mënyrë kuptimplote pohon konsistencën e kësaj teorie.

Teorema e parë e paplotësisë së Gödel-it

Deklarata e teoremës së parë të paplotësisë së Gödel mund të thuhet si më poshtë:

Nëse aritmetika formale S është konsistente, atëherë ai përmban një formulë të mbyllur G të tillë që as G dhe as mohimi i tij ¬G nuk janë të derivueshme në S .

Gjatë vërtetimit të teoremës, Gödel ndërtoi formulën G në mënyrë eksplicite, nganjëherë quhet formula e pavendosur Gödelian. Në interpretimin standard, fjalia G pohon pakësueshmërinë e vet në S. Prandaj, nga teorema e Gödel-it, nëse një teori S është konsistente, atëherë kjo formulë është me të vërtetë e pareduktueshme në S dhe për këtë arsye e vërtetë në interpretimin standard. Kështu, për numrat natyrorë, formula Gështë e vërtetë, por jo e derivueshme në S.

Vërtetimi i Gödel mund të kryhet për çdo teori të marrë nga S duke shtuar aksioma të reja, për shembull, formulën G si aksiomë. Prandaj, çdo teori konsistente që është një shtrirje e aritmetikës formale do të jetë e paplotë.

Për të vërtetuar teoremën e parë të paplotësisë, Gödel caktoi një numër specifik për çdo simbol, shprehje dhe sekuencë shprehjesh në aritmetikën formale. Meqenëse formulat dhe teoremat janë fjali aritmetike, dhe derivimet formale të teoremave janë sekuenca formulash, është bërë e mundur të flitet për teorema dhe prova në terma të numrave natyrorë. Për shembull, le të formulën e pavendosur Gödelian G ka një numër m, atëherë është ekuivalente me pohimin e mëposhtëm në gjuhën e aritmetikës: “nuk ka një numër të tillë natyror n, Çfarë n ka një numër të prodhimit të formulës me numër m Një krahasim i tillë i formulave dhe numrave natyrorë quhet aritmetizimi i matematikës dhe u krye për herë të parë nga Gödel. Kjo ide më pas u bë çelësi për zgjidhjen e shumë problemeve të rëndësishme të logjikës matematikore.

Skica e provës

Le të rregullojmë disa sisteme formale PM në të cilat mund të përfaqësohen konceptet elementare matematikore.

Shprehjet e një sistemi formal, të parë nga jashtë, janë sekuenca të fundme simbolesh primitive (ndryshore, konstante logjike dhe kllapa ose pika), dhe nuk është e vështirë të specifikosh rreptësisht se cilat sekuenca simbolesh primitive janë formula dhe cilat jo. Në mënyrë të ngjashme, nga një këndvështrim formal, provat nuk janë gjë tjetër veçse sekuenca të fundme formulash (me veti të përcaktuara rreptësisht). Për konsideratë matematikore, nuk ka rëndësi se cilat objekte i marrim si simbole primitive dhe vendosim të përdorim numra natyrorë për këto qëllime. Prandaj, formula është një sekuencë e fundme e numrave natyrorë, përfundimi i formulës është një sekuencë e fundme e sekuencave të fundme të numrave natyrorë. Konceptet matematikore (pohimet) bëhen kështu koncepte (pohime) për numrat natyrorë ose sekuencat e tyre, dhe për këtë arsye mund të shprehen vetë në simbolikën e sistemit PM (të paktën pjesërisht). Mund të tregohet, në veçanti, se konceptet "formula", "derivimi", "formula e derivueshme" janë të përcaktueshme brenda sistemit PM, domethënë është e mundur të rivendoset, për shembull, formula. F(v) në PM me një ndryshore të lirë v(lloji i së cilës është një varg numrash) i tillë që F(v), në një interpretim intuitiv, do të thotë: v- formula e prejardhur. Tani le të ndërtojmë një fjali të pavendosur të sistemit PM, domethënë fjalinë A, për të cilën as A, as jo-A e pa derivueshme, si më poshtë:

Një formulë në PM me saktësisht një ndryshore të lirë, lloji i së cilës është një numër natyror (një klasë klasash) do të quhet klasë shprehjeje. Le t'i rregullojmë shprehjet e klasës në një sekuencë në një farë mënyre, shënojmë n-e përmes R(n), dhe vini re se koncepti i "klasë-shprehje", si dhe relacioni i renditjes R mund të përcaktohet në sistemin PM. Le të jetë α një shprehje arbitrare e klasës; përmes [α; n] shënoni formulën që formohet nga shprehja e klasës α duke zëvendësuar ndryshoren e lirë me simbolin e një numri natyror n. Marrëdhënie treshe x = [y;z] gjithashtu rezulton të jetë i përcaktueshëm në PM. Tani do të përcaktojmë klasën K numrat natyrorë si më poshtë:

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

(ku Bew x do të thotë: x- formula e prejardhur). Meqenëse të gjitha konceptet e gjetura në këtë përkufizim mund të shprehen në PM, e njëjta gjë vlen edhe për konceptin K, e cila është ndërtuar prej tyre, domethënë ekziston një klasë e tillë shprehjeje S, që formula [ S;n], e interpretuar në mënyrë intuitive, do të thotë se një numër natyror n i takon K. Si një klasë shprehjeje, S identike me disa specifike R(q) në numërimin tonë, pra

S = R(q)

vlen për një numër specifik natyror q. Tani do të tregojmë se fjalia [ R(q);q] i pavendosur në PM. Pra, nëse fjalia [ R(q);q] supozohet të jetë e derivueshme, atëherë rezulton e vërtetë, domethënë në përputhje me atë që u tha më sipër, q do të përkasin K, domethënë në përputhje me (*), ¬Bew[ R(q);q] do të ekzekutohet, gjë që bie ndesh me supozimin tonë. Nga ana tjetër, nëse mohimi [ R(q);q] ishte e konkludueshme, atëherë ¬ n ∈ K, që është, Bew[ R(q);q] do të jetë e vërtetë. Prandaj, [ R(q);q] së bashku me mohimin e tij do të jetë i deduktueshëm, gjë që është përsëri e pamundur.

Forma polinomiale

Për çdo teori konsistente T mund të specifikohet një vlerë e plotë e parametrit K të tillë që ekuacioni (θ + 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 + (fq − 2ws 2 r 2 n 2) 2 + (fq 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − ksn 2) 2 + η − k 2) 2 + (r + 1 + hfq − 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 nuk ka zgjidhje në numra të plotë jo negativë, por ky fakt nuk mund të vërtetohet në teori T . Për më tepër, për çdo teori konsistente, grupi i vlerave të parametrit K që ka këtë veti është i pafund dhe algoritmikisht i pa numërueshëm.

Teorema e dytë e paplotësisë së Gödel-it

Në aritmetikën formale S, mund të ndërtohet një formulë që, në interpretimin standard, është e vërtetë nëse dhe vetëm nëse teoria S është konsistente. Për këtë formulë, pohimi i teoremës së dytë të Gödel është i vërtetë:

Nëse aritmetika formale S është konsistente, atëherë ai përmban një formulë të pareduktueshme që pohon në mënyrë kuptimplotë konsistencë S .

Me fjalë të tjera, konsistenca e aritmetikës formale nuk mund të vërtetohet me anë të kësaj teorie. Megjithatë, ka prova të konsistencës së aritmetikës formale duke përdorur mjete që nuk janë të shprehura në të.

Skica e provës

Fillimisht ndërtohet formula Kon, që shpreh kuptimisht pamundësinë e nxjerrjes së ndonjë formule në teorinë S së bashku me mohimin e saj. Pastaj pohimi i teoremës së parë të Gödel shprehet me formulën Kon ⊃ G, Ku G- Formula e pazgjidhshme e Gödel-it. I gjithë arsyetimi për të vërtetuar teoremën e parë mund të shprehet dhe kryhet me anë të S, domethënë formula është e deduktueshme në S Kon ⊃ G. Prandaj, nëse në S është e derivueshme Kon, atëherë është e deduktueshme dhe G. Megjithatë, sipas teoremës së parë të Gödel, nëse S është konsistent, atëherë G nuk është e deduktueshme në të. Rrjedhimisht, nëse S është konsistente, atëherë formula në të është gjithashtu e pareduktueshme Kon.

Shënime

Shihni gjithashtu

Lidhjet

V. A. Uspensky Teorema e paplotesise se Gödel. - M.: Nauka, 1982. - 110 f. - (Ligjërata popullore për matematikën).
Akademiku Yu. L. Ershov "Dëshmi në matematikë", programi A. Gordon i datës 16 qershor 2003
A. B. Sosinsky Teorema e Gödel // Shkolla verore "Matematika moderne". - Dubna: 2006.
P. J. Cohen Mbi bazat e teorisë së grupeve // Përparimet në shkencat matematikore. - 1974. - T. 29. - Nr.5(179). - fq 169–176.
M. Kordonsky Fundi i së vërtetës. - ISBN 5-946448-001-04
V. A. Uspensky Teorema e Gödel mbi paplotësinë dhe katër rrugët që çojnë në të // Shkolla verore "Matematika moderne". - Dubna: 2007.
Zenkin A. A. Parimi i ndarjes së kohës dhe analizës së një klase të arsyetimit të besueshëm pothuajse të fundëm (duke përdorur shembullin e teoremës së G. Cantor mbi panumërueshmërinë) // DAN. - 1997. - T. 356. - Nr 6. - F. 733-735.
Chechulin V. L. Mbi një version të shkurtër të vërtetimit të teoremave të Gödel // “Problemet themelore të matematikës dhe shkencave të informacionit”, materialet e Shkollës-Seminari Matematikor XXXIV të Lindjes së Largët me emrin Akademik E.V. Zolotova. - Khabarovsk, Rusi: 2009. - F. 60-61.

Fondacioni Wikimedia.

2010.

Shihni se cilat janë "teoremat e Gödel-it mbi paplotësinë" në fjalorë të tjerë:

Ky term ka kuptime të tjera, shih teoremën e Gödel. Teorema e Gödel-it mbi paplotësinë dhe teorema e dytë e Gödel-it [1] dy teorema të logjikës matematikore rreth kufizimeve themelore të aritmetikës formale dhe, si pasojë, çdo ... ... Wikipedia

Teoremat e paplotësisë së Gödel-it janë dy teorema të logjikës matematikore në lidhje me paplotësinë e sistemeve formale të një lloji të caktuar. Përmbajtja 1 Teorema e parë e paplotësisë së Gödelit 2 Teorema e dytë e paplotësisë së Gödelit ... Wikipedia

Ky term ka kuptime të tjera, shih teoremën e Gödel. Teorema e Gödel mbi plotësinë e llogaritjes së kallëzuesit është një nga teoremat themelore të logjikës matematikore: ajo vendos një lidhje të paqartë midis së vërtetës logjike... ... Wikipedia Emri i përbashkët për dy teorema të krijuara nga K. Gödel. Së pari G. t. thekson se në çdo sistem formal të qëndrueshëm që përmban një minimum aritmetike (shenjat dhe rregullat e zakonshme për trajtimin e tyre), ekziston një zyrtarisht i pavendosur... ...

Uspensky V.A.

Enciklopedia Matematikore

Teorema e paplotesise se Gödel.1994.

Shkenca Teoretike Kompjuterike 130, 1994, fq.273-238.

një pasojë e drejtpërdrejtë e rezultatit të marrë nga Tarski duke kombinuar

Teorema e pavendosshmërisë së Gödel me teorinë e tij të së vërtetës, sipas

për të cilat nuk mund të ketë një kriter universal të së vërtetës edhe për relativisht

fushë e ngushtë e teorisë së numrave, dhe për rrjedhojë për çdo shkencë që përdor

aritmetike. Natyrisht, ky rezultat zbatohet një fortiori për konceptin e së vërtetës

në çdo fushë jo-matematikore të dijes në të cilën është gjerësisht

përdoret aritmetika.

Karl Popper

1. Deklarata e problemit

Kur e formulojmë teoremën në këtë mënyrë, pothuajse çdo fjalë kërkon një shpjegim. Prandaj do të fillojmë duke shpjeguar kuptimin e fjalëve që përdorim në këtë formulim.

1.1.1. Alfabeti

1.1.2. Shumë deklarata të vërteta

1.1.3. Çifti themelor i gjuhës

1.2. "E paprovueshme"

“E paprovueshme” do të thotë pa prova.

1.3. Dëshmi

Kështu, përkufizimi ynë përfundimtar është si më poshtë:

(1) Kemi një alfabet L (alfabet i gjuhës) dhe një alfabet P (alfabet vërtetues).

Një kusht i trefishtë i kënaqshëm (1)-(3) quhet një sistem deduktiv mbi alfabetin L.

1.4 Përpjekjet për të formuluar me saktësi teoremën e paplotësimit

1.4.1. Së pari provoni

"Në kushte të caktuara për një çift themelor të një gjuhe alfabetike L dhe një sistem deduktiv mbi L, ekziston gjithmonë një fjalë në T që nuk ka prova." Ky opsion duket ende i paqartë. Në veçanti, ne mund të arrijmë lehtësisht me aq sisteme deduktive sa të duam që të kenë shumë pak fjalë të vërtetueshme. Për shembull, në një sistem deduktiv bosh (ku P = ?) nuk ka fare fjalë që kanë prova.

1.4.2. Prova e dytë

"Në kushte të caktuara në lidhje me çiftin themelor, nuk ekziston një sistem deduktiv në të cilin çdo fjalë nga T ka një provë."

1.5. Konsistenca

Do të ishte krejt e natyrshme të kërkohej që të vërtetohen vetëm "thëniet e vërteta", pra vetëm fjalët nga T. Do të themi se një sistem deduktiv është konsistent në lidhje me çiftin themelor nëse?(P)?T. Në të gjitha diskutimet e mëvonshme do të jemi të interesuar vetëm për sisteme të tilla deduktive konsistente. Nëse na jepet një gjuhë, atëherë do të ishte jashtëzakonisht joshëse të gjejmë një sistem deduktiv të qëndrueshëm në të cilin çdo deklaratë e vërtetë do të kishte një provë. Versioni i teoremës së Gödel-it që na intereson pohon saktësisht se në kushte të caktuara në lidhje me çiftin themelor, është e pamundur të gjendet një sistem i tillë deduktiv.

1.6. Plotësia

Thuhet se sistemi deduktiv është i plotë në lidhje me çiftin themelor, me kusht që?(P)?T. Atëherë formulimi ynë i teoremës së paplotësisë merr formën e mëposhtme:

Në kushte të caktuara në lidhje me çiftin themelor, nuk ka asnjë sistem deduktiv mbi L që të jetë edhe i plotë dhe relativisht i qëndrueshëm.