Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 83
Текст из файла (страница 83)
Пз этой формулы получается также импликация а «( Ь вЂ” г(> (а, и) «( г)> (Ь, п). В-третьих, для кап дай цифры п индукцией по а может быть выведена формула г)> (а', и) «( ф (а, и'). Действительно, неравенство г(> (О', и) «( >Ь (О, и') получается непосредственно, а с помощью формул а «( Ь вЂ” >-г(> (а, п) «( г(> (Ь, н) $3) некотОРые ОБОБщения схем РекуРсии и индукции 4)) РЕКУРСИВНЫЕ ОПРРДЕЛЕПИЯ [гл. уп и а'«( <р (а, и) могут быть получены формулы <р (а', ц) «( ф (а, ц') -+ <р (<р (а', и), ц) «« <р (ф (а, и'), и) <р (а", ц) ( <р (ф (а', ц), ц), которые в сочетании с третьей рекурсивной формулой для ф (а, и) дают нам формулу <р (а', п) « <р (а, и') -+ <р (а", и) «( <р (а', п'), так что при помощи схемы индукции мы получим формулу ф (а', и) «ф (а, и').
Объединив зту формулу с неравенством <р (а, и) ( <р (а', п), мы получим также неравенство <Ь (а, п) ( <р (а, и ), а отсюда для произвольных, отличных друг от друга цифр н й, таких что й болыпе г, мы получим формулу <р (а, т) (<р (а, й). В дальнейшем будет целесообразно использовать как явное определение следующий способ записи: <р„(а) =- <р (а, и), который соответствует взгляду на <р (а, и) как па изображение некоторой последовательности функций одного аргумента.
Используя этот способ записи, мы представим полученные нами оценки в следующем виде. Для каждой цифры ц выводимы формулы а (<('и (а) а ( Ь <р„(а) ( <р„(Ь), <(з„(а') («<)<з' (а); а кроме того, для любой цифры ш, большей ц, выводима формула <Ьз (а) ( <рм (а). С помощью этих неравенств мы покажем, что для всякой функции )(и), допускающей определение при помощи примитивных рекурсий (и подстановок), может быть указана цифра г, для которой выводимо неравенство ) (а) (<р<(а), С этой целью вспомним о том, что кан<дая функция, которая может быть определена с помощью произвольных примитивных рекурсий, может быть определена и с помощью таких рекурсий, которые содержат не более одного параметра и, следовательно, имеют вид <)(О) = а, () (и') = Ь(и, Ь(и)) или вид 1)(а, О) = о (а), ))(а, и') = Ь (а, и, ))(и)), где вместо Ь всякий раа должен быть подставлен подлежащий введению функциональный зпак 1).
При етом мы моя<ем такн<е освободиться от произвольности терма а, соответственно о (а). Если мы, например, рассматриваем рекурсию <р (а, О) == о (а), ф (а, ие) = Ь (а, и, <р (а, и)), то определенную с ее помощью функцию ф (а, и) мы можем получить из функции т (а, и), определенной при помощи рекурсивных равенств )~(а, О) =-О, т (а, и') = идп и а (а) + эдп и.Ь (а, б (и), т (а, и)); именно, ф (а, и) получится из у (а, и) с помощью следующего явного определения: <р (а, и) = у (а, и'). Подобный же прием может быть применен и к рекурсии без параметров. В этой редукции используются функции здп и, эдп и, б (и), а + Ь и а Ь.
<) В атом направлении можно было бы пойти еще дальше. Именно, с помощью уже упоминавшегося метода Р. Потер сведения рекурсий пробега к примитивным рекурсиям получается, что каждая функция, определимая при помощи примитивных рекурсий, может быть определена прп помощи одних только рекурсий без параметров, если в качестве исходных функций дополнительно к штрих-функции ваять а+ Ь, а.Ь, а", а — ' Ь, Р„, т (и, Ь). Ыы могли бы использовать этот факт в нашем доказательстве.
Тем не менее мы обойдемся без этой редукции. 11 НЕКОТОРЫЕ ОБОБЩЕНИЯ СХЕМ РЕКУРСИИ И ИНДУКЦИИ 413 сгл, чп РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ Из них функции зппп, б(п) и и.Ь определяются такими рекурсинми, у которых в правой части первого равенства стоит терм О. В рекурсии для а + Ь в правой части первого рекурсивного равенства стоит терм а, а функция зип и с помощью равенства зппп =-1 — ' и выражается через функцию а — ' Ь, у которой в первом рекурсивном равенстве справа также стоит терм а. В соответствии с этим, из примитивных рекурсий без параметров иы можем рассматривать лишь такие, у которых первое равенство имеет вид Ь(0) = О, а среди рекурсий с одним параметром — лишь такие, у которых первое равенство имеет вид ()(а, 0) = 0 или ч(а, 0)=а, так что в любом из этих случаев будет выводимо неравенство 5(а, О) ( а. Примитивную рекурсию с не болев чем одним параметром, первое равенство которой имеет один иэ видов Ь(0) = О, Ь(а, 0) =- О, (1(а, 0) = а, мы для краткости будем нааывать н о р м и р о в а н н о й р ек у р с и е й.
Пусть теперь ) (а) — функция, определенная при помощи примитивных рекурсий. Тогда эта функция может быть такхсе определена и при помощи нормированных рекурсий. (При этом явными определениями мы можем и не пользоваться, так как всякий введенный посредствои такого определения символ можно заменить определяющим его выражением.) Представим себе, что такое определение функции ( (а) с помощью нормированных рекурсий произведено. В каждой из этих рекурсий для написания второго рекурсивного равенства мы пользуемся некоторым термам Ь (г, г) или соответственно Ь (г, г, 1), который в свою очередь строится нз терман, введенных до него. Поэтому в рассматриваемом нами определении функции ( (а), вообще говоря, будут встречаться термы с тремя переменными; термы с более чем тремя переменпыии встречаться не будут, поскольку мы следим за тем, чтобы все встречающиеся составные функциональные выражения строи- лись после определения их составных частей.
В качестве исходных термов у нас имеются символ 0 и свободные индивидные пере- менные, а в качестве исходной функции — штрих-функция. Теперь для того, чтобы с помощью имеющегося у нас опре- деления функции ( (а) получить требуемое неравенство (()(ф,(), мы выведем друг за другом оценки одного и того же типа для всех входящих в определение ) (а) териов. Эти оценки для термов с одной переменной будут иметь вид 1 (а) ( ф1 (и), а для терман с двумя и тремя переменныпп — впд 1(а, Ь) (ф (р (и, Ь)) или вид 1 (а, Ь, с) ( ф (р (а, Ь, с)) соответственно, причем $ всякий раз будет озяачать какую-либо цифру; здесь р (и, Ь) и р (и, Ь, с) суть функции, которые пред- ставляют максимум а и Ь (соответственно максимум а, Ь и с) и ко- торые могут быть явно определены посредством равенств р(а, Ь) =а+(Ь вЂ” 'а), р (а, Ь, с) = р(а, р(Ь, с)), из которых можно вывести формулы а ( р (а, Ь), Ь ( р (а, Ь), а = р (а, Ь) ~/ Ь= р (а, Ь), а ( р (а, Ь, с), Ь ( р(и, Ь, с), с ( р(а, Ь, с), а = р (а, Ь, с) с/ Ь = р (а, Ь, с) '„I с = р (а, Ь, с).
То, что для каждого участвующего в определении ( (а) терма, а тем самым в итоге и для самого ) (а), действительно получается оценка искомого вида, вытекает из следующих фактов: 1. Для любой цифры 1 выводимы формулы 0(ф,(а), а(ф,(и), ф (а)' ( ср1,(а). 2. Если 1) (а) вводится рекурсией Ц(0) =О, 1) (п') = Ь (и, Ь (и)) и если для Ь (а, Ь) выведена оценка Ь (а, Ь) ( ф (р (а, Ъ)), $ м некОтОРые ОБОБщения схем РекуРсии и индукции 415 1гл, Уп РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 414 то отсюда могут быть выведены формулы Ь (а, Ь (а)) (ф ((с (а, 1) (а))), 11 (а) (~р1+ (а) -э Ь (а, 1) (а)) (ф1 (ф1+4 (а)), а с помощью равенства ф,(ф„,()) =ф„,(') и формула 5 (а) ~>1~, (а) -+ 1> (а') ( ф+, (а'), которая в сочетании с выводимой формулой 1) (0) ( фе„, (0) при помощи схемы индукции дает формулу 1) (а) ( ф1+ (а).
Заметим, что сделанные вдесь предположения выполняются и тогда, когда в 3 (а, д) встречается только одна из переменных а и Ь и когда для этой переменной оказывается выводимым неравенство Ь (а, Ь) ( ф1 (а) или Ь (а, Ъ) (чр (Ъ) соответственно. Действительно, каждое из этих неравенств с помощью формулы а ( Ь-+ ф (а) ( ~р (Ь) дает неравенство Ь (а, Ь) ( ~р (р (а, Ь)). 3. Если 1) (а, Ь) введено рекурсией 1) (а, 0) =0(или1)(а, 0)=а), 1) (а, и') = Ь (а, и, Ь (а, и)) и если для Ь(а, Ь,с) выводимо ограничение Ь (а, д, с) ~р (р (а, Ь, с)), то отсюда мы получим ограничение Ь (а, Ь) ( 1р (р (а, Ь)).
Действительно, индукцией по Ь мы сначала следующим образом выведем неравенство 1) (а, Ь) ( Ф1„, (а + Ь). Прежде всего мы имеем 1) (а, 0) ( ф1,, (а + 0); далее, мы получим 1)(а, Ь)(ф+ (а+Ь)-з-ь(а, Ь, 1)(а, Ь))< АР((ф 4(а+Ь)), а затем отсюда получим 1) (а, Ь) ( ф (а + Ь) — ~ 1) (а, Ь') ( ф (а + Ь'); теперь с помощью схемы индукции можно будет получить 1) (а, Ь) ( ~Ь1+ (а + д). С другой стороны, используя формулы а + Ь ( 2 р (а, Ь), 2.
р (а, Ь) ( 4~, (р (а, Ь)), Ф~+, ( рс (а)) ( ф1,, (Ф14 з (б (а))), а ~ 0-з-~Р+, ®1+ (б (а))) =- ч$~ (а), мы получим неравенство ~р (а+ Ь)(Ф (р(а, Ь)), так что в целом можно будет получить Ь(а, Ь) (ф (р (а, Ь)). Случай, когда в Ь(т,в, 1) входят не все три переменные а, Ь, с, рассматривается совершенно так же, как соответствующий случаи при рекурсии без параметроз. 4. Пусть 1 — терм, в котором не встречаются никакие переменные, кроме а, Ь и с, а ч (и) — функциональный знак с одним аргументом. Пусть для 1) (и) выводимо неравенство 11 (а) (~Р (а), а для 1 — неравенство 1( Ф1 (с) сгл, ун Рекурсивные ОпРеделен>ла ] 3] некотОРые Ововщения схем РекуРсии и индукции 417 где с — один из термов а, Ь, с, р (а, 6), р (а, с), р (Ь, с), р (а, Ь, с).
Тогда будет выводимо также неравенство ()(1) < >)>рс] 1>+ (с). Действительно, можно получить неравенства *) ]) (1) < ф] (ф] (с)) ~< фры, ]> (т)>р11, 1> (С) ) < фрс] ]>+> (с') <>(>рс] ]>+2 (с). 5. Пусть н н ь — термы, не содернсащие никаких переменных кроме а, 6 и с, а 1) (и>, и) — функциональный знак с двумя аргументамп. Пусть выводимы неравенства 1)(а, 6) <т]>1(р(а, 6)), п< )>](а), ь <ф](Ь), где а и Ь вЂ” термы из списка а, Ь, с, р (а, Ь), р (а, с), р (Ь, с), >с (а, Ь, с). Тогда можно вывести неравенство ])(н, ь) < фрс> ] ]~-2 (с)~ где с снова — один из тормоз а, Ь, с, р (а, Ь), р (а, с), р (Ь, с), р (а, 6, с).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
