Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 85
Текст из файла (страница 85)
Пусть функция ф (а, п) определяется следующей примитивной рекурсией: «)« (а, 0) = шах (1« (а, 0), 1 (а, 0), ..., 1 (а, 0)), «)« (а, я') = шах (ф (а, я), 1« (а, П), ..., 1 (а, и')). Отсюда обычной индукцией по и получим ((3)) с(п-»1,(а, с)(«р(а, и)«х... Й1 (а, с)(«р(а, я). Подставим теперь в ((1)) вместо Ь терм ф (а, Ь), а вместо с— сначала 1« (а, с), а затем 1э(а, с),..., 1 (а, с). Так мы получим т формул ф(«р(а, Ь), а) 0-«(11(а, с)(«р(а, Ь) -» Я(11(а, с), а)) (1 = 1, ..., т). Эти формулы вместе с ((3)) (где вместо п подставлено Ь) дают ф (ф (а, Ъ), а) = 0 8с с ( Ь вЂ” » Я (1, (а, с), а) 8с...
Ы (1 . (а, с), а). Применив вторую посылку рассматриваемой нами схемы Я(1«(а, Ь), а) 8«Я (1«. (а, Ь), а) «х... 8«Я (1,(а, Ь), а) -» Я (Ь, а') (в которую вместо Ь подставим с), мы получим ф (ф (а, Ь), а) = 0 Ь с(Ь-» Я (с, а'), а значит, и ф (ф (а, Ь), а) = 0-» (с(Ь-» Я (с, а')), откуда по схеме ((2)) следует ф (ф (а, Ь), а) = 0 -«- «р (Ь, а') = О.
С другой стороны, кэ первой посылки Я (Ь, 0) рассматриваемой нами схемы мы получим формулу с(ь-» Я (с, 0), иэ которой при помощи схемы ((2)) мы выведем формулу р (ь, о) = о. Но из двух формул ф (Ь, 0) = 0 н ф («р (а, Ь), а) = 0 -+ ф (Ь, а') = 0 в соответствии с обобщенной схемой индукции специального вида (1пд 1) получается формула ф (Ь, а) = О, из которой при помощи ((1а)) получится искомая формула Я (Ь, а). Дальнейшим обобщением схемы индукции является следующая схема и е р е к р е с т н о й и н д у к ц и и: Я (Ь, 0) Я (1м а) -» Я(0, а«) Я(1з, а)-» (Я(Ь, а') — » Я(Ь', а')) Я(Ь, а) на которую мы снова накладываем ограничение, заключающееся в требовании, чтобы формула Я (с, д) не содержала переменных а и Ь. Мы не потеряем общности, предположив, что терм 1« содержит только такие пеРеменные, котоРые вхоДЯт в Я (О, а'), а 1з— только такие, которые входят в Я (Ь, а). Действительно, в противном случае другие переменные, встречающиеся в 1«и 1э, не изменяя вида этой схемы, можно было бы удалить соответствующей подстановкой цифр.
(Гл, уп Рвкувсивныи опгйдклнния ненотогые ововщиния схим гккггсии и индукции 425 В дальнейшем мы будем записывать эти термы более развернуто в виде 1, (а) и 1, (а, Ь). (Согласно нашему предположению, 1, (а) не содержит переменной Ь.) Эту схему перекрестной индукции также можно будет свести к специальному виду обобщенной схемы индукции (1пс( 1), а твм самым и к обычной схеме индукции. С этой целью мы снова воспользуемся первводимостью формулы Я (с, д) в равенство вида а (с, с() = 0 и,как и в првдыду(нем случае, положим ср (Ь, с) = 7, .а (х; с).
с»аь На основе этого определения мы, как и раньше, получим схе- мы ((1)), ((1а)) и ((2)), а иэ посылки Я(ь, 0) рассматриваемой нами схемы мы снова получим равенство ср (Ь, 0) = О. Отметим такнсе формулу ((4)) с<с(-«(ср (с(, а) = 0-«ср (с, а) = 0), которая на основе определения функции ф переводима в формулу с(Ы вЂ” «( ~ а(х, а)=0-« ~ а(х, а)=0), с» а ая» которая может быть получена индукцией по с(. Определим теперь функцию ср (а, и) посредством примитивной рекурсии ф(а, 0) = 1, (а), ф (а, и ) = шах (»Р (а, а), 1а (а, п)). Как и в предыдущем случае, достаточно будет, кроме уже полученной формулы ф (Ь, 0), вывести формулу ср (ф (а, Ь), а) = 0 -« ср (Ь, а ) = О. Обозначим эту формулу посредством к» (а, Ь). Вывод 3 (а, Ь) может быть осуществлен обычной индукцией по Ь.
Формула к» (а, 0) на основании определений ф и ср переводима в формулу сР (1» (а), а) = 0 -« с (О, а') = О, а затем в формулу »Р (1»(а), а) = 0 -«Я (О, а'), которая при помощи схемы ((1а)) может быть получена иэ второй посылки рассматриваемой нами схемы. Формула»6 (а, Ь) -«я»(а, Ь') средствами исчисления высказываний может быть преобрааована в (ср (ф (а, Ь), а) = 0 -»- ср(Ь, а') = 0) бс ср (ср (а, Ь'), а) = 0 -». ср (Ь', а') = О. На основании неравенства ср (а, Ь) ~»Р (а, Ь ), извлекаемого из определения функции ср, мы с помощ ю мо ью „4„ по- лучим формулу ср (ср (а, Ь'), а) = 0 -« ср (ф (а, Ь), а) = О. ~Р Таким образом, для получения формулы (В (а, Ь) «Ж (а, Ь с остается вывести формулу ср (»Р (а, Ь'), а) = 0»Ус ср (Ь, а') = 0-«ср (Ь', а') = О.
Это удается проделать следующим образом. На основании определения ср имеем 1, (а, Ь)~(ср (а, Ь), откуда с помощью ((4)) можно получить ф (ср (а, Ь'), а) = 0 -« ср (1 (а, Ь), а) = О. Тогда в силу ((1а)) имеем ((5)) ср (»Р (а, Ь'), а) = 0 « Я (1» (а, Ь), а). Далее, определение ср дает нам ср (Ь, а') = 0 8с а (Ъ', а') = 0 -« ср (Ь', а') = О, а значит, и ((6)) ср (Ь, а') = 0-«(Я (Ъ', а')-«сР(Ь', а') = ) В силу ((1а)) имеем ((7)) ф (ь, а') = О Я (Ь, а') Формулы ((5)), ((6)) и ((7)) вместе с третьей посылкой нашей схемы Я(1а(а, Ь), а)-«(Я(Ь, а')-«Я (Ь', а')) дают ср (ф (а, Ь'), а) = 0 сс ср (Ь, а') = 0 « ср (Ь', а') = О, что и требовалось для завершения искомого сведения. В качестве примера применения схемы перекрестной индукции приведем вывод неравенства а ( ср (а, н) РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 426 НРедстАвимость РекуРсиэных Функции )гл, уп нз рекурсивных равенств ф (а, 0) = 2 а + 1, ф (О, и') = ф (1, и), ф (а', и') = ф (ф (а, и'), и).
11ока мы к до авали, что это неравенство выводимо только и и фик- сированных значениях переменной и. С помощью схемы пере- крестной индукции оно теперь следующим образом может быть выведено с переменной и. Иа первого рекурсивного равенства мы получаем а «,.ф (а, 0), из второго— 1 < ф (1, и) -+- 0 <ф (О, и') а из третьего— ф (а, и') < ф (ф (а, и'), и) -1 ф (а, и') « ф (а', и') и отсюда, далее,— 1р (а, и') <ф (ф (а, и'), и) Р. (а <ф (а, и') -Р а' <ф (а', и')) Если в полученных формулах подставить Ь вместо а, а вместо и и затем применить схему перекрестной индукции, взяв в каче- стве Я (с, а) формулу с <1)1 (с, с)), а в качестве 11 и)а — термы 1 и ф (, а'), то мы придем к формуле Ь < ф (Ь, а), из которой с по- мощью подстановок можно будет получить искомое неравенство а <13 (а, и).
Совершенно аналогично с помощью схемы перекрестной индукции может быть получено неравенство а<3(2, а, и+2) для аккермановской функции $ (а, Ь, и) '), из которого на осно- вании рекурсивных равенств для $ (а, Ь, и) можно непос ед- ственно получить ред- $ (2, а, и + 3) < $ (2, а + 1, и + 3), а тем самым и $ (2, а, и + 2) < з (2, а + 1, и+ 2), т. е. неравенство, выводимость которого пренще мы могли ста- новнть только при фиксированных аначениях переменной и.
1) См. е. 406, Из сводимости рассмотренных нами обобщенных схем к обычным схемам индукции, в частности, следует, что при использовании обобщенных схем остается в силе теорема о том, что каждая выводимая в рекурсивной арифметике формула без формульных переменных является вернфицируемой. а 4, Представнмость рекурсивных функций) переход к удовлетворительной системе аксиом для арифметики 1. Возврат к полному формализму; система (С); понятие существенного расширения формализма; примеры несущественных расширений; предетавимость функции. От рассмотрения рекурсивной арифметики мы теперь вернемся к преяснему кругу идей.
Мы исходили из тех сообрая1ений, что присоединение к исчислению преднкатов системы аксиом (В) ') еще не дает нам формализма арифметики, несмотря на то, что все пять аксиом Паапа оказались в ней формализованными, причем не дает по той простой причине, что мы не включили в эту систему разрешения вводить функции при помощи рекурсивных определений. Это привело нас к более детальному рассмотрению метода рекурсивных определений а), которое показало, что хотя рекурсивное введение функции и заслуживает названия определения, поскольку при подстановке какой- либо цифры вместо выделенной (посредством данной рекурсии) переменной, а тем более при подстановке цифр вместо всех первменных, оно дает нам некоторое определяющее выражение, но что для самой функции, рассматриваемой с переменными аргументами, при этом не получается никакого выражения, чем рекурсивное введение и отличается от явного определения, которое заключается во введении определенного сокращенного обозначения.
В качестве еще одного отличия рекурсивного определения в сравнении с явным мы констатировали то обстоятельство, что непротиворечивость введения рекурсивных определений еще не гарантируется не~ротиворечивостью предшествующих аксиом, а зависит от определенных свойств этих аксиом. Рекурсивные определения неявно характеризуют штрих-функцию и поэтому они могут также играть роль арифметических аксиом. В частности, мы нашли, что аксиомы (Р,) н (Р,) с помощью аксиомы равенства (1,) ((11) оказывается здесь излишней) и формулы 0' ~ 0 могут быть выведены из рекурсивных равенств для функций з3Ц и и б (и) а). В случае присоединения схемы индукции, для вывода формул (Р1) н (Р,) достаточно уже одних рекурсивных равенств для функциц б (и).
А из рекурсивных равенств для б (и) и а — ' Ь на основе ') См. с. 335. ') См. с. 331. э) См. с. 367 — 368. 1гл. У11 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 1 Ы пРедстлэимость РекуРсиВных Функций 429 явного определения а < Ь Ь -'- а ф 0 с помощью аксиом равенства, формулы 0' ~ 0 и схемы индукции монгно вывести аксиомы ') 1(а < а), а < а', а < Ь 61 Ь < с -«- а < с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
