Нумерация Гёделя
Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С её помощью можно явно пронумеровать следующие объекты языка: переменные, предметные константы, функциональные символы, предикатные символы и формулы, построенные из них. Построение нумерации Гёделя для объектов теории называется арифметизацией теории — оно позволяет переводить высказывания, аксиомы, теоремы, теории в объекты арифметики. При этом требуется, чтобы нумерация g была эффективно вычислимой и для любого натурального числа можно было определить, является ли оно номером или нет, и если является, то построить соответствующий ему объект языка. Нумерация Гёделя очень похожа на посимвольное кодирование строк числами, но с той разницей, что для кодирования последовательностей номеров букв используется не конкатенация номеров одинаковой длины, а основная теорема арифметики.
Данная нумерация была применена Гёделем в качестве инструмента для доказательства неполноты формальной арифметики.
Вариант нумерации Гёделя формальной теории первого порядка
Пусть [math]\displaystyle{ \mathrm{K} }[/math] — теория первого порядка, содержащая переменные [math]\displaystyle{ x_1,x_2,... }[/math], предметные константы [math]\displaystyle{ a_1, a_2, ... }[/math], функциональные символы [math]\displaystyle{ f_k^n }[/math] и предикатные символы [math]\displaystyle{ A_k^n }[/math], где [math]\displaystyle{ k }[/math] — номер, а [math]\displaystyle{ n }[/math] — арность функционального или предикатного символа.
Каждому символу [math]\displaystyle{ u }[/math] произвольной теории первого порядка [math]\displaystyle{ \mathrm{K} }[/math] поставим в соответствие его гёделев номер [math]\displaystyle{ g(u) }[/math] следующим образом:[1]
[math]\displaystyle{ g(()=3; \ g())=5; \ g(,)=7; \ g(\neg )=9; \ g(\to )=11; }[/math]
[math]\displaystyle{ g(x_k)=5+8k, \ k=1,2,...; }[/math]
[math]\displaystyle{ g(a_k)=7+8k, \ k=1,2,...; }[/math]
[math]\displaystyle{ g(f_k^n)=9+8\cdot 2^n3^k, \ k,n\geqslant 1; }[/math]
[math]\displaystyle{ g(A_k^n)=11+8\cdot 2^n3^k, \ k,n\geqslant 1. }[/math]
Гёделев номер произвольной последовательности [math]\displaystyle{ e_0,...,e_r }[/math] выражений определим следующим образом: [math]\displaystyle{ g(e_0,...,e_r) =2^{g(e_0)}\cdot 3^{g(e_1)}\cdot...\cdot p_r^{g(e_r)} }[/math].
Существуют также другие нумерации Гёделя формальной арифметики.
Пример
[math]\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} }[/math]
Обобщения
Вообще, нумерацией множества [math]\displaystyle{ F }[/math] называют всюду определенное сюръективное отображение [math]\displaystyle{ \nu: \mathbb{N}\to F }[/math]. Если [math]\displaystyle{ \nu(n)=f }[/math], то [math]\displaystyle{ n }[/math] называют номером объекта [math]\displaystyle{ f }[/math]. Частные случаи [math]\displaystyle{ F }[/math] - языки и теории.
Примечания
- ↑ Мендельсон, 1971, §4.Арифметизация.Гёделевы номера., с. 151—152.
Литература
- Клини С.К. Введение в метаматематику. — М.: ИЛ, 1957. — 526 с.
- Мендельсон Э. Введение в математическую логику. — М.: «Наука», 1971. — 320 с.