Gödel-Nummerering
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 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.
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.
