Нумерация Гёделя

Нумерация Гёделя — это функция 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)}$ следующим образом:^[1]

${\displaystyle g(()=3;\ g())=5;\ g(,)=7;\ g(\neg )=9;\ g(\to )=11;}$

${\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}$ - языки и теории.