Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
Загадка Гёделя
— Итак,— продолжал Фергюссон,— если задана неко-_ торая система аксиом, то доказательство в данной системе представляет собой конечную последовательность высказываний, построенную по очень строгим правилам. При этом оказывается совсем несложно чисто механическим путем решить, является ли данная последовательность высказываний доказательством в этой системе или нет. Собственно говоря, совсем несложно даже придумать машину, которая может это делать. Гораздо труднее оказывается создать такую машину, которая могла бы решать, какие высказывания в данной системе аксиом доказуемы, а какие нет.
* То есть построение куба с объемом, вдвое большим, чем объем данного куба.— Прим. перев.
166
Ответ, я полагаю, зависит от выбора исходной системы аксиом...
Сейчас меня интересуют вопросы механического доказательства теорем, то есть вопросы создания таких машин, которые могли бы доказывать различные математические истины. Вот, например, мое последнее детище,— сказал Фергюссон, с гордостью указав на какое-то престранное сооружение.
Крейг и Мак-Каллох несколько минут разглядывали машину, пытаясь разгадать ее назначение.
— И что же она умеет?—спросил наконец Крейг.
— Она может доказывать различные утверждения, касающиеся положительных целых чисел,— ответил Фергюссон.— Я использую язык, в котором имеются имена для разных множеств чисел,—точнее, подмножеств положительных целых чисел. При этом существует бесконечно много таких числовых множеств, которые поддаются наименованию на этом языке. Например, у нас имеются специальные названия для множества четных чисел, для множества нечетных чисел, для множества простых чисел, для множества чисел, делящихся на 3, и т. д.— вообще, можно сказать, что практически любое множество чисел, которое могло бы представить интерес для специалиста по теории чисел, обладает своим именем на этом языке. И хотя сама совокупность числовых множеств, поддающихся описанию на этом языке, содержит бесконечно много элементов, она (по мощности.— Перев.) будет все же не больше, чем множество всех положительных чисел. С каждым положительным целым числом и оказывается связанным определенное множество чисел Ап, имеющее имя на нашем языке—это позволяет представить себе, что все именуемые множества расположены в виде последовательности А\, Аг,..., А„.......
(Если хотите, можете вообразить себе, например, книгу с бесконечным числом страниц, причем для каждого целого положительного п на соответствующей п-й странице приведено описание того или иного множества положительных целых чисел. Тогда система Ап—это множество, описанное на п-й странице этой книги.)
Введем теперь математический символ ?, который означает «принадлежит» или «является членом». .Для
167
каждого числа х и произвольного числа у мы можем сформировать утверждение х Е А у, которое означает, что х принадлежит множеству Ау. Это единственный вид утверждений, которые воспринимает моя машина. При этом задача машины состоит в том, чтобы определить, какие числа каким поддающимся описанию множествам принадлежат.
Далее, каждое утверждение хЕАу имеет свой кодовый номер — число, которое, будучи записано в обычной десятичной системе счисления, состоит из цепочки единиц длиной х и следующей за ней цепочки нулей длиной у. Например, кодовый номер утверждения ЗЕАг выглядит как 11100; кодовый номер утверждения 1ЕА5 имеет вид 100000. При этом кодовый номер утверждения хЕАу, то есть число, состоящее ИЗ X единиц и следующих за ними у нулей, я буду обозначать символом х*у.
— Машина работает следующим образом,— продолжал Фергюссон.— Когда она обнаруживает, что число х принадлежит множеству Ау, то она отпечатывает число х*у, то есть кодовый номер утверждения хЕАу. Если при этом машина печатает число х*у, то я говорю, что машина доказала утверждение хЕАу. Кроме того, если машина способна напечатать число х*у, то я говорю, что утверждение хЕАу доказуемо (с помощью моей машины).
Наконец, я знаю, что моя машина всегда точна—в том смысле, что каждое утверждение, которое можно доказать с ее помощью, является истинным.
— Минуточку,— вмешался Крейг.— Что значит «является истинным»? Какая разница между «является истинным» и «доказуемо»?
— Да это же совершенно разные вещи,— объяснил Фергюссон.—Я говорю, что утверждение ХЕАУ истинно, если х действительно является элементом множества А у. Если же оказывается, что машина способна напечатать число х*у, тогда я говорю, что утверждение хЕАу доказуемо с помощью моей машины.
— Вот теперь ясно,— сказал Крейг.—Другими словами, утверждая, что ваша машина точна — или, иначе, что каждое утверждение, доказуемое с помощью машины, является истинным,— вы имеете в виду, что ваша
168
машина никогда не напечатает число х*у, если х в действительности не принадлежит множеству А у. Правильно я понял?
— Совершенно верно!—ответил Фергюссон.
— Скажите, а почему вы так уверены, что машина
всегда точна?—спросил Крейг.
*
— Чтобы ответить на этот вопрос, я должен рассказать о ней более подробно,— ответил Фергюссон.— Дело в том, что машина работает на основе определенных аксиом относительно положительных целых чисел; эти аксиомы запрограммированы в машине в виде неких команд. Все эти аксиомы представляют собой хорошо известные математические истины. При этом машина не может доказать какое-либо утверждение, если оно не вытекает логически из этих аксиом. Но поскольку все аксиомы истинны, а любое логическое следствие из истинных утверждений тоже является истинным, то, стало быть, машина не способна доказать ложное утверждение. Если хотите, я могу перечислить эти аксиомы, и вы убедитесь сами, что машина действительно может доказывать только истинные утверждения.
