Русская Википедия:Нумерация Гёделя

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

<math>g(()=3; \ g())=5; \ g(,)=7; \ g(\neg )=9; \ g(\to )=11;</math>

<math>g(x_k)=5+8k, \ k=1,2,...;</math>

<math>g(a_k)=7+8k, \ k=1,2,...;</math>

<math>g(f_k^n)=9+8\cdot 2^n3^k, \ k,n\geqslant 1;</math>

<math>g(A_k^n)=11+8\cdot 2^n3^k, \ k,n\geqslant 1.</math>

Гёделев номер произвольной последовательности <math>e_0,...,e_r</math> выражений определим следующим образом: <math>g(e_0,...,e_r) =2^{g(e_0)}\cdot 3^{g(e_1)}\cdot...\cdot p_r^{g(e_r)}</math>.

Существуют также другие нумерации Гёделя формальной арифметики.

Пример

<math>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>F</math> называют всюду определенное сюръективное отображение <math>\nu: \mathbb{N}\to F</math>. Если <math>\nu(n)=f</math>, то <math>n</math> называют номером объекта <math>f</math>. Частные случаи <math>F</math> - языки и теории.

Литература

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

См. также

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