Том 22. Сон разума. Математическая логика и ее парадоксы - [8]

* * *

В ПРОТИВОРЕЧИВОЙ СИСТЕМЕ АКСИОМ ЛЮБОЕ ВЫСКАЗЫВАНИЕ — ТЕОРЕМА

Допустим, что мы хотим доказать истинность высказывания Q. Так как система аксиом противоречива, существует теорема Р, отрицание которой, не-Р, также будет теоремой. Это означает, что можно найти доказательства Р и не-Р. Как мы уже говорили, когда речь шла о правилах вывода, заключение «Если Р и не-Р, то Q» является корректным, так как исходные посылки никогда не выполняются одновременно. Так как в противоречивой системе аксиом Р и не-Р — теоремы, объединив правило вывода «Если Р и не-Р, то Q» и доказательства Р и не-Р, с помощью modus ponens можно показать, что Q — теорема. Иными словами, сколь бы невероятным это ни казалось, в мире, где ноль равен единице и одновременно отличается от нее, вы — мой отец (даже если вы — женщина). Ex contradictione… — из противоречия следует все что угодно.

* * *

Чтобы объяснить понятие полноты, оставим в стороне научную фантастику и воспользуемся примером, который мне подсказало одно из произведений аргентинского писателя Гильермо Мартинеса. Представьте, что в закрытой комнате совершено убийство. Прибыв на место преступления, полиция обнаруживает рядом с трупом двух подозреваемых. Каждому из них известна вся правда о том, кто же убийца. Тем не менее если подозреваемые не признаются, полицейским придется начать поиски отпечатков пальцев, следов ДНК и любых других косвенных доказательств, которые позволят вынести обвинение. Если же эти поиски ни к чему не приведут, то подозреваемые будут выпущены на свободу.

Или: после тяжелого рабочего дня полицейские отправляются в бар, чтобы расслабиться. Один из них только что поступил на службу, и остальные едва знакомы с ним. Судя по тому, что он рассказывает сослуживцам, он родился в Саламанке, затем его семья сразу же переехала в Барселону, потому что его родители хотели жить у моря. При этом его коллеги не могут понять, женат он или нет. Нет сомнений в том, что на этот вопрос существует только один правильный ответ.

Из обеих ситуаций понятно, что довольно часто «истинное» не означает «доказуемое». Именно это имеют в виду логики, когда говорят о неполноте системы аксиом. В идеале все истинные утверждения о некоторых объектах можно доказать на основе нескольких аксиом. Но, как правило, теория содержит высказывания, которые нельзя ни доказать, ни опровергнуть, — такие высказывания называются неразрешимыми. Опровергнуть высказывание означает доказать его отрицание: например, опровергнуть высказывание «все лебеди белые», которое мы уже упоминали, означает доказать, что «существует лебедь не белого цвета». Полные теории — это теории, которые не содержат неразрешимых высказываний, или, что аналогично, это системы аксиом, в которых для произвольного высказывания можно доказать или это высказывание, или обратное ему. Внимательный читатель уже заметил, что во втором определении полноты расплывчатое понятие «истина» заменено понятием «доказательство». Так удалось разрешить некоторые из парадоксов, которые издавна волновали философов.

С большинством математических теорий дело обстоит так же, как в нашем первом примере: никто не может однозначно ответить, виновны подозреваемые или нет. Но не удивляйтесь, когда мы скажем, что всегда можно выбрать аксиомы так, чтобы теория была полной: для этого система аксиом должна содержать все истинные высказывания. В этом случае все доказательства будут выполняться в одну строчку, так как всё, что мы захотим доказать, уже будет аксиомой. Почему бы нам не поступить именно так, ведь полные теории — это настоящий рай для логиков?

Всё доказуемое будет совпадать с истинным, а доказательства будут максимально короткими. Однако множество всех возможных истинных высказываний слишком велико, чтобы его можно было выбрать в качестве множества аксиом. Нас интересует не столько длина доказательств, сколько возможность проверить их корректность каким-либо автоматическим методом. Так как в доказательстве каждое утверждение является либо аксиомой, либо выводится из предыдущих с помощью правил, чтобы узнать, доказывает ли перечень высказываний некоторую теорему, мы должны иметь возможность подтвердить, что некоторое высказывание является аксиомой. И если мы включим в систему слишком много аксиом, подобная проверка потребует бесконечно много времени.

Система аксиом называется рекурсивно перечислимой, когда подобного не происходит, то есть когда за конечное число шагов можно доказать, является ли произвольное утверждение аксиомой. Критерий рекурсивной перечислимости становится препятствием на пути «жадного» логика, который хочет доказать все больше и больше теорем, не позволяя добавить к системе все необходимые аксиомы. Разумеется, рекурсивно перечислимыми являются системы аксиом геометрии и арифметики, а также, в общем случае, все системы, содержащие конечное число аксиом. Также существуют рекурсивно перечислимые системы с бесконечным множеством аксиом, поскольку основной особенностью таких систем является не число аксиом, а то, что корректность любого доказательства, составленного на их основе, можно подтвердить за конечное число действий.