Teopeмa Гёделя
Шрифт:
А вот такая же таблица для второй аксиомы:
p q pq р(рq)
K 1 K 1 K 1 K 1
K 1 K 2 K 1 K 1
K 2 K 1 K 1 K 1
K 2 K 2 K 2 K 1
В
Докажем теперь, что свойство «быть тавтологией» наследственно относительно применений правила modus ponens. (Доказательство его наследственности относительно правила подстановки предоставляется читателю.) Пусть формулы S1 и S1 S2 — тавтологии; нам надо доказать, что тогда и формула S2 есть тавтология. Допустим, что S2 не является тавтологией. В таком случае для хотя бы одного распределения элементарных компонент этой формулы по классам K1 и K2 она принадлежит классу K2. Но, по предположению, S1 является тавтологией, т. е. принадлежит классу Ki при любых распределениях своих элементарных компонент, в том числе и при том, при котором S2 принадлежит K2 [7] . Но тогда при этом распределении формула S1 S2 должна (в силу второго условия) принадлежать классу K2, что, однако, противоречит предположению о тавтологичности S1 S2. Противоречие показывает, что S2 должна быть тавтологией. Таким образом, тавтологичность формулы есть свойство наследственное, т. е. передаваемое от посылок правила modus ponens к его заключению.
7
Причем сказанное верно безотносительно к тому, входит ли в формулы S1 и S2 хоть одна общая переменная. — Прим. перев.
Теперь нам остается указать пример формулы нашего исчисления, не являющейся тавтологией. Такова, например, формула «p q», принадлежащая классу K2, если обе ее компоненты («p» и «q») принадлежат этому классу [8] . (В переводе на содержательный язык: высказывание «„p“ или q“» ложно, если ложны оба входящие в его состав высказывания «p» и «q».)
8
Конечно, еще более простой пример — формула, состоящая из одной-единственной переменной p. — Прим. перев.
Наша цель достигнута. Мы нашли формулу, не являющуюся теоремой нашей системы. Но в случае противоречивости выбранной нами системы аксиом такой формулы в нашем исчислении не нашлось бы. Таким образом, из аксиом исчисления высказываний нельзя вывести никакой формулы одновременно с ее отрицанием. Этим и завершается абсолютное доказательство непротиворечивости исчисления высказываний.
Легко видеть, что классы K1 и K2 можно понимать соответственно как класс истинных и класс ложных высказываний. Мы, однако, намеренно воздерживались от этой терминологии в ходе самого доказательства (хотя не раз, комментируя отдельные ее шаги, подразумевали возможность ее использования),
В заключение следует сказать еще об одной важной проблеме, относящейся к исчислению высказываний. Мы установили, что каждая теорема этого исчисления является тавтологией, т. е. — если выражаться в терминах неоднократно упоминаемой выше содержательной интерпретации — логической истиной, «законом логики». Естественно задать в известной мере и обратный вопрос: каждое ли логически истинное высказывание, выразимое на языке нашего исчисления (т. е. каждая ли тавтология), является теоремой данного исчисления (выводимой из его аксиом)? И на этот вопрос можно дать положительный ответ; но доказательство такого факта слишком длинно, чтобы приводить его здесь. Но нам хотелось бы обратить внимание на одно обстоятельство, не имеющее отношения к самому доказательству: дело в том, что результат этот свидетельствует о достаточности выбранных нами аксиом для получения всех тавтологичных формул — иными словами, всех логически истинных высказываний, выразимых на языке исчисления высказываний. Системы аксиом, обладающие таким свойством, принято называть «полными».
Вопрос о полноте той или иной системы аксиом представляет, как правило, большой интерес. В самом деле, основным стимулом для аксиоматизации различных разделов математики бывает стремление найти подходящий перечень исходных допущений, из которых затем можно было бы вывести все истинные предложения данной области. Скажем, когда Евклид формулировал некоторую аксиоматизацию элементарной геометрии, он старался отобрать аксиомы таким образом, чтобы из них можно было вывести все истинные геометрические утверждения, не только уже известные в то время, но в принципе и любые другие, которые можно было бы научиться доказывать когда-либо в будущем.
Помимо прочего, Евклид обнаружил поразительную проницательность своей трактовкой знаменитой аксиомы параллельности как допущения, логически не зависящего от остальных аксиом предложенной им системы. Лишь спустя много времени удалось доказать, что эта аксиома действительно не может быть выведена из остальных аксиом Евклида, т. е. что без аксиомы параллельности эта система аксиом неполна.
До недавнего времени считалось более или менее само собой разумеющимся, что для каждой конкретной области математики можно подобрать полную систему аксиом. В частности, математики были убеждены, что система аксиом, предложенная для аксиоматизации арифметики натуральных чисел, полна или во всяком случае может быть пополнена (сделана полной) добавлением к исходному перечню еще конечного списка аксиом. Одним из величайших открытий Гёделя и было как раз обнаружение невозможности такой полной аксиоматизации арифметики.
6
Идея кодирования и ее использование в математике
Исчисление высказываний представляет собой пример математической системы, по отношению к которой задачи, выдвигаемые гильбертовской теорией доказательства, оказались, как мы видели, полностью реализованными. Конечно, это исчисление формализует лишь некоторый фрагмент формальной логики, язык и дедуктивный аппарат которого недостаточны даже для формального построения элементарной арифметики. Но возможности гильбертовской программы отнюдь не ограничиваются доказательством непротиворечивости исчисления высказываний. Можно привести примеры гораздо более богатых теорий, для которых оказалось возможным дать строго метаматематические доказательства непротиворечивости и полноты. Примером может служить арифметическая система с операцией сложения (но без операции умножения) натуральных чисел, для которой также можно провести абсолютное доказательство непротиворечивости. Но достаточно ли сильны финитные методы Гильберта для установления непротиворечивости систем вроде Principia — систем, выразительные и логические средства которых позволяют построить всю арифметику, а не только отдельные ее фрагменты? Неоднократные попытки найти такое доказательство успехом не увенчались, а работа Гёделя 1931 г. показала, что они и не могли быть успешными, так как, строго придерживаясь границ, предначертанных в исходной формулировке гильбертовской программы, эту задачу вообще решить нельзя.
Что же, собственно, доказал Гёдель и как именно доказал? В работе Гёделя имеются два основных результата. Прежде всего (мы здесь не имеем в виду тот порядок, в каком эти результаты излагаются в самой работе Гёделя) он доказывает невозможность метаматематического доказательства непротиворечивости любой системы, достаточно обширной, чтобы включать в себя всю арифметику, которое (доказательство) не использовало бы каких-либо существенно иных правил вывода, кроме тех, что используются для вывода теорем в самой рассматриваемой системе. Конечно, и такое (пользующееся более сильными в некотором смысле правилами вывода) доказательство может быть очень важным и полезным. Но все же если доказательство строится на основе правил вывода, значительно более мощных, нежели логические средства арифметического исчисления, так что уверенность в непротиворечивости используемых в доказательстве допущений будет ничуть не больше, чем расчеты на непротиворечивость арифметики, то ценность такого доказательства будет довольно-таки специфической: мы убьем одно чудовище ценой рождения другого. Во всяком случае, если это доказательство будет не финитистским, то основной пункт гильбертовской программы останется, конечно, невыполненным. Гёделевское рассуждение как раз и показывает всю беспочвенность расчетов на нахождение финитистского доказательства непротиворечивости арифметики.