Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 63
Текст из файла (страница 63)
Замечание. В основу дальнейших определений мы положим понятие формулы в его узко»«смысле, так что термин форм ул а будет пониматься нами в том смысле, в каком выше говорилось о собственных формулах. 288 МЕТОД АРИ«МЕТИЗАПИИ МЕТАМАТЕМАТИКИ [ГЛ. !е АРИФМЕТИЗАЦИЯ ИСЧИСЛЕНИЯ ПРСДИКАТОВ 288 Арифметизацню подстановки вместо формульных переменных без аргументов и вместо свободных индивидных переменных можно без особего труда произвести с помощью некоторой рекур- сивной функции з!Т(т, й, 1), значение которой в случае, когда т и 1 являются номерами некоторых выражений нашего формализма, или же а й — номером какой-либо свободной нндивидной пере нн й ме о е формульной переменной без аргументов, представляет собой номер того (возможно уже не принадлежащего нашему ме формализму) выражения, которое получается из выражения с ром и в результате замены переменной с номером й всюду, где она встречается, выражением с номером 1.
Имея в виду также и арифметнзацию переименования связанных переменных, мы я определим функцию з1,(т, й, 1) так, чтобы в том случае, когда а, огда и а[си 1 — но, вляется номером какого-либо выражения нашего фо формализма, а и — номерами связанных переменных, значение фун ,( , , ) представляло собой номер того выражения, которое получается из выражения с номером т в результате замены пере- менной с намером й всюду, где она встречается, пе е с номером 1. с, переменной Функцию з(,(т„)г, 1), подобно функции з!(т, й) 1), мы опре- делим следующим образом: «Если т=й и й=й р, причем г)=1, или г) 2, или г) 10, а р — простое число, большее или равное 7, то з(,(т, Ег, 1) =1; если т=2е 5 и, причем и не делится ни на одно из чисел 2, 3 и 5 и не является простым, то т Ег 1) 2, 5 1 — 1 Еаеь [«[к,кь«,[1 «<а если т г) 50 г)", г) = 1 или г) = 2, а р — простое число большее или равное 7, то е з[г(т, К 1) е й 50 (з(,(р, й, 1))а [' " '1; если т=3 п, а пчаО и делится на !О, то з[,(т, й, 1)=3.з1,(п, й, Е); в остальных случаях 5!г (гп, й, 1) =и».
Теперь с помощью функции з!«(т, й, 1) можно рекурсивно выразить отношение, связывающее две формулы, одна из которых получается из другой в результате падппанавка вместо свабадпой апдивадной переменной или соответственно влеслпо фармуль- 0 см. с. 280 и далее. най перез[виной без арвйвгениов. Именно, мы введем следующее определение; «Формула с номером п получается из другой, отличной от иее формулы с номером и в результате подстановки вместо свободной индивидной переменной тогда н только тогда, когда и и п являются номерами формул, тчьп и существуют число и, не превосходящее т и являющееся номером некоторой свободной индивидной переменной, и число 1, не превосходящее и и являющееся номером некоторого терма, такие, что имеет место равенство з(,(т, Ег, 1) и».
Совершенно аналогично выглядит определение предиката «формула с н мерам п получается из отличной от нее формулы с номером т в результате подстановки вместо формульной переменной без аргументовм Это определение отличается от предыдущего лишь тем, что в отношении з(,(т, К 1)= и число Ег в данном случае должно быть номером какой-нибудь формульной переменной без аргументов, а число 1 †номер какой-либо формулы. Далее, с помощью функции з(,(т, й, 1) можно рекурсивно выразить условие, необходимое и достаточное для того, чтобы индивидная переменная с номером й входила в выражение с номер'м и.
Действительно, это условие может быть изображено формулой з!г(и, й, 2) чьт. Тем ие менее функции з1, (т, Ег, 1) еще недостаточно для того, чтобы непосредственно выразить то обстоятельство, что одна из двух данных формул получается из другой в результате пер«имено«алия некоторой связанной переменной. Причина этого заключается в том, что переименование связанной переменной должно производится ие всюду, где рассматриваемая связанная переменная встречается, а только в области действия соответствующего квантора. Однако с помощью еще одного рекурсивного определения можно добиться, чтобы было учтено и это обстоятельство.
Этого можно достичь с помощью функции О(а, Ь) и ее обращений О,(п) и о,(п) '), если удастся сформулировать рекурсивное определение для некоторого предиката Ч',(в), который для числа з такого, что о, (з) и а, (в) суть номера некоторых формул, выполняется тогда и только тогда, когда вторая из этих формул получается из первой в результате переименования какой-либо связанной переменной (производимого в области действия соответствующего кваитора). Определение предиката Ч', (з) дается следующей альтернативой: ') Си, сноску 2 иа с. 272. !О Д Ге«евере П Берке«с метод лриеметизлции метлмлтемлтики !гл, >е «Либо о,(в) является числом вида 50 >).р", о (в) являет яется д, где а = 1 или >) = 2, р чь 1 — простые числа, ольшие или равные 7, и имеет место равенство либо з(>(а,(в), р, 1) =о,(в); а> (в) = т, о, (в) = 3 и >и и чь 0 и Ч> ( либо о>(в) =50 ° >7 р' и о«(в)=50.д.р> где д= ! или у=2 — п о и,(о(а, а)); — — р — р стае число, большее или равное 7, либо а,(в)=20 в.7' ° 1!> и о«(в) = 20 а ° 7' 11" где а †делите числа 8 и а=сл>Ч'>(о(Ь, й)) или Ь=ййЧ>,(о(а с))> Определенный таким образом предикат >Р ( ( т и и явл кат,(а(т, и)) для чисел ляющихся номерами некоторых двух фо м л, из аиз этих фо .
ния некоторой связанной переменной. Теперь необходимо е е п для того факта, что одна из в щ остроить рекурсивное выражен ие двух заданных формул получается друго в результате некоторой подстановки вместо фо м ной переменной с аргументами. к вместо Формульмы Сначала напомним, что для выпал пения такой подстановки должны взять какую-либо именную фо м ' той о ной переменной, вместо кото ой ю о р м у ) той формульо оторои будет производиться подстановка.
е сво дные иидивидные переменные, являю этой имени " фо р, являющиеся аргументами ру дру а; р ме того, иногда ой рмы, отличны д г от г; жно, что ы они отличались еще и от некоторых индиновка. видных переменных той формулы, в катар рую производится подста. Например, если мы хотим из формулы а=Ь->-(А(а) — А(Ь)) получить подстановкой формулу а=Ь- (а=а-+-Ь=а), то в качестве именной формы мы не можем взять А(а), так при подстановке вместо А (а) ф ь а), так как а формулы а=а получилась бы >) Сн. Приложение 1, е, 460.
АРиФметизлция исчисления пРедикАтов не требующаяся нам формула а формула а=Ь->.(а=а->-Ь=Ь). Таким образом, в этом случае в качестве аргументной переменной нужно взять какую-нибудь индивидную переменную, отличную от а. Такого рода требованием мы удовлетворим с запасом, если в качестве аргументных переменных именной формы будем брать такие, которые вообще не входят в формулу 5, в которую производится подстановка. Если т — номер этой формулы, то в любом случае в нее не входят переменные, имеющие номера 2 1>>, где Ь =-т. С другой стороны, число аргументов у формульвой переменной, вместо которой будет производиться подстановка, всегда меньше т, так как эта переменная входит в формулу с номером т, Таким образом, в качестве переменных именной формы можно брать переменные с номерами из списка 2!>, 21> и,, 2Р» и.
Теперь подстановка производится следующим образом. Сначала указывается формула, которая будет подставляться вместо именной формы; эта формула — мы будем кратко называть ее замен и тел ем — должна содержать аргументы именной формы. Затем отыскиваются все вхождения в формулу 5 таких выражений, которые либо совпадают с именной формой, либо отличаются от нее тем, что вместо некоторых из аргументов именной формы или вместо каждого из них в качестве аргументов стоят другие квазитермы; выражения такого рода мы будем кратко называть в а р и а н т а м и этой именной формы. Вместо каждого варианта И рассматриваемой именной формы подставляется выражение, которое получается из заменителя в результате тех же самых замен аргументных переменных именной формы, в результате которых из именной формы получается И.
А теперь это описание операции подстановки необходимо перевести, пользуясь нашей нумерацией, на язык арифметики. Сначала мы должны будем дать арифметические определения понятиям именная форма, заменитель и вариант, что без особого труда может быть сделано на основе следующих утверждений: «Число и является номером какой-либо именной формы тогда и только тогда, когда у=10 и, где и — число, большее ! и не делящееся ни на одно из чисел 2 3 и 5 и такое, что каждое из отличных от 0 чисел ч(п, х) (х<й) имеет вид 2 р, где р — простое число, не меньшее 7, и что для х <у< й либо ч(п, х)~Р(п, у), либо числа т(п, х) и т(п, у) оба равны Ок «Число 1 является номером некоторого заменителя именной формы с номером 1« тогда и только тогда, когда й является номеРом некоторой именной формы, 1 является номером некоторой 1о* МЕТОД АРИФМЕТИЗАЦИИ МЕТАМАТЕМАТИКИ [Гл >н формулы и когда для всех чисел х таких, что 3» (, )Ф, свободные переменные с номерами о(Й, х) входят в формулу с номером !> ').
Пусть ф>(т) обозначает рекурсивную функцию Ц )Ок«ие[л. к> к<и Тогда «число Г является номером некоторого варианта именной формы с номером )[ тогда и только тогда, когда й является номером некоторой именной формы, Ч>> (1) = >)>> (й), т (), О) =!, т (1, 2) = ! и когда для каждого числа х такого, что 3»х» Г, ™ (, либо равно О, либо является номером некоторого квазитерма>. Теперь мы определим функцию з(э(т, )е, 1), значение которой, когда т является номером некоторого выражения 1>[ мого нами формализма, й является номером некоторой именной формы, а 1 †номер некоторого варианта ~ этой именной формы, равняется номеру того выражения, котор из [>! в рое получается пе е в результате замены каждой входящей в 2! арг р менной данной именной формы всюду, где она входит в 21, аргументной тем квазитермом, который стоит в ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
