В 1931 г. 25-летний австрийский математик Венского университета Курт Гедель (позднее, после аншлюса, эмигрировавший в США) доказал теоремы, из которых следовало, что программа Гильберта невыполнима. Идеи Геделя оказали столь сильное влияние, что дальнейшее развитие логики шло уже под знаком тех выводов, которые были получены Геделем.
Аксиоматизируя какую-либо область знания, полагали, что систему аксиом удается подобрать так, что она будет полной. По Гильберту и Аккерману, полнота означает возможность выведения всех истинных формул определенной области знания из данной системы аксиом. Это широкий смысл. Более строгое понятие полноты пред-
__________________
1 С помощью теории доказательства «я хотел бы, – писал Гильберт, – окончательно разделаться с вопросами обоснования математики как таковыми...» (Гильберт Д. Основания геометрии. С. 365).
полагает, что присоединение к системе какой-либо невыводимой, «чужой» формулы обязательно приводит к противоречию1.
Но что значит «невыводимая» формула? Это формула (высказывание), недоказуемая в данной системе, то есть ее нельзя определить на истинность: ни подтвердить, ни опровергнуть. Такие образования мысли считаются неразрешимыми. Математики и логики, строя аксиоматические системы (Рассел и Уайтхед, Цермело, Френкель и др.), исходили из того, что аксиом и правил вывода системы достаточно для того, чтобы решить любой математический вопрос, который может быть формально выражен в соответствующих системах. Следовательно, аксиоматизированная арифметика полна или может быть пополнена добавлением конечного числа аксиом.
Гедель же как раз и доказал, что это не так, что все подобные построения, содержащие в качестве своей части формальную арифметику, неполны. Это значит, что в них всегда можно сформулировать проблему, построить предложение, которое нельзя ни доказать, ни опровергнуть. В частности, подобное предложение можно высказать в виде х, которое содержит утверждение о своей недоказуемости. Хотя такое предложение и является истинным, но доказать его невозможно. Отсюда вытекает, что система неполна. То есть при попытке провести полную формализацию всегда обнаруживается некий остаток, который не поддается формализации, свидетельством чему и является предложение х.
Однако можно поступить и так. Принять этот неподдающийся остаток в качестве аксиомы и пополнить им список аксиом нашей системы, сделав ее полной. Но тогда в этой новой системе найдется другое предложение х', которое, несмотря на истинность, также окажется неразрешимым, и т.д. Иначе говоря, система неполна и непополняема.
В своей первой теореме Гедель и резюмировал, что любая логистическая система, настолько богатая, чтобы содержать формализованную рекурсивную арифметику, либо противоречива, либо включает хотя и истинную, но неразрешимую формулу – такую, которая недоказуема сама и недоказуемо ее отрицание . Утверждая,
__________________
1 Гильберт Д., Аккерман В. Основы теоретической логики. С. 66.
2 Г. Вейль по этому поводу в шутку заметил: «Бог существует, поскольку математика несомненно непротиворечива. Но существует и дьявол, поскольку доказать ее непротиворечивость мы не можем».
что система либо неполна, либо противоречива, имеют в виду следующее. Систему можно сделать полной, но лишь включив в нее такую аксиому, на основе которой предложение будет и истинным и ложным.
Эта теорема и была названа теоремой о неполноте формализации (точнее, формализованной арифметики).
В чем же источник неполноты? Математические системы, включающие формальную арифметику, допускают, как мы уже отметили, возможность формулировать предложение о собственной недоказуемости. Здесь и возникает антиномия. Запишем предложение: