Gödelovo číslování

Gödelovo číslování je funkce g , která přiřazuje každému objektu nějakého formálního jazyka jeho číslo. Lze jej použít k explicitnímu výčtu následujících jazykových objektů: proměnných, objektových konstant, funkčních symbolů, predikátových symbolů a vzorců z nich vytvořených. Konstrukce Gödelova číslování pro objekty teorie se nazývá aritmetizace teorie - umožňuje překládat výroky, axiomy, věty, teorie do objektů aritmetiky . Požaduje se, aby výčet g byl efektivně vypočitatelný a pro jakékoli přirozené číslo bylo možné určit, zda se jedná o číslo či nikoli, a pokud ano, pak sestrojit odpovídající objekt jazyka. Gödelovo číslování je velmi podobné kódování řetězců s čísly znak po znaku, s tím rozdílem, že ke kódování posloupností písmenových čísel se nepoužívá zřetězení čísel stejné délky, ale základní věta aritmetiky .

Gödelovo číslování použil Gödel jako nástroj pro prokázání neúplnosti formální aritmetiky .

Varianta Gödelova číslování formální teorie prvního řádu

Nechť je teorie prvního řádu obsahující proměnné , objektové konstanty , funkční symboly a predikátové symboly , kde je číslo a je arita funkčního nebo predikátového symbolu. $\mathrm{K}$ $x_1, x_2,...$ $a_{1},a_{2},...$ $f_{k}^{n}$ $A_{k}^{n}$ $k$ $n$

Každý symbol libovolné teorie prvního řádu je spojen se svým Gödelovým číslem následovně: [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ödelovo číslo libovolné posloupnosti výrazů je definováno takto: . $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})}}$

Existují také jiná Gödelova číslování formální aritmetiky.

Příklad

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

Zobecnění

Obecně se výčet množiny nazývá všude definované surjektivní mapování . If , then se nazývá číslo objektu . Konkrétní případy - jazyky a teorie. $F$ $\nu :{\mathbb {N}}\to F$ $\nu(n)=f$ $n$ $F$ $F$

Poznámky

↑ Mendelssohn, 1971 , § 4. Aritmetizace. Gödelova čísla., str. 151-152.

Literatura

Klini S.K. Úvod do metamatematiky . - M. : IL, 1957. - 526 s.
Mendelsohn E. Úvod do matematické logiky . - M .: "Nauka", 1971. - 320 s.

Viz také

Godelova věta o neúplnosti