Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 64
Текст из файла (страница 64)
вместо то этой аргументной переменной данной именной формы. Определение функции з1,(т, й, 1) дается следую й патиной: следующе альтер- «Если т=2р, где р — простое число, большее или равное 7, и если существует число х такое, что 3»х(й и т(л, х) =т то з1,(т, й, !) = т(Г, х); и т, х,=т, если т=2" 3' 5' п, с О, а и не делится ни на о чисел 2, 3 и 5, то на одно из з1,(т, )е, !)=2 .3>.5. Ц (э.ц[,[,,„>, „.
к<и во всех остальных случаях з1,(т, й, Г) =т>. А теперь с помощью функции з(э(т, )с, [) легко определить функцию з1>(>п, й, !), значение которой в том случае, когда т является номером некоторой формулы й и — номе именной формы 6, ! — номером некоторого заменителя именной ф я ю для этой й формы, равняется номеру той формулы, которая получается из й в результате выполнения подстановки формулы (5 вместо именной формы 6. В самом деле, определение этой функции дается следующей альтернативой: «Если й является номером некоторой именной формы, а т— номером некоторого варианта этой именной формы, то з1>(>п, )е, !) =Е1,(), й, >и); ') Относительно п редстввленин последнего иэ этих условий см.
с. 289. $ н АРИФМЕТИЗАЦИЯ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ если т= 3 и, и отлично от О и делится на !О, то з(э(>п, /г„!) = 3 з1>(п, й, !); если т=2' 5' и, а+(>)2 и и не делится ни на одно из чисел 2, 3 и 5, то з1>(т, )е, !) = 2«5> ГТ (эк>.[е[и, *>, >, о. к к(к во всех остальных случаях з1,(т, й, !)= т>, Итак, арифметическое определение подстановки вместо формульиой переменной почти завершено; н все же, длн того чтобы выразить тот факт, что формула с номером и получается из формулы с номером т в результате подстановки заменителя с номером [ вместо именной формы с номером Й, требуется (чтобы представление было рекурсивным) некоторая оценка для й и 1 :срез т и и.
Действительно, нельзя быть уверенным, чс й меньше т, так как наша именная форма может содержать переменные, которые не входят в формулу с номером и, и по той же самой причине нельзя быть уверенным, что ) меньше п. Мы воспользуемся здесь тем ранее отмеченным обстоятельством, что при подстановке в формулу с номером т аргументные переменные именной формы могут быть выбраны из числа переменных с номерами 2(о„, 2)о „, ..., 2!о,[ „, так что номера всех этих аргументных переменных будут меньше 2)ов„.
Далее, мы воспользуемся тем, что фактически подстановка в формулу [Т с номером т вместо именной формы с номером )е будет производиться только тогда, когда формула б содержит в качестве составной части какой-либо вариант этой именной формы или же она сама является ее вариантом. Если в каком-либо входящем в формулу б варианте этой именной формы каждую (свободную или связанную) индивидную переменную и каждую цифру заменить переменной с номером 2)оэ, то рассматриваемая формульная переменная будет иметь только такие аргументы, номера которых >[с меныпе 2)оэ и, следовательно, больше номеРов аРгУментов именной формы. Поэтому, заменив в формуле 8 каждую индивидИУю пеРеменнУю и каждУю цифРУ пеРеменной с номеРом 2!Рэ, мы получим выражение, номер которого будет больше )е; таким образом, номер этого выражения (которое, впрочем, не обязано принадлежать рассматриваемому нами формализму) дает нам некоторую оценку для й. Зту оценку можно выразить рекурсивно, воспользовавшись функцией з(«(т, !), определяемой с помощью следующей альтернативы; «Если т=р или т=2р, где р — простое число, большее или равное 3, или если т=2 3', то з1, (т, !) = !' 295 294 МЕТОЛ АРИФЫЕТИЗАИИИ МГТАМАТГМАТИКИ !Го 4ч АРИФМЕТИЗАШ«Я ИСЧИСЛ! ИИЯ ПРЕДИКАТОВ 4 П если т,=2'.3» 5' а, с- О, а а не делится ни на одно из чисел 2, 3 и 5, то з(4(т 1) — 2 .3».5'.
П )о«!.42!и«г,и. «ч о« если ни один из перечисленных двух случаев места не имеет, то з14 (и, 1) = т». Еоли числа и и 1 являются номерами выражений нашего формализма, то э!4(т, 1) представляет собой номер того (не обя. зательно принадлежащего нашему формализму) выражения, которое получается из выражения с номером т в результате замены каждой индивидиой переменной и каждой цифры этого выражения выражением с номером 1.
Таким образом, найденная нами оценка для г! изо ражается неравенством Аналогичную оценку мы получим и для номера заменителя. Действительно, если (8 — формула с номером л, т. е. формула, получающаяся подстановкой из формулы 5, то в (») входит по крайней мере одно такое выражение, которое отличается от заменителя только тем, что вместо аргументных переменных именной формы в ием стоят некоторые квазитермы. Если в такого рода выражении все индивидные переменные и все цифры заменить переменной с номером 2)о», то получится выражение, номер которой превосходит число 1. Если же указанную замену произвести в ($ повсюду, то и подавно получится выражение с номером, ббльшим 1, так как вне подставляемых выражений в формуле Я фигурируют только такие переменные и цифры, которые встречаются и в 0.
Таким образом, 1(э14(п, 21»2 ). А теперь уже можно сформулировать следующее определение: «Формула с номером а получается из другой, отличной от нее формулы с номером и в результате некоторой подстановки вместо формульной переменной о аргументами тогда и только тогда, когда т и и являются номерами формул (и~а) и существуют числа й и 1 1Й вЂ” номер некоторой именной формы, а 1 — номер соответствующего заменителя) такие, что й ( з1, (т, 2)о»Ф), 1(з(4(а, 2)о» ) и з(2(т, й, 1)».
Таким образом, теперь мы уже выразили на языке рекурсивной арифметики все глаьиые понятия, необходимые для определения вывода. Осталось только дать следующие вспомогательные определения: «Формула с номером и получается из формулы с номером т по схеме (а) тогда и только тогда, когда и имеет вид 80 7' 11', где а — номер формулы, не содержащей переменной с номером 14, Ь вЂ” номер формулы, содержащей переменную с номером 14, но не содержащей переменной с номером 7, и 80.
7«, 11»о ти !» '4 тг «Формула с номером а получается из формулы с номером т по схеме (р) тогда и только тогда, когда и имеет вид 80 7' 11', где а — номер формулы, содержащей переменную с номером 14, но не содержащей переменной с номером 7, Ь вЂ” номер формулы, не содержащей переменной с номером 14, и Е),7!о» !'! !« '4. ~г 11»» «Формула с номером з получается из формул с номерами и и а по схеме заключения тогда и только тогда, когда т, а и з являются номерами формул и а=80 ° 7'" !1'». Номера следующих двух формул: ЧхА (х)-4- А (а) и А (а)-+ ЛхА (х), т. е.
числа 80 7(»о !!!о ! г) !Ею !"г и 80, 74!о ! г, 11(гоо т ' ' )« мы обозначим через и, и и,. Пользуясь тем, что последовательность формул с номерами гп, ..., т могкет быть изображена числом 2: ' « гг»«! О»2 мы приходим к следующему определению: «Мы говорим, что число и представляет список формул, являющийся выводом формулы с номером а, если выполняются следующие условия: !) для всякого числа х( Л(т) число т (т, х) является номером некоторой формулы; 2) т(т, ).
(т)) = а; 3) для каждого из чисел х(Х(т) выполняется следующая альтернатива: а) т(т, х) является номером какой-либо тождественно истинной формулы исчисления высказываний или равняется одному из чисел и, и я;, либо б) хне:0 и формула с номером о(т, х) получается из формулы с номером о(лг, х — 1) в результате подстановки вместо какой-либо формульной переменной без аргумента, или вместо 297 4 2! 296 !гл г.
т(т, 0), ..., т(л2 Х(п2)) ') См. с. 238 — 245. метод АРиеметизкнии мгткмктематики свободной индивидной переменной, или вместо формульной переменной с одним или несколькими аргументами, или в результ»ле переименования какой-либо связанной переменной, или же го одной из схем (сс) и ((1); либо в) х ) 1 и формула с номером т(т, х) получается из формул с номерами т (и, х -- 1) и т(пс, х †' 2) по схеме заключения; либо г) существует число у(х такое, что т(т, д) е м(т, х)». Тем самым построен некоторый рекурсивный преднкат — обозначим его 1)й(т, л) (1)о будет напоминать нам о дедукции),— который для чисел т и и выполняется тогда и только тогда, когда числа являются номерами таких формул нашего формализма, которые в указанном порядке образуют вывод последней из этих формул (по правилам нашего формализма), причем эта последняя формула им ет номер м.
Короче, можно сказать, что высказывание: «Представленный числом т список формул является выводом формулы г номером и» может быть изображено с помощью некоторого рекурсивного предиката 1)о(т, и). Метод получения этого результата отчетливо показывает, что возможность построения рекурсивного предиката, который с помощью нашей нумерации характеризовал бы данный список формул как вывод некоторой формулы, основывается вовсе не на осо ой структуре рассматриваемого конкретного формализма, т. е. исчисления преднкатов с добавлением цифр и функциональных знаков, а только на том, что характер нашего оперирования с объектами этого формализма является строго формальным и одновременно наглядно элементарным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
