Гильберт, Аккерман - Основы теоретической логики (947372), страница 19
Текст из файла (страница 19)
Все же остается слишком много возможносчей для различ- ных видов стонщей в начале формулы комбинации знаков общности н существования, которую мы будем называть приставкой формулы. В этом о>ношении 11б Ноплаоьппе форам У.мое по ~псоеппо птееипамоо интересен результат Сколема ', являющийся некоторым уточнением предложения о предваренной нормальной форме. Предложение Сколема гласит (в формулировке, которая нам здесь понадобится); Для каждой формула исчисления предикатов можно указать другую формулу, имеющую не проще предваренную нормальнуго форлау, но специально такую, что всякий знак сущесавования предшествует всякому знаку общности; причем зта новая форагУла выводима или невыводима одновременно с данной формулой из нашей системы аксиом исчисления предикатов. В дальнейшем мы будем называть формулу в пред- варенной нормальной форме, з которой ни один знак существопания не следует за знаком общности, форлгУ- лой в нпрмальной форме Сколелае.
Для доказательства предложения нам достаточно рассмотреть только формулы, имеющие предваренную нормальную форму. Мы можем допустить, далее, что наша формула не содержит свободных предметных переменных. В самом деле, если бы таковые имелись, то достаточно было бы (в силу аксиомы е) и правила .!') рассмотреть формулу, получающуюся из заданной, если связатЬ Вее еЕ СвОбодные переменные знаками общности, понесена ПОСлЕдние в начале формулы.
Под степенью подобного рода формулы мы будем понимать число знаков общности, за которыми следуют еще знаки существования. То~да достаточна показать, что для каждой формулы в предварепной нормальной форме, но не в форме Сксяема, можно указагь такую другую форлгулу, которая в смысле выводимое!и равносильна перв)й, но степень которой ниже сгепени первоначальной формулы. Мы люжем, далее„допУстиггп что пРиставка РассматРиваемой фоР. мулы начинаегся со знака существования. Действительно, если формула, которую мы обозначим через т(, начинается со знака общности, то мы берем предмет' Япогам, тп., 3.оп!ась-ьоппыпа1ог1асье ппеегапсьппаеп еьег пм нгюпьагье11 олег Веооа!аьагке11 опашмпа1ыасьег заьм пеьог е1пем тьеогеюе пьет и!гые мепаеп.
Уш, загп1ег 1, л1а1.- пае. К1аоаа, Шаа, Ко а. ную переменную, не встречающуюся в е(, например и, и удовлетворяющую аналогичному требованиго предикат. ную переменную, например О, невменяем л формулой: (еи)(ййб(и) 1т 0(п)), которая, как легко обнаружить, в смысле выводимости равносильна п(, так как в области действия (Еи) к 6 прибавлен истинный коныонктивный член. Формула (Еи)('21йб(и) ~/6(и)) может быть затем приведена к предваренной нормальной форме так, чтобы в приставке на первом месте стоял знак существования.
Итак, наша формула начинается с л(л' 1) знаков существованил, за которыми следует по крайней мере один знак пбщиости. Она имеет поэтому форму: (!) (Ех,)... (Ех„)(у) 6(х„х„..., х„, у). Здесь 6 (х„х„..., х„, у) формула в предваренной нормальной форме, которая в качество свободных предметных переиенных содержит только х„х„..., х„,у. Пусть Н-преднкатная переменная с л+1 пустыми местами, которая не встречается в 6, Мы образуем формулу: (11) ( Ех ) ... (Ех ) ((Еу) (6 (х„..., х„у) й й (х„..., х,у)) тд (а) Н (х„..., х„,а)).
Зта формула выводима в том случае, когда (1) выводима, и наооорот. В самом деле, если мы заменим в (11) Н через 6 по правилу аЗ), то получим: (Ех,)... (Ех,) ((Еу)(6 (х„..., х„, у) й 6 (х„..., х„у)) Ч (а) 6 (х„.. „т„, .-Я. После э~ого мы мо кем отбРосить часть, пРеоеставлающую ложное высказывание, т. е.о (Еу) (6 (х„..., х„у) й 6 (х„..., х„у)).
Вывод (П) на(!) несколько сложнее. Прежде всего, 1>а узкое ксоосзскис прсдакоп>оо Нсзооисимсмпь скмпсмм оксиом >!т путем перенменоваяия связанных переменных мы получаем из фарп>улы (3!): (у)(Е(у)- О(у))- ((у)РЫ ЫО(у)) По правилам исчисления высказываниИ формулу: лй — о (5 — ь Г) можно преобразовать в 5 — мЯ лс и. (правило Ч1!). В данная случае мы получаем: (у)ЕЫ- (Еу)(ЕЫйО(у)) Ъ'(у)ОЫ, если, кроме правила образованна противоположности, мы используем еще, что л — о 6 является сокращением для И лс' 5. В этой фориуле Р (у) заменяем на 5 (Х„., х„у'„а О (у) — на рр(х„...,х„.у).
Получаем: Ы 5(х„...,х„у)- (Еу)(5(х„,, х,у)бк й (х„, х„, у)) око (у) Е (»„..., х„, у), Применяя затем несколько раз пропило, сформулированное а конце доказательства формулы (34), получаем: (Ех,)... (Ехп) (у) 5(х„,хп,у)- (Ех,) ... (Ех„) ((Еу) (5 (х„... хп, у) В1 17(хь..., х„,уД 'ос (у) )1 ( " .."" у)1. Если учесть, что по предположению посылка (1; у>ко ныведена, то схема заключения и праввло переименования 3) дают формулу (! !). После этого мы приводим формулу (П) к предваренной нормальной форме.
Это иожно сделать так; приставку начинаем с(Ех,)... (Ех,) (Еу), ззгем ставим знаки общности н существовавия, содержащиеся в выражении 5(х„...,х„,у), не меняя их порядка следования, и в заключение-знак общности (з). Так как степень получающейся формулы на единицу ниже чем степень (1), то предложение о нормальной форме Сколема, таким образом, доказано. 4 З. Неирптивпречиоость н иеппписпмость системы пионом Метод арифметической интерпретации, с помощью кош>рога мы ранее установили непротиворечивость н независимость аксиом а) — б), дает нам возмшкность выясню:ь вопрос о лелросс>иворечивоссли, и ранее нынсненнам смыс>се, также н для всей системы аксиом исчисзснше предика>иош Для этой цели мы должны ааспрострзннть арнфие>нчсскую интерпретацию, которая была устгнанлена только для переменных высказываний, на неиспользованные еще знаки.
Это делается следующим образом. Мы действуем со знаками предикатов так же, как са знаками высказываний, рассматривая те и другие как арифметические переменные, которые могут принимать только значения О и !. При этом мы не обращаем внимания на то, как в знаках предикатов заполняются пустые места. Кванторы всюду отбрасываем. Связь '„' опять рассматриваем как арифметическое произведение; пад О понимаем 1, а под Гпонимаем О. При эгнх определенпях оказывается прежде всего, что все аксиомы, включая е) н 1), при таком арифметическом истолковании всегда имеют значение О. Если, далее, одна илн несколько формул имеют всегда значение О, та легко убедиться, что всякая другая формула, ньшеденная из данных по нашим правилам, также всегда имеет значение О.
С другой стороны, так как два выражения, из которых одна является отрицанием другого, не могут одновременно иметь значение О, то отсюда следует, что среди формул, касорые матус быть выведены нз наших аксиом, никакие две не могут находиться в отношении противоположности друг к другу. Таким образом, условие непротиворечи. ности выпалйено. Незти.ии кпсл системы сессии 1!З Узкое иеивснелие л!идикнтон Впрочем, значение результата этого доказательства непротиворечивости наших аксиом пе следует переоценивать. В самом целе, приведенное доссазагельство непротиворечивости солержателыю сводится к >К!пущению, чтп ппло>кенная в основу область инднннлуумов состоит только из одного ецннстаеннот! элемента и, значит, является конечной. Это отнюдь пе дает нам гарантии, что прн символическом введении содержательно бесспорных посылок система дпкпзуемых формул останется непротиворечивой.
Например, остается открытыи вопрос, не станет ли прн присоединении математических аксиом доказуемой в нашем исчислении всякая произвольная формула. Эта проблема, решение которой имеет центральное значение лля математики, по трудности не может даже сравниться с рассмотренным нами вопросом. Математические аксиомы как раз предполагают бесконечную область индивидуумов, а с понятием бескокечносю! связаны трудности и парадоксы, играющие роль з вопросах оснований математики. Чтобы иметь возможность с успехом взяться за разрешение этой проблемы, Гильберт счел даже необходимым создать особую теорию. Изложение этой теории, которая, конечна, использует результаты пател!атнческой логики, в ранках этой книги невозможно. По всем вопросам па ее счет мы отсылаеи к книге Гильберта и Бернайсач Но возвратимся к нашей системе аксиом.
Мы закажем теперь независимость аксиом этой сиса!Ьмы, показав, что при получении тождественных формул исчисления преяикатов нельзя отбросить пн одну из аксиом а) — 1) и ни одно из правил и1) — аЗ), б), у) 3,)*. с нньсгг В. и. Р Вегпауз, сгипп1ззеп аег мз1летзнк, 1, Бегин, 1934. з Цокззптельство пезззпекыостп была дз!т (уже после появление ! пзлзпля настоящей книги) Мзк-Кппзп. Ср. !. С. С. МсК(пзеу, Оп 1Ье !паерепаепее ог Нньег1 зпа Ае!сегтапп'з аз1и1з1ез1ог шесо(еи!из о! ргоронптпз11ипспапз Атег.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
