Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 95
Текст из файла (страница 95)
Такой сокращающий символ в том случае, когда заменяемый им 1-терм не содержит свободных переменных, будет символом без аргумента, играющим роль индивидного символа. Если же заменяемый 1-терм содержит свободные переменные, то в соответствии с нашим общим соглашением относительно явных определений ') сокращающий символ будет содержать встречающиеся в этом 1-терме свободные переменные в качестве аргументов. При содержательном истолковании этот символ будет изобра»кать некоторую функцию, и если в качестве аргументов будут фигурировать лишь индивидные переменные, то это будет обычная математическая функция.
Если в качестве аргументов будут фигурировать формульпые переменные, у которых в свою очередь в качестве аргументов имеется одна или несколько индивидных переменных, то аргументы этих формульных переменных мы будем указывать при помощи свяаанных переменных, которые будут записываться в виде нижних индексов у зависящего от этих аргументов вводимого алака а). Таким способом мы получим символы типа ))х (Л (х)), !) См. гл. У)1, с. 357. а) Если в»-терке, для которого мы вводим сокращеппе, в качестве аргументов формулькых перемепкых встречаются свободные ккдквкдные перемеккые, то этк ввдквкдкые переменные должны быть указаны в качестве самостоятельных аргументов вводкмого символа наряду с формулькымк переменными.
В соответстввк с этим, для »-терка, содер»кащего в качестве составной части выражение А (с) я пе содержащего более никаких свободных переменных, сокращающий скмвол будет, например, иметь вкд (х (А (х), с), где ( — какой-либо фуккцвокальяый акак; роль х может играть к какая- нибудь другая свяааппая переменная. 7„а, (а, В (х), С (у, г)); при атом с содержательной точки зрения (3„(А (х)) будет изображать функцию, которая всякому предикату с одним аргументом ставит в соответствие некоторый индивид, а ухл, (а, В (х), С (у, г)) будет изображать функцию, которая любой тройке, состоящей иа индивида, предиката с одним аргументом и предиката с двумя аргументами, ставит в соответствие некоторый новый индивид.
3. Функция ю(А); формализация понятия наименьшего числа е помощью функции )А„А(х); формулы однозначности. Мы займемся сейчас подробным рассмотрением ряда важных функциональных конструкций, оказывающихся осуществимыми благодаря наличию 1-символа. В качестве первого примера мы рассмотрим изображение такой функции высказывания, которая лтобому высказыванито сопоставляет значение 0 или 1 в зависимости от того, истинно это высказывание или нет. С этой целью мы будем исходить иа формулы (А -»- а = О) д» ( )А — «- а = 0 ).
Формулы единственности для пее запишутся в виде Зх ((Л -«х = 0) дс (~ Л вЂ” «х = 0')), Мх»бу((Л-«х= 0) б»(» Л вЂ” ».х=О') д»(Л-+.у=О) 8» (~ А — »- у = 0') — »- х = у). Обе они могут быть выведены с помощью аксиом равенства. Вывод первой формулы протекает следующим образом. Из первой аксиомы равенства подстановкой и добавлением посылок пол чаем 5 А -+. (А — 0 = 0). Из тождественной формулы А — «()А -+. В) подстановкой получаем А — «(~А -»- 0 = 0'). Полученные формулы по схеме конъюнкции дают А -+. ((А -+ 0 = 0) д» ( )А -+.
0 = 0')); далее, иэ формулы (Ъ) подстановкой получается формула (А -+- 0=- 0)А( )Л вЂ” «О= 0') — »- Вх ((А-+. х =- 0) й (~А-«х=О')), которая вместе с предыдущей формулой по правилу силлогизма дает А -»- Вх ((Л-»- х —. 0) д» ( )Л -»- х = 0')). 47З ПОНЯТИЕ «ТОТ, КОТОРЫЙ«И ЕГО УСТРЛНИМОСТЬ [ГЛ. Ч!Ы Аналогичным образом мы получим и формулу ~А -«.
Зх ИА -~ х = 0) & ( !А 1- х = ()')) Теперь по схеме для дизъюнкции можно получить формулу А ~/ 1А «- йх ((А -+. х =- 0) & ( ~А -~ х = 0')), и так как А ~/ !А является тождественной формулой, то мы получаем Эх ((А -«- х = 0) & (~ 4 — «х = 0'))„ Совершенно аналогичным образом протекает вывод второй фо— м лы у единственности: с одной стороны, ее можно вывести с посылй ор- ной А, а с другой стороны, с посылкой !А. Вместо первой аксиомы равенства, используемой в доказательстве первой формулы, здесь используется формула а = с & Ь = с -э а = Ь„ иа которой в результате применения подстановки и средств исчис- ленин высказываний получается формула А -~ ((А -«.
а = 0) & ( !А «- а = 0') & (А -+ Ь = 0) & (~А -«. Ь = 0') -«- а = Ь), а также аналогичная формула с посылкой !А; вместо формулы (Ь) здесь используются схема (а) и правило переименования. Выводимость обеих формул единственпости позволяет ввести в качестве г-терма выражение ьк ((А -«- х = 0) Й ( !А -«- х = 1)). Чтобы иметь для этого терма соответствующее сокращение, мы сформулируем следующее явное определение: в (А) = г„((А -«.
х = 0) & (~А -~ х = 1)). Опираясь на это определение и испольауя вторую аксиому равен- ства, мы с помощью ~-правила получим формулы А-+-в(А) =О, !А -«- в (А) = 1, а из них, применив формулу 0' чь 0 получим эквивалентность А- ю(А) =О. Тем самым мы в общем виде показали, что всякая формула переводима в равенство вида а О.
ОПРЛВИЛО И ОПЕРИРОВАНИЕ С НИМ В рекурсивной арифметике это было воаможно только для формул некоторого специального вида. В полученных нами формулах для ю (А) вместо переменной А можно будет подставлять проиавольные формулы и таким образом мы получим ряд дальнейших функций. Например, если мы вместо А подставим А (а), то получатся формулы А (а) — «- ю (А (а)) = О, ЧА (а) — «со (А (а)) = 1, в которые вместо А (а) можно будет снова подставить какую-ни- будь формулу Я (а). Тогда ю (Я (а)) изобрааит нам такую функцию, которая принимает значение 0 или 1 в зависимости от того, выполняется высказывание Я (а) для индивида а или же нет. Тем самым с помощью функции ю (А (а)) в общем виде формализуется переход от логических функций (предикатов) к математическим функциям.
Если в приведенных выше формулах мы подставим вместо переменной А формулу эх А (х), то, используя преобравование !'1!х А (х) в Лх!А (х), получим формулы ЧхА (х) «. ю (!чхА (х)) = О, Лх )А (х) -«- «о (ЧхА (х)) = 1, Здесь снова вместе А (а) можно будет подставить какую-нибудь конкретную формулу Я (а), и тогда ю (чх Я (х)) изобрааит нам значение 0 или 1 в зависимости от того, верен предикат Я (а) для всех элементов индивидной области или же он неверен по крайней мере для одного из них. При введении функции ю (А) и при выводе характеризующих ее формул А -«.
ю (А) = 0 и )А -«. ог (А) = 1 кроме общих логических формул и правил, включан ~-правило, мы польаовались только аксиомами равенства и формулой 0' ~ О. Теперь мы рассмотрим таку!о функциональнучо конструкцию, в которой г-правило будет применяться в сочетании с арифметическими аксиомами, в частности с аксиомой индукции. Таким обрааом, зта конструкция при содержательном ее истолковании будет относиться специально к числовой индивидной области. Как мы показали в гл. ч'1, иэ аксиомы индукции и на аксиом для символов = и (, т. е. иэ формул системы (В), может быть 488 ПОНЯтиа етОт, КОтОРЫйа И ВГО РотРАНКМОСтЬ ИГЛ.
РШ выведена формула А (а) — 1- Зх (А (х) сй 'асу (.4 (у) -з- х = у ~/ х у)), изображающая принцип наименьшего числа. Если формулу А (с) бс Чи (А (и) -+ с = и ')/ с ( и) сокращенно обозначить посредством % (с), то предыдусцую формулу, переименовав в пей переменную у в и, можно будет записать в виде А (а) — е- лх% (х). Из этой формулы с помощью схемы (р) мы получим формулу ЗхА (х)-э Эх% (х). Применим с-правило к формуле (Чй 1 А (й) е. а = 0) бс (ЗзА (з) -+. % (а)) .
Соответствующие формулы единственности снова можно будет получить при помощи схемы диэъюнкции: свачала каждая иэ обеих этик формул выводится, с одпой стороны, с посылкой Чз ~А (з), а с другой стороны, с посылкой ЪА(г); после этого можно будет воспользоваться формулой 7й 1А (г) )/ Эз А (з). Упомяпутые выводы могут быть получены средствами исчисления предикатов с помощью формул 0 = О, ЗхА (х)-+. Зхрл (х), а =- 0 бс Ь = — 0 -е- а = Ь, %(а) бс % (Ь)-е- а = Ь. Последняя из этих формул может быть получена следующим образом. Используя основную формулу (а) (в сочетании с правилом переимепования), с помощью исчисления высказываний мы получим % (Ь) -е А (Ь) Й (А (а) -е- Ь = а ~/ Ь ~ а).
Если (с помощью подстаповок) мы поменяем в пей местами перемепяые а и Ь, то получим рас (а)-+. А (а) бс (А (Ь) -~ а = Ь ~/ а ( Ь). Взяв обе полученные формулы, мы с помощью исчисления высказываний получим формулу Ща) Ос % (Ь) е. (а = Ь ~/ а Ь) ос (Ь = а )/ Ь ( а), с-ПРАВИЛО И ОПЕРИРОВАНИЕ С НИМ 481 которая в сочетапии с формулами Ь = а -е- а = Ь, а ( Ь -е- 1(Ь ( а) с помощью исчисления высказываний дает пам формулу % (а) сй И (Ь) -~- а = Ь. Теперь, после того как выведены обе формулы единственности для формулы (1/г Ч А (г) — 1- а = 0) сй (Зй А (з) — е- й)с (а)), выражение с„((Чй 1 А (й)-~х= О) сй(ЗзА(г)-~Юс (х))) может быть введено в качестве с-герма.
В качестве едипствеикой свободной переменной в кем фигурирует формульяая переменная А с одним аргументом. Мы возьмем для этого терма в качестве сокращения символ р 4(): таким образом, мы вводим этот символ при помощи следующего явного определения: рнА (х) = с ((йз'ЧА (г) -е- х = 0) бс ДйА (з) -+- % (х))); это функциональный знак, который в качестве аргумента имеет формульпую переменную, которая, со своей стороны, зависит от некоторого аргумента. Разповидпость подчинения, изображаемую этим функциональным знаком, мы выявим, написав формулу, которая извлекается для р„А (х) из схемы с-правила. Эта формула имеет вид (7з 3 А(з)-е-р„А(х)=0) сй (ЗйА(з) -э-% (р 4(х))) Если мы разобьем эту конъюнкцию па члены и переименуем перемеппую з в х, то получим Чх с А(х)-е р„А(х)=0, ЗхА (х) -е- И (р„.4 (х)) Теперь учтем уже использовавшуюся ранее (при выводе второй формулы едипствеппости) формулу % (Ь) -е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
