Gödel-nummerering: Definition og kodning af formler i talteori
Gödel-nummerering: Lær hvordan symboler og formler i formel talteori kodes som naturlige tal, og hvorfor det er centralt for Gödels ufuldstændighedssætning.
I formel talteori er en Gödel-nummerering en funktion, der tildeler hvert symbol og hver formel i et formelt sprog et unikt naturligt tal kaldet Gödel-nummer (GN). Begrebet blev første gang anvendt af Kurt Gödel til beviset for hans ufuldstændighedssætning. En sådan nummerering gør det muligt at behandle syntaks (symboler, formler, beviser) som objekter i talteori ved at repræsentere dem som tal.
En Gödel-nummerering kan fortolkes som en kodning, hvor der til hvert symbol i en matematisk notation tildeles et tal, og en strøm af naturlige tal kan derefter repræsentere en form eller funktion. En nummerering af mængden af beregnelige funktioner kan derefter repræsenteres af en strøm af Gödel-tal (også kaldet effektive tal). Rogers' ækvivalenssætning angiver kriterier for, hvilke nummereringer af mængden af beregnelige funktioner der er Gödel-nummereringer.
Formel definition og krav
Formelt er en Gödel-nummerering en injektiv funktion g fra mængden af (finite) syntaktiske objekter i et formelt sprog (f.eks. symboler, udtryk, formler, sekvenser af tegn) til naturlige tal. Ofte stilles der ekstra krav om, at både kodningen og dekodningen er effektive, dvs. beregnelige eller endda primitive-rekursive. Det vil sige:
- Injektivitet: Forskellige syntaktiske objekter får forskellige Gödel-numre.
- Effektivitet: Der eksisterer en (primitive-rekursiv eller beregnelig) procedure, som fra et tal kan rekonstruere det tilhørende syntaktiske objekt, og omvendt.
- Konkateneringsvenlighed: En måde at kombinere koder (f.eks. for at kode en sekvens af symboler) bør være beregnelig, så man kan kode/afkode sammensatte strukturer.
Typiske kodningsmetoder
Der findes flere standardmetoder til at konstruere en Gödel-nummerering. De mest brugte i teoretisk behandling er:
- Primtal-eksponent-kodning: Hvert symbol får et naturligt tal som indeks, og en sekvens af symboler a1,a2,...,an kodes som produktet p1^{a1} p2^{a2} ... pn^{an}, hvor p1,p2,... er de første primtal. Denne kodning er entydig pga. primtalsfaktoriseringen.
- Parringsfunktioner: Bijektive funktioner N×N → N (fx Cantors parringsfunktion) udvides til at kode sekvenser og træstrukturer gennem iterativ parring.
- Positionskodning (base-kodning): Symboler tildeles cifre i en stor base, og en streng repræsenteres som et tal i denne base; ofte kombineret med separatorer for at sikre entydighed.
Egenskaber og varianter
Alle "rimelige" Gödel-nummereringer er ækvivalente i den forstand, at man kan gå fra én nummerering til en anden ved en beregnelig bijektion på de naturlige tal. Mange resultater forudsætter desuden, at nummereringen er effectiv (dvs. både kodning og dekodning er beregnelige funktioner). Nogle yderligere bemærkninger:
- Gödel-nummereringen kan gøres primitive-rekursiv, hvilket er nyttigt i beviser, hvor man ønsker totale, effektive operationer på koder.
- Entydighed opnås normalt ved at sikre, at forskellige objekter ikke deler samme kode; men konstruktionen af kodningen er ofte ikke unik — kun op til beregnelige permutationer.
- En god nummerering gør det muligt at beskrive relationer som "x er et gyldigt bevis for y" eller "x er en kode for en korrekt formel" som aritmetiske (ofte rekursive eller primitive-rekursive) relationer på Gödel-numrene.
Anvendelse: Gödels ufuldstændighed og videre
Gödel brugte en specifik form for nummerering til at omforme påstande om sætninger og beviser til udsagn om naturlige tal. Derved kunne han konstruere en sætning, der siger om sig selv, at den ikke er bevisbar i teorien — et centralt skridt i beviset for hans første ufuldstændighedssætning. Generelt er Gödel-nummerering fundamentet for at gøre metamatematiske påstande til aritmetiske udsagn.
Rogers' ækvivalenssætning
Rogers' ækvivalenssætning (i recursivitetsteori) giver kriterier for, hvornår to nummereringer af mængden af beregnelige funktioner kan betragtes som ækvivalente. Sætningen karakteriserer, hvilke nummereringer der bevarer den effektive struktur — kort sagt: to 'rigtige' Gödel-nummereringer adskiller sig kun ved en beregnelig permutation.
Praktiske bemærkninger
I praksis vælger man ofte en kodning, som er let at arbejde med i beviser (fx primtal-kodning eller primitive-rekursive koder). Ved implementering i computerbeviser eller formelle systemer bruges kodninger, der gør parsing og manipulation af syntaks effektiv. Det væsentlige er, at kodningen gør syntaks til et aritmetisk objekt uden at miste den nødvendige beregnelighed.
Samlet set er Gödel-nummerering et centralt koncept i logik og beregnelighedsteori, som forbinder syntaktiske konstruktioner med tal og dermed gør det muligt at formulere og bevise dybe metamatematiske resultater.
Definition
Givet en tællelig mængde S er en Gödel-nummerering en injektiv funktion
f : S → N {\displaystyle f:S\til \mathbb {N} } 
med både f og f - 1{\displaystyle f^{-1}}} 
(det omvendte af f) er beregnelige funktioner.
Eksempler
Basisnotation og strenge
En af de enkleste Gödel-nummersystemer anvendes hver dag: Korrespondancen mellem hele tal og deres repræsentationer som symbolstrenge. F.eks. forstås sekvensen 2 3 ved et bestemt sæt regler som svarende til tallet 23. På samme måde kan symbolstrenge fra et alfabet med N symboler indkodes ved at identificere hvert symbol med et tal fra 0 til N og læse strengen som base N+1-repræsentationen af et heltal.
Spørgsmål og svar
Spørgsmål: Hvad er en Gödel-nummerering?
Svar: En Gödel-nummerering er en funktion, der tildeler et unikt naturligt tal til hvert symbol og hver formel i et formelt sprog, kaldet et Gödel-tal (GN).
Sp: Hvem brugte først begrebet Gödel-nummerering?
Svar: Kurt Gödel brugte først begrebet Gödel-nummerering i forbindelse med beviset for sit ufuldstændighedssætnings-sæt.
Spørgsmål: Hvordan kan vi fortolke Gödels nummerering?
A: Vi kan fortolke Gödels nummerering som en kodning, hvor hvert symbol i en matematisk notation tildeles et tal, og en strøm af naturlige tal kan repræsentere en form eller funktion.
Spørgsmål: Hvad kalder vi de naturlige tal, der er tildelt ved Gödel-nummerering?
Svar: De naturlige tal, der tildeles ved en Gödel-nummerering, kaldes Gödel-tal eller effektive tal.
Spørgsmål: Hvad siger Rogers' ækvivalenssætning?
Svar: Rogers' ækvivalenssætning angiver kriterier for, hvilke nummereringer af mængden af beregnelige funktioner der er Gödel-nummereringer.
Spørgsmål: Hvad repræsenteres af en strøm af Gödel-tal?
Svar: En nummerering af mængden af beregnelige funktioner kan repræsenteres af en strøm af Gödel-tal.
Spørgsmål: Hvorfor er Gödel-nummerering vigtig i formel talteori?
Svar: Gödel-nummerering er vigtig i formel talteori, da den giver mulighed for at repræsentere matematiske formler og funktioner som naturlige tal, hvilket gør det muligt at bevise vigtige sætninger som f.eks. ufuldstændighedsteoremet.
Søge