De onvolledigheidsstellingen van Gödel hebben een filosofische betekenis. Bekentenis van een geweldige logicus

Onvolledigheidsstelling van Godel

Uspensky V.A.

Misschien is de onvolledigheidsstelling van Gödel echt uniek. Uniek omdat ze ernaar verwijzen wanneer ze "alles in de wereld" willen bewijzen - van de aanwezigheid van goden tot de afwezigheid van rede. Ik ben altijd geïnteresseerd geweest in een meer "primaire vraag" - en wie van degenen die naar de onvolledigheidsstelling verwijzen, zou deze niet alleen kunnen formuleren, maar ook kunnen bewijzen? Ik post Dit artikel om de reden dat het een zeer toegankelijke formulering van de stelling van Gödel is. Ik raad je aan eerst het artikel van Tullio Regge Kurt Gödel en zijn beroemde stelling te lezen

De conclusie over de onmogelijkheid van een universeel waarheidscriterium is een direct gevolg van het resultaat dat Tarski heeft verkregen door de onbeslisbaarheidsstelling van Gödel te combineren met zijn eigen waarheidstheorie, volgens welke er zelfs voor een relatief smal gebied geen universeel waarheidscriterium kan zijn van de getaltheorie, en dus voor elke wetenschap die rekenkunde gebruikt. Uiteraard is dit resultaat a fortiori van toepassing op het waarheidsbegrip in elk niet-wiskundig kennisgebied waarin rekenen wijdverbreid wordt gebruikt.

Karl Popper

Uspensky Vladimir Andreevich werd geboren op 27 november 1930 in Moskou. Afgestudeerd aan de Faculteit Mechanica en Wiskunde van de Staatsuniversiteit van Moskou (1952). Doctor in de fysische en wiskundige wetenschappen (1964). Professor, hoofd van de afdeling Wiskundige Logica en Theorie van Algoritmen van de Faculteit Mechanica en Wiskunde (1966). Leest lessenreeksen "Inleiding tot wiskundige logica", "Berekenbare functies", "De volledigheidsstelling van Gödel". 25 kandidaten en 2 doctoren in de wetenschappen voorbereid

1. Verklaring van het probleem

De onvolledigheidsstelling, waarvan we de exacte formulering aan het einde van dit hoofdstuk zullen geven, en misschien later (als de lezer hierin geïnteresseerd is) en het bewijs, zegt ongeveer het volgende: onder bepaalde voorwaarden in elke taal zijn er waar, maar niet te bewijzen uitspraken.

Als we een stelling op deze manier formuleren, heeft bijna elk woord uitleg nodig. Daarom zullen we beginnen met het uitleggen van de betekenis van de woorden die we in deze formulering gebruiken.

1.1. Taal

We zullen niet de meest algemeen mogelijke definitie van een taal geven, maar ons liever beperken tot die taalconcepten die we later nodig zullen hebben. Er zijn twee van dergelijke concepten: "het alfabet van de taal" en "de verzameling ware uitspraken van de taal".

1.1.1. Alfabet

Met alfabet bedoelen we een eindige reeks elementaire tekens (dat wil zeggen, dingen die niet kunnen worden opgesplitst in samenstellende delen). Deze tekens worden letters van het alfabet genoemd. Met het woord van het alfabet bedoelen we: laatste reeks brieven. Zo zijn gewone woorden in het Engels (inclusief eigennamen) woorden van het 54-letterige alfabet (26 kleine letters, 26 hoofdletters, een streepje en een apostrof). Een ander voorbeeld zijn de natuurlijke getallen in decimale notatie zijn woorden van het 10-letteralfabet, waarvan de letters tekens zijn: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Om alfabetten aan te duiden, gebruiken we gewone hoofdletters. Als L een alfabet is, dan L? geeft de verzameling van alle woorden van het alfabet L aan, - woorden gevormd uit de letters. We nemen aan dat elke taal zijn eigen alfabet heeft, zodat alle uitdrukkingen van deze taal (dwz - namen van verschillende objecten, uitspraken over deze objecten, enz.) woorden van dit alfabet zijn. Bijvoorbeeld elk voorstel van de Engelse taal, evenals elke tekst die in het Engels is geschreven, kan worden beschouwd als een woord van het uitgebreide alfabet van 54 letters, dat ook leestekens, interwoordruimte, een rood lijnteken en mogelijk enkele andere nuttige tekens bevat. Ervan uitgaande dat taaluitdrukkingen woorden van een of ander alfabet zijn, sluiten we dus "meerlaagse" uitdrukkingen zoals ???f(x)dx uit. Deze beperking is echter niet al te belangrijk, aangezien elke dergelijke uitdrukking, met behulp van geschikte conventies, kan worden "uitgerekt" tot een lineaire vorm. Elke set M in L? wordt een woordverzameling van het alfabet L genoemd. Als we simpelweg zeggen dat M een woordverzameling is, dan bedoelen we dat het een woord is van een of ander alfabet. Nu kan de bovenstaande taalaanname als volgt worden geherformuleerd: in elke taal is elke reeks uitdrukkingen een woordenreeks.

1.1.2. Veel echte claims

We nemen aan dat we een deelverzameling T krijgen van de verzameling L? (waarbij L het alfabet is van een taal die we overwegen), die de verzameling "ware uitspraken" (of gewoon "waarheden") wordt genoemd. Als we direct overgaan op de deelverzameling T, laten we de volgende tussenliggende redeneerstappen weg: ten eerste, welke woorden van het alfabet L zijn goedgevormde uitdrukkingen van de taal, dat wil zeggen met bepaalde waarde in onze interpretatie van deze taal (bijvoorbeeld, 2+3, x+3, x=y, x=3, 2=3, 2=2 zijn goedgevormde uitdrukkingen, terwijl uitdrukkingen zoals +=x dat niet zijn); ten tweede, welke uitdrukkingen formules zijn, d.w.z. kan afhangen van een parameter (bijv. x=3, x=y, 2=3, 2=2); ten derde, welke van de formules zijn gesloten formules, d.w.z. instructies die niet afhankelijk zijn van parameters (bijvoorbeeld 2=3, 2=2); en tot slot, welke gesloten formules ware uitspraken zijn (bijvoorbeeld 2=2).

1.1.3. Fundamenteel talenpaar

1.2. "Onbewijsbaar"

"Onbewijsbaar" betekent geen bewijs hebben.

1.3. Een bewijs

Ondanks het feit dat de term "bewijs" misschien wel een van de belangrijkste in de wiskunde is (de Bourbaki beginnen hun boek "Fundamentals of Mathematics" met de woorden: "Vanaf de tijd van de oude Grieken betekende het zeggen van "wiskunde" hetzelfde als zeggen "bewijs""), heeft hij geen precieze definitie. In het algemeen behoort het begrip bewijs met al zijn semantische takken eerder tot het terrein van de psychologie dan tot de wiskunde. Maar hoe het ook zij, bewijs is gewoon een argument dat we zelf heel overtuigend vinden om alle anderen te overtuigen.

Wanneer het wordt opgeschreven, wordt het bewijs een woord in een of ander alfabet P, net als elk ander Engelse tekst is een woord van het alfabet L, waarvan hierboven een voorbeeld werd gegeven. De verzameling van alle bewijzen vormt een deelverzameling (en een behoorlijk grote deelverzameling) van de verzameling P?. We zullen niet proberen een precieze definitie te geven van dit zowel "naïeve" als "absolute" concept van bewijs, of - wat equivalent is - om de overeenkomstige deelverzameling van P? te definiëren. In plaats daarvan zullen we een formeel analoog van dit vage concept beschouwen, waarvoor we in wat volgt nog steeds de term "bewijs" zullen gebruiken. Deze analoog heeft twee zeer belangrijke kenmerken die hem onderscheiden van het intuïtieve concept (hoewel het intuïtieve idee van het bewijs deze kenmerken tot op zekere hoogte nog steeds weerspiegelt). Allereerst nemen we aan dat er verschillende concepties van bewijs zijn, dat wil zeggen dat verschillende subsets van bewijzen in P? zijn toegestaan, en zelfs meer dan dat: we zullen in feite aannemen dat het alfabet van bewijzen van P zelf kan veranderen . In wat volgt, zullen we eisen dat er voor elk dergelijk bewijsconcept een efficiënte methode is, met andere woorden, een algoritme dat noodzakelijkerwijs zou bepalen of gegeven woord alfabet P-bewijs of niet. We gaan er ook van uit dat er een algoritme is dat altijd kan bepalen welke uitspraak bewijst bewijs geleverd. (In veel situaties is de bewering die wordt bewezen gewoon de laatste bewering in de reeks stappen die het bewijs vormen.)

Onze definitieve formulering van de definitie is dus als volgt:

(1) We hebben het alfabet L (het alfabet van de taal) en het alfabet P (het alfabet van het bewijs).

(2) We krijgen een verzameling P die een deelverzameling is van P? en waarvan de elementen "bewijzen" worden genoemd. In het volgende nemen we aan dat we ook een algoritme hebben waarmee we kunnen bepalen of een willekeurig woord van het alfabet P een element is van de verzameling P, dat wil zeggen een bewijs, of niet.

(3) Hebben we ook een functie? (voor het vinden van wat er precies is bewezen), wiens domein is? voldoet aan de voorwaarde P???P?, en wiens bereik ligt in P?. We nemen aan dat we een algoritme hebben dat deze functie berekent (de exacte betekenis van de woorden "algoritme berekent een functie" is de volgende: de waarden van de functie worden verkregen met behulp van dit algoritme - een reeks speciale transformatieregels). We zullen zeggen dat het element p? P is een bewijs van het woord?(p) van het alfabet L.

Trojka<Р, Р, ?>, die aan de voorwaarden (1)-(3) voldoet, wordt een deductief systeem genoemd over het alfabet L.

Voor de lezer die bekend is met de gebruikelijke manier om "bewijs" te definiëren in termen van "axioma" en "inferentieregel", zullen we nu uitleggen hoe deze methode kan worden beschouwd als een speciaal geval van de definitie gegeven in paragraaf 1.3.2. Dat wil zeggen, een bewijs wordt meestal gedefinieerd als een reeks van dergelijke taaluitingen, die elk ofwel een axioma zijn of eerder verkregen zijn uit reeds bestaande uitspraken met behulp van een van de afleidingsregels. Als we een nieuw woord * toevoegen aan het alfabet van onze taal, dan kunnen we zo'n bewijs schrijven als een woord dat is samengesteld met behulp van het resulterende alfabet: de reeks uitdrukkingen wordt het woord C1*C2*...*Cn. In dit geval heeft de functie die bepaalt wat precies is bewezen, zijn waarde in het deel van dit woord dat onmiddellijk volgt op de laatste letter * in de reeks. Het algoritme waarvan het bestaan vereist is in paragraaf 1.3.2. definities, kunnen gemakkelijk worden geconstrueerd als we eenmaal een van de geaccepteerde betekenissen van de woorden "axioma" en "inferentieregel" precies hebben gedefinieerd.

1.4 Pogingen om de onvolledigheidsstelling nauwkeurig te formuleren

1.4.1. Eerste poging

"Onder bepaalde voorwaarden voor het fundamentele paar van de taal van het alfabet L en het deductieve systeem<Р, Р, ?>boven L is er altijd een woord in T dat geen bewijs heeft. Deze optie ziet er nog steeds vaag uit. In het bijzonder kunnen we gemakkelijk zoveel deductieve systemen bedenken als we willen, met heel weinig bewijsbare woorden. ?) er zijn geen woorden dat zou in ieder geval bewijs hebben.

1.4.2. Tweede poging

Er is nog een, meer natuurlijke benadering. Stel dat we een taal krijgen - in de zin dat we een fundamenteel paar van deze taal krijgen. Nu gaan we op zoek naar een deductief systeem over L (intuïtief zoeken we een bewijstechniek) waarmee we kunnen bewijzen hoe meer woorden van T, in de limiet alle woorden uit T. De stelling van Gödel beschrijft een situatie waarin zo'n deductief systeem (waarmee elk woord in T bewijsbaar zou zijn) niet bestaat. Daarom willen we de volgende stelling formuleren:

"Onder bepaalde voorwaarden met betrekking tot het fundamentele paar, is er geen dergelijk deductief systeem waarin elk woord van T een bewijs zou hebben."

Een dergelijke verklaring is echter duidelijk onjuist, omdat het alleen nodig is om een deductief systeem te nemen waarin P = L, P = P? en?(p) = p voor alle p in P?; dan elk woord van L? is triviaal aantoonbaar. Daarom moeten we enige beperking accepteren van de deductieve systemen die we gebruiken.

1.5. Samenhang

Het zou heel natuurlijk zijn om te eisen dat alleen "ware uitspraken", dat wil zeggen alleen woorden van T, kunnen worden bewezen. We zullen zeggen dat het deductieve systeem<Р, Р, ?>is consistent met betrekking tot een fundamenteel paar als?(P)?T. In alle volgende redeneringen zullen we alleen geïnteresseerd zijn in dergelijke consistente deductieve systemen. Als we een taal krijgen, zou het buitengewoon verleidelijk zijn om zo'n consistent deductief systeem te vinden waarin elke ware bewering een bewijs zou hebben. De variant van de stelling van Gödel die ons interesseert, stelt precies dat het onder bepaalde voorwaarden met betrekking tot het fundamentele paar onmogelijk is om zo'n deductief systeem te vinden.

1.6. volledigheid

Er wordt gezegd dat het deductieve systeem<Р,Р,?>is compleet met betrekking tot het fundamentele paar, op voorwaarde dat?(P)?T. Dan heeft onze formulering van de onvolledigheidsstelling de volgende vorm:

Onder bepaalde voorwaarden met betrekking tot het fundamentele paar is er geen dergelijk deductief systeem<Р,Р,?>boven L zou dat zowel volledig als relatief consistent zijn.

Bibliografie

Voor de voorbereiding van dit werk is gebruik gemaakt van materiaal van de site http://filosof.historic.ru.

Een van de meest bekende stellingen wiskundige logica geluk en pech tegelijk. Hierin is ze als speciale theorie Einsteins relativiteit. Aan de ene kant heeft bijna iedereen wel iets over hen gehoord. Aan de andere kant, in de populaire interpretatie, de theorie van Einstein, zoals u weet, "zegt dat alles in de wereld relatief is". En de onvolledigheidsstelling van Gödel (hierna simpelweg TGN), in een ongeveer even vrije volksformulering, "bewijst dat er dingen zijn die onbegrijpelijk zijn voor de menselijke geest". En dus proberen sommigen het aan te passen als een argument tegen het materialisme, terwijl anderen juist met haar hulp bewijzen dat er geen god is. Het is niet alleen grappig dat beide kanten niet tegelijkertijd gelijk kunnen hebben, maar ook dat noch de een noch de ander de moeite neemt om uit te zoeken wat deze stelling in feite zegt.

En dan? Hieronder zal ik proberen om "op de vingers" om erover te praten. Mijn uiteenzetting zal natuurlijk niet rigoureus en intuïtief zijn, maar ik zal wiskundigen vragen om mij niet streng te beoordelen. Het is mogelijk dat voor niet-wiskundigen (waartoe ik in feite ook behoor), er iets nieuws en nuttigs zal zijn in wat hieronder wordt verteld.

Wiskundige logica is inderdaad een nogal gecompliceerde wetenschap, en vooral niet erg vertrouwd. Het vereist zorgvuldige en strikte manoeuvres, waarbij het belangrijk is om het echt bewezen niet te verwarren met het feit dat "het al duidelijk is". Ik hoop echter dat de lezer, om het volgende "overzicht van het bewijs van TGN" te begrijpen, alleen kennis nodig heeft van schoolwiskunde / informatica, vaardigheden logisch denken en 15-20 minuten tijd.

Enigszins vereenvoudigd beweert TGN dat het genoeg is moeilijke talen er zijn ongefundeerde verklaringen. Maar in deze zin heeft bijna elk woord een uitleg nodig.

Laten we beginnen met uit te zoeken wat een bewijs is. Laten we een schoolprobleem in rekenen nemen. Laat het bijvoorbeeld nodig zijn om de juistheid van de volgende ongecompliceerde formule te bewijzen: "" (ik herinner u eraan dat het symbool wordt gelezen "voor elke" en de "universele kwantor" wordt genoemd). Het kan worden bewezen door identiek te transformeren, laten we zeggen, als volgt:

De overgang van de ene formule naar de andere gebeurt volgens sommigen bekende regels. De overgang van de 4e formule naar de 5e vond bijvoorbeeld plaats omdat elk getal gelijk is aan zichzelf - dat is het axioma van de rekenkunde. En de hele procedure van bewijzen vertaalt de formule dus in de booleaanse waarde TRUE. Het resultaat zou ONWAAR kunnen zijn - als we een formule zouden weerleggen. In dit geval zouden we de ontkenning ervan bewijzen. Het is mogelijk om je een programma voor te stellen (en zulke programma's zijn ook echt geschreven) dat zulke (en complexere) stellingen zou bewijzen zonder menselijke tussenkomst.

Laten we hetzelfde wat formeler stellen. Stel dat we een verzameling hebben die bestaat uit tekenreeksen van een of ander alfabet, en dat er regels zijn volgens welke een subset van de zogenaamde uitspraken- dat wil zeggen, grammaticaal zinvolle zinnen, die elk waar of onwaar zijn. We kunnen zeggen dat er een functie is die overeenkomt met uitspraken van een van de twee waarden: TRUE of FALSE (dat wil zeggen, ze worden toegewezen aan een Booleaanse set van twee elementen).

Laten we zo'n paar - een set instructies en een functie van tot - noemen "taal van uitspraken". Merk op dat in de alledaagse zin het begrip taal iets ruimer is. Bijvoorbeeld de Russische uitdrukking "Nou, kom hier!" is niet waar en niet onwaar, dat wil zeggen, vanuit het oogpunt van wiskundige logica is het geen bewering.

Voor wat volgt hebben we de notie van een algoritme nodig. Ik zal hier niet de formele definitie geven - dit zou ons behoorlijk ver op een zijspoor brengen. Ik beperk me tot het informele: "algoritme"- deze opeenvolging van ondubbelzinnige instructies ("programma"), die per eindig getal stappen zet invoergegevens om in uitvoer. Het cursieve is van fundamenteel belang - als het programma vastloopt bij een aantal initiële gegevens, dan beschrijft het het algoritme niet. Voor de eenvoud en in toepassing op ons geval, kan de lezer overwegen dat een algoritme een programma is dat is geschreven in een programmeertaal die hem bekend is en dat, voor alle invoergegevens van een bepaalde klasse, gegarandeerd zijn werk voltooit met een Booleaans resultaat.

Laten we ons de vraag stellen: is er een “bewijsalgoritme” voor elke functie (of, kortom, "deductief") equivalent aan deze functie, dat wil zeggen dat elke instructie wordt vertaald in exact dezelfde booleaanse waarde als deze? Korter gezegd kan dezelfde vraag als volgt worden geformuleerd: is elke functie boven een verzameling stellingen? berekenbaar? Zoals je al kunt raden, volgt uit de geldigheid van TGN dat nee, geen - er zijn niet-berekenbare functies van dit type. Met andere woorden, niet elke ware bewering kan worden bewezen.

Het kan heel goed zijn dat deze verklaring bij u intern protest oproept. Dit komt door verschillende omstandigheden. Ten eerste, als we worden onderwezen school wiskunde, dan is er soms een verkeerde indruk van de bijna volledige identiteit van de zinnen "de stelling is waar" en "het is mogelijk om de stelling te bewijzen of te verifiëren". Maar als je erover nadenkt, is het helemaal niet duidelijk. Sommige stellingen worden heel eenvoudig bewezen (bijvoorbeeld door een klein aantal opties op te sommen), en sommige zijn erg moeilijk. Denk bijvoorbeeld aan de beroemde laatste stelling van Fermat:

waarvan het bewijs pas drie en een halve eeuw na de eerste formulering werd gevonden (en het is verre van elementair). Het is noodzakelijk om onderscheid te maken tussen de waarheid van een bewering en de bewijsbaarheid ervan. Het volgt nergens uit dat er geen ware, maar onbewijsbare (en niet volledig verifieerbare) uitspraken zijn.

Het tweede intuïtieve argument tegen TGN is subtieler. Stel dat we een soort van onbewijsbare (in het kader van deze deductieve) verklaring hebben. Wat weerhoudt ons ervan het als een nieuw axioma te aanvaarden? We zullen ons bewijssysteem dus een beetje ingewikkelder maken, maar dit is niet verschrikkelijk. Dit argument zou absoluut correct zijn als er een eindig aantal onbewijsbare proposities zou zijn. In de praktijk kan het volgende gebeuren: na het postuleren van een nieuw axioma, stuit je op een nieuwe onbewijsbare bewering. Neem het als een ander axioma - je zult struikelen over de derde. En zo verder tot in het oneindige. Ze zeggen dat deductica blijft incompleet. We kunnen ook krachtige maatregelen nemen zodat het bewijsalgoritme eindigt na een eindig aantal stappen met enig resultaat voor elke uitspraak van de taal. Maar tegelijkertijd zal hij beginnen te liegen - leiden tot de waarheid voor onjuiste verklaringen, of tot leugens - voor de gelovigen. In dergelijke gevallen wordt gezegd dat de deductieve tegenstrijdig. Zo klinkt nog een formulering van TGN als volgt: "Er zijn propositietalen waarvoor volledige consistente deducties onmogelijk zijn" - vandaar de naam van de stelling.

Soms ook wel de "stelling van Gödel" genoemd, is de bewering dat elke theorie problemen bevat die niet kunnen worden opgelost binnen het kader van de theorie zelf en die veralgemening vereisen. In zekere zin is dit waar, hoewel een dergelijke formulering de kwestie eerder verdoezelt dan verduidelijkt.

Ik merk ook op dat als we het hadden over de gebruikelijke functies die de set weergeven echte getallen erin, dan zou de "niet-berekenbaarheid" van de functie niemand verbazen (verwar "berekenbare functies" en "berekenbare getallen" niet - dit zijn verschillende dingen). Elk schoolkind weet dat, laten we zeggen, in het geval van een functie, je veel geluk moet hebben met het argument, zodat het proces van het berekenen van de exacte decimale representatie van de waarde van deze functie eindigt in een eindig aantal stappen. En hoogstwaarschijnlijk bereken je het met een oneindige reeks, en deze berekening zal nooit leiden tot exact resultaat, hoewel het er zo dicht bij kan komen als je wilt - simpelweg omdat de waarde van de sinus van de meeste argumenten irrationeel is. TGN vertelt ons eenvoudig dat zelfs onder functies waarvan de argumenten strings zijn en waarvan de waarden nul of één zijn, er ook niet-berekenbare functies bestaan, hoewel ze op een geheel andere manier zijn gerangschikt.

Voor wat volgt, zullen we de "taal van de formele rekenkunde" beschrijven. Beschouw een klasse van tekstreeksen van eindige lengte, bestaande uit Arabische cijfers, variabelen (letters Latijns alfabet), natuurlijke waarden, spaties, tekens gebruiken rekenkundige bewerkingen, gelijkheid en ongelijkheid, kwantoren ("bestaat") en ("voor elk") en misschien enkele andere symbolen (hun exacte aantal en samenstelling zijn voor ons niet belangrijk). Het is duidelijk dat niet al dergelijke regels zinvol zijn (bijvoorbeeld "" is onzin). De subset van betekenisvolle uitdrukkingen van deze klasse (dat wil zeggen, tekenreeksen die waar of onwaar zijn in termen van gewone rekenkunde) zal onze reeks uitspraken zijn.

Voorbeelden van formele rekenkundige uitspraken:

enz. Laten we nu een "formule met een vrije parameter" (FSP) een tekenreeks noemen die een instructie wordt als we deze als deze parameter vervangen natuurlijk nummer. Voorbeelden van FSP (met parameter):

enz. Met andere woorden, FSP's zijn equivalent aan functies van een natuurlijk argument met een Booleaanse waarde.

Geef de verzameling van alle FSP's aan met de letter . Het is duidelijk dat het geordend kan worden (we schrijven bijvoorbeeld eerst formules van één letter alfabetisch geordend, gevolgd door formules van twee letters, enz.; het is voor ons niet fundamenteel in welk alfabet de volgorde zal plaatsvinden). Elke FSP komt dus overeen met zijn nummer in de geordende lijst, en we zullen het aanduiden .

Laten we nu overgaan tot een schets van het bewijs van TGN in de volgende formulering:

Voor de propositietaal van de formele rekenkunde is er geen volledig consistente deductie.

We zullen bewijzen door tegenspraak.

Dus laten we aannemen dat zo'n deductief bestaat. Laten we het volgende hulpalgoritme beschrijven dat als volgt een booleaanse waarde toewijst aan een natuurlijk getal:

Simpel gezegd, het algoritme resulteert in de waarde TRUE als en alleen als het resultaat van het vervangen van zijn eigen nummer in onze lijst in de FSP een valse verklaring geeft.

Hier komen we bij de enige plaats waar ik de lezer zal vragen om mij op mijn woord te geloven.

Het is duidelijk dat, onder de bovenstaande aanname, elke FSP van kan worden geassocieerd met een algoritme dat een natuurlijk getal aan de invoer en een Booleaanse waarde aan de uitvoer bevat. Minder voor de hand liggend is het tegenovergestelde:

Het bewijs van dit lemma zou op zijn minst een formele, niet intuïtieve, definitie van het begrip algoritme vereisen. Als je er echter een beetje over nadenkt, is het heel aannemelijk. Algoritmen zijn inderdaad geschreven in algoritmische talen, waaronder exotische talen zoals Brainfuck, dat bestaat uit acht woorden van één teken, waarin niettemin elk algoritme kan worden geïmplementeerd. Het zou vreemd zijn als de rijkere taal van formele rekenkundige formules die we hebben beschreven armer zou blijken te zijn - hoewel het ongetwijfeld niet erg geschikt is voor gewoon programmeren.

Na het passeren van deze glibberige plek komen we snel aan het einde.

Daarom hebben we het algoritme hierboven beschreven. Volgens het lemma dat ik je vroeg te geloven, bestaat er een equivalente FSP. Het heeft een nummer in de lijst - laten we zeggen . Laten we ons afvragen, wat heeft het voor zin? Laat het WAAR zijn. Dan, volgens de constructie van het algoritme (en dus de functie die er equivalent aan is), betekent dit dat het resultaat van het vervangen van een getal in de functie ONWAAR is. Het tegenovergestelde wordt op dezelfde manier gecontroleerd: uit ONWAAR volgt op WAAR. We zijn tot een contradictie gekomen, wat betekent dat de oorspronkelijke veronderstelling onjuist is. Voor formele rekenkunde is er dus geen volledige consistente aftrek. QED

Hier is het passend om Epimenides in herinnering te roepen (zie het portret in de titel), die, zoals u weet, verklaarde dat alle Kretenzers leugenaars zijn, omdat hij zelf een Kretenzer is. In een meer beknopte formulering kan zijn verklaring (bekend als de "leugenparadox") worden geformuleerd als: "Ik lieg." Het is precies zo'n verklaring, die zelf haar onwaarheid verkondigt, die we voor het bewijs hebben gebruikt.

Tot slot wil ik opmerken dat TGN niets bijzonders beweert. Iedereen is er immers al lang aan gewend dat niet alle getallen kunnen worden weergegeven als een verhouding van twee gehele getallen (weet je nog, deze uitspraak heeft een zeer elegant bewijs dat meer dan tweeduizend jaar oud is?). En de wortels van veeltermen met rationale coëfficiënten zijn ook niet allemaal getallen. En nu bleek dat niet alle functies van een natuurlijk argument berekenbaar zijn.

De schets van het gegeven bewijs was voor formeel rekenen, maar het is niet moeilijk in te zien dat THN ook voor veel andere propositietalen geldt. Natuurlijk zijn niet alle talen zo. Laten we bijvoorbeeld een taal als volgt definiëren:

"Elke zin Chinese is een waarheidsgetrouwe verklaring als het in het citatenboek van kameraad Mao Tse Tung staat, en is onjuist als het niet is opgenomen.

Dan ziet het bijbehorende complete en consistente bewijsalgoritme (het kan "dogmatisch deductief" worden genoemd) er ongeveer zo uit:

“Blader door het citatenboek van kameraad Mao Tse Tung tot je de uitspraak vindt die je zoekt. Als het wordt gevonden, dan is het waar, en als het citatenboek voorbij is en de bewering niet wordt gevonden, dan is het onwaar.

Hier worden we gered door het feit dat elke bronvermelding duidelijk eindig is, dus het proces van "bewijzen" zal onvermijdelijk eindigen. TGN is dus niet van toepassing op de taal van dogmatische uitspraken. Maar we hadden het over complexe talen, toch?

De onvolledigheidsstellingen van Kurt Gödel waren een keerpunt in de 20e-eeuwse wiskunde. En in zijn manuscripten, gepubliceerd na zijn dood, was het logische bewijs van het bestaan van God bewaard gebleven. Tijdens de laatste kerstlezingen werd een interessant verslag gemaakt over dit weinig bekende erfgoed door priester Dimitri Kiryanov, universitair hoofddocent van het Tobolsk Theological Seminary, kandidaat voor de theologie. "NS" vroeg om de belangrijkste ideeën van de wetenschapper uit te leggen.

Gödels onvolledigheidsstellingen: een gat in de wiskunde

- Kun je op de een of andere manier in het algemeen de onvolledigheidsstellingen van Gödel verklaren? De kapper scheert alleen degenen die zichzelf niet scheren. Scheert de kapper zichzelf? Heeft deze beroemde paradox er iets mee te maken?

De belangrijkste stelling van het logische bewijs van het bestaan van God, naar voren gebracht door Kurt Gödel: "God bestaat in het denken. Maar het bestaan in de werkelijkheid is groter dan het bestaan alleen in het denken. Daarom moet God bestaan." Op de foto: de auteur van de onvolledigheidsstelling Kurt Godel met zijn vriend, de auteur van de relativiteitstheorie Albert Einstein. Preston. Amerika. 1950

— Ja, natuurlijk is dat zo. Vóór Gödel was er het probleem van de axiomatisering van de wiskunde en het probleem van zulke paradoxale zinnen die formeel in elke taal konden worden geschreven. Bijvoorbeeld: "Deze verklaring is niet waar." Wat is de waarheid van deze verklaring? Als het waar is, dan is het onwaar, als het onwaar is, dan is het waar; wat resulteert in een taalkundige paradox. Gödel onderzocht de rekenkunde en toonde in zijn stellingen aan dat de consistentie ervan niet kan worden bewezen aan de hand van de vanzelfsprekende principes: de axioma's van optellen, aftrekken, delen, vermenigvuldigen, enzovoort. We hebben enkele aanvullende aannames nodig om dit te rechtvaardigen. Het is aan de zeer de eenvoudigste theorie, maar hoe zit het met meer complexe (natuurkundige vergelijkingen, enz.)! Om een of ander redeneersysteem te rechtvaardigen, zijn we altijd gedwongen onze toevlucht te nemen tot een of andere aanvullende redenering, die niet gerechtvaardigd is binnen het kader van het systeem.

Dit geeft in de eerste plaats de beperkingen aan van de aanspraken van de menselijke geest op de kennis van de werkelijkheid. Dat wil zeggen, we kunnen niet zeggen dat we een soort van alomvattende theorie van het universum zullen bouwen die alles zal verklaren - zo'n theorie kan niet wetenschappelijk zijn.

Hoe denken wiskundigen nu over de stellingen van Gödel? Niemand probeert ze te weerleggen, op de een of andere manier te omzeilen?

'Het is alsof je de stelling van Pythagoras probeert te weerleggen. De stellingen hebben een rigoureus logisch bewijs. Tegelijkertijd worden er pogingen ondernomen om beperkingen te vinden aan de toepasbaarheid van de stellingen van Gödel. Maar het grootste deel van de controverse draait om de filosofische implicaties van de stellingen van Gödel.

Hoe uitgebreid is Gödels bewijs van het bestaan van God? Is het klaar?

- Het werd tot in detail uitgewerkt, hoewel de wetenschapper het tot zijn dood zelf niet durfde te publiceren. Gödel ontwikkelt een ontologische (metafysische. "NS") een argument dat voor het eerst werd voorgesteld door Anselmus van Canterbury. In beknopte vorm kan dit argument als volgt worden uitgedrukt: “God is per definitie de Ene die groter is dan wie niets kan worden bedacht. God bestaat in gedachten. Maar het bestaan in de werkelijkheid is groter dan het bestaan in gedachten alleen. Daarom moet God bestaan." Anselmus' argument werd later ontwikkeld door René Descartes en Gottfried Wilhelm Leibniz. Dus, volgens Descartes, te denken dat het Hoger Volmaakt Wezen, dat geen bestaan heeft, betekent in een logische tegenstrijdigheid vervallen. In de context van deze ideeën ontwikkelt Gödel zijn eigen versie van het bewijs; het past letterlijk op twee pagina's. Helaas is de presentatie van zijn betoog onmogelijk zonder een zeer complexe modale logica in de fundamenten te introduceren.

Natuurlijk dwingt de logische onberispelijkheid van de conclusies van Godel een persoon niet om een gelovige te worden onder de druk van de bewijskracht. We moeten niet naïef zijn en geloven dat we iedereen kunnen overtuigen met redelijke denkend persoon geloof in God door middel van ontologische argumenten of ander bewijs. Geloof wordt geboren wanneer men oog in oog komt te staan met de duidelijke aanwezigheid van de allerhoogste transcendente Werkelijkheid van God. Maar er is tenminste één persoon die het ontologische argument tot religieus geloof heeft geleid, en dat is de schrijver Clive Staples Lewis, die het zelf heeft toegegeven.

De verre toekomst is het verre verleden

Hoe dachten de tijdgenoten van Gödel over hem? Was hij bevriend met een van de grote wetenschappers?

Einsteins assistent in Princeton getuigt dat de enige persoon met wie hij bevriend was afgelopen jaren leven was Kurt Gödel. Ze waren in bijna alles anders - Einstein is sociaal, opgewekt en Gödel is buitengewoon serieus, volkomen eenzaam en wantrouwend. Maar ze hadden algehele kwaliteit: beiden gingen direct en oprecht in op de centrale vragen van wetenschap en filosofie. Ondanks zijn vriendschap met Einstein had Gödel zijn eigen specifieke kijk op religie. Hij verwierp het idee van God als een onpersoonlijk wezen, zoals God dat was voor Einstein. Bij deze gelegenheid merkte Gödel op: “Einsteins religie is te abstract, zoals die van Spinoza en de Indiase filosofie. Spinoza's God is minder dan een persoon; mijn God is meer dan een persoon; omdat God de rol van een persoon kan spelen.” Er kunnen geesten zijn die geen lichaam hebben, maar met ons kunnen communiceren en de wereld kunnen beïnvloeden.”

Hoe kwam Gödel in Amerika terecht? Op de vlucht voor de nazi's?

- Ja, hij kwam in 1940 vanuit Duitsland naar Amerika, ondanks het feit dat de nazi's hem herkenden als een Arische en een groot wetenschapper, hem bevrijdend van militaire dienst. Hij en zijn vrouw Adele baanden zich een weg door Rusland langs de Trans-Siberische spoorlijn. Hij heeft geen herinneringen aan deze reis achtergelaten. Adele herinnert zich alleen constante angst's nachts, dat ze stoppen en terugkeren. Na acht jaar in Amerika te hebben gewoond, werd Gödel Amerikaans staatsburger. Zoals alle aanvragers van het staatsburgerschap moest hij vragen beantwoorden over de Amerikaanse grondwet. Als nauwgezet persoon bereidde hij dit examen zeer zorgvuldig voor. Ten slotte zei hij dat hij een inconsistentie in de grondwet had gevonden: "Ik ontdekte een logisch legitieme mogelijkheid waarin de Verenigde Staten een dictatuur zouden kunnen worden." Zijn vrienden erkenden dat, ongeacht de logische verdiensten van Gödels argument, deze mogelijkheid puur hypothetisch van aard was, en waarschuwden voor lange gesprekken over dit onderwerp tijdens het examen.

Hebben Gödel en Einstein elkaars ideeën gebruikt in? wetenschappelijk werk?

— In 1949 verwoordde Gödel zijn kosmologische ideeën in een wiskundig essay, dat volgens Albert Einstein een belangrijke bijdrage leverde aan algemene theorie relativiteit. Gödel geloofde dat tijd - "die mysterieuze en tegelijkertijd tegenstrijdige entiteit die de basis vormt van de wereld en ons eigen bestaan" - uiteindelijk zou worden grootste illusie. Het zal "op een dag" ophouden te bestaan, en er zal een andere vorm van zijn komen, die de eeuwigheid kan worden genoemd. Dit idee van tijd leidde de grote logicus tot een onverwachte conclusie. Hij schreef: “Ik ben overtuigd van een hiernamaals, ongeacht de theologie. Als de wereld intelligent is geconstrueerd, moet er een hiernamaals zijn.”

"Tijd is een zichzelf tegensprekende entiteit." Klinkt raar; het heeft wat fysieke betekenis?

Gödel toonde aan dat het binnen het raamwerk van de Einstein-vergelijking mogelijk is om een kosmologisch model te construeren met gesloten tijd, waarin het verre verleden en de verre toekomst samenvallen. In dit model wordt het theoretisch mogelijke reis op tijd. Het klinkt vreemd, maar het is wiskundig uit te drukken - dat is het punt. Dit model kan al dan niet experimentele implicaties hebben. Het is een theoretische constructie die al dan niet nuttig kan zijn bij het bouwen van nieuwe kosmologische modellen. De moderne theoretische fysica, in het bijzonder de kwantumkosmologie, heeft zo'n complexe wiskundige structuur dat het erg moeilijk is om deze structuren een eenduidig filosofisch begrip te geven. Bovendien zijn sommige van de theoretische constructies nog steeds experimenteel niet verifieerbaar om de eenvoudige reden dat hun verificatie de detectie van zeer hoogenergetische deeltjes vereist. Weet je nog hoe mensen in paniek raakten over de lancering van de Large Hadron Collider: fondsen massa media voortdurend bang mensen met de nadering van het einde van de wereld. In feite een serieuze wetenschappelijk experiment om modellen van kwantumkosmologie en de zogenaamde "grote unificatietheorieën" te testen. Als het mogelijk zou zijn om de zogenaamde Higgs-deeltjes te detecteren, dan zou dit de volgende stap zijn in ons begrip van de meest vroege stadia het bestaan van ons universum. Maar totdat er experimentele gegevens zijn, blijven concurrerende modellen van kwantumkosmologie slechts wiskundige modellen.

Geloof en intuïtie

“…Mijn God is meer dan een persoon; aangezien God de rol van een persoon kan spelen…” Is het geloof van Gödel nog ver verwijderd van de orthodoxe belijdenis?

— Zeer weinig van Gödels uitspraken over zijn geloof zijn bewaard gebleven, ze zijn stukje bij beetje verzameld. Ondanks het feit dat Gödel al in 1941, tot 1970, de eerste versies van zijn eigen versie van het betoog maakte, uit angst voor de spot van zijn collega's, sprak hij er niet over. In februari 1970, toen hij zijn dood voelde naderen, stond hij zijn assistent toe een versie van zijn bewijs te kopiëren. Na de dood van Gödel in 1978 werd in zijn papieren een iets andere versie van het ontologische argument gevonden. De vrouw van Kurt Gödel, Adele, zei twee dagen na de dood van haar man dat Gödel, "hoewel hij niet naar de kerk ging, religieus was en elke zondagochtend in bed de Bijbel las."

Als we het hebben over wetenschappers als Gödel, Einstein of, laten we zeggen, Galileo of Newton, is het belangrijk om te benadrukken dat ze geen atheïsten waren. Ze zagen dat er achter het Universum Rede is, een zekere Hoge spanning. Voor veel wetenschappers is het geloof in het bestaan Opperste intelligentie was een van de gevolgen van hun wetenschappelijke reflectie, en deze reflectie leidde niet altijd tot het ontstaan van een diepe religieuze band tussen mens en God. Met betrekking tot Gödel kan men zeggen dat hij de behoefte voelde aan deze verbinding, aangezien hij benadrukte dat hij een theïst was, dat hij over God als een persoon dacht. Maar zijn geloof kan natuurlijk niet orthodox genoemd worden. Hij was, om zo te zeggen, een 'huis-Lutheraan'.

- Jij kan geven historische voorbeelden: Hoe komen verschillende wetenschappers ertoe in God te geloven? Hier is de genetica van Francis Collins, volgens zijn bekentenissen leidde de studie van de structuur van DNA tot geloof in God ...

“Op zichzelf is natuurlijke kennis van God niet voldoende voor de kennis van God. Het is niet genoeg om God te ontdekken door de natuur te bestuderen - het is belangrijk om Hem te leren kennen door de Openbaring die God aan de mens heeft gegeven. Iemands geloof, of hij nu een wetenschapper is of niet, steunt altijd op iets dat verder gaat dan louter logische of wetenschappelijke argumenten. Francis Collins schrijft dat hij op 27-jarige leeftijd tot het geloof kwam na een lang intellectueel geschil met zichzelf en onder invloed van Clive Staples Lewis. Twee mensen bevinden zich in dezelfde historische situatie, onder dezelfde beginvoorwaarden: de een wordt een gelovige, de ander een atheïst. Alleen al de studie van DNA leidt tot het geloof in het bestaan van God. De andere studies komen er niet aan. Twee mensen kijken naar de foto: de een vindt hem mooi, de ander zegt: "Zo-zo, een gewone foto!" De een heeft smaak, intuïtie en de ander niet. Professor van de orthodoxe St. Tikhon humanitaire universiteit Vladimir Nikolajevitsj Katasonov, doctor in de wijsbegeerte, een wiskundige van eerste opleiding, zegt: "Geen bewijs in de wiskunde is mogelijk zonder intuïtie: een wiskundige ziet eerst een afbeelding en formuleert dan een bewijs."

De vraag of iemand tot geloof komt, is altijd een vraag die verder gaat dan alleen logisch redeneren. Hoe leg je uit wat je tot geloof heeft geleid? De man antwoordt: ik ging naar de tempel, dacht na, las dit en dat, zag de harmonie van het universum; maar het belangrijkste, het meest uitzonderlijke moment waarop een persoon zich plotseling bewust wordt dat hij de aanwezigheid van God heeft ontmoet, kan niet worden uitgedrukt. Het is altijd een geheim.

- U kunt problemen identificeren die niet kunnen worden opgelost moderne wetenschap?

— Toch is de wetenschap een voldoende zelfverzekerde, onafhankelijke en gevestigde onderneming om zich zo scherp uit te spreken. Het is een goed en zeer nuttig hulpmiddel in de handen van de mens. Sinds de tijd van Francis Bacon is kennis inderdaad een kracht geworden die de wereld heeft veranderd. De wetenschap ontwikkelt zich in overeenstemming met haar interne wetten: de wetenschapper probeert de wetten van het universum te begrijpen, en het lijdt geen twijfel dat deze zoektocht tot succes zal leiden. Maar tegelijkertijd is het noodzakelijk om je bewust te zijn van de grenzen van de wetenschap. Men moet wetenschap niet verwarren met die ideologische vragen die in verband met wetenschap kunnen worden gesteld. Belangrijkste problemen worden tegenwoordig niet zozeer geassocieerd met de wetenschappelijke methode als wel met waardeoriëntaties. Wetenschap gedurende de lange twintigste eeuw werd door mensen gezien als een absoluut goed dat bijdraagt aan de vooruitgang van de mensheid; en we zien dat de twintigste eeuw de meest wrede is geworden in termen van menselijke slachtoffers. En dan is er nog de kwestie van waarden. wetenschappelijke vooruitgang, kennis in het algemeen. Ethische waarden volgen niet uit de wetenschap zelf. Een briljante wetenschapper kan een wapen uitvinden voor de vernietiging van de hele mensheid, en hier rijst de vraag naar de morele verantwoordelijkheid van een wetenschapper, die de wetenschap niet kan beantwoorden. De wetenschap kan de mens niet de betekenis en het doel van zijn bestaan aangeven. De wetenschap zal nooit in staat zijn om de vraag te beantwoorden waarom zijn we hier? Waarom bestaat het universum? Deze vragen worden opgelost op een ander kennisniveau, zoals filosofie en religie.

— Is er, naast de stellingen van Gödel, enig ander bewijs dat de wetenschappelijke methode zijn grenzen heeft? Herkennen wetenschappers dit zelf?

- Al aan het begin van de 20e eeuw wezen de filosofen Bergson en Husserl op relatieve waarde wetenschappelijke kennis natuur. Het is nu een bijna universeel geloof geworden onder wetenschapsfilosofen dat wetenschappelijke theorieën hypothetische modellen vertegenwoordigen om verschijnselen te verklaren. Een van de makers kwantummechanica Erwin Schrödinger zei dat elementaire deeltjes zijn slechts afbeeldingen, maar we kunnen zonder hen. Volgens de filosoof en logicus Karl Popper zijn wetenschappelijke theorieën als een net waardoor we de wereld proberen te vangen, ze zijn niet als foto's. wetenschappelijke theorieën zijn voortdurend in ontwikkeling en verandering. De makers van de kwantummechanica, zoals Pauli, Bohr, Heisenberg spraken over de grenzen van de wetenschappelijke methode. Pauli schreef: “...Natuurkunde en psyche kunnen worden beschouwd als aanvullende aspecten dezelfde realiteit" - en gericht op de onherleidbaarheid hogere levels naar het lagere zijn. Verschillende verklaringen bestrijken telkens slechts één aspect van de materie, maar een alomvattende theorie zal nooit worden bereikt.

De schoonheid en harmonie van het universum impliceert de mogelijkheid van zijn kennis wetenschappelijke methodes. Tegelijkertijd hebben christenen altijd de onbegrijpelijkheid van het mysterie achter dit materiële universum begrepen. Het universum heeft geen fundament op zichzelf en wijst naar de volmaakte bron van bestaan - God.

Een van de beroemdste stellingen van de wiskundige logica, geluk en pech tegelijk. Hierin is het vergelijkbaar met de speciale relativiteitstheorie van Einstein. Aan de ene kant heeft bijna iedereen wel iets over hen gehoord. Aan de andere kant, in de populaire interpretatie, de theorie van Einstein, zoals u weet, "zegt dat alles in de wereld relatief is". En de onvolledigheidsstelling van Gödel (hierna simpelweg TGN), in een ongeveer even vrije volksformulering, "bewijst dat er dingen zijn die onbegrijpelijk zijn voor de menselijke geest". En dus proberen sommigen het aan te passen als een argument tegen het materialisme, terwijl anderen juist met haar hulp bewijzen dat er geen god is. Het is niet alleen grappig dat beide kanten niet tegelijkertijd gelijk kunnen hebben, maar ook dat noch de een noch de ander de moeite neemt om uit te zoeken wat deze stelling in feite zegt.

Wiskundige logica is inderdaad een nogal gecompliceerde wetenschap, en vooral niet erg vertrouwd. Het vereist zorgvuldige en strikte manoeuvres, waarbij het belangrijk is om het echt bewezen niet te verwarren met het feit dat "het al duidelijk is". Ik hoop echter dat de lezer, om het volgende "overzicht van het bewijs van TGN" te begrijpen, alleen kennis van schoolwiskunde / informatica, logisch denkvermogen en 15-20 minuten tijd nodig heeft.

Enigszins vereenvoudigd stelt TGN dat er in voldoende complexe talen onbewijsbare proposities zijn. Maar in deze zin heeft bijna elk woord een uitleg nodig.

De overgang van de ene formule naar de andere gebeurt volgens bepaalde welbekende regels. De overgang van de 4e formule naar de 5e vond bijvoorbeeld plaats omdat elk getal gelijk is aan zichzelf - dat is het axioma van de rekenkunde. En de hele procedure van bewijzen vertaalt de formule dus in de booleaanse waarde TRUE. Het resultaat zou ONWAAR kunnen zijn - als we een formule zouden weerleggen. In dit geval zouden we de ontkenning ervan bewijzen. Het is mogelijk om je een programma voor te stellen (en zulke programma's zijn ook echt geschreven) dat zulke (en complexere) stellingen zou bewijzen zonder menselijke tussenkomst.

Voor wat volgt hebben we de notie van een algoritme nodig. Ik zal hier niet de formele definitie geven - dit zou ons behoorlijk ver op een zijspoor brengen. Ik beperk me tot het informele: "algoritme"- deze opeenvolging van ondubbelzinnige instructies ("programma"), die in een eindig aantal stappen zet invoergegevens om in uitvoer. Het cursieve is van fundamenteel belang - als het programma vastloopt bij een aantal initiële gegevens, dan beschrijft het het algoritme niet. Voor de eenvoud en in toepassing op ons geval, kan de lezer overwegen dat een algoritme een programma is dat is geschreven in een programmeertaal die hem bekend is en dat, voor alle invoergegevens van een bepaalde klasse, gegarandeerd zijn werk voltooit met een Booleaans resultaat.

Het kan heel goed zijn dat deze verklaring bij u intern protest oproept. Dit komt door verschillende omstandigheden. Ten eerste, wanneer we schoolwiskunde leren, is er soms een verkeerde indruk dat de uitdrukkingen "de stelling is waar" en "het is mogelijk om de stelling te bewijzen of te verifiëren" bijna identiek zijn. Maar als je erover nadenkt, is het helemaal niet duidelijk. Sommige stellingen worden heel eenvoudig bewezen (bijvoorbeeld door een klein aantal opties op te sommen), en sommige zijn erg moeilijk. Denk bijvoorbeeld aan de beroemde laatste stelling van Fermat:

Ik merk ook op dat als we het hadden over de gebruikelijke functies die de reeks reële getallen eraan toewijzen, de "niet-berekenbaarheid" van de functie niemand zou verbazen (verwar "berekenbare functies" en "berekenbare getallen" niet - dit zijn verschillende dingen). Elk schoolkind weet dat, laten we zeggen, in het geval van een functie, je veel geluk moet hebben met het argument, zodat het proces van het berekenen van de exacte decimale representatie van de waarde van deze functie eindigt in een eindig aantal stappen. En hoogstwaarschijnlijk bereken je het met een oneindige reeks, en deze berekening zal nooit tot een exact resultaat leiden, hoewel het er in de buurt kan komen - simpelweg omdat de waarde van de sinus van de meeste argumenten irrationeel is. TGN vertelt ons eenvoudig dat zelfs onder functies waarvan de argumenten strings zijn en waarvan de waarden nul of één zijn, er ook niet-berekenbare functies bestaan, hoewel ze op een geheel andere manier zijn gerangschikt.

Voor wat volgt, zullen we de "taal van de formele rekenkunde" beschrijven. Laten we eens kijken naar een klasse tekstreeksen van eindige lengte, bestaande uit Arabische cijfers, variabelen (letters van het Latijnse alfabet) met natuurlijke waarden, spaties, tekens van rekenkundige bewerkingen, gelijkheid en ongelijkheid, kwantoren ("bestaat") en ("voor any") en, misschien, enkele andere symbolen (hun exacte aantal en samenstelling zijn voor ons niet belangrijk). Het is duidelijk dat niet al dergelijke regels zinvol zijn (bijvoorbeeld "" is onzin). De subset van betekenisvolle uitdrukkingen van deze klasse (dat wil zeggen, tekenreeksen die waar of onwaar zijn in termen van gewone rekenkunde) zal onze reeks uitspraken zijn.

Voorbeelden van formele rekenkundige uitspraken:

enz. Laten we nu een "formule met een vrije parameter" (FSP) een tekenreeks noemen die een instructie wordt als een natuurlijk getal erin wordt vervangen als deze parameter. Voorbeelden van FSP (met parameter):

enz. Met andere woorden, FSP's zijn equivalent aan functies van een natuurlijk argument met een Booleaanse waarde.

Laten we nu overgaan tot een schets van het bewijs van TGN in de volgende formulering:

Voor de propositietaal van de formele rekenkunde is er geen volledig consistente deductie.

We zullen bewijzen door tegenspraak.

Dus laten we aannemen dat zo'n deductief bestaat. Laten we het volgende hulpalgoritme beschrijven dat als volgt een booleaanse waarde toewijst aan een natuurlijk getal:

Simpel gezegd, het algoritme resulteert in de waarde TRUE als en alleen als het resultaat van het vervangen van zijn eigen nummer in onze lijst in de FSP een valse verklaring geeft.

Hier komen we bij de enige plaats waar ik de lezer zal vragen om mij op mijn woord te geloven.

Na het passeren van deze glibberige plek komen we snel aan het einde.

"Elke zin in de Chinese taal is een waarheidsgetrouwe uitspraak als deze is opgenomen in het citatenboek van kameraad Mao Tse Tung, en is onjuist als deze niet is opgenomen."

Dan ziet het bijbehorende complete en consistente bewijsalgoritme (het kan "dogmatisch deductief" worden genoemd) er ongeveer zo uit:

“Blader door het citatenboek van kameraad Mao Tse Tung tot je de uitspraak vindt die je zoekt. Als het wordt gevonden, dan is het waar, en als het citatenboek voorbij is en de bewering niet wordt gevonden, dan is het onwaar.

Tags: Tags toevoegen

Elk systeem van wiskundige axioma's, beginnend met een bepaald niveau van complexiteit, is ofwel intern inconsistent of onvolledig.

In 1900 werd in Parijs de World Conference of Mathematicians gehouden, waarop David Hilbert (1862-1943) in de vorm van abstracts de 23 belangrijkste, naar zijn mening, door hem geformuleerde problemen presenteerde die door theoretische wetenschappers moesten worden opgelost van de komende twintigste eeuw. Nummer twee op zijn lijst was er zo een eenvoudige taken, waarvan het antwoord voor de hand lijkt te liggen totdat je wat dieper graaft. praten moderne taal, dat was de vraag: is wiskunde op zich voldoende? Hilberts tweede probleem was om rigoureus te bewijzen dat het systeem axioma's- de basisuitspraken die in de wiskunde als basis zonder bewijs worden genomen - is perfect en volledig, dat wil zeggen, het stelt je in staat om alles wat bestaat wiskundig te beschrijven. Het was nodig om te bewijzen dat het mogelijk is om een dergelijk systeem van axioma's vast te stellen dat, ten eerste, ze onderling consistent zullen zijn, en ten tweede, men daaruit een conclusie kan trekken met betrekking tot de waarheid of onwaarheid van een bewering.

Laten we een voorbeeld nemen uit schoolgeometrie. Standaard Euclidische planimetrie(geometrie op het vlak) is het mogelijk om onvoorwaardelijk te bewijzen dat de stelling "de som van de hoeken van een driehoek is 180°" waar is, en de stelling "de som van de hoeken van een driehoek is 137°" onjuist is. In wezen gesproken, in de Euclidische meetkunde, is elke bewering onwaar of waar, en de derde wordt niet gegeven. En aan het begin van de twintigste eeuw geloofden wiskundigen naïef dat dezelfde situatie zou moeten worden waargenomen in elk logisch consistent systeem.

En toen, in 1931, nam een of andere Weense bebrilde wiskundige Kurt Godel een kort artikel op en publiceerde het dat de hele wereld van de zogenaamde "mathematische logica" omver wierp. Na lange en complexe wiskundige en theoretische preambules stelde hij letterlijk het volgende vast. Laten we een uitspraak nemen als: "Aanname #247 is logisch niet te bewijzen in dit systeem van axioma's" en het "uitspraak A" noemen. Dus Gödel bewees eenvoudig de volgende geweldige eigenschap elk axioma systemen:

"Als een bewering A kan worden bewezen, kan een niet-A-verklaring worden bewezen."

Met andere woorden, als het mogelijk is om de geldigheid van de stelling "Veronderstelling 247" niet bewijsbaar", dan is het mogelijk om de geldigheid van de stelling "Veronderstelling 247 aantoonbaar". Dat wil zeggen, terugkomend op de formulering van het tweede Hilbert-probleem, als het systeem van axioma's compleet is (dat wil zeggen, elke bewering erin kan worden bewezen), dan is het inconsistent.

De enige uitweg uit deze situatie is het accepteren van een onvolledig systeem van axioma's. Dat wil zeggen, men moet het feit accepteren dat in de context van een logisch systeem we blijven achter met "type A" uitspraken waarvan bekend is dat ze waar of onwaar zijn - en we kunnen alleen hun waarheid beoordelen buiten het raamwerk van de axiomatiek die we hebben aangenomen. Als dergelijke uitspraken niet bestaan, is onze axiomatiek tegenstrijdig, en binnen haar kader zullen er onvermijdelijk formuleringen zijn die zowel kunnen worden bewezen als weerlegd.

Dus de bewoording eerst,of zwak De onvolledigheidsstellingen van Gödel: "Elk formeel systeem van axioma's bevat onopgeloste aannames." Maar daar stopte Gödel niet met formuleren en bewijzen seconde, of krachtig Onvolledigheidsstelling van Godel: “De logische volledigheid (of onvolledigheid) van een systeem van axioma's kan niet worden bewezen binnen het kader van dit systeem. Om het te bewijzen of te weerleggen, zijn aanvullende axioma's (versterking van het systeem) nodig.”

Het zou veiliger zijn om te denken dat de stellingen van Godel abstract zijn en ons niet aangaan, maar alleen gebieden van sublieme wiskundige logica, maar in feite bleek dat ze rechtstreeks verband houden met de structuur van het menselijk brein. Engelse wiskundige en de natuurkundige Roger Penrose (geb. 1931) toonde aan dat de stellingen van Gödel kunnen worden gebruikt om fundamentele verschillen tussen het menselijk brein en een computer te bewijzen. Het punt van zijn redenering is eenvoudig. De computer werkt strikt logisch en is niet in staat om te bepalen of bewering A waar of onwaar is als deze buiten het bereik van de axiomatiek valt, en dergelijke beweringen bestaan, volgens de stelling van Gödel, onvermijdelijk. Een persoon, geconfronteerd met zo'n logisch onbewijsbare en onweerlegbare bewering A, is altijd in staat om de waarheid of onwaarheid ervan te bepalen - op basis van alledaagse ervaring. In ieder geval hierin menselijke brein presteert beter dan een computer geketend met clean logische circuits. Het menselijk brein is in staat om de volledige diepte van de waarheid in de stellingen van Gödel te begrijpen, maar een computer kan dat nooit. Daarom is het menselijk brein allesbehalve een computer. Hij is in staat om beslissingen te nemen, en de Turing-test zal slagen.

Ik vraag me af of Hilbert enig idee had hoe ver zijn vragen ons zouden brengen?

Kurt Gödel, 1906-1978

Oostenrijkse, toen Amerikaanse wiskundige. Geboren in Brünn (Brünn, nu Brno, Tsjechië). Hij studeerde af aan de Universiteit van Wenen, waar hij leraar bleef bij de afdeling Wiskunde (sinds 1930 - een professor). In 1931 publiceerde hij een stelling die later zijn naam kreeg. Als puur apolitiek persoon overleefde hij extreem hard de moord op zijn vriend en afdelingsmedewerker door een nazi-student en raakte hij in een diepe depressie, waarvan de terugvallen hem tot het einde van zijn leven achtervolgden. In de jaren dertig emigreerde hij naar de Verenigde Staten, maar keerde terug naar zijn geboorteland Oostenrijk en trouwde. In 1940, op het hoogtepunt van de oorlog, moest hij op doorreis via de USSR en Japan naar Amerika vluchten. Werkte een tijdje bij het Princeton Institute geavanceerd onderzoek. Helaas kon de psyche van de wetenschapper het niet uitstaan, en hij stierf van de honger in een psychiatrische kliniek en weigerde te eten, omdat hij ervan overtuigd was dat ze van plan waren hem te vergiftigen.