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

Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С её помощью можно явно пронумеровать следующие объекты языка: переменные, предметные константы, функциональные символы, предикатные символы и формулы, построенные из них. Построение нумерации Гёделя для объектов теории называется арифметизацией теории — оно позволяет переводить высказывания, аксиомы, теоремы, теории в объекты арифметики. При этом требуется, чтобы нумерация g была эффективно вычислимой и для любого натурального числа можно было определить, является ли оно номером или нет, и если является, то построить соответствующий ему объект языка. Нумерация Гёделя очень похожа на посимвольное кодирование строк числами, но с той разницей, что для кодирования последовательностей номеров букв используется не конкатенация номеров одинаковой длины, а основная теорема арифметики.

Данная нумерация была применена Гёделем в качестве инструмента для доказательства неполноты формальной арифметики.

Вариант нумерации Гёделя формальной теории первого порядкаПравить

Пусть $\mathrm{K}$$\mathrm{K}$  — теория первого порядка, содержащая переменные $x_1,x_2,...$$x_1,x_2,...$ , предметные константы $a_1,a_2,...$$a_{1},a_{2},...$ , функциональные символы $f_k^n$$f_{k}^{n}$  и предикатные символы $A_k^n$$A_{k}^{n}$ , где $k$$k$  — номер, а $n$$n$  — арность функционального или предикатного символа.

Каждому символу $u$$u$  произвольной теории первого порядка $\mathrm{K}$$\mathrm{K}$  поставим в соответствие его гёделев номер $g(u)$$g(u)$  следующим образом:

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

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

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

$g(f_k^n)=9+8\cdot <!--\; \cdot \; -->2^n{3}^k,k,n⩾<!--\; ⩾\; -->1;$$g(f_{k}^{n})=9+8\cdot 2^{n}3^{k},\ k,n\geqslant 1;$ 

$g(A_k^n)=11+8\cdot <!--\; \cdot \; -->2^n{3}^k,k,n⩾<!--\; ⩾\; -->1.$$g(A_{k}^{n})=11+8\cdot 2^{n}3^{k},\ k,n\geqslant 1.$ 

Гёделев номер произвольной последовательности $e_0,...,e_r$$e_{0},...,e_{r}$  выражений определим следующим образом: $g(e_0,...,e_r)=2^{g(e_0)}\cdot <!--\; \cdot \; -->3^{g(e_1)}\cdot <!--\; \cdot \; -->...\cdot <!--\; \cdot \; -->p_r^{g(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 <!--\; \cdot \; -->3^{g(()}\cdot <!--\; \cdot \; -->5^{g(x_1)}\cdot <!--\; \cdot \; -->7^{g(,)}\cdot <!--\; \cdot \; -->{11}^{g(x_2)}\cdot <!--\; \cdot \; -->{13}^{g())}=2^{107}\cdot <!--\; \cdot \; -->3^3\cdot <!--\; \cdot \; -->5^{13}\cdot <!--\; \cdot \; -->7^7\cdot <!--\; \cdot \; -->{11}^{21}\cdot <!--\; \cdot \; -->{13}^5$$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$$F$  называют всюду определенное сюръективное отображение $\mathrm{\nu <!--\; \nu \; -->}:\mathbb{N}\to <!--\; \to \; -->F$$\nu :{\mathbb {N}}\to F$ . Если $\mathrm{\nu <!--\; \nu \; -->}(n)=f$$\nu (n)=f$ , то $n$$n$  называют номером объекта $f$$f$ . Частные случаи $F$$F$  - языки и теории.

ЛитератураПравить

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

См. такжеПравить

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