Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 107
Текст из файла (страница 107)
Мы покажем здесь несколько больше, а именно, что может быть указана некоторая рекурсивная формула 6 (1, т, и), не содержащая переменных, отличных от 1, т и п, и обладающая тем свойствам, что для любых цифр 1, п« и и отношение 6(1, п», и) имеет место тогда и только тогда, когда в нашей нумерации ! и а являются номерами списков формул, и является номером некоторого равенства 6 и список с номером а представляет собой вывод равенства Ж из равенств списка с номером ! при помощи правила подстановки и схем замены и перестановки.
Построение такой рекурсивной формулы 6(1, и», п) мы начнем с рекурсивного изображения предиката «число и является номером некоторого термам Такое изображение на основе нашей нумерации может быть дано следующей„ равносильной изображаемому высказыванию альтернативой: «и= 8 или и является простым числом « 11 или и= 3 т, где п« отлично от 0 и является номером некоторого терма, или п имеет вид 5 р", .... р ', где р„ ..., р„— различные пррстые числа ) 7, а и„ ..., и, — номера каких-либо тер мовы Исходя из этой альтернативы и применяя способ, аналогичный тому, который мы применяли в гл.
1Ч') в связи со сходной задачей для рассматривавшегося там формализма, мы действительно получим рекурсивное определение некоторой функции 1(п), с помощью которой высказывание «число п является номером некоторого терма» изобразится равенством 1(п)=0. Вслед за этим мы немедленно получим рекурсивное изображение предиката «число п является номером некоторого равенства между термами», так как этот предикат, как мы знаем„может быть сформулирован в виде высказывания «и является числом вида 10 7«11»„где а и Ь суть номера некоторых термов». Далее, отсюда мы получим изображение предиката «число и является номером некоторого списка формул» в виде некоторой ») См.
«. 278-279, 496 ппиложение и! рекурсивной формулы Е)(и). В самом деле этот п е ик ~~О~~Ф~~" ной о м л предикат Рав дога числа х„удовлетворяющего ело ческому высказыванию: « для кажго условию х()((и), число у(и, х) ' номером некоторо О равенства между термами». еперь мы можем рекурсивно изо «числа ги р ур изобразить и высказывание р р нств, второе из которых из первого в результате применения схемы перестасамом деле, это высказывание а р внозначно следуют числа х и у, меньшие т и такие, что т = а и = 10 7» 11а», а это после нее п в некоторую рекурсивну ф О ю формулу ,(и, и). Для того чтобы дать реку сини о р ую формулировку правила з1(т, й, 1), рекурсивное опр схемы замены, мы введем реку сини р аную функцию следующей альтернативы'): е определение кото ой изв р " лекается из «Если ги = 3« .
й — и й является простым числом )7, то з1 (и[, й, 1) = 3" 1; если т=2' 3» 5» и, с'=»О и и се235 Ф з1 (т, )г, 1) =2' 3» . 5«. Ц 1»»1(»(е, к[, а, (Р к<ге если ни один из названных случаев места не имев, имеет, то з[(т, Й, 1) =т.» С помощью этой функции для любого числа щ являю номером какой-либо формулы, можно б ет формулы в результате подстановки поручается фощего рекурсивного предиката, зависящего от пе ем «для некоторого про р стого числа х такого, что 11.с некоторого числа у( и имеет место отношение з1(ги х у = , являющегося номе ом н двх ф" мл Лля любых чисел 1 и ш, яв вляющихся номерами некоторых вух формул, условие, что из этих формул по правил зам получается формула с номером мощью следую[цего рекурсивного п е и, может ыть вы ажено с менных 1, ги и и': «с предиката, зависящего от переги и и ): «существует число х(т, обладающее тем ОБШЕРЕКУРСИВИЫЕ ФУНКЦИИ 497 своиством что з1(х, 7, у(1, 3))=ги и з1(х, 7, у(1, 4))=и».
Оба упомянутых предиката тоже могут быть изображены рекурсивными формулами, которые мы обозначим посредством Оз(т, и) и «зз(1, а(, и) соответственно. После того как мы таким образом получили рекурсивные изображения для всех содержащихся в понятии вывода терминов и отношений, искомую рекурсивную формулу 6(1, и[, и) мы построим путем рекурсивного перевода следующего арифметического высказывания: «имеет место к((1) и у(иг, ).((и)) =и и для лю'ого числа х( Х (иг) выполняется альтернатива: либо существует число у().(1), для которого Р(иг, х)4 У(1„у), либо существует число у ( х, для которого имеет место к(1 (у (т, у), у (а[, х)) или Оя (У (иг, у), У (иг, х)), либо существует число у ( х и число г (х, для которых имеет место Ов(у(иг, у), у(иг, г), у(иг, х))».
Этим закончено доказательство утверждения о том, что любая квазирекурсивная функция одного аргумента вычислима в некотором формализме, для выражений которого можно построить нумерацию, удовлетворяющую трем условиям рекурсивности, или, короче, что любая каазиргкурсивная функция одного аргумента является регулярно аычислимой.
Этот результат вместе с ранее установленной квазирекурсивностью всякой регулярно вычислимой функции одного аргумента позволяет сделать вывод, что класс регулярно вычиглимых арифметических функций одного аргумента совпадает с классом квазирекурсивных функций одного аргумента. Проведенное нами рассуждение дает еще один результат, В самом деле, пусть [(и) — какая-либо квазирекурсивная функция одного аргумента, и пусть 1 — номер какого-либо представляющего собой нормированное квазирекурсивное определение функции [ списка формул только что рассмотренного нами формализма, или — что короче — номер некоторого квазирекурсивного определения г.
Пусть и — цифра, 1 — значение [ (и), а ч — функциональный знак, который в этом квазирекурсивном определении представляет функцию (. Тогда номер формулы Ч(п) 1 будет равен числу 1[), 7».гз з" 11» з[ щем ек 1) Переход от одной сове ш н р е но аналогичной альтернативы к соогвег ему рекурсивному определению проделан в гг. [Ч на с, г60— го обсгоягел ') В втой арифметической фо м ян ьсгво, яго число 7, явля ееся н фор у нровке данного условия проявляет ся ющееся номером яменяой переменной а также меньше номера нмвола О допускаемой в качестве те ма нн нв р, Далее, можно указать цифру щ, являющуюся номером некоторого списка формул, представляющего собой вывод формулы ([(и) 1 из формул списка с номером 1. Вывод этот, как мы знаем, производится с помощью правил подстановки и схем замены и пере- ПРИЛОЖЕНИЕ ОБШЕРЕКУРСИВНЫЕ ФУНКЦИИ п! становкн.
Прн этом выполняется условие 6(! ~и, !0.7'"'~" 1Ро!). Если числа г равно 2' Зо', то 1Ф у(г, 0), а=у(г, 1), и, значит, имеет место отношение 6 (1, у(г, 1), 10 7о го'зо ! !о з (о о)) При этом 5(1, у(г 1) !0.7огохо !!о оооо о!) является рекурсивной формулой, не содержащей отличных от1, и и г переменных, и, следовательно, имеет внд некоторого равенства 1!(1, и, г) =О, где й(1, и, г) — рекурсивный терм, не содержащий переменных, отличных от 1, п и г. Если 1 является номером норми ов квази ек сн р ур вного определения какой-либо функцнйодного аргумента, то для некоторой, подходящим образом выбранной цнф ы г найденное нами соотношение ной цн ры г ()(1, и, г)=0 имеет место прн произвольном выборе цифры и. Тогда для любой цифры г, для которой выполняется отношение 1)(1, и, г) =О, значенне у(г, 0) будет равно значению((и) определяемой этим квази- рекурсивным определением функции !.
Для фигурирующей здесь рекурсивной функции У(т, 0) мы будем употреблять функциональный знак уо(гп). Если мы теперь объединим полученный нами результат с тем, чтб было установлено относнтельно выводов в формализме (Хо), то получится, что для цифры 1, являющейся номером какого-либо нормированного квазнрекурснвного определения, и для произвольной цифры и в формализме (Р) выводимо равенство р 1) (1, и, х) = г, где о — наименьшая нз цифр г таких, что значение ()(1, и, г) равно 0; нз этого равенства, далее, в (Ло) выводимо равенство уо(ро()((, и, х)) =1, где 1 — цифра, являющаяся значением квазирекурсивной функции, определяемой системой равенств с номером 1, при значении арг- мента, равном и.
С другой стороны, вследствие нумернческой и а гу- непротиворечивости формализма (Ео) нн для какой нф д, какой цифры д, отличной от 1, равенство уо(Ро() (1, И, Х)) = о невыводнмо в (Хо). Тем самым для любой квазнрекурсивной, а значит, и для любой регулярно вычнслнмой функции одного аргумента в (Ео) получается некоторое нормальное представление в виде уо(р-()(1, и, х)). Прн этом произвольная отдельно взятая регулярно вычнслнмая функция характеризуется цифрой 1, а сама функция 1)(1, п, а) определяется независимо от функций, которые ей надлежнт изображать.
Впрочем, терм уо(р„()(1, а, х)) изображает квазнрекурснвную (а тем самым и регулярно вычнслнмую) функцию не только прн цифре 1, являющейся номером какого-либо нормированного квази- рекурсивного определения. Это имеет место всякий раз, когда для любой цифры и может быть указана такая цифра г, что имеет место равенство ()(1, и, г) =О. В самом деле, в конце 5 1 мы показали, что любой терм нз (Ео), нмеющнн внд а (р„о (и, х)), где а (и) и 9(п, щ) суть рекурснвные термы, содержащие только указанные переменные, причем для каждой цифры и может быть указана цифра г, для которой имеет место равенство о(и, г) =О, всегда изображает регулярно вычнслнмую функцию; это верно, в частности, и для терма уо(р„() (1, п, х)), если цифра 1 удовлетворяет указанному условию.
В формализме (Х') в роли терма уо (р„() (1, п, х)) выступает терм уо(р„(() (1, и, х)=0)), т. е. терм вида уо(роЯ(1. и, х)) с рекурсивной формулой И (1, и, гп). Этим термом каждая регулярно вычнслнмая арифметическая функция одного аргумента также представляется в анде»,(р„Я(1, и, х)) в том смысле, что имеет место выводимость равенств о„(р„.й! (1, и„х)) =1, когда цифра 1 является номером какого-либо цормнрованного квазнрекурснвного определения этой функции; с другой стороны, терм Уо(р И(1, п, х)) представляет регулярно вычнслнмую функцию всякий раз уже тогда, когда для любой цифры и можно указать такую цифру г, для которой имеет место отношение Я(1, и, г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
