Gödel numrering

Inom matematisk logik är en Gödel-numrering en funktion som tilldelar varje symbol och välformad formel för något formellt språk ett unikt naturligt tal , som kallas dess Gödel-nummer . Konceptet utvecklades av Kurt Gödel för att bevisa hans ofullständighetsteorem . ( Gödel 1931 )

En Gödel-numrering kan tolkas som en kodning där ett nummer tilldelas varje symbol i en matematisk notation , varefter en sekvens av naturliga tal sedan kan representera en sekvens av symboler. Dessa sekvenser av naturliga tal kan återigen representeras av enstaka naturliga tal, vilket underlättar deras manipulation i formella aritmetiska teorier.

Sedan utgivningen av Gödels tidning 1931 har termen "Gödelnumrering" eller "Gödelkod" använts för att hänvisa till mer generella tilldelningar av naturliga tal till matematiska objekt.

Förenklad översikt

Gödel noterade att varje påstående inom ett system kan representeras av ett naturligt tal (dess Gödel-tal ) . Betydelsen av detta var att egenskaper hos ett påstående – såsom dess sanning eller falskhet – skulle vara likvärdigt med att avgöra om dess Gödelnummer hade vissa egenskaper. Antalet inblandade kan verkligen vara mycket stort, men detta är inte ett hinder; allt som spelar roll är att sådana siffror kan konstrueras.

Enkelt uttryckt tog han fram en metod där varje formel eller påstående som kan formuleras i systemet får ett unikt nummer, på ett sådant sätt att formler och Gödel-tal kan omvandlas mekaniskt fram och tillbaka. Det finns många sätt detta kan göras. Ett enkelt exempel är det sätt på vilket engelska lagras som en nummersekvens i datorer som använder ASCII . Eftersom ASCII-koder är i intervallet 0 till 127 räcker det att fylla dem med 3 decimaler och sedan sammanfoga dem:

Ordet foxy representeras av 102 111 120 121 .
Den logiska formeln x=y => y=x representeras av 120 061 121 032 061 062 032 121 061 120 .

Gödels kodning

Gödels originalkodning
								talvariabler				egenskapsvariabler			...
Symbol	0	s	¬	∨	∀	(	)	x ₁	x ₂	x ₃	...	P ₁	P ₂	P ₃	...
siffra	1	3	5	7	9	11	13	17	19	23	...	289	361	529	...

Gödel använde ett system baserat på primtalsfaktorisering . Han tilldelade först ett unikt naturligt nummer till varje grundläggande symbol i det formella aritmetiska språket som han hade att göra med.

För att koda en hel formel, som är en sekvens av symboler, använde Gödel följande system. Givet en sekvens $(x_{1},x_{2},x_{3},...,x_{n})$ av positiva heltal, Gödel-kodningen av sekvensen är produkten av de första n primtal som höjts till deras motsvarande värden i sekvensen:

\mathrm {enc} (x_{1},x_{2},x_{3},\dots,x_{n})=2^{x_{1}}\cdot 3^{x_{2} }\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.

Enligt aritmetikens grundsats kan vilket tal som helst (och i synnerhet ett tal som erhålls på detta sätt) unikt faktoriseras till primtalsfaktorer , så det är möjligt att återskapa den ursprungliga sekvensen från dess Gödel-tal (för ett givet tal n) symboler som ska kodas).

Gödel använde specifikt detta schema på två nivåer: för det första för att koda sekvenser av symboler som representerar formler, och för det andra för att koda sekvenser av formler som representerar bevis. Detta gjorde det möjligt för honom att visa en överensstämmelse mellan påståenden om naturliga tal och påståenden om bevisbarheten av satser om naturliga tal, den viktigaste observationen av beviset. ( Gödel 1931 )

Det finns mer sofistikerade (och mer koncisa) sätt att konstruera en Gödel-numrering för sekvenser .

Exempel

I den specifika Gödel-numreringen som används av Nagel och Newman är Gödel-talet för symbolen "0" 6 och Gödel-numret för symbolen "=" är 5. I deras system är alltså Gödel-talet för formeln "0 = 0" är 2 ⁶ × 3 ⁵ × 5 ⁶ = 243 000 000.

Brist på unikhet

Oändligt många olika Gödel-numrering är möjliga. Om man till exempel antar att det finns K grundläggande symboler, skulle en alternativ Gödel-numrering kunna konstrueras genom att inverterbart mappa denna uppsättning symboler (genom, säg, en inverterbar funktion h ) till uppsättningen siffror i ett bijektivt bas- K -talsystem . En formel bestående av en sträng av n symboler $s_{1}s_{2}s_{3}\dots s_{n}$ skulle sedan mappas till talet

h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n- 1})\ gånger K^{1}+h(s_{n})\ gånger K^{0}.

Med andra ord, genom att placera uppsättningen av K grundsymboler i någon fast ordning, så att $i$ -te symbolen motsvarar unikt i { $displaystyle i}$ -te siffran i ett bijektivt bas- K siffersystem , kan varje formel fungera som själva siffran för sitt eget Gödel-tal.

har numreringen som beskrivs här K=1000.

Ansökan till formell aritmetik

Rekursion

Man kan använda Gödel-numrering för att visa hur funktioner definierade av värdeförloppsrekursion i själva verket är primitiva rekursiva funktioner .

Att uttrycka påståenden och bevis med siffror

När väl en Gödel-numrering för en formell teori är etablerad kan varje slutledningsregel i teorin uttryckas som en funktion på de naturliga talen. Om f är Gödel-avbildningen och r är en inferensregel, så borde det finnas någon aritmetisk funktion g _r av naturliga tal så att om formel C härleds från formler A och B genom en inferensregel r , dvs.

A,B\vdash _{r}C,

sedan

g_{r}(f(A),f(B))=f(C).

Detta gäller för numreringen som Gödel används, och för alla andra numreringar där den kodade formeln kan återställas aritmetiskt från dess Gödel-nummer.

I en formell teori som Peano-arithmetik där man kan göra påståenden om tal och deras aritmetiska relationer till varandra, kan man alltså använda en Gödel-numrering för att indirekt göra påståenden om själva teorin. Denna teknik gjorde det möjligt för Gödel att bevisa resultat om konsistens och fullständighetsegenskaper hos formella system .

Generaliseringar

I beräkningsbarhetsteorin används termen "Gödel-numrering" i inställningar mer generella än den som beskrivs ovan. Det kan syfta på:

Varje tilldelning av elementen i ett formellt språk till naturliga tal på ett sådant sätt att talen kan manipuleras av en algoritm för att simulera manipulation av element i det formella språket. ^{[ citat behövs ]}
Mer generellt, en tilldelning av element från ett räknebart matematiskt objekt, såsom en räknebar grupp , till naturliga tal för att tillåta algoritmisk manipulation av det matematiska objektet. ^{[ citat behövs ]}

Även termen Gödel-numrering används ibland när de tilldelade "numren" faktiskt är strängar, vilket är nödvändigt när man överväger beräkningsmodeller som Turing-maskiner som manipulerar strängar snarare än siffror. ^{[ citat behövs ]}

Gödel ställer

Gödel-mängder används ibland i mängdteorin för att koda formler, och liknar Gödel-tal, förutom att man använder mängder snarare än siffror för att göra kodningen. I enkla fall när man använder en ärftligt ändlig mängd för att koda formler är detta i huvudsak likvärdigt med användningen av Gödel-tal, men något lättare att definiera eftersom formlers trädstruktur kan modelleras av mängdens trädstruktur. Gödel-uppsättningar kan också användas för att koda formler i infinitära språk .

Se även

Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF) , Monatshefte für Mathematik und Physik , 38 : 173–198, doi : 10.1007/BF01700692 , S2CID 197663120 , archived from the original ( PDF) 2018-04-11 , hämtad 2013-12-07 .
Gödels bevis av Ernest Nagel och James R. Newman (1959). Denna bok ger en bra introduktion och sammanfattning av beviset, med ett stort avsnitt tillägnat Gödels numrering.

Vidare läsning

Gödel, Escher, Bach: an Eternal Golden Braid , av Douglas Hofstadter . Denna bok definierar och använder en alternativ Gödel-numrering.
I Am a Strange Loop av Douglas Hofstadter . Detta är en nyare bok av Hofstadter som innehåller historien om Gödels numrering.
Visualisera Turing Tarpit av Jason Hemann och Eric Holk. Använder Gödel-numrering för att koda program.