Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 84
Текст из файла (страница 84)
Действительно, сначала мы получим () (П, Ь) < ф] (]с (т(>1 (а), >)>1 (Ь) )) т)>1 (т]>рС] ]> (р (а, Ь))), а отсюда, аналогично тому, как это делалось в п. 4, получим ()(и, ь) <фрс> 1 „.,(р(а, Ь)). Кроме того, выводимо равенство р (а, Ь) = с, в котором с — один из терман, указанных в нашем утверждении. Иа основании установленных в пп. 1 — 5 утвернсдений о выводи- *> По нонотонноотн фувнцнн ф (а, и) (сн. о.
410).— Прил. ред. мости, для всякой функции 7 (а), следуя ее определению с помощью нормированных рекурсий, мы получим некоторую оценку ) (а) <ф (а), которую можно также ааписать в виде ( (а) < ф (а, т ). Отсюда следует, что функция >(> (а, и) не может быть определена при помощи примитивных рекурсий. В самом деле, если бы это оказалось возможным, то это же самое было бы справедливо и в отношении функции ф (а, а) и в соответствии с этим для некоторой вполне определенной цифры г было бы выводимо неравенство ф (а, а) < т)> (а, с ), из которого подстановкой т вместо а получилась бы формула ф (т, т) < ф (т, т), а из нее — противоречие. Однако это противоречие было бы про- тиворечием внутри рекурсивной арифметики (понимаемой в нашем первоначальном смысле), в то время как мы показали, что воз- можность противоречия такого рода исключается. Тем самым мы показали, что рекурсия, определяющая функ- цию т)> (а, и), действительно выходит эа рамки примитивных рекур- сий.
Из этого результата мы можем следующим образом получить аналогичное утверждение и относительно аккермановской функ- ции $ (а, Ь, и). Рассмотрим функцию )С(а, и) =$(2, а+1, и+2). Для этой функции мы получим сначала )С (а, 0) = $ (2, а + 1, 2) = 2'+', у(а, 0))т)>(а, 0), затем )С (О, и') = $ (2, 1, и + 3) = $ (2, ~ (2, О, и + 3), и + 2) = $ (2, 2, и + 2), )с (О и ) = )с.(1 и) е наконец, у (а', и') = $ (2, а + 2, и + 3) = $ (2, $ (2, а + 1, и + 3), и + 2), )С (а', и') = $ (2, й (а, и'), и + 2).
27 Д. Гниесерт, П. Бернезе Йгл. уп РЕКУРСИВНЫЕ ОИРЕДЕЛЕНИЯ 418 $3) некотОРые Ововщения схим РекуРсии и индукции 419 С помощью этих формул для каждой цифры и может быть выве- дена формула Х (а, и) =» ф (а, «). Для и = 0 эта формула уже выведена. Таким обрааом, достаточно покааать, что с помощью формулы Х (а, и) ) чр (а, и) может быть выведена формула Х (а, и') ) ф(а, и').
Этот вывод может быть получен индукцией ло а. Прежде всего, иа формул Х(0 и') =Х(1, и), Х(1 «))$(1, и), 1р (1, и) = ~р (О, и') получим формулу Х (О, и) ) ф(0, п). Теперь все дело сводится к тому, чтобы получить формулу Х(а, и') )1Р(а, и')-» Х(а', и')»ф (а', и'). Для этой цели мы используем тот факт, что для любой цифры спо- собом, совершенно аналогичным тому, с помощью которого ранее г) была выведепа формула ф (а, и) ( ф (а', п), может быть выведена формула $ (2, а, и + 2) ~ $ (2, а', и + 2), а тем самым и формула Ь)а -» $ (2, Ь, и + 2) ) $ (2, а, и + 2). Иа этой формулы, испольэуя формулу Х (а, п') ) ф (а, и') — » Х (а, и') ~)ф (а, и') + 1 и равенства.
$ (2, Х (а, и'), и + 2) = Х (а', е'), $ (2, ~Р (а, и') + 1, п + 2) = Х (ф (а, и'), и), мы получим формулу Х (а, п') ) ф (а, и') -» Х (а', и'))Х (ф (а, «'), и) е) Сн. с. 409. С другой стороны, иэ формулы Х (а, «) ) ф (а, и) путем подстановки получим Х (ф (а, и'), и) ) ф (1р (а, и'), и), а Отсюда с помощью рекурсивного равенства ~Ь (а', и') = ~р (ф (а, и'), и) формулу Х(ф(а, и'), п))1г(а', и) так что в итоге получится искомая формула Х (а, и') ) ~р (а, и') -» Х (а', и') ) $ (а', и'). Тем самым, действительно, формула Х (а, и) ) ~р (а, «) окаэывается выводимой для любой цифры и. На основании докаааниого относительно функции $ (а, и) отсюда следует, что для всякой функции ((а), определимой посредством примитивных рекурсий, можно укааать такую цифру г, что будет выводимо неравенство ) (а) (Х (а, г).
Поэтому функция Х (а, а), так же как и ф (а, а), ке может быть определека посредством примитивных рекурсий. Следовательно, ие может быть определена примитивными рекурсиями функция $(2, а+1, а+2), а потому и функцию $ (а, Ь, п) пельэя будет определить посред- ством примитивных рекурсий. 3. Обобщенная схема индукции; устраиимость этой схемы. Мы ке будем эдесь продолжать рассмотрение возможных обобще- ний рекурсивного определения, а только вкратце обсудим одно обобщение схемы индукции.
Опо будет касаться применения схемы индукции к таким формулам, которые содержат более одпой инди- видной переменной. В этих случаях для формализации перехода от и к и + 1 оказывается целесообразным — поскольку в полном соответствии с методами рекурсивной арифметики мы хотим иэбе- пеать употребления связанных переменных — допустить схему индукции следующего вида: Я (Ь, 0) Я (й, а) -» Я (Ь, а') Я (Ь, а) РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ !ГЧ, Ч11 420 а таклге схему еще более общего вида: Я (Ь, 0) Я (1О а) бг ... бг Я (1,, а) -1- Я (Ь, а') 1 3! некотОРые ОБОБщения схем РекуРсии и индукции 42! дующей примитивной рекурсией: гр (а, Ь, 0) = Ь, гр (а, Ь, Ь') = 1 (а †' й', гу (а, Ь, Й)).
Я(Ь, а) Здесь 1, 1„..., 1 обозначают какие-либо термы, которые могут также содержать и переменные а, Ь; единственным условием применимости этой схемы является отсутствие переменных а и Ь в формуле Я (с, г). Заметим, что если допустить использование связанных переменных, то эта обобщенная схема индукции сведется к обычной. Действительно, средствами исчисления предикатов из формул Я(Ь, 0), Я(г„а)сг... А Я(1„а)- Я(Ь, а') моп!Ио получить формулы 'чхЯ (х, 0), ~хЯ (х, а) — ь ч хЯ (х, а'), иэ которых с помощью обычной схемы индукции мы получим формулу ))хЯ (х, а), а из нее — формулу Я (Ь, а). Ио сведение к обычной схеме индукции может быть осуществлено, как это впервые показал Сколем '), и без привлечения связанных переменных. Сперва рассмотрим схему Я(ь, о) ~)па() Я (1(а, Ь), а) -ь Я (Ь, а') Я(Ь, а) '(в которой возможность наличия в 1 переменных а и Ъ указана теперь явным образом).
Пусть функция гр (а, Ь, й) вводится сле- г) 8 )г о 1 с ш ТЬ. Е!пс Всшсг)гпп8 6Ьег б!з !пбп)гг!спззсйсшага ш дзг гс1ппз!Усп Еа)г!епг)гесг!е.— Мспашй. Магй., РЬуз., !939, 48, Б. 268 — 276. Парвовачальнс здесь использовалась еще одна схема рекурсии, кстсрак нзпосрздстзскво вида примитивной рекурсии ве имеет; однако, как зтс было указано Р. Петер з реферате работы Пкслема (У. 8ушЬсйс Боб!с, !940, 5, ,% 1, р. 34 — 35), онз может быть сведена к кркмктквной рекурсии. Если во второе иэ этих равенств вместо а подставить переменную п, а вместо Й вЂ” терм п — ' а' и использовать формулы и — ' а 4: 0 -э (п — ' а')' = п — а и а' ( п -э- п — ' а 4: О, то, применив аксиому равенства (з ), мы получим а (п -ь гз (п, Ь, п — ' а) = 1 (п — ' (и — ' а), ф (и, Ь, п — ' а )), а затем с помощью ранее выведенной формулы ') Ь вЂ” а -ь 0 -ь Ь вЂ” ' (Ь вЂ” а) = а, которая вместе с а'(и -ь п — ' а чь 0 дает формулу а'(п-ь п — (и — а) = а, получим а'(п-+.гр (и, Ь, п — ' а) = 1(а, гз (п, Ь, и — а )).
Из этой формулы в сочетании со второй посылкой рассматриваемой схемы (1пг) 1), в которой вместо Ь подставлено !р (п, Ь, и — ' а'), и с аксиомой равенства мы получим формулу а' ( и -~- (Я (ф (и, Ь, и — ' а), а) — ь Я (гр (п, Ь, п — а'), а')), а она вместе с а'(и-+ а(и при помощи средств исчисления высказываний дает (а (п -ь Я (гР (и, Ь, п — ' а), а)) -ь- (а'( и -~- Я (гР (и, Ь, п — ' а'),а )).
Зта формула имеет вид В (п, Ь, а) -+- В (п, Ь, а'). Поэтому для того, чтобы индукцией по а получить формулу гп (и, Ь, а), кам остается получить формулу В (и, Ь, 0), т. е. 0(и-ь Я (гр (и, Ь, п — ' 0), 0). Но эту формулу можно вывести иэ первой посылки нашей схемы, произведя подстановку и применив преобразования исчисления высказывании. Таким образом, нами получена формула 3 (и, Ь, а), т. е.
а ( п -ь Я (ф (и, Ь, п — ' а), а). !) См. с. 375. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 1гл. чп 1 11 некотоРые ОБОБщения схем РекуРсии и индукции 433 Если мы подставим в нее вместо и переменную а н воспользуемся формулами а (а и а — а = О, то получим формулу Я («р (а, Ь, 0), а), откуда с помощью первой рекурсивной формулы для «)«и аксиомы равенства получается искомая формула Я (Ь, а). Теперь для того, чтобы общий вид обобщенной схемы индукции свести к более специальному виду (1пб 1), а тем самым и к обычной схеме индукции, мы воспользуемся тем, что формула Я (Ь, с) может быть переведена в некоторое равенство а (Ь, с) = 0 с рекурсивным термам с (Ь, с).
Поло«ким ф (Ь, с) = ~ч~ а(х, с). и<а Опираясь на выводимые схемы для многочленных сумм ~) и иа эквивалентность Я (с, а) а (с, а) = О, мы получим ((1)) ф (Ь, а) = 0 -«- (с ( Ь -» Я(с, а)) и, в частности, формулу ((1а)) ф (Ь, а) = 0 -« Я (д, а), ((2)) «) См, с. 383 — 383. а также получим переход й) — (с(Ь- Я (с, 8)) «8-«ф(Ь, 8)=0 для произвольной формулы «В, не содержащей переменной с. УчаствУюЩие в этой схеме теРмы 1м ..., 1, в котоРые, как мы знаем, могут входить переменные а и Ь, запишем более раавернуто в виде 1, (а, Ь),..., 1 (а, Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
