yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->6.5. Арифметизация. Геделевы номера.

Математическая логика

6.5. Арифметизация. Геделевы номера.

Каждому символу и произвольной теории первого Порядка К следующим образом поставим и соответствие положительное число g(u), называемое геделевым номером символа и:

g(( )=3;  g( ))=5:   g(,)=7,   g(¬)=9,  g()=11.

g(xk)=5 + 8k для k=l,2....;

g(ak) = 7 + 8k для k=l,2,...;

g(fkn)=9+8(2n3k)   для k, n1;

g(Akn)=11+8(2n3k)  для k, nl;

при этом положим g(xi)=g((xi).

Таким образом, различным символам поставлены в соответствие различные геделевы номера, являющиеся положительными числами.

Примеры. g(x2) = 21. g(a4)=39. g(f12)=105,  g(A21)=155.

Пусть дано выражение u0,u1,...ur Геделев номер g(u0,u1,...ur) этого выражения определим как 2g(u0)3g('u)...prg(Ur), где рi есть 1-е простое число и р0=2. Заметим, что, в силу единственности разложения натуральных чисел в произведения степеней простых чисел, различный выражения получают при этом разные геделевы номера. Кроме того, геделевы номера выражений четны и потому отличны от го деловых номеров символов. Всякий символ можно рассматривать как выражение, и тогда он снабжается геделевым номером, отличным от того, который становится ему в соответствие как символу. Это не должно, однако, приводить к недоразумению.

Наконец, геделев номер произвольной последовательности е0,...,ег выражений определим следующим образом: g(e0,…еr)=2g(e0)...3g(e1)...prg(er). Как и прежде, различные последовательности выражений имеют различные геделевы номера, а так как эти последние четны и, кроме того, имеют четный показатель степени при 2, то они отличны и от геделевых номеров символов, и от геделевых номеров выражений.

Таким образом, функция g взаимно однозначно отображает множество всех символов, выражений и конечных последовательностей выражений в множество целых положительных чисел. Множество значений функции g не совпадает, однако, с множеством всех целых положительных чисел; так, число 12 не является геделевым номером.

Такая нумерация символов, выражений и последовательностей выражений впервые была предложена Геделем [1931] с целью арифметизации математики, т.е. с целью замены утверждений о формальной системе эквивалентными высказываниями о натуральных числах с последующим выражением этих высказываний в формальной системе. Идея арифметизации стала ключом к решению многих важных проблем математической логики.

Утверждение 6.6. Пусть для данной теории первого порядка К следующие отношения примитивно рекурсивны (рекурсивны): (а) IС(х), что означает "х есть геделев номер предметной константы теории К", (b) FL(x), что означает "х есть геделев номер функциональной буквы теории К", (с) PL(х), что означает "х есть геделев номер предикатной буквы теории К". Тогда, на основе этих отношении можно пре делить новые отношения и функции, так что эти отношения будут определять высказывания относительно выражений и операции формальной теории S, причем эти отношении и функции также будут примитивно рекурсивны (рекурсивны).

Здесь мы рассмотрим (без доказательства) только одно отношение, которое является примитивно рекурсивным:

W1(u,y): "u есть геделев номер формулы A(х1), содержащей свободную переменную х1, и у есть геделев номер вывода в S формулы A(u)``.

Теорема 6.7. Всякая функция f(x1,...,xn,z), представимая в S, рекурсивна.

Теорема  6.7  вместе с теоремой  6.5  показывает,  что класс рекурсивных функций совпадет с классом функций, представимых в S.

 Следствие. Всякий заданный на множестве натуральных чисел предикат R(х1,…,хn) рекурсия тогда и только тогда, когда он выразим  в теории S.

 Доказательство. Согласно  определению, предикат R(x1,…,xn) рекурсивен тогда и только тогда, когда рекурсивна функция CR , с другой стороны, предикат R выразим в S тогда и только тогда, когда функция CR представима в S(теорема 6.1.)

 

41