Принцесса или тигр?

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

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

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

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

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

Стр.168

машина никогда не напечатает число х*у, если х в действительности не принадлежит множеству Ау. Правильно я понял?

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

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

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

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