Gödel számozás

A Gödel-számozás egy g függvény, amely valamilyen formális nyelv minden objektumához hozzárendeli a számot. Használható a következő nyelvi objektumok explicit felsorolására: változók, objektumkonstansok, függvényszimbólumok, predikátumszimbólumok és ezekből épített képletek. A Gödel-számozás felépítését egy elmélet tárgyaira egy elmélet aritmetizálásának nevezik - ez lehetővé teszi kijelentések, axiómák, tételek, elméletek aritmetikai objektumokká történő fordítását . Szükséges, hogy a g felsorolás hatékonyan kiszámítható legyen, és bármely természetes számról meg lehet határozni, hogy szám-e vagy sem, és ha igen, akkor megszerkeszthető a nyelv megfelelő objektuma. A Gödel-számozás nagyon hasonlít a karakterláncok számokkal történő karakterenkénti kódolásához , azzal a különbséggel, hogy az azonos hosszúságú számok összefűzését nem betűszám-sorozatok kódolására használják, hanem az aritmetika alaptételét .

A gödel-számozást Gödel a formális aritmetika hiányosságának bizonyítására használta .

Az elsőrendű formális elmélet Gödel-számozásának változata

Legyen egy elsőrendű elmélet , amely változókat , objektumkonstansokat , függvényszimbólumokat és predikátumszimbólumokat tartalmaz , ahol a funkcionális vagy predikátumszimbólum száma és aritása . $\mathrm{K}$ $x_1,x_2,...$ $a_{1},a_{2},...$ $f_{k}^{n}$ $A_{k}^{n}$ $k$ $n$

Egy tetszőleges elsőrendű elmélet minden szimbóluma hozzá van rendelve a Gödel-számához a következőképpen: [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.$

Egy tetszőleges kifejezéssorozat Gödel-számát a következőképpen definiáljuk: . $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})}}$

Vannak más formális aritmetikai Gödel-számozások is.

Példa

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

Általánosítások

Általában egy halmaz felsorolását mindenhol meghatározott szürjektív leképezésnek nevezik . Ha , akkor az objektum számának nevezzük . Egyedi esetek - nyelvek és elméletek. $F$ $\nu :{\mathbb {N}}\ to F$ $\nu(n)=f$ $n$ $f$ $F$

Jegyzetek

↑ Mendelssohn, 1971 , 4. § Aritmetizálás. Gödel-számok, p. 151-152.

Irodalom

Klini S.K. Bevezetés a metamatematikába . - M. : IL, 1957. - 526 p.
Mendelsohn E. Bevezetés a matematikai logikába . - M . : "Nauka", 1971. - 320 p.

Lásd még

Godel befejezetlenségi tétele