Gödels ufuldstændighedssætninger (1931): definition og betydning

Forklaring af Gödels ufuldstændighedssætninger (1931): definition, konsekvenser og betydning for matematik og logik — hvorfor intet aksiomsystem kan forklare alt.

Gödels ufuldstændighedssætninger er navnet på to sætninger (sande matematiske udsagn), der blev bevist af Kurt Gödel i 1931. De hører til feltet matematisk logik og handler om begrænsninger i formelle axiomatiske systemer, især systemer kraftige nok til at beskrive almindelig aritmetik.

Hvad betyder ”komplet” og ”konsistent”?

Først nogle centrale begreber: Et formelt systems aksiomer og regler er komplet, hvis hvert udsagn i systemets sprog enten kan bevises eller dets negation kan bevises ud fra aksiomerne. Et system er konsistent, hvis det ikke indeholder nogen modsigelse — altså at man ikke kan bevise både et udsagn og dets negation. Aksiomer er grundantagelser, som accepteres uden bevis; de definerer systemet.

Hvad siger Gödels sætninger?

1. Der vil altid være spørgsmål, som ikke kan besvares ved hjælp af et bestemt sæt aksiomer;
2. Du kan ikke bevise, at et system af aksiomer er konsistent, medmindre du bruger et andet sæt aksiomer.

Formuleret lidt mere præcist:

• Første ufuldstændighedssætning: I ethvert effektivt axiomatisk system, der er stærkt nok til at repræsentere simpel talteori (fx Peano-aritmetik), findes der sande udsagn om naturlige tal, som ikke kan bevises inden for systemet. Gödel konstruerede en speciel formel G (ofte kaldet en Gödel-sætning) der i praksis siger: "G er ikke beviselig i systemet". Hvis systemet er konsistent, kan G ikke bevises i systemet, og dermed er systemet ufuldstændigt.
• Anden ufuldstændighedssætning: Samme slags system kan ikke bevises konsistent ved hjælp af de bevismetoder, som kan formaliseres inden for systemet selv. Mere formelt: Hvis systemet er konsistent, så kan det ikke bevise sin egen konsistens (givet at konsistensen kan udtrykkes i systemet).

Hvordan opnås dette? (kort forklaring)

Gödel brugte to nøgleteknikker:

• Gödel-nummerering: Hvert symbol, formel og bevis i systemet kodes som et naturligt tal. Dermed kan metaudsagn om beviser og formler formuleres som aritmetiske udsagn i systemet selv.
• Diagonaliserings- eller selvreference-trick: Ved hjælp af kodningen konstrueres en sætning, der i praksis siger noget om sin egen beviselighed (”jeg er ikke beviselig”). Denne selvhenvisning ligner paradokset ”Dette udsagn er falsk”, men Gödel undgik selvmotsigelsen ved at arbejde inden for et formelt aritmetisk sprog.

Vigtige betingelser

Gödels resultater gælder ikke for alle tænkelige systemer, men for systemer der opfylder visse krav:

• Systemet skal være effektivt axiomatisk (der skal findes en algoritme, som kan afgøre, om en given sætning er et aksiom eller ej).
• Systemet skal være stærkt nok til at udtrykke grundlæggende aritmetik (fx addition og multiplikation af naturlige tal).
• Resultaterne anvender antagelsen om, at systemet er konsistent. Hvis et system er inkonsistent, kan det bevise alt, og sætningerne mister deres almindelige fortolkning.

Betydning og konsekvenser

Gödels ufuldstændighedssætninger fik store konsekvenser for matematik og filosofien om matematik:

• De viste, at Hilberts program (målet om at finde et fuldstændigt og samtidig konsistent axiom-system, som kunne begrunde al matematik) ikke kan lykkes fuldt ud for alle ikke-trivielle systemer, der indeholder aritmetik.
• De banede vejen for senere resultater om beregnelighed og uafgørbarhed (fx Turing's arbejde om beregnelighed og Entscheidungsproblem), fordi ideerne om kodning og selvreference også ligger bag beviser for, at visse problemer ikke kan løses af nogen algoritme.
• De påvirker også matematikfilosofi: spørgsmålet om hvad der er "sandhed" vs. hvad der er "beviseligt" blev skarpere formuleret.

Ofte misforståelser

• Gödel sagde ikke, at matematisk tænkning er værdiløs eller at "ingenting kan bevises". Mange udsagn bevises fint i et givet system; sætningerne handler om, at der uundgåeligt findes udsagn, som ligger uden for beviskraften i systemet.
• Det betyder heller ikke, at alle matematiske spørgsmål er uafgørbare — kun at hvis systemet er stærkt nok, findes der enkelte sande udsagn, som ikke kan bevises i systemet.
• Uafhængighedsresultater som Gödels sætninger er teknisk beslægtede med senere resultater (fx uafhængighed af kontinuumhypotesen fra ZFC), men hver konkret uafhængighed kræver egne beviser.

Eksempler på systemer

Typiske systemer, hvor Gödels sætninger gælder, er Peano-aritmetik (PA) og standard axiomatiske systemer for sætteori som Zermelo–Fraenkel med Choice (ZFC). For disse systemer kan man konstruere sætninger, som hverken kan bevises eller modbevises inden for systemet (givet konsistens).

Samlet set viser Gödels ufuldstændighedssætninger, at ethvert tilstrækkeligt kraftigt formelt system har grundlæggende begrænsninger: vi kan ikke både have fuldstændighed og samtidig bevise vores systems konsistens indefra. Resultatet ændrede forståelsen af, hvad man kan forvente af formelle matematiske systemer og har fortsat indflydelse i logik, datalogi og filosofi.

Spørgsmål og svar

Spørgsmål: Hvad er Gödels ufuldstændighedssætninger?

Spørgsmål: Hvad er et fuldstændigt system i matematik?

Spørgsmål: Hvad er et ufuldstændigt system i matematik?

Spørgsmål: Hvad er et konsistent system i matematik?

Spørgsmål: Hvad er aksiomer i matematik?

Spørgsmål: Hvad påstod Gödel om ethvert ikke-trivielt formelt system?

Spørgsmål: Hvorfor er Gödels ufuldstændighedssætninger vigtige for matematikere?

Søg efter bogstav