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

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

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

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

Литература

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

См. также

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