Godels ufuldstændighedsteoremer

Godels ufuldstændighedssætning og Godels anden sætning [~ 1]  er to sætninger inden for matematisk logik om de grundlæggende begrænsninger af formel aritmetik og som en konsekvens af ethvert formelt system , hvor de grundlæggende aritmetiske begreber kan defineres: naturlige tal , 0 , 1 , addition og multiplikation .

Den første sætning siger, at hvis formel aritmetik er konsistent, så indeholder den en uigendrivelig og uigendrivelig formel.

Den anden sætning hævder, at hvis en formel aritmetik er konsistent, så er der en formel, der ikke kan udledes i den, som på en meningsfuld måde hævder konsistensen af ​​denne aritmetik.

Begge disse teoremer blev bevist af Kurt Gödel i 1930 (udgivet i 1931) og er direkte relateret til det andet problem i Hilberts berømte liste .

Historie

Tilbage i begyndelsen af ​​det 20. århundrede proklamerede David Hilbert målet om at aksiomatisere hele matematikken, og for at fuldføre denne opgave var det tilbage at bevise konsistensen og den logiske fuldstændighed af aritmetikken af ​​naturlige tal . Den 7. september 1930 blev der afholdt en videnskabelig kongres om matematikkens grundlag i Königsberg , og på denne kongres offentliggjorde den 24-årige Kurt Gödel først to grundlæggende ufuldstændighedssætninger, som viste, at Hilberts program ikke kan realiseres: for evt. valg af aksiomer for aritmetik, er der sætninger, der er umulige, hverken bevise eller modbevise med simple ( finite ) midler leveret af Hilbert, og et endeligt bevis for aritmetikkens konsistens er umuligt [6] .

Denne tale var ikke annonceret på forhånd og havde en forbløffende effekt, Gödel blev straks en verdensberømthed, og Hilberts program til at formalisere grundlaget for matematik krævede en hurtig revision. Den 23. oktober 1930 blev Gödels resultater præsenteret for Videnskabsakademiet i Wien af ​​Hans Hahn . En artikel med begge sætninger (" Om fundamentalt uafklarelige påstande i Principia Mathematica og relaterede systemer ") blev offentliggjort i det videnskabelige månedsblad Monatshefte für Mathematik und Physik i 1931. Selvom Gödel kun gav beviset for den anden sætning i form af en idé, var hans resultat så klart og ubestrideligt, at ingen tvivlede på det. Hilbert erkendte straks værdien af ​​Gödels opdagelser; de første fuldstændige beviser for begge teoremer blev offentliggjort i Hilbert og Bernays 'Fundament of Mathematics (1938). I forordet til andet bind anerkendte forfatterne, at endelige metoder ikke er nok til at nå deres mål, og tilføjede transfinit induktion til listen over logiske midler ; i 1936 lykkedes det Gerhard Gentzen at bevise konsistensen af ​​aritmetik ved hjælp af dette aksiom, men logisk fuldstændighed forblev uopnåelig [6]

Godels ufuldstændighedssætning

I sin oprindelige form

I sin formulering af ufuldstændighedssætningen brugte Gödel forestillingen om et ω-konsistent formelt system, en stærkere betingelse end blot konsistens. Et formelt system kaldes ω-konsistent, hvis det for en hvilken som helst formel A ( x ) i dette system er umuligt samtidigt at udlede formlerne A ( 0 ), A ( 1 ), A ( 2 ), ... og ∃ x ¬ A ( x ) (med andre ord, af det faktum, at for hvert naturligt tal n er formlen A ( n ) afledelig, følger det, at formlen ∃ x ¬ A ( x ) ikke kan udledes). Det er let at vise, at ω-konsistens indebærer simpel konsistens (det vil sige, at ethvert ω-konsistent formelt system er konsistent) [7] .

I processen med at bevise sætningen konstrueres en sådan formel A for et aritmetisk formelt system S, at [7] :

Hvis det formelle system S er konsistent, så kan formlen A ikke udledes i S ; hvis systemet S er ω-konsistent, så kan formlen ¬A ikke udledes i S . Således, hvis et system S er ω-konsistent, så er det ufuldstændigt [~ 2] , og A er et eksempel på en uløselig formel.

Formlen A kaldes undertiden den Gödel uløselige formel [8] .

Fortolkning af den uløselige formel

I standardfortolkningen [~ 3] betyder formlen A "der er ingen afledning af formlen A ", dvs. hævder sin egen ikke-afledningsevne i S. Derfor, ved Gödels sætning, hvis blot systemet S er konsistent, så er denne formel faktisk ikke-afledbar i S og derfor sand i standardfortolkningen. For naturlige tal er formlen A altså sand, men i S er den ikke udledelig [9] .

I Rosser-uniform

I processen med at bevise sætningen konstrueres en sådan formel B for et aritmetisk formelt system S, at [10] :

Hvis et formelt system S er konsistent, så er både formlerne B og ¬B ikke-afledelige i det; med andre ord, hvis systemet S er konsistent, så er det ufuldstændigt [~ 2] , og B er et eksempel på en uløselig formel.

Formlen B kaldes undertiden Rossers uløselige formel [11] . Denne formel er lidt mere kompliceret end Gödels.

Fortolkning af den uløselige formel

I standardfortolkningen [~3] betyder formel B "hvis der er en afledning af formel B , så er der en afledning af formel ¬B " . Men ifølge Gödels sætning i form af Rosser, hvis et formelt system S er konsistent, så er formlen B i det ikke-afledelig; derfor, hvis systemet S er konsistent, så er formlen B korrekt i standardfortolkningen [12] .

Generaliserede formuleringer

Beviset for Gödels sætning udføres normalt for et specifikt formelt system (ikke nødvendigvis det samme), og derfor viser sætningens udsagn sig kun at være bevist for dette system alene. Studiet af tilstrækkelige betingelser, som et formelt system skal opfylde for at kunne bevise dets ufuldstændighed, fører til generaliseringer af teoremet til en bred klasse af formelle systemer. Et eksempel på en generaliseret formulering [13] :

Enhver tilstrækkelig stærk rekursivt aksiomatiserbar konsistent førsteordensteori er ufuldstændig.

Især gælder Gödels sætning for hver konsistent endeligt aksiomatiserbar forlængelse af et aritmetisk formelt system S.

Polynomisk form

Efter at Yuri Matiyasevich beviste , at ethvert effektivt optalbart sæt er diofant , og der blev fundet eksempler på universelle diofantiske ligninger , blev det muligt at formulere ufuldstændighedssætningen i polynomisk (eller diofantisk) form [14] [15] [16] [17] :

For hver konsistente teori T kan man angive en heltalsværdi af parameteren K, således at ligningen har ingen løsninger i ikke-negative heltal, men dette faktum kan ikke bevises i teorien T . Desuden, for hver konsistent teori, er værdisættet af parameteren K, der har denne egenskab, uendeligt og algoritmisk ikke-tælleligt .

Graden af ​​denne ligning kan reduceres til 4 på bekostning af at øge antallet af variable.

Skitse af beviset

Gödel giver i sit papir en oversigt over bevisets hovedideer [18] , som er gengivet nedenfor med mindre ændringer.

Hvert primitivt symbol, udtryk og sekvens af udtryk for et formelt system [~ 4] S vil være forbundet med et bestemt naturligt tal [~ 5] . Matematiske begreber og udsagn bliver således til begreber og udsagn om naturlige tal, og kan derfor selv udtrykkes i symbolikken i systemet S. Det kan især påvises, at begreberne "formel", "afledning", "afledt" formel" er definerbare i systemet S, dvs. det er muligt at gendanne f.eks. en formel F ( v ) i S med én fri naturlig talvariabel v , således at F ( v ), i en intuitiv fortolkning, betyder: v  er en afledelig formel. Lad os nu konstruere en uafgørlig sætning af systemet S, det vil sige en sætning A , for hvilken hverken A eller ikke-A er ikke- afledbar, som følger:

En formel i S med præcis én fri naturlig talvariabel kaldes et klasseudtryk . Lad os ordne klasseudtryk i en sekvens på en eller anden måde, betegne n'te ved R ( n ), og bemærke, at begrebet "klasseudtryk", såvel som ordensrelationen R , kan defineres i systemet S. Lad os α være et vilkårligt klasseudtryksudtryk; gennem [α; n ] betegne den formel, der dannes ud fra klasseudtrykket α ved at erstatte den frie variabel med symbolet for et naturligt tal n . Ternær relation x = [ y ; z ] viser sig også at være definerbar i S. Nu definerer vi klassen K af naturlige tal som følger:

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

(hvor Bew x betyder: x  er den afledte formel [~ 6] ). Da alle de definerende begreber fra denne definition kan udtrykkes i S, gælder det samme for begrebet K , som er konstrueret ud fra dem, det vil sige, at der er et sådan klasseudtryk C , at formlen [ C ; n ], som er intuitivt fortolket, betyder, at et naturligt tal n hører til K . Som klasseudtryk er C identisk med et bestemt R ( q ) i vores opregning, dvs.

C = R ( q )

gælder for et bestemt naturligt tal q . Lad os nu vise, at sætningen [ R ( q ); q ] er uafgørlig i S. Hvis sætningen [ R ( q ); q ] antages at være afledelig, så viser det sig at være sandt, dvs. ifølge ovenstående vil q tilhøre K , det vil sige ifølge (*), ¬Bew[ R ( q ); q ], hvilket modsiger vores antagelse. På den anden side, hvis vi antager afledbar negationen [ R ( q ); q ], så vil ¬ q ∈ K finde sted , det vil sige Bew[ R ( q ); q ] vil være sandt. Derfor [ R ( q ); q ] sammen med dens negation vil kunne udledes, hvilket igen er umuligt.

Forbindelse med paradokser

I standardfortolkningen [~3] betyder Gödels uafslutbare formel A "der er ingen afledning af formlen A ", dvs. hævder sin egen ikke-afledelse i systemet S. Således er A analogen til løgnerparadokset . Gödels ræsonnement er stort set meget lig Richards paradoks . Desuden kan ethvert semantisk paradoks bruges til at bevise eksistensen af ​​ikke-afledte udsagn [19] .

Det skal bemærkes, at påstanden udtrykt ved formel A ikke indeholder en ond cirkel, da det i første omgang kun hævdes, at en bestemt formel, hvis eksplicitte udtryk er let (omend besværlig), er ubeviselig. "Først senere (og så at sige tilfældigt) viser det sig, at denne formel netop er den, der udtrykker selve dette udsagn" [19] .

Gödels anden sætning

I formel aritmetik S kan man konstruere en formel, der i standardfortolkningen [~ 3] er sand, hvis og kun hvis teorien S er konsistent. For denne formel er udsagnet i Gödels anden sætning sand:

Hvis en formel aritmetisk S er konsistent, så er der ingen afledelig formel i den, der på en meningsfuld måde hævder konsistensen af ​​S .

Med andre ord kan konsistensen af ​​formel aritmetik ikke bevises ved hjælp af denne teori. Imidlertid kan der være beviser for konsistensen af ​​formel aritmetik ved hjælp af midler, der er uudsigelige i den.

Skitse af beviset

Først konstrueres en formel Con , som meningsfuldt udtrykker umuligheden af ​​at udlede en formel i teorien S, sammen med dens negation. Så er påstanden om Gödels første sætning udtrykt ved formlen Con ⊃ G , hvor G  er en Gödel uløselig formel. Alle argumenter for beviset for den første sætning kan udtrykkes og udføres ved hjælp af S, det vil sige, at formlen Con ⊃ G kan udledes i S. Derfor, hvis Con er afledelig i S , så er G også afledelig i den . Men ifølge Gödels første sætning, hvis S er konsistent, så er G ikke-afledbar i den. Derfor, hvis S er konsistent, så er formlen Con også ikke-afledbar i den .

Historisk indflydelse

Eksperter giver meget forskellige, nogle gange endda polære, vurderinger af den historiske betydning af Gödels sætninger. Nogle videnskabsmænd mener, at disse teoremer "vendte" grundlaget for matematikken eller endda hele vidensteorien , og betydningen af ​​Gödels strålende opdagelse vil gradvist blive afsløret i lang tid fremover [20] . Andre (for eksempel Bertrand Russell ) opfordrer til ikke at overdrive, da sætningerne er baseret på Hilberts endelige formalisme [21] [22] .

I modsætning til den almindelige misforståelse indebærer Gödels ufuldstændighedssætninger ikke, at nogle sandheder aldrig vil blive kendt for evigt. Desuden følger det ikke af disse teoremer, at den menneskelige evne til erkendelse på en eller anden måde er begrænset. Nej, sætningerne viser kun de formelle systemers svagheder og mangler [23] .

Overvej for eksempel følgende bevis for aritmetikkens konsistens [24] .

Lad os antage, at Peanos aksiomatik for aritmetik er inkonsekvent. Så kan ethvert udsagn udledes af det, inklusive falsk. Alle Peanos aksiomer er dog åbenbart sande, og en falsk konklusion kan ikke følge af sande udsagn – vi får en selvmodsigelse. Derfor er regnestykket konsistent.

Fra et synspunkt af den daglige menneskelige logik er dette bevis acceptabelt og overbevisende. Men det kan ikke skrives efter reglerne i Hilberts bevisteori, da semantik i disse regler erstattes af syntaks, og sandhed erstattes af "deducibility" [24] . Under alle omstændigheder løftede Gödels sætninger matematikfilosofien til et nyt niveau.

Se også

Noter

Kommentarer
  1. ↑ Nogle gange omtalt som Gödels anden sætning "om beviser for konsistens" [1] , "om ufuldstændighed" [2] [3] [4] , "om ufuldstændigheden af ​​aritmetik" [5] .
  2. ↑ 1 2 Et formelt system, der indeholder en ubeslutsom, dvs. ikke-afledbar og uigendrivelig formel, kaldes ufuldstændig.
  3. ↑ 1 2 3 4 En fortolkning af formlerne for en teori S kaldes standard, hvis dens domæne er et sæt af ikke-negative heltal, symbolet 0 fortolkes med tallet 0, funktionsbogstaverne ', +, • fortolkes af ved at lægge et til, henholdsvis addition og multiplikation, fortolkes prædikatbogstavet = af identitetsrelationen.
  4. ↑ Gödel brugte Whitehead og Russells Principia Mathematica , med det forbehold, at ræsonnementet gælder for en bred klasse af formelle systemer.
  5. ↑ En sådan sammenligning af formler og naturlige tal kaldes matematikkens aritmetisering og blev udført for første gang af Gödel. Denne idé blev efterfølgende nøglen til at løse mange vigtige problemer inden for matematisk logik. Se Gödel nummerering
  6. ↑ "Bew" forkortelse. fra ham. "Beweisbar" - bevisbar , uddragbar
Kilder
  1. ↑ Kleene 1957 s.513
  2. ↑ tilsvarende medlem RAS Lev Dmitrievich Beklemishev i "Introduktion til matematisk logik" . Dato for adgang: 7. januar 2010. Arkiveret fra originalen 21. marts 2009.
  3. ↑ Explanatory Dictionary of Computing Systems - Side 205
  4. ↑ Rapporter fra USSR's Videnskabsakademi, bind 262 - side 799 (1982)
  5. ↑ Proceedings of the Academy of Sciences of the USSR, bind 50 - side 1140 (1986)
  6. ↑ 1 2 Pinheiro, 2015 , s. 13, 48-49, 66, 89-90.
  7. ↑ 1 2 Kleene 1957 s.187
  8. ↑ Mendelssohn 1971 s.165
  9. ↑ Dette ræsonnement er taget fra Mendelssohn 1971 s.160
  10. ↑ Se f.eks. Kleene 1957 s.188
  11. ↑ Mendelssohn 1971 s.162
  12. ↑ Mendelssohn 1971 s. 162-163
  13. ↑ Mendelssohn 1971 s.176
  14. ↑ Jones JP, Undecidable diophantine equations
  15. ↑ Martin Davis, Diophantine Equations & Computation (link utilgængeligt) . Hentet 17. november 2009. Arkiveret fra originalen 24. maj 2010. 
  16. ↑ Martin Davis, The Incompleteness Theorem . Hentet 30. november 2011. Arkiveret fra originalen 4. marts 2016.
  17. ↑ K. Podnieks, Gödels sætning i diofantisk form . Hentet 17. november 2009. Arkiveret fra originalen 10. september 2017.
  18. ↑ Godel, Kurt. Om formelt uafgørlige påstande fra Principia Mathematica og beslægtede systemer. I. - 1931. i Davis, Martin (red.). Det uafklarelige: Grundlæggende artikler om uafklarelige påstande, uløselige problemer og beregnelige funktioner . - New York: Raven Press, 1965. - S.  6 -8.
  19. ↑ 1 2 Gödel 1931
  20. ↑ Stephen Hawking . Godel and the End of the Universe (utilgængeligt link) . Hentet 8. april 2018. Arkiveret fra originalen 29. maj 2020. 
  21. ↑ Mikhailova N.V. Problemet med at underbygge moderne matematik i forbindelse med nye filosofiske og metodiske kriser // Mathematics Philosophy: Actual Problemer. Matematik og virkelighed. Sammendrag af den tredje alrussiske videnskabelige konference; 27.-28. september 2013 . - M . : Center for Strategisk Konjunktur, 2013. - S. 187. - 270 s. - ISBN 978-5-906233-39-4 . Arkiveret 16. december 2017 på Wayback Machine
  22. ↑ Musiker A. .
  23. ↑ Livio, Mario. Var Gud en matematiker? Kapitel "Sandhed i ufuldstændighed". - M. : AST, 2016. - 384 s. — (videnskabens gyldne fond). - ISBN 978-5-17-095136-9 .
  24. ↑ 1 2 Pinheiro, 2015 , s. 155-162.

Litteratur

Links

Bibliografi - artikler af Gödel

  • 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38 : 173-198.
  • 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. og On formally unecidable propositions of Principia Mathematica and related systems I in Solomon Feferman , ed., 1986. Kurt Gödel Collected works, Vol. I. _ Oxford University Press: 144-195. - Original tysk tekst med parallel engelsk oversættelse, med en rudimentær introduktion skrevet af Stephen Kleene .
  • Hirzel, Martin, 2000, Om formelt uafklarelige udsagn om Principia Mathematica og relaterede systemer I. . - Moderne oversættelse af Marina Herzel.
  • 1951, Nogle grundlæggende teoremer om grundlaget for matematik og deres implikationer i Solomon Feferman , red., 1995. Kurt Gödel Samlede værker, Vol. III . Oxford University Press: 304-323.