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

Нумерація Геделя — це функція 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(\mathrm{\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⩾1;$

$g(A_k^n)=11+8\cdot 2^n{3}^k,k,n⩾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$ — мови і теорії.

Див. також

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

Література

• Шаблон:Книга
• Шаблон:Книга