De onvolledigheidsstelling van Gödel in eenvoudige bewoordingen. Interessante weetjes en handige tips

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 Wereldconferentie voor Wiskundigen 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, waarop 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 compleet, 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 ieder axioma systemen:

"Als een verklaring A kan worden bewezen, dan kan een non-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, we moeten het feit accepteren dat we in de context van elk logisch systeem "type A" uitspraken zullen hebben die duidelijk waar of onwaar zijn - en we kunnen hun waarheid alleen 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 tweede, 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 direct verband houden met de structuur van het menselijk brein. De Engelse wiskundige en natuurkundige Roger Penrose (geboren in 1931) toonde aan dat de stellingen van Gödel konden 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 beslissingen 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-78

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 buitengewoon hard de moord op zijn vriend en afdelingsmedewerker door een nazi-student en viel 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.

Ik ben al lang geïnteresseerd in wat de sensationele stelling van Gödel is. En hoe het nuttig is voor het leven. En eindelijk kon ik het uitzoeken.

De meest populaire formulering van de stelling is:
"Elk systeem van wiskundige axioma's, beginnend met een bepaald niveau van complexiteit, is ofwel intern inconsistent of onvolledig."

Ik zou het vertalen in een menselijke, niet-wiskundige taal zoals deze (een axioma is de uitgangspositie van een theorie, die binnen het kader van deze theorie als waar wordt aanvaard zonder dat bewijs nodig is en wordt gebruikt als basis voor het bewijzen van de andere bepalingen ervan). In het leven is een axioma de principes die worden gevolgd door een persoon, de samenleving, wetenschappelijke richting, staten. Onder de vertegenwoordigers van religie worden axioma's dogma's genoemd. Bijgevolg wordt elk van onze principes, elk systeem van opvattingen, beginnend vanaf een bepaald niveau, intern tegenstrijdig of onvolledig. Om van de waarheid van een bepaalde stelling overtuigd te zijn, zal men voorbij het gegeven stelsel van opvattingen moeten gaan en een nieuw stelsel moeten bouwen. Maar het zal ook onvolmaakt zijn. Dat wil zeggen, het PROCES VAN KENNIS IS ONEINDIG. De wereld kan niet volledig bekend zijn totdat we de bron hebben bereikt.

"... als we het vermogen om logisch te redeneren beschouwen als het belangrijkste kenmerk van de menselijke geest, of op zijn minst het belangrijkste hulpmiddel, dan geeft de stelling van Gödel direct de beperkte mogelijkheden van ons brein aan. Mee eens dat het erg moeilijk is voor een persoon die wordt gebracht geloof in de oneindige kracht van het denken om de stelling over de grenzen van zijn macht te accepteren ... Veel experts geloven dat de formeel-computationele, "aristotelische" processen die ten grondslag liggen aan logisch denken, zijn slechts een deel menselijk bewustzijn. Het andere gebied, dat fundamenteel 'niet-computationeel' is, is verantwoordelijk voor manifestaties als intuïtie, creatieve inzichten en begrip. En als de eerste helft van de geest onder de beperkingen van Gödel valt, dan is de tweede helft vrij van dergelijke beperkingen ... Natuurkundige Roger Penrose ging nog verder. Hij suggereerde het bestaan ​​van enkele kwantumeffecten van niet-computationele aard, die zorgen voor de realisatie van creatieve bewustzijnshandelingen... Een van de talrijke consequenties van de Penrose-hypothese kan met name de conclusie zijn dat kunstmatige intelligentie op basis van moderne computerapparatuur, ook al zal de komst van kwantumcomputers leiden tot een grandioze doorbraak op het gebied van computertechnologie. Het feit is dat elke computer het werk van de formeel-logische, 'computationele' activiteit van het menselijk bewustzijn alleen maar meer en nauwkeuriger kan modelleren, maar de 'niet-computationele' vermogens van het intellect zijn er niet voor toegankelijk.

Een belangrijke consequentie van de stelling van Gödel is de conclusie dat men niet in uitersten kan denken. Altijd binnen bestaande theorie er is een verklaring die niet kan worden bewezen of weerlegd. Of, met andere woorden, bij een of andere verklaring is er altijd een paar dat deze weerlegt.

Volgende conclusie. Goed en kwaad zijn slechts 2 kanten van dezelfde medaille, zonder welke het niet kan bestaan. En het komt voort uit het principe dat er in het universum maar één bron van alles is: goed en kwaad, liefde en haat, leven en dood.

Elke verklaring van volledigheid van het systeem is vals. Je kunt niet vertrouwen op dogma's, want vroeg of laat zullen ze worden weerlegd.

In die zin bevinden moderne religies zich in een kritische positie: de dogma's van de kerk verzetten zich tegen de ontwikkeling van onze ideeën over de wereld. Ze proberen alles in het kader van rigide concepten te persen. Maar dit leidt ertoe dat vanuit het monotheïsme, vanuit de enige bron van alles natuurlijke processen ze gaan verder naar het heidendom, waar er krachten van het goede en van het kwade zijn, er is een god van het goede ergens ver weg in de hemel, en er is een duivel (de god van het kwaad), die al lang zijn poot heeft gelegd op alles wat is op aarde. Deze benadering leidt tot de verdeling van alle mensen in vrienden en vijanden, rechtvaardigen en zondaars, gelovigen en ketters, vrienden en vijanden.

Hier is nog een kleine tekst die in de volksmond de essentie onthult die volgt uit de stelling van Gödel:
"Het lijkt mij dat deze stelling een belangrijke filosofische betekenis. Er zijn slechts twee opties mogelijk:

a) De theorie is onvolledig, d.w.z. in termen van een theorie kan men een vraag formuleren waarop het onmogelijk is om een ​​positief of een negatief antwoord af te leiden uit de axioma's/postulaten van de theorie. Tegelijkertijd kunnen op al deze vragen antwoorden worden gegeven in het kader van een meer omvattende theorie, waarbij de oude een speciaal geval zal zijn. Maar dit nieuwe theorie zal zijn eigen "onbeantwoorde vragen" hebben, enzovoort tot in het oneindige.

b) Compleet, maar tegenstrijdig. Elke vraag kan worden beantwoord, maar sommige vragen kunnen tegelijkertijd met ja en nee worden beantwoord.

Wetenschappelijke theorieën zijn van het eerste type. Ze zijn consistent, maar dat betekent dat ze niet alles beschrijven. Er kan geen "finale" zijn wetenschappelijke theorie. Elke theorie is onvolledig en beschrijft iets niet, ook al weten we nog niet wat het is. Men kan alleen maar meer en meer omvattende theorieën creëren. Voor mij persoonlijk is dit reden tot optimisme, omdat het betekent dat de vooruitgang van de wetenschap nooit zal stoppen.

"Almachtige God" behoort tot het tweede type. Almachtige God is het antwoord op elke vraag. En dit betekent automatisch dat het leidt tot logische absurditeit. Paradoxen zoals de "zware steen" kunnen in batches worden uitgevonden.

Over het algemeen, wetenschappelijke kennis is waar (consistent), maar beschrijft op een gegeven moment niet alles. Tegelijkertijd staat niets in de weg om de grenzen van het bekende tot in het oneindige te verleggen, steeds verder en vroeg of laat wordt elk onbekende bekend. Religie beweert Volledige beschrijving wereld "nu", maar het is automatisch onjuist (absurd)."

Ooit, toen ik net begon met mijn volwassenheid Ik was aan het programmeren. En er was zo'n principe: als er veel correcties in het programma worden aangebracht, moet het opnieuw worden geschreven. Dit principe komt naar mijn mening overeen met de stelling van Godel. Als het programma complexer wordt, wordt het inconsistent. En het zal niet goed werken.

Nog een voorbeeld uit het leven. We leven in een tijdperk waarin ambtenaren zeggen dat het belangrijkste bestaansbeginsel de wet moet zijn. Dat wil zeggen, het rechtssysteem. Maar zodra de wetgeving complexer wordt en de regelgeving floreert, beginnen wetten elkaar tegen te spreken. Wat we nu zien. Je kunt nooit creëren rechtssysteem, die alle aspecten van het leven zou voorschrijven. Aan de andere kant zou het eerlijk zijn voor iedereen. Omdat de beperkingen van ons begrip van de wereld altijd naar buiten zullen komen. En menselijke wetten zullen op een gegeven moment in conflict komen met de wetten van het universum. We begrijpen veel dingen intuïtief. Ook intuïtief moeten we de acties van andere mensen beoordelen. Het volstaat dat de staat een grondwet heeft. En vertrouwend op de artikelen van deze grondwet, om de verhoudingen in de samenleving te regelen. Maar vroeg of laat zal de grondwet moeten worden gewijzigd.

Het GEBRUIK is een ander voorbeeld van de misvatting van onze ideeën over menselijke vermogens. We proberen de rekencapaciteiten van de hersenen te testen in een examen. Maar intuïtieve vermogens op school zijn niet meer ontwikkeld. Maar de mens is geen biorobot. Het is onmogelijk om een ​​scoresysteem te creëren dat in staat zou zijn om alle mogelijkheden te onthullen die inherent zijn aan een persoon, in zijn bewustzijn, in zijn onderbewustzijn en in zijn psyche.

Bijna 100 jaar geleden zette Gödel een ongelooflijke stap in het begrijpen van de wetten van het universum. En we hebben dit nog steeds niet kunnen gebruiken, gezien deze stelling als zeer gespecialiseerd wiskunde probleem voor een kleine kring van mensen die in hun eigen kring met enkele abstracte onderwerpen bezig zijn. Samen met Kwantum theorie en de leer van Christus, stelt de stelling van Gödel ons in staat om te ontsnappen aan de gevangenschap van valse dogma's, om de crisis te overwinnen die nog steeds in ons wereldbeeld voortduurt. En de tijd dringt.

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 zijn 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 van schoolwiskunde / informatica, logisch denkvermogen en 15-20 minuten tijd nodig heeft.

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 plaats, laten we zeggen, 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 eigenlijk 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 reeks uitspraken en een functie van tot - noemen "taal van uitspraken". Merk op dat het begrip taal in de alledaagse zin 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 geen 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 achter 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 voor elke functie (of kortom, "deductief") equivalent aan deze functie, dat wil zeggen, elke instructie vertalen 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 enkele - 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 uitdrukkingen "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 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 enigszins ingewikkeld maken, maar dit is niet verschrikkelijk. Dit argument zou volkomen juist 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" gewoon niet - dit zijn verschillende dingen). Elk schoolkind weet dat je, bijvoorbeeld in het geval van een functie, 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, niet-berekenbare functies, hoewel op een geheel andere manier gerangschikt, ook bestaan.

Voor wat volgt, beschrijven we de taal formeel rekenen". Beschouw een klasse van tekstreeksen van eindige lengte, bestaande uit Arabische cijfers, variabelen (letters Latijns alfabet), natuurlijke waarden, spaties, karakters nemen 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, strings die waar of onwaar zijn in termen van gewone rekenkunde) zal onze reeks uitspraken zijn.

Voorbeelden van formele rekenkundige uitspraken:

enzovoort. 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):

enzovoort. 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 substitueren in de FSP van zijn eigen nummer in onze lijst 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 aanname niet klopt. 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, aangezien 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 formele rekenkunde, 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 bewering 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 verklaring 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?

Tags: Tags toevoegen

09sen

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

In 1900 werd de Wereldconferentie van Wiskundigen gehouden in Parijs, waar: David Gilbert(David Hilbert, 1862-1943) schetste in de vorm van stellingen de 23 belangrijkste, naar zijn mening, taken die theoretici van de komende twintigste eeuw moesten oplossen. Nummer twee op zijn lijst was een van die simpele problemen die voor de hand liggend lijken totdat je wat dieper graaft. In moderne termen was het de vraag: is wiskunde op zich voldoende? Hilberts tweede taak was beperkt tot de noodzaak om strikt te bewijzen dat het systeem van axioma's - fundamentele uitspraken in de wiskunde als basis genomen zonder bewijs - perfect en volledig is, dat wil zeggen, het maakt een wiskundige beschrijving mogelijk van alles wat bestaat. 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. In standaard Euclidische planimetrie (geometrie op een vlak), kan onvoorwaardelijk worden bewezen 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°". " is fout. 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 een of andere Weense bebrilde wiskundige Kurt Gödel- nam en publiceerde een kort artikel dat eenvoudigweg de hele wereld van de zogenaamde "mathematische logica" op zijn kop zette. 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. Gödel bewees dus eenvoudig de volgende verbazingwekkende eigenschap van elk systeem van axioma's:

"Als een verklaring A kan worden bewezen, dan kan een non-A-verklaring worden bewezen."

Met andere woorden, als het mogelijk is om de geldigheid van de stelling "Veronderstelling 247 is niet bewijsbaar" te bewijzen, dan is het ook mogelijk om de geldigheid van de stelling "Veronderstelling 247 is bewijsbaar" te bewijzen. 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, we moeten het feit accepteren dat we in de context van elk logisch systeem nog steeds uitspraken van het type A zullen hebben die duidelijk waar of onwaar zijn, en we kunnen hun waarheid alleen beoordelen buiten het kader van de axiomatiek die we hebben geadopteerd. 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 formulering van Gödels eerste, of zwakke, onvolledigheidsstelling is: "Elk formeel systeem van axioma's bevat onopgeloste aannames". Maar Gödel stopte daar niet met het formuleren en bewijzen van Gödels tweede of sterke onvolledigheidsstelling: “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 direct verband houden met de structuur van het menselijk brein. De Engelse wiskundige en natuurkundige Roger Penrose (geboren 1931) toonde aan dat: De stellingen van Gödel kan worden gebruikt om het bestaan ​​van 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 dit opzicht is het menselijk brein in ieder geval superieur aan een computer die is geketend aan puur 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.

over het onderwerp: "GODEL'S THEOREM"

Kurt Gödel

Kurt Gödel is de grootste specialist in wiskundige logica- werd geboren op 28 april 1906 in Brunn (nu Brno, Tsjechië). Hij studeerde af aan de Universiteit van Wenen, waar hij zijn proefschrift verdedigde, was een assistent-professor in 1933-1938. Na de Anschluss emigreerde hij naar de Verenigde Staten. Van 1940 tot 1963 werkte Gödel bij het Princeton Institute hogere studies. Gödel, eredoctoraat van de universiteiten van Yale en Harvard, Fellow Nationale Academie Wetenschappen van de Verenigde Staten en de American Philosophical Society.

In 1951 ontving Kurt Gödel de hoogste wetenschappelijke onderscheiding in de Verenigde Staten, de Einsteinprijs. In een artikel dat aan deze gebeurtenis is gewijd, schreef een andere van de grootste wiskundigen van onze tijd, John von Neumann: “De bijdrage van Kurt Gödel aan de moderne logica is werkelijk monumentaal. Dit is meer dan alleen een monument. Dit is een mijlpaal die twee tijdperken scheidt ... Zonder enige overdrijving kan worden gezegd dat het werk van Gödel het onderwerp van logica als wetenschap fundamenteel heeft veranderd.

Zelfs een droge lijst van de prestaties van Godel op het gebied van wiskundige logica laat zien dat hun auteur in wezen de basis heeft gelegd voor hele secties van deze wetenschap: de theorie van modellen (1930; de zogenaamde stelling over de volledigheid van de smalle predikaatrekening, waaruit blijkt: ruwweg, de toereikendheid van de middelen van "formele logica" om alle ware zinnen uitgedrukt in haar taal te bewijzen), constructieve logica (1932-1933; resulteert in de mogelijkheid om sommige klassen van zinnen van klassieke logica te herleiden tot hun intuïtionistische tegenhangers, die de basis gelegd voor het systematische gebruik van "onderdompelingsoperaties" die een dergelijke vermindering van verschillende logische systemen elkaar), formele rekenkunde (1932-1933; resultaten over de mogelijkheid om klassieke rekenkunde te reduceren tot intuïtionistische rekenkunde, waarbij in zekere zin de consistentie van de eerste ten opzichte van de tweede wordt aangetoond), de theorie van algoritmen en recursieve functies (1934; definitie van het concept van een algemene recursieve functie, die speelde beslissende rol bij het vaststellen van de algoritmische onoplosbaarheid van de reeks kritieke problemen wiskunde aan de ene kant. En bij de implementatie van logische en wiskundige problemen op elektronische computers - aan de andere kant), axiomatische verzamelingenleer (1938; bewijs van de relatieve consistentie van het keuzeaxioma en de continuümhypothese van Cantor uit de axioma's van de verzamelingenleer, die het begin markeerde van de serie belangrijkste resultaten over de relatieve consistentie en onafhankelijkheid van set-theoretische principes).

Onvolledigheidsstelling van Godel

Invoering

In 1931, in een van de Duitse wetenschappelijke tijdschriften er verscheen een relatief korte paper met de nogal ontmoedigende titel "On Formeel Onbeslisbare Propositions of Principia Mathematica and Related Systems". De auteur was een vijfentwintigjarige wiskundige van de Universiteit van Wenen, Kurt Gödel, die later werkte aan het Princeton Institute for Advanced Study. Dit werk speelde een beslissende rol in de geschiedenis van logica en wiskunde. in de beslissing Harvard universiteit het toekennen van een eredoctoraat aan Gödel (1952), werd ze beschreven als een van de grootste prestaties moderne logica.

Op het moment van publicatie echter geen titel van het werk van Gödel. Noch de inhoud zei iets tegen de meeste wiskundigen. Principia Mathematica, genoemd in de titel, is de monumentale driedelige verhandeling van Alfred North Whitehead en Bertrand Russell over wiskundige logica en de grondslagen van de wiskunde; bekendheid met de verhandeling was geenszins Noodzakelijke voorwaarde voor succesvol werk in de meeste takken van de wiskunde. De belangstelling voor de kwesties die in het werk van Gödel aan de orde komen, is altijd het lot geweest van een zeer kleine groep wetenschappers. Tegelijkertijd waren de argumenten van Gödel in zijn bewijzen zo ongebruikelijk voor hun tijd. Dat een volledig begrip ervan een exclusieve kennis van het onderwerp vereiste en bekendheid met de literatuur die aan deze zeer specifieke problemen was gewijd.

Eerste onvolledigheidsstelling

Gödels eerste onvolledigheidsstelling lijkt het belangrijkste resultaat in de wiskundige logica te zijn. Het klinkt als volgt:

Voor een willekeurig consistente formele en berekenbare theorie waarin fundamentele rekenkundige proposities kunnen worden bewezen, kan een echte rekenkundige propositie worden geconstrueerd waarvan de waarheid niet kan worden bewezen binnen het kader van de theorie. Met andere woorden, elke perfect bruikbare theorie die voldoende is om rekenkunde weer te geven, kan niet zowel consistent als volledig zijn.

Hier betekent het woord "theorie" " oneindige reeks» uitspraken, waarvan sommige zonder bewijs voor waar worden aangenomen (dergelijke uitspraken worden axioma's genoemd), terwijl andere (stellingen) uit axioma's kunnen worden afgeleid en daarom worden aangenomen (bewezen) waar te zijn. De uitdrukking "aantoonbaar in theorie" betekent "af te leiden uit de axioma's en primitieven van de theorie (constante symbolen van het alfabet) met behulp van standaard (eerste-orde) logica." Een theorie is consistent (consistent) als het onmogelijk is om een ​​tegenstrijdige bewering erin te bewijzen. De uitdrukking "kan worden gebouwd" betekent dat er een mechanische procedure (algoritme) is die een verklaring kan bouwen op basis van axioma's, primitieven en eerste-orde logica. "Elementaire rekenkunde" is de aanwezigheid van bewerkingen van optellen en vermenigvuldigen over natuurlijke getallen. De resulterende ware maar niet-bewijsbare propositie wordt voor een bepaalde theorie vaak de "Gödel-reeks" genoemd, maar er is een oneindig aantal andere proposities in de theorie die dezelfde eigenschap hebben dat ze binnen de theorie onbewijsbaar zijn.

De aanname dat de theorie berekenbaar is, betekent dat het in principe mogelijk is om een ​​computeralgoritme te implementeren ( computerprogramma) die (indien toegestaan ​​om willekeurig lange tijden te berekenen, tot oneindig) een lijst berekent van alle stellingen van de theorie. In feite is het voldoende om alleen de lijst met axioma's te berekenen, en alle stellingen kunnen efficiënt worden afgeleid uit zo'n lijst.

De eerste onvolledigheidsstelling was getiteld "Theorem VI" in Gödel's 1931 paper. Over formeel onbeslisbare stellingen in Principia Mathematica en gerelateerde systemen I. In de originele opname van Gödel klonk het als volgt:

“De algemene conclusie over het bestaan ​​van onbeslisbare proposities is deze:

Stelling VI .

Voor elke ω-consistente recursieve klasse k FORMULE er zijn recursieve TEKENS r zodanig dat geen van beide (v Gen r), noch ¬( v Gen r)behoren niet tot Flg (k)(waar v is GRATIS VARIABELE r ) ».

Aanwijzing Flg komt van hem. Folgerungsmenge- reeks sequenties, Gen komt van hem. generalisatie- generalisatie.

Grofweg gezegd, de verklaring van Gödel G stelt: "waarheid" G niet te bewijzen." Indien G binnen de theorie zou kunnen worden bewezen, dan zou de theorie een stelling bevatten die zichzelf tegenspreekt, en daarom zou de theorie inconsistent zijn. Maar als G onbewijsbaar, dan is het waar, en daarom is de theorie onvolledig (de bewering G daarin niet af te leiden).

Deze uitleg is in de gebruikelijke natuurlijke taal, en daarom niet helemaal wiskundig rigoureus. Om een ​​rigoureus bewijs te leveren, nummerde Gödel uitspraken met: natuurlijke getallen. In dit geval behoort de theorie die getallen beschrijft ook tot de verzameling stellingen. Vragen over de bewijsbaarheid van stellingen kunnen worden weergegeven in deze zaak in de vorm van vragen over de eigenschappen van de natuurlijke getallen, die berekenbaar moeten zijn als de theorie compleet is. In deze termen zegt Gödels verklaring dat er geen nummer is met een bepaalde eigenschap. Een getal met deze eigenschap zal het bewijs zijn van de inconsistentie van de theorie. Als een dergelijk aantal bestaat, is de theorie inconsistent, in tegenstelling tot de oorspronkelijke veronderstelling. Dus aangenomen dat de theorie consistent is (zoals de premisse van de stelling suggereert), blijkt dat een dergelijk aantal niet bestaat, en de bewering van Gödel is waar, maar dit kan niet worden bewezen binnen het kader van de theorie (vandaar dat de theorie onvolledig is) . Een belangrijke conceptuele opmerking is dat men moet aannemen dat een theorie consistent is om de bewering van Gödel waar te maken.

Tweede onvolledigheidsstelling van Gödel

De tweede onvolledigheidsstelling van Gödel luidt als volgt:

Voor elke formeel recursief opsombare (dat wil zeggen, effectief gegenereerde) theorie T, inclusief elementaire rekenkundige waarheidsverklaringen en bepaalde formele bewijsbaarheidsverklaringen, deze theorie T bevat een uitspraak over de consistentie ervan als en alleen als de theorie T inconsistent is.

Met andere woorden, consistentie is genoeg rijke theorie kan met deze theorie niet worden bewezen. Het kan echter heel goed blijken dat de consistentie van een bepaalde theorie kan worden vastgesteld door middel van een andere, krachtigere formele theorie. Maar dan rijst de vraag naar de consistentie van deze tweede theorie, enzovoort.

Velen hebben geprobeerd deze stelling te gebruiken om te bewijzen dat intelligente activiteit niet kan worden teruggebracht tot berekeningen. In 1961 bedacht de beroemde logicus John Lucas bijvoorbeeld een soortgelijk programma. Zijn redenering bleek nogal kwetsbaar, maar hij stelde de taak breder. Roger Penrose hanteert een iets andere benadering, die in het boek volledig "from scratch" wordt gepresenteerd.

Discussies

De gevolgen van stellingen zijn van invloed op de filosofie van de wiskunde, vooral die formalismen die gebruik maken van formele logica om hun principes te definiëren. Men kan de eerste onvolledigheidsstelling als volgt herformuleren: het is onmogelijk om een ​​alomvattend systeem van axioma's te vinden dat zou kunnen bewijzen: alle wiskundige waarheden, en geen enkele leugen". Aan de andere kant, vanuit het oogpunt van strikte formaliteit, heeft deze herformulering weinig zin, aangezien zij ervan uitgaat dat de concepten "waar" en "onwaarheid" in absolute zin worden gedefinieerd, in plaats van in relatieve zin voor elk specifiek systeem.