Нумерація Ґьоделя

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

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

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

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

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

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

${\displaystyle g(x_{k})=5+8k,\ k=1,2,...;}$

${\displaystyle g(a_{k})=7+8k,\ k=1,2,...;}$

${\displaystyle g(f_{k}^{n})=9+8\cdot 2^{n}3^{k},\ k,n\geqslant 1;}$

${\displaystyle g(A_{k}^{n})=11+8\cdot 2^{n}3^{k},\ k,n\geqslant 1.}$

Номер Геделя довільної послідовності ${\displaystyle e_{0},...,e_{r}}$ виразів визначимо наступним чином: ${\displaystyle g(e_{0},...,e_{r})=2^{g(e_{0})}\cdot 3^{g(e_{1})}\cdot ...\cdot p_{r}^{g(e_{r})}}$.

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

Приклад

${\displaystyle 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}}$

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

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

Див. також

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

Література

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