Нумерація Геделя

Нумерація Геделя — це функція g , що зіставляє з кожним об'єктом деякої формальної мови її номер. З її допомогою можна явно пронумерувати наступні об'єкти мови: змінні, предметні константи, функціональні символи, предикатні символи і формули, побудовані з них.

Побудова нумерації Геделя для об'єктів теорії називається арифметизацією теорії — вона дозволяє переводити висловлювання, аксіоми, теореми чи теорії в об'єкти арифметики . При цьому потрібно, щоб нумерація g була ефективно обчислюваною і для будь-якого натурального числа можна було визначити, чи є воно номером чи ні, і якщо є, то побудувати відповідний йому об'єкт мови. Нумерація Геделя дуже схожа на посимвольне кодування рядків числами, але з тією різницею, що для кодування послідовностей номерів букв використовується не конкатенація номерів однакової довжини, а основна теорема арифметики.

Нумерація Геделя була ним застосована як інструмент для доказу неповноти формальної арифметики.

Варіант нумерації Геделя формальної теорії першого порядку

Нехай $\mathrm {K}$ — теорія першого порядку, що містить змінні $x_{1},x_{2},...$, предметні константи $a_{1},a_{2},...$, функціональні символи $f_{k}^{n}$ і предикатні символи $A_{k}^{n}$ , де $k$ — номер, а $n$ — арність функціонального або предикатного символу.

Кожному символу $u$ довільній теорії першого порядку $\mathrm {K}$ поставимо у відповідність його Ґьоделя номер $g(u)$ наступним чином: $g(()=3;\ g())=3;\ g(,)=3;\ g(\neg )=3;\ g(\to )=3;$

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

Номер Геделя довільної послідовності $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})}$.

Існують також інші нумерації Геделя формальної арифметики.

Приклад

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

Узагальнення

Взагалі, нумерацією множини $F$ називають усюди повне сюр'єктивне відображення$\nu :\mathbb {N} \to F$. Якщо $\nu (n)=f$, то $n$ називають номером об'єкта $f$. Окремі випадки $F$ — мови і теорії.

Див. також

• Теорема Геделя про неповноту

Література

• Кліні С.К. Введення в метаматематику. — М. : ІЛ, 1957. — 526 с.
• Мендельсон Е. Введення в математичну логіку. — М. : «Наука», 1971. — 320 с.