Рэймонд Смаллиан - Принцесса или тигр

• Название: Принцесса или тигр
• Автор: Рэймонд Смаллиан
• Жанр: Математика

Задачи по логике

---

С другой стороны, особенно важно иметь точное определение доказательства тогда, когда нужно увидить, что данное математическое утверждение недоказуемо в той или иной системе аксиом. Данная ситуация очень похожа на положение дел с построением при помощи циркуля и линейки в евклидовой геометрии: там, для того чтобы показать, что некое построение (например, трисекция угла, квадратура круга или удвоение куба[6]) невозможно, требуется обычно более критическое определение понятия «построение», чем для того, чтобы показать, например, что то или иное геометрическое построение с помощью циркуля и линейки действительно возможно. То же самое происходит и с доказуемостью: чтобы продемонстрировать, что данное утверждение недоказуемо в некоторой исходной системе аксиом, требуется гораздо более строгое и критическое определение самого понятия «доказательство», чем для получения соответствующего положительного результата, а именно что данное утверждение в самом деле является доказуемым при принятии той или иной аксиомы.

Загадка Гёделя

— Итак, — продолжал Фергюссон, — если задана некоторая система аксиом, то доказательство в данной системе представляет собой конечную последовательность высказываний, построенную по очень строгим правилам. При этом оказывается совсем несложно чисто механическим путем решить, является ли данная последовательность высказываний доказательством в этой системе или нет. Собственно говоря, совсем несложно даже придумать машину, которая может это делать. Гораздо труднее оказывается создать такую машину, которая могла бы решать, какие высказывания в данной системе аксиом доказуемы, а какие нет.

— Ответ, я полагаю, зависит от выбора исходной системы аксиом…

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

Крейг и Мак-Каллох несколько минут разглядывали машину, пытаясь разгадать ее назначение.

— И что же она умеет? — спросил наконец Крейг.

— Она может доказывать различные утверждения, касающиеся положительных целых чисел, — ответил Фергюссон. — Я использую язык, в котором имеются имена для разных множеств чисел, — точнее, подмножеств положительных целых чисел. При этом существует бесконечно много таких числовых множеств, которые поддаются наименованию на этом языке. Например, у нас имеются специальные названия для множества четных чисел, для множества нечетных чисел, для множества простых чисел, для множества чисел, делящихся на 3, и т. д. — вообще, можно сказать, что практически любое множество чисел, которое могло бы представить интерес для специалиста по теории чисел, обладает своим именем на этом языке. И хотя сама совокупность числовых множеств, поддающихся описанию на этом языке, содержит бесконечно много элементов, она (по мощности. — Перев.) будет все же не больше, чем множество всех положительных чисел. С каждым положительным целым числом n оказывается связанным определенное множество чисел Аn, имеющее имя на нашем языке — это позволяет представить себе, что все именуемые множества расположены в виде последовательности А1, А2…., Аn… (Если хотите, можете вообразить себе, например, книгу с бесконечным числом страниц, причем для каждого целого положительного n на соответствующей n-й странице приведено описание того или иного множества положительных целых чисел. Тогда система An — это множество, описанное на n-й странице этой книги.)

Введем теперь математический символ Є, который означает «принадлежит» или «является членом». Для каждого числа х и произвольного числа у мы можем сформировать утверждение х Є Ау, которое означает, что х принадлежит множеству Ау. Это единственный вид утверждений, которые воспринимает моя машина. При этом задача машины состоит в том, чтобы определить, какие числа каким поддающимся описанию множествам принадлежат.

Далее, каждое утверждение х Є Ау имеет свой кодовый номер — число, которое, будучи записано в обычной десятичной системе счисления, состоит из цепочки единиц длиной х и следующей за ней цепочки нулей длиной у. Например, кодовый номер утверждения З Є А2 выглядит как 11100; кодовый номер утверждения 1 Є А5 имеет вид 100000. При этом кодовый номер утверждения х Є Ау, то есть число, состоящее из х единиц и следующих за ними у нулей, я буду обозначать символом х*у.

— Машина работает следующим образом, — продолжал Фергюссон. — Когда она обнаруживает, что число х принадлежит множеству Ау, то она отпечатывает число х*у, то есть кодовый номер утверждения х Є Ау. Если при этом машина печатает число х*у, то я говорю, что машина доказала утверждение х Є Ау. Кроме того, если машина способна напечатать число х*у, то я говорю, что утверждение х Є Ау доказуемо (с помощью моей машины).

Наконец, я знаю, что моя машина всегда точна — в том смысле, что каждое утверждение, которое можно доказать с ее помощью, является истинным.

— Минуточку, — вмешался Крейг. — Что значит «является истинным»? Какая разница между «является истинным» и «доказуемо»?

— Да это же совершенно разные вещи, — объяснил Фергюссон. — Я говорю, что утверждение х Є Ау истинно, если х действительно является элементом множества А у. Если же оказывается, что машина способна напечатать число х*у, тогда я говорю, что утверждение х Є А, доказуемо с помощью моей машины.

— Вот теперь ясно, — сказал Крейг. — Другими словами, утверждая, что ваша машина точна — или, иначе, что каждое утверждение, доказуемое с помощью машины, является истинным, — вы имеете в виду, что ваша машина никогда не напечатает число х*у, если х в действительности не принадлежит множеству Ау. Правильно я понял?

— Совершенно верно! — ответил Фергюссон.

— Скажите, а почему вы так уверены, что машина всегда точна? — спросил Крейг.

— Чтобы ответить на этот вопрос, я должен рассказать о ней более подробно, — ответил Фергюссон. — Дело в том, что машина работает на основе определенных аксиом относительно положительных целых чисел; эти аксиомы запрограммированы в машине в виде неких команд. Все эти аксиомы представляют собой хорошо известные математические истины. При этом машина не может доказать какое-либо утверждение, если оно не вытекает логически из этих аксиом. Но поскольку все аксиомы истинны, а любое логическое следствие из истинных утверждений тоже является истинным, то, стало быть, машина не способна доказать ложное утверждение. Если хотите, я могу перечислить эти аксиомы, и вы убедитесь сами, что машина действительно может доказывать только истинные утверждения.

— Сначала я хотел бы выяснить вот что, — сказал Мак-Каллох. — Допустим на некоторое время, что любое утверждение, доказуемое с помощью вашей машины, на самом деле является истинным. Значит ли это, что любое истинное утверждение вида х Є А, доказуемо с ее помощью? Иначе говоря, способна ли ваша машина доказывать все истинные утверждения типа х Є Ау или только некоторые из них?

— Это очень важный вопрос, — ответил Фергюссон, — но, увы, ответа на него я не знаю. В этом-то как раз и состоит главная проблема, которую я никак не могу разрешить! Уже не один месяц я пытаюсь найти ответ на этот вопрос, но пока безуспешно. Так, я совершенно точно знаю, что моя машина может доказать любое утверждение вида х Є Ау, которое является логическим следствием заложенных в нее аксиом, однако я не знаю, достаточное ли количество аксиом введено мною в машину. Аксиомы, о которых идет речь, представляют собой нечто вроде общей суммы сведений, известных математикам относительно системы положительных целых чисел; и все же, может быть, их недостаточно, чтобы строго установить, какие же числа х и к каким поддающимся описанию множествам Ау принадлежат. До сих пор любое утверждение вида х Є Ау, которое я считал истинным, исходя из чисто математических соображений, оказывалось логическим следствием заложенных в машину аксиом; при этом машина способна доказать любое взятое мною утверждение такого вида. Однако то, что я не сумел найти истинного утверждения, которое машина не могла бы доказать, вовсе не означает, что такого утверждения не существует — может быть, я его просто еще не обнаружил. В то же время вполне может оказаться, что машина действительно способна доказать все истинные утверждения — но этого я тоже еще не сумел доказать. Пока я просто не знаю, как это сделать!

Короче говоря, после этого Фергюссон подробно объяснил Крейгу и Мак-Каллоху, какие аксиомы заложены в машину и какие чисто логические правила позволяют доказывать новые утверждения на основании уже имеющихся. Все эти подробности вполне убедили Крейга и Мак-Каллоха в том, что машина на самом деле точна — что она действительно доказывает лишь истинные утверждения. Однако вопрос о том, может ли машина доказать все истинные утверждения или только некоторые из них, так и остался нерешенным. На протяжении нескольких последующих месяцев они часто собирались вместе для детального обсуждения возникших вопросов — пока, наконец, задача не была полностью решена.