Anumang sistema ng mathematical axioms, simula sa isang tiyak na antas ng pagiging kumplikado, ay alinman sa panloob na hindi naaayon o hindi kumpleto.

Noong 1900, ang World Conference of Mathematicians ay ginanap sa Paris, kung saan ipinakita ni David Hilbert (1862–1943) sa anyo ng mga abstract ang 23 pinakamahalaga, sa kanyang opinyon, mga problemang binuo niya, na dapat lutasin ng mga theoretical scientist. ng darating na ikadalawampung siglo. Ang pangalawang numero sa kanyang listahan ay isa sa mga simpleng problema na tila halata hanggang sa humukay ka ng mas malalim. Sa modernong mga termino, ito ang tanong: sapat ba ang matematika sa sarili nitong? Ang pangalawang gawain ni Hilbert ay nabawasan sa pangangailangan na mahigpit na patunayan na ang sistema ng mga axiom - mga pangunahing pahayag na kinuha sa matematika bilang batayan nang walang patunay - ay perpekto at kumpleto, iyon ay, pinapayagan nito ang matematikal na paglalarawan ng lahat ng bagay na umiiral. Kinakailangang patunayan na posible na magtakda ng gayong sistema ng mga axiom na, una, sila ay magkatugma, at pangalawa, ang isa ay maaaring gumawa ng konklusyon mula sa kanila tungkol sa katotohanan o kasinungalingan ng anumang pahayag.

Kumuha tayo ng isang halimbawa mula sa geometry ng paaralan. Sa karaniwang Euclidean planimetry (geometry sa isang eroplano), mapapatunayan nang walang kondisyon na ang pahayag na "ang kabuuan ng mga anggulo ng isang tatsulok ay 180°" ay totoo, at ang pahayag na "ang kabuuan ng mga anggulo ng isang tatsulok ay 137° "ay hindi totoo. Sa esensyal na pagsasalita, sa Euclidean geometry, alinmang pahayag ay mali o totoo, at ang pangatlo ay hindi ibinigay. At sa simula ng ikadalawampu siglo, ang mga mathematician ay walang muwang na naniniwala na ang parehong sitwasyon ay dapat sundin sa anumang lohikal na pare-parehong sistema.

At pagkatapos noong 1931, kinuha at inilathala ng ilang Viennese bespectacled mathematician na si Kurt Godel ang isang maikling artikulo na nagpabaligtad lamang sa buong mundo ng tinatawag na "mathematical logic". Pagkatapos ng mahaba at masalimuot na mathematical at theoretical preambles, literal niyang itinatag ang mga sumusunod. Kunin natin ang anumang pahayag tulad ng: "Ang Assumption #247 ay lohikal na hindi mapapatunayan sa sistemang ito ng mga axiom" at tawagin itong "statement A". Kaya, pinatunayan lamang ni Gödel ang sumusunod na kamangha-manghang pag-aari ng anumang sistema ng mga axiom:

"Kung ang isang pahayag A ay mapapatunayan, kung gayon ang isang hindi A na pahayag ay mapapatunayan."

Sa madaling salita, kung posibleng patunayan ang bisa ng pahayag na "Ang Assumption 247 ay hindi mapapatunayan", kung gayon posible ring patunayan ang bisa ng pahayag na "Ang Assumption 247 ay mapapatunayan". Iyon ay, bumalik sa pagbabalangkas ng pangalawang problema sa Hilbert, kung ang sistema ng mga axiom ay kumpleto (iyon ay, anumang pahayag dito ay maaaring patunayan), kung gayon ito ay hindi naaayon.

Ang tanging paraan sa labas ng sitwasyong ito ay upang tanggapin ang isang hindi kumpletong sistema ng mga axiom. Iyon ay, kailangan nating tiisin ang katotohanan na sa konteksto ng anumang lohikal na sistema ay magkakaroon pa rin tayo ng mga "uri A" na mga pahayag na malinaw na totoo o mali - at maaari nating hatulan ang kanilang katotohanan sa labas lamang ng balangkas ng axiomatics na mayroon tayo. pinagtibay. Kung walang ganoong mga pahayag, kung gayon ang ating axiomatics ay magkasalungat, at sa loob ng balangkas nito ay tiyak na magkakaroon ng mga pormulasyon na maaaring mapatunayan at mapabulaanan.

Kaya, ang pormulasyon ng una, o mahina, incompleteness theorem ni Gödel ay: "Anumang pormal na sistema ng axioms ay naglalaman ng hindi nalutas na mga pagpapalagay." Ngunit hindi tumigil doon si Gödel, na binabalangkas at pinatutunayan ang pangalawa o malakas na teorama ng kawalan ng kumpleto ni Gödel: “Ang lohikal na pagkakumpleto (o kawalan) ng anumang sistema ng mga axiom ay hindi maaaring patunayan sa loob ng balangkas ng sistemang ito. Upang patunayan o pabulaanan ito, kinakailangan ang mga karagdagang axiom (pagpapalakas ng system).

Ito ay magiging mas ligtas na isipin na ang mga theorems ni Godel ay abstract at hindi nag-aalala sa atin, ngunit ang mga lugar lamang ng napakahusay na lohika ng matematika, ngunit sa katunayan ito ay naging direktang nauugnay sa istraktura ng utak ng tao. Ang English mathematician at physicist na si Roger Penrose (ipinanganak 1931) ay nagpakita na ang mga theorems ni Gödel ay maaaring gamitin upang patunayan ang mga pangunahing pagkakaiba sa pagitan ng utak ng tao at isang computer. Ang punto ng kanyang pangangatwiran ay simple. Ang computer ay gumagana nang mahigpit na lohikal at hindi matukoy kung ang pahayag A ay totoo o mali kung ito ay lalampas sa saklaw ng axiomatics, at ang mga naturang pahayag, ayon sa teorama ni Gödel, ay hindi maiiwasang umiiral. Ang isang tao, na nahaharap sa ganoong lohikal na hindi mapapatunayan at hindi masasagot na pahayag A, ay palaging nagagawang matukoy ang katotohanan o kamalian nito - batay sa pang-araw-araw na karanasan. Hindi bababa sa ito, ang utak ng tao ay mas mataas kaysa sa isang computer na nakagapos ng mga purong lohikal na circuit. Naiintindihan ng utak ng tao ang buong lalim ng katotohanan na nakapaloob sa mga theorems ni Gödel, ngunit hinding-hindi maiintindihan ng isang computer. Samakatuwid, ang utak ng tao ay anumang bagay maliban sa isang computer. Nagagawa niyang gumawa ng mga desisyon, at papasa ang Turing test.

I wonder if Hilbert had any idea kung hanggang saan kami dadalhin ng mga tanong niya?

Kurt GOEDEL
Kurt Godel, 1906–78

Austrian, noon ay American mathematician. Ipinanganak sa Brünn (Brünn, ngayon ay Brno, Czech Republic). Nagtapos siya sa Unibersidad ng Vienna, kung saan nanatili siyang guro sa Departamento ng Matematika (mula noong 1930 - isang propesor). Noong 1931 inilathala niya ang isang teorama na kalaunan ay natanggap ang kanyang pangalan. Bilang isang purong apolitical na tao, napakahirap niyang nakaligtas sa pagpatay sa kanyang kaibigan at empleyado ng departamento ng isang estudyanteng Nazi at nahulog sa isang malalim na depresyon, ang mga pagbabalik nito ay pinagmumultuhan siya hanggang sa katapusan ng kanyang buhay. Noong 1930s, lumipat siya sa Estados Unidos, ngunit bumalik sa kanyang katutubong Austria at nagpakasal. Noong 1940, sa kasagsagan ng digmaan, napilitan siyang tumakas patungong Amerika sa paglalakbay sa pamamagitan ng USSR at Japan. Sa loob ng ilang panahon nagtrabaho siya sa Princeton Institute for Advanced Study. Sa kasamaang palad, ang pag-iisip ng siyentipiko ay hindi makayanan, at siya ay namatay sa gutom sa isang psychiatric clinic, tumanggi na kumain, dahil siya ay kumbinsido na nilayon nilang lasonin siya.

Mga komento: 0

Paano umuunlad ang siyentipikong modelo sa mga natural na agham? Ang pang-araw-araw o pang-agham na karanasan ay nag-iipon, ang mga milestone nito ay maingat na binabalangkas sa anyo ng mga postulate at bumubuo ng batayan ng modelo: isang hanay ng mga pahayag na tinatanggap ng lahat na nagtatrabaho sa loob ng modelong ito.

Anatoly Wasserman

Noong 1930, pinatunayan ni Kurt Gödel ang dalawang teorema na, isinalin mula sa wikang matematika tungo sa wika ng tao, ay nangangahulugang ganito: Anumang sistema ng mga axiom na sapat na mayaman upang magamit upang tukuyin ang aritmetika ay maaaring hindi kumpleto o hindi magkatugma. Ang isang hindi kumpletong sistema ay nangangahulugan na ang isang pahayag ay maaaring buuin sa sistema, na hindi maaaring patunayan o pabulaanan sa pamamagitan ng sistemang ito. Ngunit ang Diyos, ayon sa kahulugan, ay ang pinakahuling dahilan ng lahat ng dahilan. Sa matematika, nangangahulugan ito na ang pagpapakilala ng axiom tungkol sa Diyos ay ginagawang kumpleto ang ating buong axiom. Kung mayroong Diyos, kung gayon ang anumang pahayag ay maaaring mapatunayan o mapabulaanan, na tumutukoy, sa isang paraan o iba pa, sa Diyos. Ngunit ayon kay Gödel, ang kumpletong sistema ng mga axiom ay hindi maiiwasang magkasalungat. Iyon ay, kung naniniwala tayo na ang Diyos ay umiiral, kung gayon tayo ay mapipilitang magkaroon ng konklusyon na ang mga kontradiksyon ay posible sa kalikasan. At dahil walang mga kontradiksyon, kung hindi, ang ating buong mundo ay gumuho mula sa mga kontradiksyon na ito, kailangan nating makarating sa konklusyon na ang pagkakaroon ng Diyos ay hindi tugma sa pagkakaroon ng kalikasan.

Sosinsky A. B.

Ang theorem ni Gödel, kasama ang pagtuklas ng relativity, quantum mechanics, at DNA, ay karaniwang itinuturing na pinakadakilang tagumpay sa siyensya noong ika-20 siglo. Bakit? Ano ang kakanyahan nito? Ano ang kahulugan nito? Alexei Bronislavovich Sosinsky, mathematician, propesor sa Independent Moscow University, opisyal ng Order of Academic Palms ng French Republic, nagwagi ng RF Government Prize sa larangan ng edukasyon noong 2012, ay nagpapakita ng mga tanong na ito sa kanyang panayam sa loob ng balangkas ng Proyekto ng Polit.ru Public Lectures. Sa partikular, maraming iba't ibang pormulasyon nito ang ibinigay, tatlong diskarte sa patunay nito ang inilarawan (ni Kolmogorov, Chaitin, at Gödel mismo), at ipinaliwanag ang kahalagahan nito para sa matematika, pisika, computer science, at pilosopiya.

Uspensky V. A.

Ang panayam ay nakatuon sa syntactic na bersyon ng Gödel's Incompleteness Theorem. Pinatunayan mismo ni Gödel ang syntactic na bersyon gamit ang isang mas malakas na palagay kaysa sa consistency, katulad ng tinatawag na omega-consistency.

Uspensky V. A.

Mga Lektura ng Summer School "Modern Mathematics", Dubna.

Ang incompleteness theorem ni Godel

Uspensky V.A.

Marahil ay talagang kakaiba ang incompleteness theorem ni Gödel. Natatangi dahil tinutukoy nila ito kapag gusto nilang patunayan ang "lahat ng bagay sa mundo" - mula sa presensya ng mga diyos hanggang sa kawalan ng katwiran. Ako ay palaging interesado sa isang mas "pangunahing tanong" - at sino sa mga sumangguni sa incompleteness theorem ay hindi lamang maaaring bumalangkas nito, ngunit mapatunayan din ito? Inilathala ko ang artikulong ito sa kadahilanang ito ay nagpapakita ng isang napaka-accessible na pagbabalangkas ng teorama ni Gödel. Inirerekomenda ko na basahin mo muna ang artikulo ni Tullio Regge Kurt Gödel at ang kanyang sikat na teorama

Ang konklusyon tungkol sa imposibilidad ng isang unibersal na pamantayan ng katotohanan ay isang direktang bunga ng resulta na nakuha ni Tarski sa pamamagitan ng pagsasama-sama ng undecidability theorem ni Gödel sa kanyang sariling teorya ng katotohanan, ayon sa kung saan hindi maaaring magkaroon ng isang unibersal na pamantayan ng katotohanan kahit para sa isang medyo makitid na lugar. ng teorya ng numero, at samakatuwid para sa anumang agham na gumagamit ng arithmetic. Natural, ang resultang ito ay naglalapat ng isang fortiori sa konsepto ng katotohanan sa anumang di-matematikong larangan ng kaalaman kung saan malawakang ginagamit ang aritmetika.

Karl Popper

Si Uspensky Vladimir Andreevich ay ipinanganak noong Nobyembre 27, 1930 sa Moscow. Nagtapos mula sa Faculty of Mechanics at Mathematics ng Moscow State University (1952). Doktor ng Physical and Mathematical Sciences (1964). Propesor, Pinuno ng Departamento ng Mathematical Logic at Theory of Algorithms ng Faculty of Mechanics and Mathematics (1966). Nagbabasa ng mga kurso ng lektura na "Introduction to Mathematical Logic", "Computable Functions", "Gödel's Completeness Theorem". Naghanda ng 25 kandidato at 2 doktor ng agham

1. Paglalahad ng suliranin

Ang incompleteness theorem, ang eksaktong pormulasyon kung saan ibibigay namin sa dulo ng kabanatang ito, at marahil mamaya (kung interesado ang mambabasa dito) at ang patunay, ay nagsasaad ng humigit-kumulang sa mga sumusunod: sa ilalim ng ilang mga kundisyon sa anumang wika ay may totoo, ngunit hindi mapapatunayang mga pahayag.

Kapag bumalangkas tayo ng teorama sa ganitong paraan, halos bawat salita ay nangangailangan ng ilang paliwanag. Samakatuwid, magsisimula tayo sa pagpapaliwanag ng kahulugan ng mga salitang ginagamit natin sa pagbabalangkas na ito.

1.1. Wika

Hindi namin ibibigay ang pinaka-pangkalahatang posibleng kahulugan ng isang wika, mas pinipiling i-confine ang ating sarili sa mga konseptong iyon ng wika na kakailanganin natin mamaya. Mayroong dalawang ganoong konsepto: "ang alpabeto ng wika" at "ang hanay ng mga totoong pahayag ng wika".

1.1.1. Alpabeto

Sa pamamagitan ng alpabeto, ang ibig naming sabihin ay isang may hangganang hanay ng mga elementarya na palatandaan (iyon ay, mga bagay na hindi maaaring hatiin sa mga bahaging bahagi). Ang mga karakter na ito ay tinatawag na mga titik ng alpabeto. Ang ibig sabihin ng isang salita ng isang alpabeto ay isang may hangganang pagkakasunod-sunod ng mga titik. Halimbawa, ang mga ordinaryong salita sa Ingles (kabilang ang mga wastong pangalan) ay mga salita ng 54-titik na alpabeto (26 maliliit na titik, 26 malalaking titik, isang gitling at isang kudlit). Ang isa pang halimbawa - ang mga natural na numero sa decimal notation ay mga salita ng isang 10-titik na alpabeto, na ang mga titik ay mga palatandaan: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Gagamit kami ng ordinaryong malalaking titik upang tukuyin mga alpabeto. Kung ang L ay isang alpabeto, kung gayon ang L? ay tumutukoy sa hanay ng lahat ng mga salita ng alpabeto L, - mga salitang nabuo mula sa mga titik nito. Ipagpalagay namin na ang anumang wika ay may sariling alpabeto, upang ang lahat ng mga expression ng wikang ito (ibig sabihin - mga pangalan ng iba't ibang mga bagay, mga pahayag tungkol sa mga bagay na ito, atbp.) ay mga salita ng alpabeto na ito. Halimbawa, ang anumang pangungusap sa wikang Ingles, gayundin ang anumang tekstong nakasulat sa Ingles, ay maaaring ituring bilang isang salita ng pinalawig na 54-titik na alpabeto, na kinabibilangan din ng mga bantas, interword space, isang pulang linya ng character, at posibleng ilang iba pang mga kapaki-pakinabang na karakter. Ipagpalagay na ang mga expression ng wika ay mga salita ng ilang alpabeto, sa gayon ay hindi namin isasama sa pagsasaalang-alang ang mga "multilayer" na expression tulad ng ???f(x)dx. Gayunpaman, ang limitasyong ito ay hindi masyadong makabuluhan, dahil anumang ganoong expression, gamit ang angkop na mga kombensiyon, ay maaaring "iunat" sa isang linear na anyo. Any set M na nakapaloob sa L? ay tinatawag na set ng salita ng alpabeto L. Kung sasabihin lang natin na ang M ay isang set ng salita, ibig sabihin natin na ito ay isang salita ng ilang alpabeto. Ngayon ang pagpapalagay ng wika sa itaas ay maaaring muling i-rephrase tulad ng sumusunod: sa anumang wika, anumang hanay ng mga expression ay isang hanay ng salita.

1.1.2. Maraming totoong claim

Ipinapalagay namin na binibigyan kami ng subset T ng set L? (kung saan ang L ay ang alpabeto ng ilang wikang ating isinasaalang-alang), na tinatawag na set ng "mga totoong pahayag" (o simpleng "mga katotohanan"). Direkta na dumaan sa subset T, inalis namin ang mga sumusunod na intermediate na hakbang ng pangangatwiran: una, kung aling mga salita ng alpabeto L ang mahusay na nabuong mga expression ng wika, iyon ay, mayroon silang tiyak na kahulugan sa aming interpretasyon ng wikang ito (halimbawa , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 ay mahusay na nabuo na mga expression, habang ang mga expression tulad ng +=x ay hindi); pangalawa, kung aling mga expression ang mga formula, i.e. maaaring depende sa isang parameter (hal., x=3, x=y, 2=3, 2=2); pangatlo, alin sa mga formula ang mga closed formula, i.e. mga pahayag na hindi nakadepende sa mga parameter (halimbawa, 2=3, 2=2); at panghuli, kung aling mga saradong formula ang mga totoong pahayag (halimbawa, 2=2).

1.1.3. Pangunahing pares ng wika

1.2. "Hindi mapapatunayan"

Ang ibig sabihin ng "unprovable" ay walang ebidensya.

1.3. Patunay

Sa kabila ng katotohanan na ang terminong "patunay" ay marahil isa sa pinakamahalaga sa matematika (sinimulan ng Bourbaki ang kanilang aklat na "Fundamentals of Mathematics" na may mga salitang: "Mula sa panahon ng mga sinaunang Griyego, ang pagsasabi ng "matematika" ay nangangahulugang pareho ng pagsasabi ng "patunay""), wala siyang tiyak na kahulugan. Sa pangkalahatan, ang konsepto ng patunay kasama ang lahat ng mga sangay ng semantiko nito ay kabilang, sa halip, sa larangan ng sikolohiya kaysa sa matematika. Ngunit kahit na ano pa man, ang patunay ay isang argumento lamang na nakikita nating lubos na nakakumbinsi upang kumbinsihin ang iba.

Kapag isinulat, ang patunay ay nagiging isang salita sa ilang alpabeto P, tulad ng anumang tekstong Ingles ay isang salita sa alpabeto L, isang halimbawa nito ay ibinigay sa itaas. Ang hanay ng lahat ng mga patunay ay bumubuo ng isang subset (at medyo malaking subset) ng hanay na P?. Hindi namin tatangkaing magbigay ng isang tumpak na kahulugan ng parehong "walang muwang" at "ganap" na konsepto ng patunay, o - na katumbas - upang tukuyin ang kaukulang subset ng P?. Sa halip, isasaalang-alang natin ang isang pormal na analogue ng malabong konseptong ito, kung saan gagamitin pa rin natin ang terminong "patunay" sa mga sumusunod. Ang analog na ito ay may dalawang napakahalagang tampok na nakikilala ito mula sa intuitive na konsepto (bagaman ang intuitive na ideya ng patunay ay sumasalamin pa rin sa mga tampok na ito sa ilang mga lawak). Una sa lahat, ipinapalagay namin na mayroong iba't ibang mga konsepto ng patunay, iyon ay, ang iba't ibang mga subset ng mga patunay sa P? ay pinahihintulutan, at higit pa rito: sa katunayan, ipagpalagay natin na ang alpabeto ng mga patunay ng P mismo ay maaaring magbago . Sa kung ano ang sumusunod, hinihiling namin na para sa bawat naturang konsepto ng isang patunay mayroong isang mahusay na pamamaraan, sa madaling salita, isang algorithm, na tiyak na tutukuyin kung ang isang ibinigay na salita ng alpabeto P ay isang patunay o hindi. Ipinapalagay din namin na mayroong isang algorithm na palaging magagamit upang matukoy kung aling pahayag ang pinatutunayan ng isang ibinigay na patunay. (Sa maraming sitwasyon, ang pahayag na pinatutunayan ay ang huling pahayag lamang sa pagkakasunud-sunod ng mga hakbang na bumubuo ng patunay.)

Kaya, ang aming huling salita ng kahulugan ay ang mga sumusunod:

(1) Mayroon tayong alpabeto L (ang alpabeto ng wika) at ang alpabeto P (ang alpabeto ng patunay).

(2) Binigyan tayo ng set P na isang subset ng P? at ang mga elemento ay tinatawag na "proofs". Sa hinaharap, ipagpalagay namin na mayroon din kaming algorithm na nagbibigay-daan sa amin upang matukoy kung ang isang arbitrary na salita ng alpabeto P ay isang elemento ng set P, iyon ay, isang patunay, o hindi.

(3) Mayroon din tayong function? (para sa paghahanap kung ano ang eksaktong napatunayan), kaninong domain? nakakatugon sa kondisyong P???P?, at kaninong saklaw ang nasa P?. Ipinapalagay namin na mayroon kaming isang algorithm na kinakalkula ang function na ito (ang eksaktong kahulugan ng mga salitang "kinakalkula ng algorithm ang isang function" ay ang mga sumusunod: ang mga halaga ng function ay nakuha gamit ang algorithm na ito - isang hanay ng mga espesyal na panuntunan sa pagbabago). Sasabihin natin na ang elementong p? Ang P ay isang patunay ng salita?(p) ng alpabeto L.

Troika<Р, Р, ?>, ang mga kasiya-siyang kondisyon (1)-(3) ay tinatawag na deductive system sa alpabeto L.

Para sa mambabasa na pamilyar sa karaniwang paraan ng pagtukoy ng "patunay" sa mga tuntunin ng "axiom" at "panuntunan ng hinuha", ipapaliwanag namin ngayon kung paano ang pamamaraang ito ay maituturing na isang espesyal na kaso ng kahulugan na ibinigay sa seksyon 1.3.2. Ibig sabihin, ang isang patunay ay karaniwang binibigyang kahulugan bilang isang pagkakasunud-sunod ng naturang mga pagpapahayag ng wika, na ang bawat isa ay alinman sa isang axiom o dati nang nakuha mula sa mga umiiral nang pahayag gamit ang isa sa mga panuntunan ng hinuha. Kung magdaragdag tayo ng bagong salita * sa alpabeto ng ating wika, maaari tayong sumulat ng gayong patunay bilang isang salita na binubuo gamit ang resultang alpabeto: ang pagkakasunod-sunod ng mga ekspresyon ay nagiging salitang C1*C2*...*Cn. Sa kasong ito, ang function na tumutukoy kung ano ang eksaktong napatunayan ay may halaga nito sa bahagi ng salitang ito kaagad kasunod ng huling titik * sa pagkakasunud-sunod. Ang algorithm na ang pagkakaroon ay kinakailangan sa Seksyon 1.3.2. mga kahulugan, ay madaling mabuo kapag natukoy na natin ang alinman sa mga tinatanggap na kahulugan ng mga salitang "axiom" at "rule of inference".

1.4 Mga pagtatangka na tumpak na bumalangkas ng incompleteness theorem

1.4.1. Unang pagsubok

"Sa ilalim ng ilang mga kundisyon para sa pangunahing pares ng wika ng alpabeto L at ng deductive system<Р, Р, ?>higit sa L, palaging mayroong isang salita sa T na walang patunay. Ang pagpipiliang ito ay mukhang malabo pa rin. ?) wala talagang mga salita na magkakaroon ng ebidensya.

1.4.2. Pangalawang pagsubok

May isa pang mas natural na diskarte. Ipagpalagay na binigyan tayo ng isang wika - sa kahulugan na binibigyan tayo ng pangunahing pares ng wikang ito. Ngayon ay hahanapin natin ang gayong deduktibong sistema sa L (sa madaling salita, naghahanap tayo ng isang patunay na pamamaraan) kung saan mapapatunayan natin ang pinakamaraming salita mula sa T hangga't maaari, sa limitasyon ng lahat ng mga salita mula sa teorema ni T. Gödel ay naglalarawan ng sitwasyon kung saan tulad ng deductive system (kung saan ang bawat salita sa T ay mapapatunayan) ay hindi umiiral. Kaya, nais naming bumalangkas ng sumusunod na pahayag:

"Sa ilalim ng ilang mga kundisyon tungkol sa pangunahing pares, walang ganoong deductive system kung saan ang bawat salita mula sa T ay magkakaroon ng patunay."

Gayunpaman, ang nasabing pahayag ay malinaw na mali, dahil kinakailangan lamang na kumuha ng isang deductive system kung saan ang P = L, P = P? at?(p) = p para sa lahat ng p sa P?; tapos bawat salita galing kay L? ay trivially provable. Samakatuwid, kailangan nating tanggapin ang ilang limitasyon kung aling mga deductive system ang ginagamit natin.

1.5. Hindi pagbabago

Ito ay magiging natural na humiling na ang "mga totoong pahayag" lamang, iyon ay, mga salita lamang mula sa T, ang maaaring patunayan. Sasabihin natin na ang deductive system<Р, Р, ?>ay pare-pareho sa paggalang sa isang pangunahing pares kung?(P)?T. Sa lahat ng kasunod na pangangatwiran, kami ay magiging interesado lamang sa mga pare-parehong sistemang deduktibo. Kung tayo ay bibigyan ng isang wika, kung gayon ito ay magiging lubhang kaakit-akit na makahanap ng tulad ng isang pare-parehong sistema ng deduktibo kung saan ang bawat totoong pahayag ay magkakaroon ng patunay. Ang variant ng theorem ni Gödel na interesado sa amin ay eksaktong nagsasaad na sa ilalim ng ilang mga kundisyon na may paggalang sa pangunahing pares, imposibleng makahanap ng ganoong deductive system.

1.6. pagkakumpleto

Sinasabi na ang deductive system<Р,Р,?>ay kumpleto na may kinalaman sa pangunahing pares, sa kondisyon na?(P)?T. Pagkatapos ang aming pagbabalangkas ng incompleteness theorem ay tumatagal ng sumusunod na anyo:

Sa ilalim ng ilang mga kundisyon tungkol sa pangunahing pares, walang ganoong deductive system<Р,Р,?>higit sa L na magiging kumpleto at medyo pare-pareho.

Bibliograpiya

Para sa paghahanda ng gawaing ito, ginamit ang mga materyales mula sa site na http://filosof.historic.ru.

09si sen

Anumang sistema ng mathematical axioms, simula sa isang tiyak na antas ng pagiging kumplikado, ay alinman sa panloob na hindi naaayon o hindi kumpleto.

Noong 1900, ang World Conference of Mathematicians ay ginanap sa Paris, kung saan David Gilbert(David Hilbert, 1862–1943) binalangkas sa anyo ng mga theses ang 23 pinakamahalaga, sa kanyang palagay, mga gawain na kailangang lutasin ng mga theoreticians ng darating na ikadalawampu siglo. Ang pangalawang numero sa kanyang listahan ay isa sa mga simpleng problema na tila halata hanggang sa humukay ka ng mas malalim. Sa modernong mga termino, ito ang tanong: sapat ba ang matematika sa sarili nitong? Ang pangalawang gawain ni Hilbert ay nabawasan sa pangangailangan na mahigpit na patunayan na ang sistema ng mga axiom - mga pangunahing pahayag na kinuha sa matematika bilang batayan nang walang patunay - ay perpekto at kumpleto, iyon ay, pinapayagan nito ang matematikal na paglalarawan ng lahat ng bagay na umiiral. Kinakailangang patunayan na posible na magtakda ng gayong sistema ng mga axiom na, una, sila ay magkatugma, at pangalawa, ang isa ay maaaring gumawa ng konklusyon mula sa kanila tungkol sa katotohanan o kasinungalingan ng anumang pahayag.

Kumuha tayo ng isang halimbawa mula sa geometry ng paaralan. Sa karaniwang Euclidean planimetry (geometry sa isang eroplano), mapapatunayan nang walang kondisyon na ang pahayag na "ang kabuuan ng mga anggulo ng isang tatsulok ay 180°" ay totoo, at ang pahayag na "ang kabuuan ng mga anggulo ng isang tatsulok ay 137° "ay hindi totoo. Sa esensyal na pagsasalita, sa Euclidean geometry, alinmang pahayag ay mali o totoo, at ang pangatlo ay hindi ibinigay. At sa simula ng ikadalawampu siglo, ang mga mathematician ay walang muwang na naniniwala na ang parehong sitwasyon ay dapat sundin sa anumang lohikal na pare-parehong sistema.

At pagkatapos ay noong 1931 ang ilang Viennese bespectacled mathematician Kurt Gödel- kumuha at naglathala ng maikling artikulo na nagpabaligtad lamang sa buong mundo ng tinatawag na "mathematical logic". Pagkatapos ng mahaba at masalimuot na mathematical at theoretical preambles, literal niyang itinatag ang mga sumusunod. Kunin natin ang anumang pahayag tulad ng: "Ang Assumption #247 ay lohikal na hindi mapapatunayan sa sistemang ito ng mga axiom" at tawagin itong "statement A". Kaya, pinatunayan lamang ni Gödel ang sumusunod na kamangha-manghang pag-aari ng anumang sistema ng mga axiom:

"Kung ang isang pahayag A ay mapapatunayan, kung gayon ang isang hindi A na pahayag ay mapapatunayan."

Sa madaling salita, kung posibleng patunayan ang bisa ng pahayag na "Ang Assumption 247 ay hindi mapapatunayan", kung gayon posible ring patunayan ang bisa ng pahayag na "Ang Assumption 247 ay mapapatunayan". Iyon ay, bumalik sa pagbabalangkas ng pangalawang problema sa Hilbert, kung ang sistema ng mga axiom ay kumpleto (iyon ay, anumang pahayag dito ay maaaring patunayan), kung gayon ito ay hindi naaayon.

Ang tanging paraan sa labas ng sitwasyong ito ay upang tanggapin ang isang hindi kumpletong sistema ng mga axiom. Iyon ay, kailangan nating tiisin ang katotohanan na sa konteksto ng anumang lohikal na sistema ay magkakaroon pa rin tayo ng mga "uri A" na mga pahayag na malinaw na totoo o mali - at maaari nating hatulan ang kanilang katotohanan sa labas lamang ng balangkas ng axiomatics na mayroon tayo. pinagtibay. Kung walang ganoong mga pahayag, kung gayon ang ating axiomatics ay magkasalungat, at sa loob ng balangkas nito ay tiyak na magkakaroon ng mga pormulasyon na maaaring mapatunayan at mapabulaanan.

Kaya ang pormulasyon ng una, o mahina, incompleteness theorem ni Gödel ay: "Ang anumang pormal na sistema ng mga axiom ay naglalaman ng mga hindi nalutas na pagpapalagay". Ngunit hindi tumigil doon si Gödel, na binabalangkas at pinatutunayan ang pangalawa o malakas na teorama ng kawalan ng kumpleto ni Gödel: “Ang lohikal na pagkakumpleto (o kawalan) ng anumang sistema ng mga axiom ay hindi maaaring patunayan sa loob ng balangkas ng sistemang ito. Upang patunayan o pabulaanan ito, kinakailangan ang mga karagdagang axiom (pagpapalakas ng system).

Ito ay magiging mas ligtas na isipin na ang mga theorems ni Godel ay abstract at hindi nag-aalala sa atin, ngunit ang mga lugar lamang ng napakahusay na lohika ng matematika, ngunit sa katunayan ito ay naging direktang nauugnay sa istraktura ng utak ng tao. Ipinakita iyon ng English mathematician at physicist na si Roger Penrose (ipinanganak 1931). Ang mga teorema ni Gödel ay maaaring gamitin upang patunayan ang pagkakaroon ng mga pangunahing pagkakaiba sa pagitan ng utak ng tao at isang computer. Ang punto ng kanyang pangangatwiran ay simple. Ang computer ay gumagana nang mahigpit na lohikal at hindi matukoy kung ang pahayag A ay totoo o mali kung ito ay lalampas sa saklaw ng axiomatics, at ang mga naturang pahayag, ayon sa teorama ni Gödel, ay hindi maiiwasang umiiral. Ang isang tao, na nahaharap sa ganoong lohikal na hindi mapapatunayan at hindi masasagot na pahayag A, ay palaging nagagawang matukoy ang katotohanan o kamalian nito - batay sa pang-araw-araw na karanasan. Hindi bababa sa ito, ang utak ng tao ay mas mataas kaysa sa isang computer na nakagapos ng mga purong lohikal na circuit. Naiintindihan ng utak ng tao ang buong lalim ng katotohanan na nakapaloob sa mga theorems ni Gödel, ngunit hinding-hindi maiintindihan ng isang computer. Samakatuwid, ang utak ng tao ay anumang bagay maliban sa isang computer. Nagagawa niyang gumawa ng mga desisyon, at papasa ang Turing test.

Mga teorema ng kawalan ng kumpleto ni Godel

Mga teorema ng kawalan ng kumpleto ni Godel

Mga teorema ng kawalan ng kumpleto ni Godel- dalawang theorems ng mathematical logic sa mga pangunahing limitasyon ng pormal na aritmetika at, bilang resulta, ng anumang sapat na malakas na first-order theory.

Ang unang teorama ay nagsasaad na kung ang pormal na aritmetika ay pare-pareho, kung gayon ito ay naglalaman ng isang hindi masasagot at hindi masasagot na pormula.

Ang pangalawang teorama ay nagsasaad na kung ang pormal na aritmetika ay pare-pareho, kung gayon ang ilang mga pormula ay hindi maaaring makuha sa loob nito, na makabuluhang iginigiit ang pagkakapare-pareho ng teoryang ito.

Ang unang incompleteness theorem ni Gödel

Ang pag-aangkin ng unang incompleteness theorem ni Gödel ay maaaring sabihin tulad ng sumusunod:

Kung pormal na aritmetika S ay pare-pareho, pagkatapos ay naglalaman ito ng saradong formula G na ang G o ang negasyon nito ¬G ay hindi makukuha sa S .

Sa pagpapatunay ng teorama, itinayo ni Gödel ang pormula G tahasan, kung minsan ito ay tinatawag na Gödel's unsolvable formula. Sa karaniwang interpretasyon, ang pangungusap G iginiit ang sarili nitong di-derivable sa S. Samakatuwid, sa pamamagitan ng Gödel's theorem, kung ang isang theory S ay pare-pareho, kung gayon ang formula na ito ay talagang di-derivable sa S at samakatuwid ay totoo sa karaniwang interpretasyon. Kaya, para sa mga natural na numero, ang formula G ay totoo, ngunit hindi mababawas sa S.

Ang patunay ni Gödel ay maaari ding isagawa para sa anumang teorya na nakuha mula sa S sa pamamagitan ng pagdaragdag ng mga bagong axiom, halimbawa, ang formula G bilang isang axiom. Samakatuwid, ang anumang pare-parehong teorya na extension ng pormal na aritmetika ay hindi kumpleto.

Upang patunayan ang unang incompleteness theorem, nagtalaga si Gödel ng isang tiyak na numero sa bawat simbolo, expression, at sequence ng mga expression sa pormal na aritmetika. Dahil ang mga pormula at teorema ay mga pangungusap ng aritmetika, at ang mga pormal na derivasyon ng mga teorema ay mga pagkakasunud-sunod ng mga pormula, naging posible na magsalita ng mga teorema at patunay sa mga tuntunin ng mga natural na numero. Halimbawa, hayaan ang hindi malulutas na formula ng Gödel G may numero m, kung gayon ito ay katumbas ng sumusunod na pahayag sa wika ng aritmetika: "walang ganoong natural na numero n, Ano n mayroong isang formula derivation number na may numero m". Ang ganitong paghahambing ng mga pormula at natural na mga numero ay tinatawag na arithmetization ng matematika at isinagawa ni Gödel sa unang pagkakataon. Ang ideyang ito sa kalaunan ay naging susi sa paglutas ng maraming mahahalagang suliranin ng lohika ng matematika.

proof sketch

Ayusin natin ang ilang pormal na sistemang PM kung saan maaaring katawanin ang mga elementaryang konsepto ng matematika.

Ang mga expression ng isang pormal na sistema ay, mula sa labas, may hangganang pagkakasunud-sunod ng mga primitive na simbolo (mga variable, logical constant, at bracket o tuldok) at hindi mahirap na mahigpit na tukuyin kung aling mga pagkakasunud-sunod ng mga primitive na simbolo ang mga formula at alin ang hindi. Katulad nito, mula sa isang pormal na pananaw, ang mga patunay ay walang iba kundi may hangganang pagkakasunud-sunod ng mga formula (na may mahigpit na tinukoy na mga katangian). Para sa pagsasaalang-alang sa matematika, hindi mahalaga kung aling mga bagay ang gagawin bilang mga primitive na simbolo, at nagpasya kaming gumamit ng mga natural na numero para sa mga layuning ito. Alinsunod dito, ang formula ay isang may hangganang pagkakasunod-sunod ng mga natural na numero, ang derivation ng formula ay isang may hangganang pagkakasunod-sunod ng mga may hangganang pagkakasunod-sunod ng mga natural na numero. Ang mga konsepto ng matematika (mga pahayag) ay nagiging mga konsepto (mga pahayag) tungkol sa mga natural na numero o ang kanilang mga pagkakasunud-sunod, at samakatuwid ay maaaring ipahayag sa kanilang sarili sa simbolismo ng sistema ng PM (kahit sa bahagi). Maaari itong ipakita, sa partikular, na ang mga konseptong "formula", "derivation", "derivable formula" ay natutukoy sa loob ng PM system, iyon ay, maaaring mabawi ng isa, halimbawa, ang formula. F(v) sa PM na may isang libreng variable v(na ang uri ay isang numeric sequence) tulad na F(v), sa isang intuitive na interpretasyon, ay nangangahulugang: v- derivable formula. Ngayon ay buuin natin ang isang hindi mapagpasyang pangungusap ng sistema ng PM, iyon ay, ang pangungusap A, para sa kung saan hindi A, hindi rin hindi-A hindi maibabawas, gaya ng sumusunod:

Ang isang formula sa PM na may eksaktong isang libreng variable na ang uri ay isang natural na numero (isang klase ng mga klase) ay tatawaging isang expression class. Ayusin natin ang mga class-expression sa isang pagkakasunod-sunod sa ilang paraan, ipahiwatig n-sa pamamagitan ng R(n), at tandaan na ang konsepto ng "class-expression", pati na rin ang pagkakaugnay ng pag-order R maaaring tukuyin sa sistema ng PM. Hayaang ang α ay isang arbitraryong pagpapahayag ng klase; sa pamamagitan ng [α; n] tukuyin ang formula na nabuo mula sa class-expression na α sa pamamagitan ng pagpapalit sa libreng variable ng simbolo ng natural na numero n. Ternary na relasyon x = [y;z] din pala ang definable sa PM. Ngayon ay tutukuyin natin ang isang klase K natural na mga numero tulad ng sumusunod:

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

(kung saan si Bew x ibig sabihin: x- derivable formula). Dahil ang lahat ng mga konsepto na nagaganap sa kahulugan na ito ay maaaring ipahayag sa PM, ang parehong ay totoo para sa konsepto K, na kung saan ay binuo mula sa kanila, iyon ay, mayroong isang klase-expression S na ang formula [ S;n], na intuitively na binibigyang kahulugan, ay nangangahulugan na isang natural na numero n nabibilang K. Bilang pagpapahayag ng klase, S magkapareho sa ilang partikular R(q) sa aming pagnunumero, kumbaga

S = R(q)

humahawak para sa ilang tiyak na natural na numero q. Ipakita natin ngayon na ang pangungusap [ R(q);q] ay undecidable sa PM. Kaya, kung ang pangungusap [ R(q);q] ay ipinapalagay na maaaring makuha, pagkatapos ito ay lumalabas na totoo, iyon ay, alinsunod sa sinabi sa itaas, q mapapabilang K, ibig sabihin, ayon sa (*), ¬Bew[ R(q);q] ay masisiyahan, na sumasalungat sa aming palagay. Sa kabilang banda, kung ang negasyon [ R(q);q] ay maaaring makuha, pagkatapos ay ¬ n ∈ K, ibig sabihin, Bew[ R(q);q] ay magiging totoo. Samakatuwid, [ R(q);q] kasama ang negasyon nito ay maaaring makuha, na muli ay imposible.

Polynomial form

Para sa bawat pare-parehong teorya T ang isa ay maaaring tukuyin tulad ng isang integer na halaga ng parameter K na ang equation (θ + 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 + (p − 2ws 2 r 2 n 2) 2 + (p 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − ksn 2) 2 + η − k 2) 2 + (r + 1 + hp − 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 ay walang mga solusyon sa mga di-negatibong integer, ngunit ang katotohanang ito ay hindi mapapatunayan sa teorya T . Bukod dito, para sa bawat pare-parehong teorya, ang hanay ng mga halaga ng parameter K na may ganitong katangian ay walang hanggan at hindi mabilang sa algorithm.

Pangalawang incompleteness theorem ni Gödel

Sa pormal na arithmetic S, ang isang tao ay maaaring bumuo ng isang formula na, sa karaniwang interpretasyon, ay totoo kung at kung ang teorya S ay pare-pareho. Para sa pormula na ito, ang pahayag ng pangalawang teorama ni Gödel ay totoo:

Kung pormal na aritmetika S ay pare-pareho, pagkatapos ay naglalaman ito ng di-derivable na pormula na lubos na iginigiit ang pagkakapare-pareho S .

Sa madaling salita, ang pagkakapare-pareho ng pormal na aritmetika ay hindi maaaring patunayan sa pamamagitan ng teoryang ito. Gayunpaman, may mga patunay ng pagkakapare-pareho ng pormal na aritmetika gamit ang mga paraan na hindi maipahayag dito.

proof sketch

Una, nabuo ang isang formula Con, makahulugang pagpapahayag ng imposibilidad ng pagkuha ng anumang pormula sa teoryang S kasama ang negasyon nito. Pagkatapos ang pahayag ng unang teorama ni Gödel ay ipinahayag ng pormula Con ⊃ G, saan G- Ang hindi malulutas na formula ni Gödel. Ang lahat ng mga argumento para sa patunay ng unang teorama ay maaaring ipahayag at isagawa sa pamamagitan ng S, iyon ay, sa S ang pormula ay maaaring makuha. Con ⊃ G. Kaya naman, kung ang S ay derivable Con, pagkatapos ay nakukuha namin ito at G. Gayunpaman, ayon sa unang teorama ni Gödel, kung pare-pareho ang S, kung gayon G sa ito ay hindi deducible. Samakatuwid, kung ang S ay pare-pareho, kung gayon ang formula Con.

Mga Tala

Tingnan din

Mga link

• V. A. Uspensky Ang incompleteness theorem ni Godel. - M.: Nauka, 1982. - 110 p. - (Mga sikat na lektura sa matematika).
• Akademikong si Yu. L. Ershov "Ebidensya sa Matematika", programa ni A. Gordon noong Hunyo 16, 2003
• A. B. Sosinsky Teorama ni Gödel // summer school na "Modern Mathematics". - Dubna: 2006.
• P. J. Cohen Sa mga pundasyon ng set theory // Mga Pagsulong sa Agham sa Matematika. - 1974. - T. 29. - No. 5 (179). - S. 169–176.
• M. Kordonsky Katapusan ng Katotohanan. - ISBN 5-946448-001-04
• V. A. Uspensky Ang incompleteness theorem ni Gödel at apat na daan patungo dito // summer school na "Modern Mathematics". - Dubna: 2007.
• Zenkin A. A. Prinsipyo ng pagbabahagi ng oras at pagsusuri ng isang klase ng quasi-finite plausible reasoning (sa halimbawa ng uncountability theorem ni G. Kantor) // SI DAN. - 1997. - T. 356. - Bilang 6. - S. 733-735.
• Chechulin V. L. Sa isang maikling bersyon ng patunay ng mga teorema ni Gödel // "Mga pangunahing problema ng matematika at agham ng impormasyon", mga materyales ng XXXIV Far Eastern Mathematical School-seminar na pinangalanang Academician E.V. Zolotova. - Khabarovsk, Russia: 2009. - S. 60-61.

Wikimedia Foundation. 2010 .

Tingnan kung ano ang "Gödel's Incompleteness Theorems" sa ibang mga diksyunaryo:

Ang terminong ito ay may iba pang kahulugan, tingnan ang Gödel's Theorem. Ang incompleteness theorem ni Godel at ang pangalawang theorem ni Godel [1] ay dalawang theorems ng mathematical logic tungkol sa mga pundamental na limitasyon ng pormal na arithmetic at, bilang resulta, anumang ... ... Wikipedia

Ang hindi kumpletong theorems ni Gödel ay dalawang theorems ng mathematical logic sa incompleteness ng mga pormal na sistema ng isang partikular na uri. Mga Nilalaman 1 Ang Unang Teorama ng Kakulangan ni Gödel 2 Ang Teorama ng Ikalawang Kakulangan ni Gödel ... Wikipedia

Ang terminong ito ay may iba pang kahulugan, tingnan ang Gödel's Theorem. Ang theorem ni Gödel sa pagkakumpleto ng predicate calculus ay isa sa mga pangunahing theorems ng mathematical logic: nagtatatag ito ng isang hindi malabo na relasyon sa pagitan ng lohikal na katotohanan ... ... Wikipedia

Karaniwang pangalan para sa dalawang theorems na itinatag ni K. Gödel. Ang unang G. t. tungkol sa n. inaangkin na sa anumang pare-parehong pormal na sistema na naglalaman ng isang minimum na aritmetika (mga palatandaan at ang karaniwang mga patakaran para sa paghawak sa mga ito), mayroong isang pormal na hindi mapagpasyahan ... ... Mathematical Encyclopedia

sa paksang: "GODEL'S THEOREM"

Kurt Gödel

Si Kurt Gödel - ang pinakadakilang dalubhasa sa lohika ng matematika - ay ipinanganak noong Abril 28, 1906 sa Brunn (ngayon ay Brno, Czech Republic). Nagtapos siya sa Unibersidad ng Vienna, kung saan ipinagtanggol niya ang kanyang disertasyon ng doktor, ay isang assistant professor noong 1933–1938. Pagkatapos ng Anschluss, lumipat siya sa Estados Unidos. Mula 1940 hanggang 1963 nagtrabaho si Gödel sa Princeton Institute for Advanced Study. Si Gödel ay isang Honorary Doctorate mula sa Yale at Harvard Universities, isang miyembro ng US National Academy of Sciences at ng American Philosophical Society.

Noong 1951, si Kurt Gödel ay ginawaran ng pinakamataas na pang-agham na parangal sa Estados Unidos, ang Einstein Prize. Sa isang artikulo na nakatuon sa kaganapang ito, isa pa sa pinakadakilang mathematician sa ating panahon, si John von Neumann, ay sumulat: "Ang kontribusyon ni Kurt Gödel sa modernong lohika ay tunay na napakalaki. Ito ay higit pa sa isang monumento. Ito ay isang milestone na naghihiwalay sa dalawang panahon ... Masasabing walang anumang pagmamalabis na ang gawain ni Gödel sa panimula ay nagbago sa mismong paksa ng lohika bilang isang agham.

Sa katunayan, kahit na ang isang tuyong listahan ng mga nagawa ni Godel sa matematikal na lohika ay nagpapakita na ang kanilang may-akda ay mahalagang naglatag ng mga pundasyon para sa buong seksyon ng agham na ito: ang teorya ng mga modelo (1930; ang tinatawag na teorama sa pagkakumpleto ng makitid na calculus ng panaguri, na nagpapakita, sa halos pagsasalita, ang kasapatan ng mga paraan ng "pormal na lohika "upang patunayan ang lahat ng totoong pangungusap na ipinahayag sa wika nito), nakabubuo na lohika (1932–1933; nagreresulta sa posibilidad na bawasan ang ilang klase ng mga pangungusap ng klasikal na lohika sa kanilang mga intuitionistic na katapat, na kung saan naglatag ng pundasyon para sa sistematikong paggamit ng "mga operasyon sa paglulubog" na nagbibigay-daan sa gayong pagbabawas ng iba't ibang lohikal na sistema sa isa't isa), pormal na aritmetika (1932–1933; nagreresulta sa posibilidad ng pagbabawas ng klasikal na arithmetic sa intuitionistic na arithmetic, na nagpapakita sa isang kahulugan ng pagkakapare-pareho ng una na may paggalang sa pangalawa), ang teorya ng mga algorithm at recursive function (1934; kahulugan ng konsepto ng isang pangkalahatang recursive function, na gumaganap ng isang mapagpasyang papel sa pagtatatag ng algorithmic unsolvability ng ilang mahahalagang problema sa matematika, sa isang banda. At sa pagpapatupad ng mga lohikal at matematikal na problema sa mga elektronikong kompyuter - sa kabilang banda), axiomatic set theory (1938; patunay ng kamag-anak na pagkakapare-pareho ng axiom of choice at continuum hypothesis ng Cantor mula sa axioms ng set theory, na minarkahan ang simula. ng isang serye ng mahahalagang resulta sa relatibong pagkakapare-pareho at pagsasarili set-teoretikong mga prinsipyo).

Ang incompleteness theorem ni Godel

Panimula

Noong 1931, lumitaw ang isang medyo maliit na artikulo sa isa sa mga journal na siyentipikong Aleman na may medyo nakakatakot na pamagat na "Sa pormal na hindi matukoy na mga panukala ng Principia Mathematica at mga kaugnay na sistema." Ang may-akda nito ay isang dalawampu't limang taong gulang na matematiko mula sa Unibersidad ng Vienna, Kurt Gödel, na kalaunan ay nagtrabaho sa Princeton Institute for Advanced Study. Ang gawaing ito ay gumaganap ng isang mapagpasyang papel sa kasaysayan ng lohika at matematika. Sa desisyon ng Harvard University na igawad kay Gödel ang isang honorary doctorate (1952), ito ay nailalarawan bilang isa sa mga pinakadakilang tagumpay ng modernong lohika.

Gayunpaman, sa oras ng paglalathala, walang pamagat ng gawa ni Gödel. Ni ang nilalaman nito ay walang sinabi sa karamihan ng mga mathematician. Binanggit sa pamagat nito, ang Principia Mathematica ay ang Alfred North Whitehead at ang monumental na tatlong-volume na treatise ni Bertrand Russell sa mathematical logic at ang mga pundasyon ng matematika; ang pamilyar sa treatise ay hindi nangangahulugang isang kinakailangang kondisyon para sa matagumpay na trabaho sa karamihan ng mga sangay ng matematika. Ang interes sa mga isyung tinutugunan sa gawain ni Gödel ay palaging nasa napakaliit na grupo ng mga siyentipiko. Kasabay nito, ang mga argumento na ibinigay ni Gödel sa kanyang mga patunay ay hindi karaniwan para sa kanilang panahon. Na ang kumpletong pag-unawa sa mga ito ay nangangailangan ng eksklusibong kaalaman sa paksa at pamilyar sa panitikan na nakatuon sa mga partikular na problemang ito.

Unang incompleteness theorem

Ang unang incompleteness theorem ni Gödel tila ang pinaka makabuluhang resulta sa matematikal na lohika. Parang ganito:

Para sa isang arbitraryong pare-parehong pormal at computable na teorya kung saan ang mga pangunahing aritmetika na proposisyon ay maaaring patunayan, isang tunay na arithmetic proposition ay maaaring mabuo na ang katotohanan ay hindi mapapatunayan sa loob ng balangkas ng teorya. Sa madaling salita, ang anumang perpektong kapaki-pakinabang na teorya na sapat upang kumatawan sa aritmetika ay hindi maaaring pare-pareho at kumpleto.

Dito ang salitang "teorya" ay nangangahulugang "isang walang katapusang hanay" ng mga pahayag, ang ilan sa mga ito ay ipinapalagay na totoo nang walang patunay (ang mga naturang pahayag ay tinatawag na mga axiom), habang ang iba (mga teorema) ay maaaring mahihinuha mula sa mga axiom, at samakatuwid ay ipinapalagay ( napatunayan) na totoo. Ang pariralang "mapapatunayan sa teorya" ay nangangahulugang "makukuha mula sa mga axiom at primitive ng teorya (mga pare-parehong simbolo ng alpabeto) gamit ang karaniwang (first-order) na lohika." Ang isang teorya ay pare-pareho (konsistent) kung imposibleng patunayan ang isang magkasalungat na pahayag dito. Ang pariralang "maaaring itayo" ay nangangahulugan na mayroong ilang mekanikal na pamamaraan (algorithm) na maaaring bumuo ng isang pahayag batay sa mga axiom, primitive, at first-order na lohika. Ang "elementarya na arithmetic" ay ang pagkakaroon ng mga operasyon ng pagdaragdag at pagpaparami sa mga natural na numero. Ang resultang totoo ngunit hindi mapapatunayan na proposisyon ay madalas na tinutukoy para sa isang ibinigay na teorya bilang ang "Gödel sequence", ngunit mayroong isang walang katapusang bilang ng iba pang mga proposisyon sa teorya na may parehong katangian ng pagiging hindi mapatunayan sa loob ng teorya.

Ang pagpapalagay na ang isang teorya ay computable ay nangangahulugan na ito ay sa prinsipyo ay posible na ipatupad ang isang computer algorithm (computer program) na kung saan (kung pinapayagang mag-compute nang di-makatwirang mahabang panahon, hanggang sa infinity) ay mag-compute ng isang listahan ng lahat ng mga theorems ng teorya. Sa katunayan, ito ay sapat na upang kalkulahin lamang ang listahan ng mga axiom, at lahat ng mga theorems ay maaaring mahusay na nakuha mula sa naturang listahan.

Ang unang incompleteness theorem ay pinamagatang "Theorem VI" sa 1931 na papel ni Gödel. Sa Mga Pormal na Hindi Mapagpasyahang Proposisyon sa Principia Mathematica at Mga Kaugnay na Sistema I. Sa orihinal na recording ni Gödel, ganito ang tunog:

"Ang pangkalahatang konklusyon tungkol sa pagkakaroon ng hindi mapagpasyang mga panukala ay ito:

Teorama VI .

Para sa bawat ω-consistent recursive class k FORMULA may mga recursive PALATANDAAN r tulad na hindi (v Sinabi ni Gen r), hindi rin ¬( v Sinabi ni Gen r)hindi kabilang sa Flg (k)(nasaan si v LIBRENG VARIABLE r ) ».

Pagtatalaga Flg galing sa kanya. Folgerungsmenge- set ng mga sequence, Sinabi ni Gen galing sa kanya. paglalahat- paglalahat.

Sa halos pagsasalita, ang pahayag ni Gödel G iginiit: "katotohanan G hindi mapapatunayan." Kung G maaaring patunayan sa loob ng teorya, kung gayon ang teorya ay maglalaman ng isang teorama na sumasalungat sa sarili nito, at samakatuwid ang teorya ay hindi magkatugma. Ngunit kung G hindi mapatunayan, kung gayon ito ay totoo, at samakatuwid ang teorya ay hindi kumpleto (ang pahayag G hindi mababawas dito).

Ang paliwanag na ito ay nasa ordinaryong natural na wika, at samakatuwid ay hindi masyadong mathematically rigorous. Upang magbigay ng mahigpit na patunay, binilang ni Gödel ang mga pahayag na may natural na mga numero. Sa kasong ito, ang teorya na naglalarawan ng mga numero ay kabilang din sa hanay ng mga proposisyon. Ang mga tanong tungkol sa provability ng mga proposisyon ay maaaring katawanin sa kasong ito sa anyo ng mga tanong tungkol sa mga katangian ng mga natural na numero, na dapat na computable kung kumpleto ang teorya. Sa mga terminong ito, sinabi ng pahayag ni Gödel na walang numero na may ilang tiyak na pag-aari. Ang isang numero na may ganitong katangian ay magiging patunay ng hindi pagkakapare-pareho ng teorya. Kung mayroong ganoong bilang, ang teorya ay hindi naaayon, salungat sa orihinal na palagay. Kaya ipagpalagay na ang teorya ay pare-pareho (tulad ng iminumungkahi ng premise ng theorem), lumalabas na walang ganoong numero, at ang pahayag ni Gödel ay totoo, ngunit hindi ito mapapatunayan sa loob ng balangkas ng teorya (kaya't ang teorya ay hindi kumpleto. ). Ang isang mahalagang konseptong tala ay ang isa ay dapat na ipalagay na ang isang teorya ay pare-pareho upang maideklarang totoo ang pahayag ni Gödel.

Pangalawang incompleteness theorem ni Gödel

Ang pangalawang incompleteness theorem ni Gödel ay ganito ang mga sumusunod:

Para sa anumang pormal na recursively enumerable (i.e. effectively generated) theory T, kabilang ang mga basic arithmetic truth statement at ilang pormal na provability statement, ang isang ibinigay na theory T ay may kasamang pahayag tungkol sa consistency nito kung at kung hindi pare-pareho ang theory T.

Sa madaling salita, ang pagkakapare-pareho ng isang mayamang teorya ay hindi maaaring patunayan sa pamamagitan ng teoryang ito. Gayunpaman, maaaring lumabas na ang pagkakapare-pareho ng isang partikular na teorya ay maaaring maitatag sa pamamagitan ng isa pa, mas makapangyarihang pormal na teorya. Ngunit pagkatapos ay lumitaw ang tanong tungkol sa pagkakapare-pareho ng pangalawang teorya na ito, at iba pa.

Marami ang sumubok na gamitin ang theorem na ito upang patunayan na ang matalinong aktibidad ay hindi maaaring bawasan sa mga kalkulasyon. Halimbawa, noong 1961, ang sikat na logician na si John Lucas ay nakabuo ng isang katulad na programa. Ang kanyang pangangatwiran ay naging medyo mahina - gayunpaman, itinakda niya ang gawain nang mas malawak. Si Roger Penrose ay gumagamit ng bahagyang naiibang diskarte, na ganap na ipinakita sa aklat, "mula sa simula".

Mga talakayan

Ang mga kahihinatnan ng mga theorems ay nakakaapekto sa pilosopiya ng matematika, lalo na ang mga pormalismo na gumagamit ng pormal na lohika upang tukuyin ang kanilang mga prinsipyo. Maaaring i-rephrase ng isa ang unang incompleteness theorem tulad ng sumusunod: imposibleng makahanap ng isang komprehensibong sistema ng mga axiom na maaaring patunayan lahat mga katotohanan sa matematika, at hindi isang kasinungalingan". Sa kabilang banda, mula sa punto ng view ng mahigpit na pormalidad, ang repormulasyon na ito ay walang gaanong kahulugan, dahil ipinapalagay nito na ang mga konsepto ng "totoo" at "mali" ay tinukoy sa isang ganap na kahulugan, sa halip na sa isang kamag-anak para sa bawat isa. partikular na sistema.