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

Нехай ${\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 F}$ називають усюди повне сюр'єктивне відображення${\displaystyle \nu$ :\mathbb {N} \to F} . Якщо ${\displaystyle \nu (n)=f}$, то ${\displaystyle n}$ називають номером об'єкта ${\displaystyle f}$. Окремі випадки ${\displaystyle F}$ — мови і теорії.

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

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