Gödel numrering

Gödelnumrering är en funktion g som tilldelar varje objekt på något formellt språk dess nummer. Den kan användas för att uttryckligen räkna upp följande språkobjekt: variabler, objektkonstanter, funktionssymboler, predikatsymboler och formler byggda från dem. Konstruktionen av Gödel-numrering för objekt i en teori kallas aritmetisering av en teori - den låter dig översätta påståenden, axiom, satser, teorier till aritmetiska objekt . Det krävs att uppräkningen g är effektivt beräkningsbar och för vilket naturligt tal som helst är det möjligt att avgöra om det är ett tal eller inte, och om det är det, konstruera sedan motsvarande objekt för språket. Gödel-numrering påminner mycket om tecken-för-tecken- kodning av strängar med siffror, med skillnaden att sammanlänkningen av siffror av samma längd inte används för att koda sekvenser av bokstavssiffror, utan aritmetikens grundläggande sats .

Gödel numrering tillämpades av Gödel som ett verktyg för att bevisa ofullständigheten i formell aritmetik .

En variant av Gödel-numreringen av första ordningens formell teori

Låt vara en första ordningens teori som innehåller variabler , objektkonstanter , funktionssymboler och predikatsymboler , där är numret och är ariteten för den funktionella eller predikatsymbolen. $\mathrm{K}$ $x_1,x_2,...$ $a_{1},a_{2},...$ $f_{k}^{n}$ $A_{k}^{n}$ $k$ $n$

Varje symbol för en godtycklig första ordningens teori är associerad med dess Gödel-nummer enligt följande: [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 för en godtycklig sekvens av uttryck definieras enligt följande: . $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})}}$

Det finns även andra Gödel-numrering av formell aritmetik.

Exempel

$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}}$

Generaliseringar

I allmänhet kallas uppräkningen av en mängd en överallt definierad surjektiv mappning . If , då kallas objektets nummer . Särskilda fall - språk och teorier. $F$ $\nu :{\mathbb {N}}\till F$ $\nu(n)=f$ $n$ $f$ $F$

Anteckningar

↑ Mendelssohn, 1971 , §4. Aritmetisering. Gödel numbers., sid. 151-152.

Litteratur

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

Se även

Godels ofullständighetsteorem