) невозможно, требуется обычно более критическое определение понятия «построение», чем для того, чтобы показать, например, что то или иное геометрическое построение с помощью циркуля и линейки действительно возможно. То же самое происходит и с доказуемостью: чтобы продемонстрировать, что данное утверждение недоказуемо в некоторой исходной системе аксиом, требуется гораздо более строгое и критическое определение самого понятия «доказательство», чем для получения соответствующего положительного результата, а именно что данное утверждение в самом деле является доказуемым при принятии той или иной аксиомы.
Загадка Гёделя
— Итак, — продолжал Фергюссон, — если задана некоторая система аксиом, то доказательство в данной системе представляет собой конечную последовательность высказываний, построенную по очень строгим правилам. При этом оказывается совсем несложно чисто механическим путем решить, является ли данная последовательность высказываний доказательством в этой системе или нет. Собственно говоря, совсем несложно даже придумать машину, которая может это делать. Гораздо труднее оказывается создать такую машину, которая могла бы решать, какие высказывания в данной системе аксиом доказуемы, а какие нет.
— Ответ, я полагаю, зависит от выбора исходной системы аксиом…
— Сейчас меня интересуют вопросы механического доказательства теорем, то есть вопросы создания таких машин, которые могли бы доказывать различные математические истины. Вот, например, мое последнее детище, — сказал Фергюссон, с гордостью указав на какое-то престранное сооружение.
Крейг и Мак-Каллох несколько минут разглядывали машину, пытаясь разгадать ее назначение.
— И что же она умеет? — спросил наконец Крейг.
— Она может доказывать различные утверждения, касающиеся положительных целых чисел, — ответил Фергюссон. — Я использую язык, в котором имеются имена для разных множеств чисел, — точнее, подмножеств положительных целых чисел. При этом существует бесконечно много таких числовых множеств, которые поддаются наименованию на этом языке. Например, у нас имеются специальные названия для множества четных чисел, для множества нечетных чисел, для множества простых чисел, для множества чисел, делящихся на 3, и т. д. — вообще, можно сказать, что практически любое множество чисел, которое могло бы представить интерес для специалиста по теории чисел, обладает своим именем на этом языке. И хотя сама совокупность числовых множеств, поддающихся описанию на этом языке, содержит бесконечно много элементов, она (по мощности.