Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 55
Текст из файла (страница 55)
Далее, при [ФО мы под ф([)(а) будем понимать функцию одного аргумента, получающуюся из функции ф[(о„..., а[.[,) отождествлением аргументов. Эту функцию можно также ПРИМЕНЕНИЕ К ПРОБЛЕМЕ РАЗРЕШИМОСТИ е-СИМВОЛ И ЛОГИЧЕСКИИ егОРМАЛИЗМ й з! определить рекурсивно„при помощи равенств ф" (а) =гр(а, а), ф(Г+ 1) (а) = гр (а, ф(~) (а)). Как нетрудно убедиться, функция эта удовлетворяет соотношениям ф(г) (а) о н ф(е+ ) (л) = ф(') (л) а также условию, что равенство фб) (и) = ф(0 (Ь) может иметь место только при 1=1 и а=Ь. А теперь для 1=1, ..., в положим х,(пи .... и„) =фб) (ф, г(П, и,,„..., и,)), Эти функции, как можно усмотреть из перечисленных выше свойств функций грг(а„..., ае., 1) и ф(е) (а), образуют разделяющую систему функций. Поэтому формула (2) УГ1...УГ,е*(Г1, ..., Г„Х1(Г1, ..., Гг), ..., Хе(Г„..., Гг)) истинна в области натуральных чисел. Теперь речь пойдет о том, чтобы математические функции х„..., х, заменить логическими.
Так как все функции х„..., х, получаются итерированием функции ф(а, Ь), то будет достаточно ввести одну-единственную логическую функцию от трех натуральных аргументов, которая для любой тройки чисел а, Ь и с будет принимать значение «истина» или «ложия в зависимости от того, выполняется или не выполняется равенство ф(а, Ь) =с. Для обозначения этой логической функции мы возьмем какой- нибудь символ из числа не встречающихся в формуле (2), например Ч" (а, Ь, с).
Для того чтобы с использованием этого символа исключить функциональные знаки х„..., х, мы на время введем знак равенства (вместе с выделенным распределением истинностных значений для равенства), который впоследствии опять исключим. Тогда из формулы (2) мы сначала получим истинную формулу (3) ееГ1... хгГгФ)1" . тере (Х1 (Гм ..., Г) = рз бг... сг хе(Г1г ° ° ° г Гг)=Г)е ~Де (Г1 г Ггг Рзг ° ° г Г«И Отношение хз (пм ..., и ) = 11 й... бг хе (пз, ... > п,) = 1 теперь с помощью логической функции Чг(а, Ь, с) можно выразить следующим образом: ,Ивз...Звг 1(Чг(п„п,, оз) бгЧг(п„вз, пз) бг Р(ии вм оз)сг ° ° ° огЧ (пг вг — з в, 1)б~ 1 (и, 1»1, 1 11)ог Чг(вехи 1, 1,)й...й Ч" (в...
14 и 1«)~ (В случае, когда г=1, вместо этой формулы надо будет взять формулу гр(пз, пг, 11) й Чг(пг, 11, 14) бг... бг Ч'(и,, 14,, 14)1. Внесем это выражение в формулу (3) и заметим, что любое выражение вида Зв1...Б)пг гй(91, ..., Е,,) — 2, где 2 не содержит переменных в„..., вг,„может быть преобразовано') в выражение ггеп~... 4ЕГВ„, (К (Вг, ..., Вг,) 2) и что в предваренной формуле можно произвольным образом поменять порядок следования кванторов всеобщности, не разделенных кванторами существования. Тогда, поместив кванторы всеобщности Чи„..., Чгпг 1 непосредственно вслед за квантором гегГ, и пеРеименовав' ) пеРеменные в„ ..., пг 1 в Гг+„ ..., Г, „ мы получим формулу (4) егГ1... «Г ...
ЧГИ ггп1... геев (Чг(Гь Г1, Гг+ ) бг (Гз Гг+1 Гг-!.4) ~ Ч (Ге Гг.~-з Гг+з) г (Гг' Гзг-з' Гзг-1) (Гзг-1' Гзг-1' "11г Ч (ÄР1 п„р,) а... а Ч (Г„„р, „р,) — '3*(Г1, ", Гг, рз, ", в«И которая, таким образом, оказывается истинной в области цифр. При этом логическая функция Чг(а, Ь, с) удовлетворяет формулам единственности по аргументу с. Покажем, что здесь достаточно воспользоваться первой из этих формул. Для этого мы добавим к формуле (4) истинную в области натуральных чисел формулу (5) 41хт1У=)ЗЧг(х, у, г).
') Заметим, что в результате преобразования, производимого по правилам исчисления предккатоа, из истинной формулы всегда получается формула, также являющаяся истинной. ') Этим переименованием мы избавляемся от необходимости делать какие- либо дополнительные замечания для случая г = Ц 254 255 $5! деэд... 5555--(775...3«едО(55 " ~ «е)* ддгхд . Ух„„-(уЛ (хи ..., х„, у), ') См. с, 223 и аллее. е) См. с. 25! в далее. е-СИМВОЛ И ЛОГИЧЕСКИИ ФОРМАЛИЗМ 7гл.
Ри Если формулы (4) и (5) связать знаком конъюнкции и заменить в получившейся формуле выражение 6*(ЕМ ..., $„«д, .... 775) выражением 3(5„..., 55, Р„..., д)5), а трехместный символ Ч' формульной переменной А с тремя аргументами, то построенная таким образом формула 9 будет выполнимой и будет иметь вид (1). Этот результат мы получили в качестве следствия из предположения о выполнимости формулы й, А теперь, наоборот, предположим, что выполнима формула Ж Ее выполнимость означает, что в формулах (4) и (5) предикатные символы можно так интерпретировать как символы для логических функций, определенных в какой-нибудь индивндной области ум что при этом истолковании обе эти формулы окажутся истинными. Из истинности формулы (4) следует истинность формулы )дед ° ° хдееВ5едд Зйм Бд) ...377 (Ч" (5, 5, 5„)55 (еее-д еее-е «д) (Еее д «д «е)сд" едЧ'(Еее „«5,, «е)) ч5 ".1(55Е(«д...
-(«ее)*(5д, ..., 55, д;„..., «,). Посылка этой импликации является истинной формулой ввиду истинности формулы (5) !она даже формально выводима из (5)). Значит, заключение ее тоже является истинным. Но оно получается нз б путем замены формульных переменных символами конкретных логических функций, так что в результате у нас получается некоторая модель формулы О с областью Уд. Таким образом, с точки зрения выполнимости формула 9 равносильна формуле й, что и требовалось доказать. Заметим, что формула Ж может быть преобразована в сколемовскую нормальную форму а также в формулу вида (7) ддГхд'д(хе=(уедхе...
ддх„Л(хд, ..., х„, у). Таким образом, для каждой формулы исчисления предикатов может быть указана равносильная ей по выполнимости формула вида (6) нли (7). А теперь от теоретико-модельного рассмотрения мы перейдем к финитиому теоретико-доказательственному, С точки зрения теоретико-множественной логики предикатов теорема Пепиша, ввиду совпадения выполнимости и неопровержимости, равносильна утверждению о том, что для всякой формулы б исчисления пре- пРимгнение к пРОБлеме РАЗРешимости дикатов может быть указана некоторая формула вида (1), равносильная формуле б относительно опровержимости. Доказательство этого утверждения, получающееся из предшествующего рассуждения в сочетании с геделевской теоремой о полноте и с теоремой о неопровержимости выполнимых формул, является нефинитным.
Однако, используя наши критерии опровержимости'), это доказательство можно перевести в некоторое финитное. Действительно, это может быть проделано следующим образом. Во-первых, для каждой формулы 21 исчисления предикатов может быть указана такая формула б вида ГДЕ хд, ..., 5„775, ..., 77,— ПОЛНЫЙ СПИСОК ВХОДЯЩИХ В НЕЕ ИНДИ- видных переменных, а д и 6 отличны от нуля, что в нее не входят никакие формульные переменные без аргументов, а также формульная переменная А с аргументами и что ее отрицание дедуктивно равно отрицанию формулы Л, так что формулы й и Л равносильны относительно опровержимости. Поэтому наше утверждение достаточно доказать для формулы 3. Для этого мы снова воспользуемся формулой )З, записываемой следующим образом: Рхдд!у,пгА (х, у, г) Л се!5 ...)15е...)775 Ф« ...
'57775 (А(5, 5, 5, )ЬА(гее 5, Н 5„~,)55 А(5, 55„, Л, )ед" ° ...55А(йее д, д)5,, 775) — 'ВВ(5д ° ° 55' 775 " «5)). Обозначим через д))(ри ге, ..., Е „, «, ..., 775) выражение А (5 , 5 , 5, ,) Л ... Л А (5,„ д, «, „ д)5), ! фигурирующее в ней в качестве посылки импликации, и через ш — цифру 25+6 — 1. С помощью критериев 1 и 3 мы покажем, что формула й опровержима в исчислении преднкатов тогда и только тогда„когда опровержима Оз.
С этой целью мы снова воспользуемся выделенной системой функций и„..., ке, которая была нами определена' ) с помощью функции ф(а, Ь)=2е(2Ь+!), причем теперь будет важно и то, что функции к„..., ие являются вычислимыми. 257 256 [ГЛ. 111 Е.СИМВОЛ И ЛОГИЧЕСКИП «>ОРЬГАЛМЗМ ПРИМЕНЕНИЕ К ПРОБЛЕМЕ РАЗРЕШИМОСТИ Допустим сначала, что опровержима формула 5. Тогда, сог- ласно критерию 1, можно указать такую цифру р, что формулы 6(пг 1, ..., и, р х,(п, р ..., п,;), ..., х,(п, р ..., п,,)) 1 = О, ..., (р+ 1)' — 1 не являются совместно выполнимыми.
Пусть о означает наибольшее из значений выражений х;(п, 1, ..., пг 1) при ! = 1, ..., в; 1= 0,..., (э+1)' — 1. [Нетрудно, впрочем, убедиться, что это число равно хз(», ..., р), но нам это не понадобится.] Тогда при любой замене формульных переменных из 5 какими-либо логическими функциями, определенными для цифр, изменяющихся в пределах от 0 до ч, по крайней мере одна из формул 6 (Пг 1, ..., П».1, хд(П1 1, ..., Пг 1),, хз (Пг 1, ...
> Пг 1)) 1 = о, ..., (р + 1) — 1 будет ложной. Но отсюда следует, что при любой замене формульных переменных из йх йлогическими функциями, определенными для цифр, изменяющихся в пределах от 0 до ф(о, ч) '), будет ложной по крайней мере одна из формул (8) А (11, 1„ф(!1, !»))ог (ф (пм п м 1 1 ь 6 (па п 11 1 )) где 1, 1,, и,, ..., п„„1„..., 1 независимо друг от друга пробегают цифры от 0 до г!. Действительно, любая замена формульных переменных в формуле 9 логическими функциями слагается из некоторой замены для формульной переменной А и из замен для формульных переменных формулы >1. А теперь представим себе, что мы каким-либо определенным образом произвели эти замены формульной переменной А и формульных переменных формулы 5 соответствующими логическими функциями, определенными для цифр, не превосходящих ф(2, й).
Если в результате этих замен одна из формул А(1„(„ф(1„1»)), где 1, и 1,— цифры, не превосходящие ч, получит значение «ложь», то будет ложной по крайней мере одна из формул (8) с цифрами 1ы ..., 1з, лежащими в пределах от 0 до ч. Если же в результате этих замен все эти (я+1)' формул А (!„(м ф(11, 1,)) окажутся истинными, то во всех тех формулах (8), в которых пы ..., п„( р и О для простоты мы пользуемся тем, что функция ф (а, Ь) возрастает как прн возрастании а. так н прн возрастаннн Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
