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


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

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

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

Пусть K {displaystyle mathrm {K} } — теория первого порядка, содержащая переменные x 1 , x 2 , . . . {displaystyle x_{1},x_{2},...} , предметные константы a 1 , a 2 , . . . {displaystyle a_{1},a_{2},...} , функциональные символы f k n {displaystyle f_{k}^{n}} и предикатные символы A k n {displaystyle A_{k}^{n}} , где k {displaystyle k} — номер, а n {displaystyle n} — арность функционального или предикатного символа.

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

g ( ( ) = 3 ;   g ( ) ) = 5 ;   g ( , ) = 7 ;   g ( ¬ ) = 9 ;   g ( → ) = 11 ; {displaystyle g(()=3; g())=5; g(,)=7; g( eg )=9; g( o )=11;}

g ( x k ) = 5 + 8 k ,   k = 1 , 2 , . . . ; {displaystyle g(x_{k})=5+8k, k=1,2,...;}

g ( a k ) = 7 + 8 k ,   k = 1 , 2 , . . . ; {displaystyle g(a_{k})=7+8k, k=1,2,...;}

g ( f k n ) = 9 + 8 ⋅ 2 n 3 k ,   k , n ⩾ 1 ; {displaystyle g(f_{k}^{n})=9+8cdot 2^{n}3^{k}, k,ngeqslant 1;}

g ( A k n ) = 11 + 8 ⋅ 2 n 3 k ,   k , n ⩾ 1. {displaystyle g(A_{k}^{n})=11+8cdot 2^{n}3^{k}, k,ngeqslant 1.}

Гёделев номер произвольной последовательности e 0 , . . . , e r {displaystyle e_{0},...,e_{r}} выражений определим следующим образом: g ( e 0 , . . . , e r ) = 2 g ( e 0 ) ⋅ 3 g ( e 1 ) ⋅ . . . ⋅ p r g ( e r ) {displaystyle 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 ) ⋅ 3 g ( ( ) ⋅ 5 g ( x 1 ) ⋅ 7 g ( , ) ⋅ 11 g ( x 2 ) ⋅ 13 g ( ) ) = 2 107 ⋅ 3 3 ⋅ 5 13 ⋅ 7 7 ⋅ 11 21 ⋅ 13 5 {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}}

Обобщения

Вообще, нумерацией множества F {displaystyle F} называют всюду определенное сюръективное отображение ν : N → F {displaystyle u :mathbb {N} o F} . Если ν ( n ) = f {displaystyle u (n)=f} , то n {displaystyle n} называют номером объекта f {displaystyle f} . Частные случаи F {displaystyle F} - языки и теории.


Имя:*
E-Mail:
Комментарий: