Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 99
Текст из файла (страница 99)
ае> ат> ..., а„ соответствует число 1„(х) = 1 (х). 5СО НОнятие >тот, котОРыи> и еГО УстРАнимость И'л, чн> Мы можем здесь считать, что входящие в а(а,..., 1«) и в 5(а,..., к, и, т) рекурсивные функции уже заменены соответствующими термами, так что правые части обоих равенств, если не считать функции >р и сокращенных обозначений (т. е. явно определенных символов), не содержат никаких символов, кроме функциональных знаков а', а + Ь, а.
Ь, символа )» 4 (х) и логических символов [которые могут, например, встречаться внутри какого-либо выражения [»„а(х)!. Задача теперь заключается в том, чтобы найти такой терм 1(а,..., й, и), что для него выводимы формулы ((а, ..., й, О) = с (а, ..., й) 1(а, . „й, и') = $(а,..., и, и, 1(а, ..., Й, и)). Здесь в записи термов параметры а, ..., к, можно всюду опустить, так что эти равенства могут быть записаны просто в виде ') Сначала мы изложим основные идеи решения этой аадачи. Мы будем следовать Дедекинду, который в своем сочинении «ччаз а[пс[ ппй»чаз зо11еп д[е Еа1»1еп3» впервые показал разрешимость рекурсивных равенств, рассматриваемых как определяющие равенства для вводимой в рассмотрение функции, не пользуясь наглядными соображениями.
Его доказательство заключается в том, что сначала он показывает, что для каждого числа и имеется функция 1„(а), обладающая тем свойством, что 1„ (О) = а и что для всякого числа х( и Доказательство это производится индукцией по и. Далее оп уста- навливает, что указанными условиями значение 1„(х) однознач- ным образом определяется для всех х < и, так что если х ( и и х(п», то а) Требование иеио укееыеать параметры е схеме рекурсии проистекает — по ирайией мере в случае простейшей схемы рекурсии — исключительио от того, что длк функциональных »какое иы условились явно выписывать есе их аргументы.
То, что е левых частях рекурсивных равенств стоит вновь вводимый фуккциоиалькый »как с соответствующими аргументами, а ке проиееольиые термы с теми же самыми нереиеввыии, является существекиой особеииостью киде вашей схемы рекурсии. СВЕДЕНИЕ К ЯВНЫМ ОПРЕДЕЛЕНИЯМ Отсюда следует, что функция ~ (и) = 1„(и) удовлетворяет атим рекурсивным равенствам при всех аначениях аргумента. Это докааательство может быть проведено чисто формальным образом, но не в рассматриваемом нами формализме, а в логическом исчислении «второй ступени», т. е. с использованием связанных функциональных переменных (или, вместо этого, связанных формульных переменных, или соответственно переменных для множеств).
Действительно, ведь нам требуется выразить некоторое утверждение, говорящее о сущеппвовании функции, обладающей определенными свойствами. Но эта трудность может быть обойдена. Действительно, каждую иа функций 1„(х) нам нужно рассматривать только для значений аргумента от 0 до и; поэтому существование функции 1„(х) со свойством ~„(0) = а да >Ух (х ( и -ь ~„(х') = Ь(х, г„(х))) эквивалентно существованию такой (и + 1)-членной числовой последовательности что а, = а и для каждого индекса й ( и выполняется соотношение а„= Ь(Ь, ад).
С другой стороны, мы знаем, что конечные числовые последовательности могут быть перечислены, т. е. вааимно однозначно сопоставлены с числами. В рекурсивной арифметике мы рассматривали перечисление, которое основывается на представлении чисел в виде произведения степеней простых чисел. В этом первчислении последовательности где 5ае представляет собой число 2, а фю..., 5аа суть и первых нечетных простых чисел.
Обратно, если ыы будем исходить нз числа аа аа п»=в~0 ' 'вап > то соответствующая последовательность ае ..> а„ 3! 503 ПОНЯТИЕ «ТОТ, КОТОРЫИ«И ЕГО УСТРЛНИМОСТЬ 1ГЛ Ч1П СВЕДЕНИЕ К ЯВНЫМ ОПРЕДЕЛЕНИЯМ 503 будет изображаться при помощи введенной в рекурсивной арифме- тике функции т (т, й) последовательностью т (т, О),...«т (т, п). А существование числовой послсдоватсльпости а„., а„с искомым свойством изобразится при помощи формулы Лх [з (х, 0) = а бс '9'у (у ( и ->- т (х, у') = Ь (у, о (х, у))) [ существованием определенным образом устроенного числа.
Этот способ позволяет преобразовать рассуждение Дедекинда таким образом, что в его формализации не будет встречаться никаких других переменных, кроме числовых '). И все же зто вще не приводит нас к желаемой цели. Действительно, в формализме системы (Е) в нашем распоряжении нет функции з> (т, )с). В рекурсивной арифметике зта функция определяется при помощи ряда рекурсий '). Если мы попробуем при помощи функции )>„А (х) исключить эти рекурсии, не считая рекурсий для ело>кения и умножения, которые в системе (Х) являются допустимыми, то заметим, что для некоторых из них это удается без труда; но ост ются рекурсии для двух функций ь"-з« для которых в рамках системы (Е) не известно никакого явного определения (которое не использовало бы общего способа замены схемы рекурсии явным определением, который здесь как раз и должен быть построен).
2. Формальная реализация; воаможиость обобщения этого метода. Вследствие этого мы должны пытаться каким-нибудь иным способом изобразить существование числовой последовательности а„..., а„с рассматриваемым свойством посредством экзистенциального высказывания о числах. Выход иэ этого положения удается найти на основе следующего замечания Геделя з): если число ! выбрать таким образом, чтобы оно делилось на все числа от 1 до п, то числа 11+1, 21+1, ..., п1+1, (п+1) !+1 будут попарно взаимно простыми и потому можно будет найти такое число т, что будут иметь место сравнения т = аз (шо>[ ()с + 1) ! + 1) (1с = О, 1,, п).
') Возможность такого преобразования, вероятно, впервые была замечена Дж. фон Нойманом. з) См. с. 393 — 395. з) См. доказательство теоремы Ч11 з зго работе: 0 о й з 1 К. ОЬзг 1ог>аа! иазпгзсЬе!3Ьзгз Багге йзг Рг!вс!р!в Мзгйзша!!сз иоо ззгнзвоззг йузгеше 1.— МопагзЬ. МзгЬ. РЬуз., 1931, 38, № 1. Если же 1 будет, кроме того, выбрано не меньше наибольшего из чисел аз, а„..., а„, то будут выполняться неравенства аз ( (й + 1).
1 + 1 н, значит, аз будет остатком от деления т на ()с + 1) ! + 1. Тем самым последовательность аз,..., а„будет изображаться последовательностью остатков от деления т на числа 1.1+ 1, 2 1+ 1,..., (и + 1) ! + 1 Такое изображение оказывается возможным для любой последовательности а„а„..., а„. В связи с этим существование последовательности а„а„..., а„, удовлетворяющей условиям а, = а, а, = Ь()с, аь) для всех Й(п, оказывается равносильным существованию таких чисел т и 1, что р(т,1+1) =а и что для каждого числа й от 0 до (п — 1) р (т, )с".
[ + 1) = Ь(1с, р (т, )с' ° 1 + 1)). Утверждение о существовании таких чисел >и и 1 мы можем изобразить и в нашем формализме, опираясь на сформулированное нами явное определение функции р (а, Ь), а именно, при помощи формулы Зх лу [р (х, у+ 1) = а «й )7г (г ( и -ь р (х, гз у+ 1) Ь(г, р(х, г' у+1)))), которую мы сокращенно обоаначим посредством Я(п). Теперь аадача заключается в том, чтобы вывести эту формулу и после этого построить некоторый терм )(п), для которого можно будет доказать формулы 1 (0) — а [(и') —.Ь(п, 1(и')). Вывод ') формулы Я(п) может быть проведен индукцивй по п. Формула Я(0) переводима в Злу(р(х,у+1) =а), а эту последнюю можно получить из равенства р(а, а+1)=а, >) Читатель, нз придающий большого значения проверке етого несколько утомительного зызодз, может перейти н с.
507. 5сс» пОнЯтие»тот, кОтОРый» и ЕГО УстРанимость 1гл» У1п 1 М 505 СВЕДЕНИЕ К ЯВНЫМ ОПРЕДЕЛЕНИЯМ которое получается иэ формулы а= — г (шойЬ)А-г(Ь> г=р(а, Ь). Для того чтобы получить формулу р1 (и) -~Я (п'), мы сначала иядупцией по а выведем формулу шп11„(х', п') ) й А а(и дахау (у(а->- х = р (и, у'» Х + 1) (шой (у'»Й + 1))). Эта формула имеет вид >1 А а(п->- В(а), причем переменная а в »» не входит, Формулу В (О), а тем самым и формулу Ц 81 0 ( п -»- В (О), можно немедленно получить из формулы Ъ Ъ (шой с). Теперь, для того чтобы применить индукцию, мы должны будем вывести формУлУ (11 А а (и ->- В (а)) — » (ц А а'< п -» В (а'))» а для этого достаточно будет вывести формулу И А а < п — (В (а) — В (а')), так как от этой последней с помощью исчисления высказываний и формул для < легко перейти к предшествующей ей формуле.
Таким образом, речь идет о выводе формулы шп1$„(х", и') ( Й А а < и -э (Зхуу (у(а -э х = р (т, у' ° 1 + 1) (>пой (у' Й + 1)) -~ Эха (у ( а' -»- х мм р (т, у' 1 + 1) (шой (у' Й + 1)))). Искомый вывод может быть получен с помощью ранее 1) выведен- ной формулы >зх (х «и->-х' ! Й) — >- Ргпп (шп1$„(х' й+ 1; т), т' й + 1).
Если мы подставим в нее а' вместо и и воспользуемся формулами г(а'Аа«п-~г<и', г < и' — » г' ! шп11„(х', п'), г' ) шп1$„(х'; п') А шэ11„(х', п') ) Й -~ г' ) Й, ') См. с. 458. то придем к формуле шп11„(х', п') ( Й А а ( и -» Рг1ш (шп15„(х' Й + 1; а'), а" Й + 1). Возьмем формулу Рг1ш (а, Ь) — 3» (г = Й (шой а) 81 г = 1 (шой Ь)), иа которой с помощью подстановок получим Рг>ш (шва„(х' ° й + 1; а'), а'»Й + 1) — » 3» (» = с (шой шс11„(х' Й + 1; а')) А. г гм р (и., а'.1 + 1) (П10й (а" Й + 1))); кроме того, с помощью беа труда получающихся формул Ь = с (шой шп11„(х' й + 1; а')) -+.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
