Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 53
Текст из файла (страница 53)
См. упоминание об этом в т. ! на с. )68 (скоска 3). к СИМВОЛ И ЛОГИЧЕСКИЯ ФОРМАЛИЗМ, [ГЛ. И! доказательство'), оказывается излишним. С другой стороны, в новом доказательстве требуется применять (при построении выделенного для числа 1 распределения истннностных значений) принцип «1егВшп поп да!пг» для целых чисел'). Поэтому и новое доказательство, несмотря на то, что принцип выбора в нем не применяется, тоже не является вполне финитным.
3 а м е ч а н и е 2. В рассуждении, с помощью которого мы из выполнимости конъюнкций и„, Ям 5м .. сделали вывод о совместной выполнимости формул Е„Е„6„..., а тем самым и о выполнимости формулы 5, никак не используется вид элементаРных фоРмУл $м $к, ..., входЯщих в формУлы В„, Эм Юк„... В нем идет речь лишь о присвоении этим элементарным формулам тех или иных истинностных значений. Поэтому в этом рассуждении указанные элементарные формулы можно заменить переменными для высказываний и тогда получится следующий, относящийся чисто к логике высказываний результат: Если формулы 6„6„6„...
построены из переменных для высказываний А„А„А,, ... с помощью связок логики высказываний и если для любого 1 формулы 6„..., 6! совместно вы6и, ° ° полнимы, то совместно выполнимы и все эти формулы 6, 6, 1 и Этому утверждению равносильно следующее: Если выполнимо 'каждое конечное подмножество данной последовательности формул, то и все формулы этой последовательности тоже являются совместно выполнимыми. Проведенное рассуждение может быть применено и к критериям опровержимости, которые мы сформулировали ') в общем виде для случая формулы 5 вида ЧЛЗуЗЯЕЗОм(х, у, г, и, о) йЛЛВу736(х, у, г).
Если мы, отказавшись от финнтного характера наших рассуждений, применим здесь контрапозицию и воспользуемся только что упомянутым рассмотрением, относящимся к исчислению высказываний, то у нас получится следующий результат: если формула 5 неопровержима, то для произвольных цифр 1, и ), и для любой тройки вычислимых арифметических функций !р„!р, и !ри (!р, и р,— одноместные, !рк — двуместная), образующих разделяющую систему функций, формула Ух1йи11 (х, !р,(х), !р,(х), и, !ри(х, и)) Ы1ЕЗ(!„)„г) выполнима; с другой стороны, если эта формула выполнима для ') См. с. 236.
т) См. т. 1, с, 62. в) См. с, 229 — 230, критерии 1 и 3. пгименение к пРОБлеме РАЗРешимости произвольных цифр В и 1, и для любой тройки вычислимых функций ~рм !р, и ри указанного типа, то формула 5 неопровержима. Кроме того, в силу теоремы о полноте в обоих этих утверждениях можно вместо неопровержимости формул говорить о их выполнимости. Разумеется, во всех этих рассуждениях границы финитных рассмотрений оказались нарушенными, в) Учет требований финитной точки зрения. Геделевская теорема о полноте значительно упрощает постановку задач, связанных с проблемой разрешимости, потому что на первый взгляд не связанные друг с другом вопросы выводимости (соответственно опровержимости) и выполнимости формул исчисления предикатов оказываются тесно связанными в том смысле, что установление выполнимости какой-либо формулы равносильно установлению ее неопровержимости, т.
е. невыводимостя ее отрицания, а установление общезначимости формулы — установлению ее выводимости. К этому добавляется е!це и равносильность выполнимости вообще выполнимости в области натуральных чисел. Эти прозрачные по своему характеру результаты относятся к понятиям теоретико-множественной логики предикатов, и мы не можем перенести их в сферу финитного обсуждения проблемы разрешимости уже по той простой причине, что понятие выполнимости в том виде, как оно было нами определено, непригодно для рассмотрения с финитной точки зрения. В самом деле, истинностное значение логической функции для заданной системы значений аргументов, вообще говоря, не является чем-то финитно заданным, так как в определении этой логической функции могут, например, участвовать кванторы всеобщности и существования.
Что же касается этих кванторов, то хотя их и можно, как известно!), интерпретировать финнтно, но при этой интерпретации отсутствует альтернатива между истинностью и ложностью всеобщих и экзистенциальных высказываний. Кроме того, термин <модельм в финитном смысле слова может относиться только к какому-либо наглядным образом заданному виду объектов, а ие к произвольной чисто гипотетической индивидной области. И все же существует возможность усилить понятие выполнимости до финитного понятия эффективной выполнимости.
Для этого необходимо: 1) выполнимость с самого начала определять как выполнимость в области цифр, 2) от определений логических функций требовать, чтобы они давали способ фактического вычисления исгиниостных значений этих функций при заданных значениях аргументов и 3) применять финитную интерпретацию кванторов. т) См. т. 1, с. 59. 246 Е-СИМВОЛ И ЛОГИЧГСКИИ ФОРМАЛИЗМ 1ГЛ и1 пРименение к пРОБлеме РАЗРешимости Таким образом мы получим определение эффективной выполнимости по меньшей мере для всех тех формул исчисления предикатов, у которых кваиторы не встречаются ни под знаком отрицания, ни в посылке какой-либо импликации и нн в одном из членов какой-либо эквивалентности; этим условиям удовлетворяют, в частности, предваренные формулы и их конъюнкции.
Формулу указанного вида мы будем называть эффективно выполи имой в области цифр, если вместо ее свободных индивидных переменных можно подставить такие цифры, вместо формульиых переменных без аргументов — такие истинностные значения, а вместо формульиых переменных с аргументами — такие вычислимым образом определенные логические функции, что эта формула примет значение <истина» (при вычислении этого значения, естественно, используются истинностные значения элементарных формул, истолкование связок исчисления высказываний как истинностиых функций и такое понимание кванторов, при котором формула Уу2((у) принимает значение «истнна» в том случае, если имеется эффективный способ, позволяющий доказать, что для каждой конкретно предъявленной цифры 1 формула Й(1) принимает значение «истина», а формула Э~Я(~) принимает значение «истина» тогда, когда имеется эффективный способ, позволяющий указать некоторую цифру й для которой 2((1) принимает значение «истина»).
Конечна, это понятие эффективной выполнимости ни в коей мере не является удовлетворительным эквивалентом обычного понятия выполнимости, так как для формул тех типов, к которым применимо понятие эффективной выполнимости, мы не в состоянии доказать, что их эффективная выполнимость совпадает с неопровержимостью. Правда, с помощью нашего критерия 2» удается показать '), что каждая эффективно выполнимая формула неопровержима. Поясним сказанное на примере формулы вида 1(2ь.. Ргее-"«1)ь =)1)еш(еь ° °, ее, 1рь ..., 1)е, аь ..., а„), где уь ..., хе, 1)ь ..., Ве — полныи список связанных, а ..., а„— полный список свободных индивидных переменных этой формулы. Для простоты мы будем считать, что она не содержит формульных переменных без аргументов.
Для формулы такого рода эффективная выполнимость означает, что переменные аь ... ..., ар могут быть заменены такими цифрами шь ..., шр, а формульные переменные — такими определенными на цифрах вычислимыми логическими функциями, что для каждого Г-членного е) См. с. 225. набора цифр иь ..., п, можно указать такой з-члеиный набор 1ь ..., 1«, что формула 5(пь ..., п„1ь ..., 1,, шь ..., ш„) с учетом истииностиых значений элементарных формул и пони. мания связок исчисления высказываний как истиииостиых функций принимает значение «истина». Но с помощью такой системы логических функций, продвигаясь сколь угодно далеко в послед в овательности занумерованных Г-члеиных наборов цифр В, 1, ..., и,; (1=0, 1, ...), можно для каждого из них указать такой набор (с( ° 1«,1 что формулы 8(пь1 ''' п,1 (ь! ''' 1«,1 Ш1 '' Щр) до любого, сколь угодно далекого места будут совместно выполнимыми (в элементарном смысле этого слова, который имеется в виду в наших критериях опровержимости и неопровержимости).
Поэтому, согласно критерию 2*, рассматриваемая формула неопровержима. Н вообще, отсюда получается, что любая эффективно выполнимая предваренная формула, а также любая эффективно выполнимая конъюнкция предваренных формул являются неопровержимыми. Н, однако, не в состоянии доказать, что всякая неопроо мы, Чело вержимая предваренная формула эффективно выполнима. Д здесь ие только в том, что к такому доказательству, т. е.
к финитному усилению геделевского доказательства полноты, у иас иет никакого подхода, но и в том, что, вообще говоря„в случае произвольной неопровержимой предварениой формулы может ие быть никакой модели с вычяслимыми логическими функциями. Но мы можем найти другой финитиый вариант для имеющей с теоретико-множественной точки зрения место равносильности неопровержимости и выполнимости; в самом деле, подобного рода равносильность обнаруживается в наших критериях опровержимости и неопровержимости. Геделевская теорема о полноте получается применением критерия Зе'). В этом критерии формулируется, так сказать, финитная часть теоремы Геделя.
С другой стороны„теорему о том, что всякая эффективно выполнимая формула является неопровержимой (она, как мы только установили, является следствием критерия 2"), можно рассматривать как финитную часть теоремы е) См. с. 225. а СИМВОЛ И ЛОГИЧЕСКИЕ аОРМАЛИЗМ !гл ги ПРИМЕНЕНИЕ К ПРОБЛЕМЕ РАЗРЕШИМОСТИ о неопровержимости любой выполнимой формулы, которая представляет собой обращение гегелевской теоремы о полноте.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
