Gödels ufullstendighetsteorem på en enkel måte. Interessante fakta og nyttige tips

Ethvert system av matematiske aksiomer, med utgangspunkt i et visst kompleksitetsnivå, er enten internt inkonsekvent eller ufullstendig.

I 1900 ble verdenskonferansen for matematikere holdt i Paris, hvor David Hilbert (1862-1943) presenterte i form av sammendrag de 23 viktigste, etter hans mening, problemer formulert av ham, og som skulle løses av teoretiske vitenskapsmenn av det kommende tjuende århundre. Nummer to på listen hans var en av dem enkle oppgaver, svaret på det virker åpenbart inntil du graver litt dypere. snakker moderne språk, det var spørsmålet: er matematikk tilstrekkelig alene? Hilberts andre problem var å bevise strengt at systemet aksiomer- de grunnleggende utsagnene tatt i matematikk som grunnlag uten bevis - er perfekte og fullstendige, det vil si at de lar deg matematisk beskrive alt som eksisterer. Det var nødvendig å bevise at det er mulig å sette et slikt system av aksiomer at de for det første vil være gjensidig konsistente, og for det andre kan man trekke en konklusjon fra dem angående sannheten eller usannheten til ethvert utsagn.

La oss ta et eksempel fra skolegeometri. Standard Euklidisk planimetri(geometri på planet) er det mulig å bevise ubetinget at påstanden "summen av vinklene til en trekant er 180°" er sann, og påstanden "summen av vinklene til en trekant er 137°" er usann. I hovedsak, i euklidisk geometri, er enhver påstand enten usann eller sann, og den tredje er ikke gitt. Og på begynnelsen av det tjuende århundre trodde matematikere naivt at den samme situasjonen burde observeres i ethvert logisk konsistent system.

Og så i 1931 tok en eller annen wienerbrillete matematiker Kurt Godel og publiserte en kort artikkel som rett og slett veltet hele verden av såkalt "matematisk logikk". Etter lange og komplekse matematiske og teoretiske innledninger, etablerte han bokstavelig talt følgende. La oss ta ethvert utsagn som: "Antakelse #247 er logisk ubeviselig i dette aksiomsystemet" og kalle det "utsagn A". Så Gödel beviste ganske enkelt følgende fantastiske eiendom noen aksiomsystemer:

"Hvis en påstand A kan bevises, kan en ikke-A-påstand bevises."

Med andre ord, hvis det er mulig å bevise gyldigheten av utsagnet "Antagelse 247 ikke beviselig", så er det mulig å bevise gyldigheten av utsagnet "Antagelse 247 beviselig". Det vil si å gå tilbake til formuleringen av det andre Hilbert-problemet, hvis systemet med aksiomer er komplett (det vil si at enhver påstand i det kan bevises), så er det inkonsekvent.

Den eneste veien ut av denne situasjonen er å akseptere et ufullstendig system av aksiomer. Det vil si at vi må tåle det faktum at i sammenheng med ethvert logisk system vil vi sitte igjen med "type A" utsagn som åpenbart er sanne eller usanne - og vi kan bare bedømme sannheten deres. utenfor rammeverket for aksiomatikken vi har tatt i bruk. Hvis det ikke finnes slike utsagn, så er vår aksiomatikk selvmotsigende, og innenfor dens ramme vil det uunngåelig være formuleringer som både kan bevises og tilbakevises.

Så ordlyden først,eller svak Gödels ufullstendighetsteoremer: "Ethvert formelt system av aksiomer inneholder uavklarte antakelser." Men Gödel stoppet ikke der, formulerte og beviste sekund, eller sterk Godels ufullstendighetsteorem: «Den logiske fullstendigheten (eller ufullstendigheten) til ethvert system av aksiomer kan ikke bevises innenfor rammen av dette systemet. For å bevise eller motbevise det, kreves det ytterligere aksiomer (styrking av systemet).

Det ville være tryggere å tro at Godels teoremer er abstrakte og ikke angår oss, men bare områder med sublim matematisk logikk, men faktisk viste det seg at de er direkte relatert til strukturen til den menneskelige hjernen. Den engelske matematikeren og fysikeren Roger Penrose (født 1931) viste at Gödels teoremer kunne brukes til å bevise grunnleggende forskjeller mellom den menneskelige hjernen og en datamaskin. Poenget med resonnementet hans er enkelt. Datamaskinen opererer strengt logisk og er ikke i stand til å avgjøre om påstand A er sann eller usann hvis den går utover omfanget av aksiomatikk, og slike utsagn, ifølge Gödels teorem, eksisterer uunngåelig. En person, som står overfor et slikt logisk ubeviselig og ugjendrivelig utsagn A, er alltid i stand til å fastslå sannheten eller usannheten - basert på hverdagserfaring. I hvert fall i dette Menneskehjerne utkonkurrerer en datamaskin lenket med ren logiske kretser. Den menneskelige hjernen er i stand til å forstå den fulle dybden av sannheten i Gödels teoremer, men en datamaskin kan man aldri. Derfor er den menneskelige hjernen alt annet enn en datamaskin. Han er kapabel å ta avgjørelser, og Turing-testen vil bestå.

Jeg lurer på om Hilbert hadde noen anelse om hvor langt spørsmålene hans ville ta oss?

Kurt Godel, 1906-78

Østerriksk, daværende amerikansk matematiker. Født i Brünn (Brünn, nå Brno, Tsjekkia). Han ble uteksaminert fra universitetet i Wien, hvor han forble lærer ved Institutt for matematikk (siden 1930 - professor). I 1931 publiserte han et teorem som senere fikk navnet hans. Som en rent apolitisk person, overlevde han ekstremt hardt drapet på sin venn og avdelingsansatt av en nazistudent og falt i en dyp depresjon, hvis tilbakefall hjemsøkte ham til slutten av livet. På 1930-tallet emigrerte han til USA, men returnerte til hjemlandet Østerrike og giftet seg. I 1940, på høyden av krigen, ble han tvunget til å flykte til Amerika på transitt gjennom Sovjetunionen og Japan. Jobbet en stund ved Princeton Institute avansert forskning. Dessverre kunne ikke psyken til forskeren tåle det, og han døde av sult på en psykiatrisk klinikk og nektet å spise, fordi han var overbevist om at de hadde til hensikt å forgifte ham.

Jeg har lenge vært interessert i hva det oppsiktsvekkende Gödel-teoremet er. Og hvordan det er nyttig for livet. Og endelig klarte jeg å finne ut av det.

Den mest populære formuleringen av teoremet er:
"Ethvert system av matematiske aksiomer, som starter fra et visst kompleksitetsnivå, er enten internt inkonsekvent eller ufullstendig."

Jeg ville oversatt det til et menneskelig ikke-matematisk språk som dette (et aksiom er startposisjonen til en teori, akseptert innenfor rammen av denne teorien som sann uten å kreve bevis og brukt som grunnlag for å bevise dens andre bestemmelser). I livet er et aksiom prinsippene som følges av en person, et samfunn, vitenskapelig retning, opplyser. Blant religionens representanter kalles aksiomer dogmer. Følgelig blir alle våre prinsipper, ethvert system av synspunkter, som starter fra et visst nivå, internt motstridende, eller ufullstendig. For å bli overbevist om sannheten til en viss uttalelse, må man gå utover det gitte systemet av synspunkter og bygge et nytt. Men det vil også være ufullkomment. Det vil si at KUNNSKAPENS PROSESS ER UENDELIG. Verden kan ikke være fullt kjent før vi når kilden.

"... hvis vi anser evnen til å resonnere logisk som hovedkarakteristikken til det menneskelige sinnet, eller i det minste dets hovedverktøy, så indikerer Gödels teorem direkte de begrensede evnene til hjernen vår. Enig i at det er veldig vanskelig for en person brakt opp på troen på tankens uendelige kraft for å akseptere tesen om grensene for dens makt ... Mange eksperter mener at de formelle beregningsmessige, "aristoteliske" prosessene som ligger til grunn logisk tenkning, er bare en del menneskelig bevissthet. Det andre området, grunnleggende "ikke-beregningsmessig", er ansvarlig for slike manifestasjoner som intuisjon, kreativ innsikt og forståelse. Og hvis den første halvdelen av sinnet faller inn under Gödels begrensninger, så er den andre halvdelen fri for slike grenser ... Fysiker Roger Penrose gikk enda lenger. Han foreslo eksistensen av noen kvanteeffekter av ikke-beregningsmessig natur, som sikrer realiseringen av kreative bevissthetshandlinger... En av de mange konsekvensene av Penrose-hypotesen kan spesielt være konklusjonen at kunstig intelligens på grunnlag av moderne dataenheter, selv om fremkomsten av kvantedatamaskiner vil føre til et grandiost gjennombrudd innen datateknologi. Faktum er at enhver datamaskin bare mer og mer nøyaktig kan modellere arbeidet med den formelle-logiske, "beregningsmessige" aktiviteten til den menneskelige bevisstheten, men intellektets "ikke-beregningsmessige" evner er utilgjengelige for den.

En viktig konsekvens av Gödels teorem er konklusjonen om at man ikke kan tenke i ekstremer. Alltid innenfor eksisterende teori det er et utsagn som verken kan bevises eller motbevises. Eller, med andre ord, til et utsagn er det alltid et par som motbeviser det.

Neste konklusjon. Godt og ondt er bare to sider av samme sak, uten hvilke det ikke kan eksistere. Og det kommer fra prinsippet om at i universet er det bare én kilde til alt: godt og ondt, kjærlighet og hat, liv og død.

Enhver erklæring om fullstendighet av systemet er falsk. Du kan ikke stole på dogmer, for før eller siden vil de bli tilbakevist.

Slik sett er moderne religioner i en kritisk posisjon: kirkens dogmer motsetter seg utviklingen av våre ideer om verden. De prøver å presse alt inn i rammen av rigide konsepter. Men dette fører til det faktum at fra monoteisme, fra den eneste kilden til alle naturlige prosesser de går videre til hedenskap, hvor det er gode og ondes krefter, det er en god gud et sted langt borte i himmelen, og det er en djevel (det ondes gud), som lenge har lagt poten på alt som er på jorden. Denne tilnærmingen fører til inndeling av alle mennesker i venner og fiender, rettferdige og syndere, troende og kjettere, venner og fiender.

Her er en annen liten tekst som populært avslører essensen som følger av Gödels teorem:
"Det ser ut til at dette teoremet har en viktig rolle filosofisk mening. Bare to alternativer er mulig:

a) Teorien er ufullstendig, dvs. i form av en teori kan man formulere et spørsmål som det er umulig å utlede verken et positivt eller et negativt svar på fra teoriens aksiomer/postulater. Samtidig kan svar på alle slike spørsmål gis innenfor rammen av en mer omfattende teori, der den gamle vil være et spesialtilfelle. Men dette ny teori vil ha sine egne "ubesvarte spørsmål" og så videre i det uendelige.

b) Fullstendig, men motstridende. Ethvert spørsmål kan besvares, men noen spørsmål kan besvares med både ja og nei samtidig.

Vitenskapelige teorier er av den første typen. De er konsekvente, men det betyr at de ikke beskriver alt. Det kan ikke være noen "finale" vitenskapelig teori. Enhver teori er ufullstendig og beskriver ikke noe, selv om vi ennå ikke vet hva det er. Man kan bare lage mer og mer omfattende teorier. For meg personlig er dette en grunn til optimisme, fordi det betyr at vitenskapens fremgang aldri vil stoppe.

«Den allmektige Gud» tilhører den andre typen. Den allmektige Gud er svaret på alle spørsmål. Og dette betyr automatisk at det fører til logisk absurditet. Paradokser som den "tunge steinen" kan oppfinnes i partier.

Alt i alt, vitenskapelig kunnskap er sant (konsistent), men beskriver til enhver tid ikke alt. Samtidig er det ingenting som hindrer å skyve grensene for det kjente til det uendelige, lenger og lenger og før eller siden blir enhver ukjent kjent. Religion hevder å Full beskrivelse verden "akkurat nå", men den er automatisk feil (absurd)."

På en gang, da jeg nettopp startet min voksenlivet Jeg programmerte. Og det var et slikt prinsipp: Hvis det gjøres mange rettelser i programmet, må det skrives om igjen. Dette prinsippet samsvarer etter min mening med Godels teorem. Hvis programmet blir mer komplekst, blir det inkonsekvent. Og det vil ikke fungere riktig.

Nok et eksempel fra livet. Vi lever i en tid da tjenestemenn sier at hovedprinsippet for eksistens skal være loven. Det vil si rettssystemet. Men så snart lovgivningen blir mer kompleks og regelutformingen blomstrer, begynner lovene å motsi hverandre. Det vi ser nå. Du kan aldri skape rettssystem, som ville foreskrive alle aspekter av livet. På den annen side ville det vært rettferdig for alle. Fordi begrensningene i vår forståelse av verden alltid vil komme ut. Og menneskelige lover vil på et tidspunkt begynne å komme i konflikt med universets lover. Vi forstår mange ting intuitivt. Også intuitivt må vi bedømme andre menneskers handlinger. Det er nok at staten har en grunnlov. Og stole på artiklene i denne grunnloven, for å regulere forholdet i samfunnet. Men før eller siden må grunnloven endres.

BRUKEN er et annet eksempel på feilslutningen i våre ideer om menneskelige evner. Vi prøver å teste hjernens beregningsevne i en eksamen. Men intuitive evner på skolen har sluttet å utvikles. Men mennesket er ikke en biorobot. Det er umulig å lage et poengsystem som vil kunne avsløre alle mulighetene som ligger i en person, i hans bevissthet, i hans underbevissthet og i hans psyke.

For nesten 100 år siden tok Gödel et utrolig skritt i å forstå universets lover. Og vi har fortsatt ikke vært i stand til å bruke dette, med tanke på dette teoremet som høyt spesialisert matematisk problem for en smal krets av mennesker som behandler noen abstrakte temaer i sin egen krets. Sammen med kvanteteori og Kristi lære, Gödels teorem gjør oss i stand til å flykte fra fangenskapet til falske dogmer, for å overvinne krisen som fortsatt vedvarer i vårt verdensbilde. Og tiden renner ut.

En av de mest kjente teoremer matematisk logikk, heldig og uheldig på samme tid. I dette er hun som spesiell teori Einsteins relativitet. På den ene siden har nesten alle hørt noe om dem. På den annen side, i den populære tolkningen, Einsteins teori, som du vet, "sier at alt i verden er relativt". Og Gödels ufullstendighetsteorem (heretter ganske enkelt TGN), i en omtrent like fri folkeformulering, "beviser at det er ting som er uforståelige for menneskesinnet". Og så prøver noen å tilpasse det som et argument mot materialisme, mens andre tvert imot beviser med dens hjelp at det ikke finnes noen Gud. Det er morsomt ikke bare at begge sider ikke kan ha rett samtidig, men også at verken den ene eller den andre gidder å finne ut hva denne teoremet faktisk sier.

Hva så? Nedenfor vil jeg prøve å "på fingrene" for å snakke om det. Min utstilling vil selvfølgelig ikke være streng og intuitiv, men jeg vil be matematikere om ikke å dømme meg strengt. Det er mulig at for ikke-matematikere (som jeg faktisk også tilhører) vil det være noe nytt og nyttig i det som blir fortalt nedenfor.

Matematisk logikk er faktisk en ganske komplisert vitenskap, og viktigst av alt, ikke veldig kjent. Det krever forsiktige og strenge manøvrer, der det er viktig å ikke forveksle det virkelig beviste med det faktum at «det allerede er klart». Imidlertid håper jeg at for å forstå følgende "omriss av beviset på TGN", trenger leseren bare kunnskap om skolematematikk / informatikk, logiske tenkningsferdigheter og 15-20 minutter tid.

Litt forenklet hevder TGN at det er nok vanskelige språk det er udokumenterte utsagn. Men i denne setningen trenger nesten hvert ord en forklaring.

La oss starte med å prøve å finne ut hva et bevis er. La oss ta en skoleoppgave i aritmetikk. La det for eksempel kreves å bevise riktigheten av følgende ukompliserte formel: "" (jeg minner deg om at symbolet leses "for enhver" og kalles "universell kvantifier"). Det kan bevises ved å transformere identisk, si slik:

Overgangen fra en formel til en annen skjer ifølge noen kjente regler. Overgangen fra den 4. formelen til den 5. skjedde, for eksempel, fordi hvert tall er lik seg selv - slik er aksiomet for aritmetikk. Og hele prosedyren for å bevise oversetter derfor formelen til den boolske verdien TRUE. Resultatet kan være FALSKT - hvis vi tilbakeviste en formel. I dette tilfellet vil vi bevise dens negasjon. Det er mulig å forestille seg et program (og slike programmer er faktisk skrevet) som vil bevise slike (og mer komplekse) påstander uten menneskelig innblanding.

La oss slå fast det samme litt mer formelt. Anta at vi har et sett som består av strenger av tegn i et eller annet alfabet, og det er regler som en delmengde av den s.k. uttalelser- det vil si grammatisk meningsfulle fraser, som hver er sann eller usann. Vi kan si at det er en funksjon som matcher utsagn fra en av to verdier: TRUE eller FALSE (det vil si tilordne dem til et boolsk sett med to elementer).

La oss kalle et slikt par - et sett med utsagn og en funksjon fra til - "språk for uttalelser". Merk at i daglig forstand er språkbegrepet noe bredere. For eksempel den russiske frasen "Vel, kom hit!" er ikke sant og ikke usant, det vil si fra et synspunkt av matematisk logikk, er det ikke et utsagn.

For det som følger trenger vi begrepet en algoritme. Jeg vil ikke gi dens formelle definisjon her - dette ville føre oss ganske langt til side. Jeg vil begrense meg til det uformelle: "algoritme"- denne sekvensen av entydige instruksjoner ("program"), som per endelig antall trinn konverterer inndata til utdata. Kursiv er grunnleggende viktig - hvis programmet blir hengt opp i noen innledende data, så beskriver det ikke algoritmen. For enkelhets skyld og i bruk i vårt tilfelle, kan leseren vurdere at en algoritme er et program skrevet på et hvilket som helst programmeringsspråk som er kjent for ham, som, for alle inndata fra en gitt klasse, er garantert å fullføre arbeidet med et boolsk resultat.

La oss spørre oss selv: er det en "bevisalgoritme" for hver funksjon (eller kort sagt, "deduktiv") tilsvarende denne funksjonen, det vil si å oversette hver setning til nøyaktig samme boolske verdi som den? Mer konsist kan det samme spørsmålet formuleres som følger: er hver funksjon over et sett med proposisjoner beregnelig? Som du allerede kan gjette, følger det av gyldigheten til TGN at nei, ikke noen - det er ikke-beregnbare funksjoner av denne typen. Med andre ord, ikke alle sanne utsagn kan bevises.

Det kan godt være at denne uttalelsen vil påføre deg en intern protest. Dette skyldes flere forhold. Først når vi blir undervist skolens matematikk, så er det noen ganger et feilaktig inntrykk av den nesten fullstendige identiteten til setningene "teoremet er sant" og "det er mulig å bevise eller verifisere teoremet". Men hvis du tenker deg om, er det slett ikke åpenbart. Noen teoremer bevises ganske enkelt (for eksempel ved oppregning av et lite antall alternativer), og noen er veldig vanskelige. Tenk for eksempel på Fermats berømte siste teorem:

beviset på dette ble funnet bare tre og et halvt århundre etter den første formuleringen (og det er langt fra elementært). Det er nødvendig å skille mellom sannheten i et utsagn og dets bevisbarhet. Det følger ikke fra noe sted at det ikke finnes sanne, men ubeviselige (og ikke fullt etterprøvbare) utsagn.

Det andre intuitive argumentet mot TGN er mer subtilt. Anta at vi har en ubeviselig (innenfor rammen av denne deduktive) påstanden. Hva hindrer oss i å akseptere det som et nytt aksiom? Dermed vil vi komplisere bevissystemet vårt litt, men dette er ikke forferdelig. Dette argumentet ville være helt korrekt hvis det var et begrenset antall ubevisbare påstander. I praksis kan følgende skje - etter å ha postulert et nytt aksiom, vil du snuble over et nytt ubeviselig utsagn. Ta det som et annet aksiom - du vil snuble over det tredje. Og så videre i det uendelige. De sier deductica vil bli ufullstendig. Vi kan også ta kraftfulle tiltak slik at bevisalgoritmen avsluttes etter et begrenset antall trinn med et eller annet resultat for enhver uttalelse av språket. Men samtidig vil han begynne å lyve - føre til sannheten for uriktige utsagn, eller til løgner - for de troende. I slike tilfeller sies det at deduktiv motstridende. Dermed høres enda en formulering av TGN slik ut: "Det er proposisjonelle språk som fullstendig konsistent deduktikk er umulig" - derav navnet på teoremet.

Noen ganger kalt "Gödels teorem" er påstanden om at enhver teori inneholder problemer som ikke kan løses innenfor rammen av selve teorien og krever dens generalisering. På en måte er dette sant, selv om en slik formulering skjuler problemet i stedet for å avklare det.

Jeg legger også merke til at hvis vi snakket om de vanlige funksjonene som viser settet reelle tall inn i det, så ville ikke "ikke-beregnbarheten" til funksjonen overraske noen (bare ikke bland sammen "beregnbare funksjoner" og "beregnbare tall" - dette er forskjellige ting). Ethvert skolebarn vet at, for eksempel, når det gjelder en funksjon, må du være veldig heldig med argumentet slik at prosessen med å beregne den eksakte desimalrepresentasjonen av verdien av denne funksjonen ender i et begrenset antall trinn. Og mest sannsynlig vil du beregne det ved hjelp av en uendelig serie, og denne beregningen vil aldri føre til eksakt resultat, selv om det kan komme så nært det du vil - ganske enkelt fordi verdien av sinusen til de fleste av argumentene er irrasjonell. TGN forteller oss ganske enkelt at selv blant funksjoner hvis argumenter er strenger og hvis verdier er null eller én, eksisterer også ikke-beregnbare funksjoner, selv om de er arrangert på en helt annen måte.

For det følgende beskriver vi språket formell aritmetikk". Tenk på en klasse med tekststrenger med endelig lengde, bestående av arabiske tall, variabler (bokstaver latinske alfabetet), tar naturverdier, mellomrom, karakterer aritmetiske operasjoner, likhet og ulikhet, kvantifiserere («finnes») og («for enhver») og kanskje noen andre symboler (deres nøyaktige antall og sammensetning er uviktige for oss). Det er tydelig at ikke alle slike linjer er meningsfulle (for eksempel er "" tull). Delmengden av meningsfulle uttrykk fra denne klassen (det vil si strenger som er sanne eller usanne når det gjelder vanlig aritmetikk) vil være vårt sett med utsagn.

Eksempler på formelle aritmetiske utsagn:

etc. La oss nå kalle en "formel med en ledig parameter" (FSP) en streng som blir en setning hvis et naturlig tall er erstattet med denne parameteren. Eksempler på FSP (med parameter):

etc. Med andre ord tilsvarer FSP-er funksjoner til et naturlig argument med en boolsk verdi.

Angi settet med alle FSP-er med bokstaven. Det er klart at det kan bestilles (for eksempel skriver vi først ut enbokstavsformler ordnet alfabetisk, etterfulgt av tobokstavsformler osv.; etter hvilket alfabet rekkefølgen skal skje er ikke grunnleggende for oss). Dermed tilsvarer enhver FSP nummeret i den bestilte listen, og vi vil betegne det .

La oss nå gå til en skisse av beviset for TGN i følgende formulering:

• For proposisjonsspråket for formell aritmetikk er det ingen fullstendig konsistent deduksjon.

Vi vil bevise ved selvmotsigelse.

Så la oss anta at en slik deduktiv eksisterer. La oss beskrive følgende hjelpealgoritme som tildeler en boolsk verdi til et naturlig tall som følger:

Enkelt sagt, algoritmen resulterer i verdien TRUE hvis og bare hvis resultatet av å erstatte sitt eget nummer i FSP-en i listen vår gir en falsk uttalelse.

Her kommer vi til det eneste stedet hvor jeg vil be leseren ta mitt ord for det.

Åpenbart, under antakelsen ovenfor, kan enhver FSP fra assosieres med en algoritme som inneholder et naturlig tall ved inngangen og en boolsk verdi ved utgangen. Mindre åpenbart er det motsatte:

Beviset for dette lemmaet ville i det minste kreve en formell, ikke en intuitiv, definisjon av begrepet en algoritme. Men hvis du tenker deg litt om, er det ganske plausibelt. Algoritmer er faktisk skrevet på algoritmiske språk, blant dem er det så eksotiske som for eksempel Brainfuck , som består av åtte ett-tegns ord, der uansett hvilken som helst algoritme kan implementeres. Det ville være rart om det rikere språket med formelle aritmetiske formler som vi har beskrevet skulle vise seg å være fattigere – selv om det uten tvil ikke egner seg særlig godt for vanlig programmering.

Etter å ha passert dette glatte stedet kommer vi raskt til slutten.

Så vi har beskrevet algoritmen ovenfor. I følge lemmaet jeg ba deg tro, eksisterer det en tilsvarende FSP. Den har et eller annet nummer på listen - la oss si . La oss spørre oss selv, hva er vitsen? La det være SANN. Så, i henhold til konstruksjonen av algoritmen (og derav funksjonen tilsvarende den), betyr dette at resultatet av å erstatte et tall i funksjonen er FALSE. Det motsatte krysses av på samme måte: fra FALSE følger TRUE. Vi har kommet til en selvmotsigelse, som betyr at den opprinnelige antagelsen er feil. For formell aritmetikk er det altså ingen fullstendig konsistent deduksjon. Q.E.D.

Her er det på sin plass å minne om Epimenides (se portrettet i tittelen), som, som du vet, erklærte at alle kretensere er løgnere, og er selv en kretenser. I en mer kortfattet formulering kan uttalelsen hans (kjent som «løgnerparadokset») formuleres som: «Jeg lyver». Det er nettopp et slikt utsagn, som selv forkynner sin falskhet, vi har brukt til beviset.

Avslutningsvis vil jeg bemerke at TGN ikke påstår noe spesielt overraskende. Tross alt har alle lenge vært vant til det faktum at ikke alle tall kan representeres som et forhold mellom to heltall (husk at denne uttalelsen har et veldig elegant bevis som er mer enn to tusen år gammelt?). Og røttene til polynomer med rasjonelle koeffisienter er heller ikke alle tall. Og nå viste det seg at ikke alle funksjonene til et naturlig argument er beregnelige.

Skissen av beviset som ble gitt var for formell aritmetikk, men det er ikke vanskelig å se at THN også gjelder mange andre proposisjonsspråk. Selvfølgelig er ikke alle språk slik. La oss for eksempel definere et språk som dette:

• "Hvilken som helst setning kinesisk er en sann påstand hvis den er inneholdt i sitatboken til kamerat Mao Tse Tung, og er feil hvis den ikke er inneholdt.

Da ser den tilsvarende komplette og konsistente bevisalgoritmen (den kan kalles "dogmatisk deduktiv") omtrent slik ut:

• «Bla gjennom kamerat Mao Tse Tungs sitatbok til du finner utsagnet du leter etter. Hvis det er funnet, så er det sant, og hvis sitatboken er over, og utsagnet ikke blir funnet, så er det usant.

Her er vi reddet av at enhver sitering åpenbart er begrenset, så prosessen med å "bevise" vil uunngåelig ta slutt. Dermed er TGN uanvendelig på språket til dogmatiske utsagn. Men vi snakket om komplekse språk, ikke sant?

Tags: Legg til tagger

09sen

Ethvert system av matematiske aksiomer, med utgangspunkt i et visst kompleksitetsnivå, er enten internt inkonsekvent eller ufullstendig.

I 1900 ble verdenskonferansen for matematikere holdt i Paris, hvor David Gilbert(David Hilbert, 1862–1943) skisserte i form av teser de 23 viktigste, etter hans mening, oppgavene som teoretikere i det kommende tjuende århundre måtte løse. Nummer to på listen hans var et av de enkle problemene som virker åpenbare helt til du graver litt dypere. I moderne termer var det spørsmålet: er matematikk tilstrekkelig alene? Hilberts andre oppgave ble redusert til behovet for å strengt bevise at systemet av aksiomer – grunnleggende utsagn tatt i matematikk som grunnlag uten bevis – er perfekt og fullstendig, det vil si at det tillater matematisk beskrivelse av alt som eksisterer. Det var nødvendig å bevise at det er mulig å sette et slikt system av aksiomer at de for det første vil være gjensidig konsistente, og for det andre kan man trekke en konklusjon fra dem angående sannheten eller usannheten til ethvert utsagn.

La oss ta et eksempel fra skolegeometri. I standard euklidisk planimetri (geometri på et plan) kan det ubetinget bevises at påstanden "summen av vinklene til en trekant er 180°" er sann, og utsagnet "summen av vinklene til en trekant er 137° " er falsk. I hovedsak, i euklidisk geometri, er enhver påstand enten usann eller sann, og den tredje er ikke gitt. Og på begynnelsen av det tjuende århundre trodde matematikere naivt at den samme situasjonen burde observeres i ethvert logisk konsistent system.

Og så i 1931 en eller annen wiener-brillede matematiker Kurt Gödel– tok og publiserte en kort artikkel som rett og slett veltet hele verden av såkalt «matematisk logikk». Etter lange og komplekse matematiske og teoretiske innledninger, etablerte han bokstavelig talt følgende. La oss ta ethvert utsagn som: "Antakelse #247 er logisk ubeviselig i dette aksiomsystemet" og kalle det "utsagn A". Så Gödel beviste ganske enkelt følgende fantastiske egenskap til ethvert system av aksiomer:

"Hvis en påstand A kan bevises, kan en ikke-A-påstand bevises."

Med andre ord, hvis det er mulig å bevise gyldigheten av påstanden "Forutsetning 247 er ikke bevisbar", så er det også mulig å bevise gyldigheten av påstanden "Antagelse 247 kan bevises". Det vil si å gå tilbake til formuleringen av det andre Hilbert-problemet, hvis systemet med aksiomer er komplett (det vil si at enhver påstand i det kan bevises), så er det inkonsekvent.

Den eneste veien ut av denne situasjonen er å akseptere et ufullstendig system av aksiomer. Det vil si at vi må tåle det faktum at i sammenheng med ethvert logisk system vil vi fortsatt ha "type A" utsagn som åpenbart er sanne eller usanne, og vi kan bedømme deres sannhet bare utenfor rammen av aksiomatikken vi har adoptert. Hvis det ikke finnes slike utsagn, så er vår aksiomatikk selvmotsigende, og innenfor dens ramme vil det uunngåelig være formuleringer som både kan bevises og tilbakevises.

Så formuleringen av Gödels første, eller svake, ufullstendighetsteorem er: "Ethvert formelt system av aksiomer inneholder uavklarte antakelser". Men Gödel stoppet ikke der, og formulerte og beviste Gödels andre eller sterke ufullstendighetsteorem: «Den logiske fullstendigheten (eller ufullstendigheten) til ethvert system av aksiomer kan ikke bevises innenfor rammen av dette systemet. For å bevise eller motbevise det, kreves det ytterligere aksiomer (styrking av systemet).

Det ville være tryggere å tro at Godels teoremer er abstrakte og ikke angår oss, men bare områder med sublim matematisk logikk, men faktisk viste det seg at de er direkte relatert til strukturen til den menneskelige hjernen. Den engelske matematikeren og fysikeren Roger Penrose (født 1931) viste det Gödels teoremer kan brukes til å bevise eksistensen av grunnleggende forskjeller mellom den menneskelige hjernen og en datamaskin. Poenget med resonnementet hans er enkelt. Datamaskinen opererer strengt logisk og er ikke i stand til å avgjøre om påstand A er sann eller usann hvis den går utover omfanget av aksiomatikk, og slike utsagn, ifølge Gödels teorem, eksisterer uunngåelig. En person, som står overfor et slikt logisk ubeviselig og ugjendrivelig utsagn A, er alltid i stand til å fastslå sannheten eller usannheten - basert på hverdagserfaring. I det minste i dette er den menneskelige hjernen overlegen en datamaskin lenket av rene logiske kretser. Den menneskelige hjernen er i stand til å forstå den fulle dybden av sannheten i Gödels teoremer, men en datamaskin kan man aldri. Derfor er den menneskelige hjernen alt annet enn en datamaskin. Han er i stand til å ta avgjørelser, og Turing-testen vil bestå.

om emnet: "GODELS TEOREM"

Kurt Gödel

Kurt Gödel er den største spesialisten på matematisk logikk- ble født 28. april 1906 i Brunn (nå Brno, Tsjekkia). Han ble uteksaminert fra universitetet i Wien, hvor han forsvarte sin doktoravhandling, var adjunkt i 1933–1938. Etter Anschluss emigrerte han til USA. Fra 1940 til 1963 jobbet Gödel ved Princeton Institute høyere studier. Gödel, æresdoktor fra Yale og Harvard Universities, stipendiat National Academy Sciences of the United States og American Philosophical Society.

I 1951 ble Kurt Gödel tildelt den høyeste vitenskapelige prisen i USA, Einstein-prisen. I en artikkel dedikert til denne hendelsen skrev en annen av vår tids største matematikere, John von Neumann: «Kurt Gödels bidrag til moderne logikk er virkelig monumentalt. Dette er mer enn bare et monument. Dette er en milepæl som skiller to epoker ... Det kan sies uten noen overdrivelse at Gödels arbeid fundamentalt endret selve faget logikk som vitenskap.

Faktisk viser til og med en tørr liste over Godels prestasjoner innen matematisk logikk at forfatteren deres i hovedsak la grunnlaget for hele deler av denne vitenskapen: teorien om modeller (1930; det såkalte teoremet om fullstendigheten av den smale predikatberegningen, som viser, grovt sett, tilstrekkeligheten av midlene til "formell logikk" for å bevise alle sanne setninger uttrykt på språket), konstruktiv logikk (1932–1933; resulterer i muligheten for å redusere noen klasser av klassiske logiske setninger til deres intuisjonistiske motstykker, som la grunnlaget for systematisk bruk av «fordypningsoperasjoner» som tillater en slik reduksjon av ulike logiske systemer hverandre), formell aritmetikk (1932–1933; resultater om muligheten for å redusere klassisk aritmetikk til intuisjonistisk aritmetikk, som på en måte viser konsistensen til den første med hensyn til den andre), teorien om algoritmer og rekursive funksjoner (1934; definisjon). av begrepet en generell rekursiv funksjon, som spilte avgjørende rolle ved å etablere den algoritmiske uløseligheten til serien kritiske spørsmål matematikk på den ene siden. Og i implementeringen av logiske og matematiske problemer på elektroniske datamaskiner - på den annen side), aksiomatisk settteori (1938; bevis på den relative konsistensen av valgaksiomet og Cantors kontinuumhypotese fra mengdelærens aksiomer, som markerte begynnelsen av serien nøkkelresultater om den relative konsistensen og uavhengigheten til settteoretiske prinsipper).

Godels ufullstendighetsteorem

Introduksjon

I 1931, i en av de tyske vitenskapelige tidsskrifter en relativt kort artikkel dukket opp med den ganske skremmende tittelen "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". Forfatteren var en tjuefem år gammel matematiker fra Universitetet i Wien, Kurt Gödel, som senere jobbet ved Princeton Institute for Advanced Study. Dette arbeidet spilte en avgjørende rolle i logikkens og matematikkens historie. I vedtaket Harvard University ved å tildele Gödel en æresdoktorgrad (1952), ble hun beskrevet som en av de største prestasjoner moderne logikk.

På publiseringstidspunktet var det imidlertid ingen tittel på Gödels verk. Verken innholdet sa noe til de fleste matematikere. Nevnt i tittelen, Principia Mathematica er Alfred North Whitehead og Bertrand Russells monumentale trebindsavhandling om matematisk logikk og grunnlaget for matematikk; kjennskap til avhandlingen var på ingen måte nødvendig tilstand til vellykket arbeid i de fleste grener av matematikken. Interessen for spørsmålene som behandles i Gödels arbeid har alltid vært partiet til en veldig liten gruppe forskere. Samtidig var argumentene som ble gitt av Gödel i bevisene hans så uvanlige for deres tid. At en fullstendig forståelse av dem krevde en eksklusiv kunnskap om emnet og kjennskap til litteraturen viet disse svært spesifikke problemene.

Første ufullstendighetsteorem

Gödels første ufullstendighetsteorem ser ut til å være det viktigste resultatet i matematisk logikk. Det høres slik ut:

For en vilkårlig konsistent formell og beregnbar teori der grunnleggende aritmetiske proposisjoner kan bevises, kan en sann aritmetisk proposisjon konstrueres hvis sannhet ikke kan bevises innenfor teoriens rammer. Med andre ord, enhver helt nyttig teori tilstrekkelig til å representere aritmetikk kan ikke være både konsistent og fullstendig.

Her betyr ordet "teori" " uendelig sett» utsagn, hvorav noen antas å være sanne uten bevis (slike utsagn kalles aksiomer), mens andre (setninger) kan avledes fra aksiomer, og derfor antas (vistes) å være sanne. Uttrykket "beviselig i teorien" betyr "utledet fra teoriens aksiomer og primitiver (konstante symboler i alfabetet) ved bruk av standard (førsteordens) logikk." En teori er konsistent (konsistent) hvis det er umulig å bevise et motstridende utsagn i den. Uttrykket "kan bygges" betyr at det er en eller annen mekanisk prosedyre (algoritme) som kan bygge et utsagn basert på aksiomer, primitiver og førsteordens logikk. "Elementær aritmetikk" er tilstedeværelsen av operasjoner med addisjon og multiplikasjon over naturlige tall. Den resulterende sanne, men ubeviselige påstanden omtales ofte for en gitt teori som "Gödel-sekvensen", men det er et uendelig antall andre påstander i teorien som har den samme egenskapen til å være ubevisbare innenfor teorien.

Antakelsen om at teorien er beregnelig betyr at det i prinsippet er mulig å implementere en datamaskinalgoritme ( dataprogram) som (hvis tillatt å beregne vilkårlig lange tider, opp til uendelig) beregner en liste over alle teoriens teoremer. Faktisk er det tilstrekkelig å beregne bare listen over aksiomer, og alle teoremer kan effektivt utledes fra en slik liste.

Det første ufullstendighetsteoremet fikk tittelen "Theorem VI" i Gödels artikkel fra 1931. Om formelt uavgjørelige påstander i Principia Mathematica og relaterte systemer I. I Gödels originalinnspilling hørtes det slik ut:

"Den generelle konklusjonen om eksistensen av uavgjørlige påstander er denne:

Teorem VI .

For hver ω-konsistente rekursive klasse k FORMEL det er rekursive TEGN r slik at verken (v Gen r), heller ikke ¬( v Gen r)hører ikke til Flg (k)(hvor v er GRATIS VARIABEL r ) ».

Betegnelse Flg kommer fra ham. Folgerungsmenge- sett med sekvenser, Gen kommer fra ham. generalisering- generalisering.

Grovt sett, Gödels uttalelse G hevder: "sannhet G kan ikke bevises." Hvis G kunne bevises innenfor teorien, så ville teorien inneholde et teorem som motsier seg selv, og derfor ville teorien være inkonsekvent. Men hvis G ubeviselig, så er det sant, og derfor er teorien ufullstendig (utsagnet G ikke utledes i den).

Denne forklaringen er den vanlige naturlig språk, og derfor ikke helt matematisk strenge. For å gi et strengt bevis, nummererte Gödel uttalelser med naturlige tall. I dette tilfellet hører teorien som beskriver tall også til settet med proposisjoner. Spørsmål om bevisbarheten til proposisjoner kan representeres i denne saken i form av spørsmål om egenskapene til de naturlige tallene, som må kunne beregnes dersom teorien er fullstendig. I disse vilkårene sier Gödels uttalelse at det ikke finnes et tall med en bestemt egenskap. Et tall med denne egenskapen vil være bevis på teoriens inkonsekvens. Hvis et slikt tall eksisterer, er teorien inkonsekvent, i motsetning til den opprinnelige antagelsen. Så forutsatt at teorien er konsistent (som premisset for teoremet antyder), viser det seg at det ikke finnes et slikt tall, og Gödels utsagn er sann, men dette kan ikke bevises innenfor rammen av teorien (derfor er teorien ufullstendig) . En viktig konseptuell merknad er at man må anta at en teori er konsistent for å erklære Gödels utsagn som sann.

Gödels andre ufullstendighetsteorem

Gödels andre ufullstendighetsteorem lyder som følger:

For enhver formelt rekursivt opptalbar (det vil si effektivt generert) teori T, inkludert grunnleggende aritmetiske sannhetsutsagn og visse formelle bevisbarhetsutsagn, denne teorien T inkluderer en uttalelse om dens konsistens hvis og bare hvis teorien T er inkonsistent.

Konsistens er med andre ord nok rik teori kan ikke bevises ved hjelp av denne teorien. Det kan imidlertid godt vise seg at konsistensen av én bestemt teori kan etableres ved hjelp av en annen, kraftigere formell teori. Men så oppstår spørsmålet om konsistensen av denne andre teorien, og så videre.

Mange har forsøkt å bruke denne teoremet for å bevise at intelligent aktivitet ikke kan reduseres til beregninger. For eksempel, tilbake i 1961, kom den berømte logikeren John Lucas med et lignende program. Resonnementet hans viste seg å være ganske sårbart – han satte imidlertid oppgaven bredere. Roger Penrose tar en litt annen tilnærming, som presenteres i boken fullstendig, «fra scratch».

Diskusjoner

Konsekvensene av teoremer påvirker matematikkens filosofi, spesielt de formalismene som bruker formell logikkå definere deres prinsipper. Man kan omformulere den første ufullstendighetsteoremet som følger: det er umulig å finne et omfattende system av aksiomer som vil være i stand til å bevise alle matematiske sannheter, og ikke en eneste løgn". På den annen side, fra et synspunkt av streng formalitet, gir ikke denne omformuleringen mye mening, siden den forutsetter at begrepene "sann" og "usannhet" defineres i absolutt forstand, snarere enn i en relativ forstand. hvert enkelt system.