Теорему Гёделя о неполноте до некоторой степени можно рассматривать как отрицание закона исключенного третьего. Каждое утверждение мы считаем либо истинным, либо ложным. В современных основаниях математики это означает, что рассматриваемое утверждение доказуемо или недоказуемо с помощью законов логики и аксиом того раздела математики, к которому относится интересующее нас утверждение. Гёдель же доказал, что некоторые утверждения нельзя ни доказать, ни опровергнуть. Следовательно, теорема Гёделя о неполноте в известной мере подкрепляет позиции интуиционистов, хотя те возражали против логических принципов совсем по другим причинам.

Непротиворечивость можно было бы считать доказанной, если бы в противовес подходу Гёделя в системе удалось обнаружить неразрешимое утверждение: ведь как мы уже установили, опираясь на свойства материальной импликации, если в системе имеется противоречие, то в ней можно доказать что угодно. Однако до сих пор обнаружить неразрешимое утверждение не удалось.

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

Гёдель опубликовал свои результаты в 1931 г., т.е. до выхода в свет первого (1934) и второго (1939) томов фундаментального труда Гильберта и Бернайса по основаниям математики [75]. В предисловии ко второму тому оба этих автора вынуждены были признать необходимость расширить используемые в метаматематике методы рассуждений. Гильберт и Бернайс включили в число допустимых методов трансфинитную индукцию. {140}Гильберт полагал, что новые принципы вполне могли бы быть интуитивно правильными и приемлемыми для всех. Он пытался развивать дальше это направление, но не пришел ни к каким новым результатам.

События, последовавшие за переломным 1931 г., еще более осложнили ситуацию и обрекли на неудачу любые попытки определить, что такое математика и какие результаты следует считать правильными. Мы упомянем лишь об одном таком событии, далеко не самом важном. Представителю гильбертовской школы Герхарду Генцену (1909-1945) удалось ослабить запреты на методы доказательства, допустимые в метаматематике Гильберта, в частности за счет использования трансфинитной индукции, и в 1936 г. он смог доказать непротиворечивость арифметики и отдельных разделов математического анализа.

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

Теорема Гёделя о неполноте породила ряд побочных проблем, о которых также следовало бы упомянуть. Поскольку в любой сколько-нибудь сложной области математики существуют утверждения, которые невозможно ни доказать, ни опровергнуть, возникает вопрос: можно ли определить, доказуемо или недоказуемо любое заданное утверждение? Этот вопрос известен под названием проблемы разрешимости.Решение ее требует эффективных методов (возможно, аналогичных тем, которые используются при расчетах на ЭВМ), позволяющих за конечное число шагов устанавливать доказуемость (истинность или ложность) утверждения или класса утверждений.

Поясним понятие разрешающей процедуры на нескольких простых примерах. Чтобы решить, делится ли одно целое число на другое, мы можем осуществить процесс деления. Если остаток от деления равен нулю, то это означает, что первое число на второе делится. Аналогичная процедура позволяет ответить на вопрос, делится ли один многочлен нацело на другой. Имеется также четкий алгоритм, позволяющий ответить на вопрос, существуют ли целые числа  xи y,удовлетворяющие уравнению ах + by = cс целыми a, bи c.

В своем докладе на II Международном математическом конгрессе в Париже Гильберт поставил очень интересную (десятую) проблему о разрешимости диофантовых уравнений, сформулировав ее так: можно ли указать способ, позволяющий за конечное число шагов установить, разрешимо ли диофантово уравнение в целых числах?(Класс уравнений ах + by = cсостоит из диофантовых уравнений, ибо каждый элемент класса представляет собой одно уравнение, связывающее два неизвестных, и решить его требуется в целых числах. Проблема Гильберта относится к гораздо более общему классу диофантовых уравнений.) Проблема разрешимости гораздо сложнее десятой проблемы Гильберта, но математики, работающие над ней, охотно ссылаются на десятую проблему Гильберта, так как уже одно то, что полученные при этом результаты связаны с решением указанной проблемы, придает им особую значимость.

Точный смысл понятию эффективной процедуры придал профессор Принстонского университета Алонсо Черч (р. 1903), который ввел определение рекурсивной,или, как еще говорят, вычислимой функции.Рассмотрим простой пример рекурсивности. Пусть, по определению

Тогда

Шаг за шагом мы можем вычислить все значения функции f(n).Такая функция f(x)называется рекурсивной. Введенное Черчем понятие рекурсивности равнозначно вычислимости, но отличается большей общностью.

В 1936 г. Черч, используя введенное им новое понятие рекурсивной функции, показал, что в общем случае разрешающая процедура (для узкого исчисления предикатов) невозможна: если задано конкретное утверждение, то не всегда можно найти алгоритм, позволяющий установить, доказуемо оно или опровержимо. В любом частном случае утверждение может оказаться доказуемым, но мы не располагаем критерием, который позволял бы заранее определять, доказуемо оно или недоказуемо. Математики могут годами напрасно терять время, безуспешно пытаясь доказать то, что вообще недоказуемо. Относительно десятой проблемы Гильберта Юрий Матиясевич в 1970 г. доказал, что не существует алгоритма, позволяющего установить, удовлетворяют ли какие-либо целые числа соответствующим диофантовым уравнениям или нет. {141}

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