Gödel nummerering

Gödel-nummerering er en funktion g , der tildeler hvert objekt på et formelt sprog dets nummer. Det kan bruges til eksplicit at opregne følgende sprogobjekter: variabler, objektkonstanter, funktionssymboler, prædikatsymboler og formler bygget ud fra dem. Konstruktionen af Gödel-nummerering for objekter i en teori kaldes aritmetisering af en teori - det giver dig mulighed for at oversætte udsagn, aksiomer, teoremer, teorier til aritmetiske objekter . Det kræves, at opregningen g kan beregnes effektivt, og for ethvert naturligt tal er det muligt at bestemme, om det er et tal eller ej, og hvis det er det, så konstruer det tilsvarende objekt for sproget. Gödel-nummerering minder meget om tegn-for-tegn- kodning af strenge med tal, med den forskel, at sammenkædningen af tal af samme længde ikke bruges til at kode sekvenser af bogstavtal, men aritmetikkens grundlæggende sætning .

Gödel nummerering blev anvendt af Gödel som et værktøj til at bevise ufuldstændigheden af formel aritmetik .

En variant af Gödel-nummereringen af førsteordens formelle teori

Lade være en første ordens teori indeholdende variabler , objektkonstanter , funktionssymboler og prædikatsymboler , hvor er tallet og er ariteten af det funktionelle eller prædikatsymbol. $\mathrm{K}$ $x_1,x_2,...$ $a_{1},a_{2},...$ $f_{k}^{n}$ $A_{k}^{n}$ $k$ $n$

Hvert symbol i en vilkårlig førsteordensteori er forbundet med dets Gödel-nummer som følger: [1] $u$ $\mathrm{K}$ $g(u)$

$g(()=3;\ g())=5;\ g(,)=7;\ g(\neg )=9;\ g(\to )=11;$

$g(x_{k})=5+8k,\k=1,2,...;$

$g(a_{k})=7+8k,\k=1,2,...;$

$g(f_{k}^{n})=9+8\cdot 2^{n}3^{k},\ k,n\geqslant 1;$

$g(A_{k}^{n})=11+8\cdot 2^{n}3^{k},\ k,n\geqslant 1.$

Gödelnummer for en vilkårlig sekvens af udtryk er defineret som følger: . $e_{0},...,e_{r}$ $g(e_{0},...,e_{r})=2^{{g(e_{0})}}\cdot 3^{{g(e_{1})}}\cdot ... \cdot p_{r}^{{g(e_{r})}}$

Der er også andre Gödel-nummereringer af formel aritmetik.

Eksempel

$g(A_{1}^{2}(x_{1},x_{2}))=2^{{g(A_{1}^{2})}}\cdot 3^{{g(() }}\cdot 5^{{g(x_{1})}}\cdot 7^{{g(,)}}\cdot 11^{{g(x_{2})}}\cdot 13^{{ g())}}=2^{{107}}\cdot 3^{{3}}\cdot 5^{{13}}\cdot 7^{{7}}\cdot 11^{{21}} \cdot 13^{{5}}$

Generaliseringer

Generelt kaldes opregningen af et sæt en overalt defineret surjektiv mapping . Hvis , så kaldes nummeret på objektet . Særlige tilfælde - sprog og teorier. $F$ $\nu :{\mathbb {N}}\til F$ $\nu(n)=f$ $n$ $f$ $F$

Noter

↑ Mendelssohn, 1971 , §4. Aritmetisering, Gödel-numre, s. 151-152.

Litteratur

Klini S.K. Introduktion til metamatematik . - M. : IL, 1957. - 526 s.
Mendelsohn E. Introduktion til matematisk logik . - M . : "Nauka", 1971. - 320 s.

Se også

Godels ufuldstændighedssætning