2.8. Условие -непротиворечивости 151

удастся показать, что система F является еще и полной, то можно будет вполне резонно счесть, что эта система действительно содержит абсолютно все допустимые математические процедуры, т. е. представляет собой, в некотором смысле, полное описание математического аппарата рассматриваемой области.

Однако в 1930 году (публикация состоялась в 1931) Гёдель взорвал свою "бомбу", раз и навсегда показав, что идеал формалистов принципиально недостижим. Он продемонстрировал, что не может существовать формальной системы F, которая была бы одновременно и непротиворечивой (в некоем "сильном" смысле, который мы рассмотрим в следующем разделе), и полной, - при условии, что F считается достаточно мощной, чтобы сочетать в себе формулировки утверждений обычной арифметики и стандартную логику. Таким образом, теорема Гёделя справедлива для таких систем F, в рамках которых арифметические утверждения типа теоремы Лагранжа и гипотезы Гольдбаха (см. §2.3) формулируются как утверждения математические.

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

2.8. Условие -непротиворечивости

Наиболее известная форма теоремы Гёделя гласит, что формальная система F (достаточно обширная) не может быть одновременно полной и непротиворечивой. Это не совсем та знаменитая "теорема о неполноте", которую Гёдель первоначально представил на конференции в Кенигсберге (см. §§2.1 и 2.7), а ее несколько более сильный вариант, который был позднее получен американским логиком Дж. Баркли Россером (1936). По своей сути, первоначальный вариант теоремы Гёделя оказывается эквивалентен утверждению, что система F не может быть

152 Глава 2

одновременно полной и -непротиворечивой. Условие же -непротиворечивости несколько строже, нежели условие непротиворечивости обыкновенной. Для объяснения его смысла нам потребуется ввести некоторые новые обозначения. В систему обозначений формальной системы F необходимо включить символы некоторых логических операций. Нам, в частности, потребуется символ, выражающий отрицание ("не"); можно выбрать для этого символ "~". Таким образом, если Q есть некое высказывание, формулируемое в рамках F, то последовательность символов ~ Q означает "не Q". Нужен также символ, означающий "для всех [натуральных чисел]" и называемый квантор общности', он имеет вид . Если Р (п) есть некое высказывание, зависящее от натурального числа п (т. е. Р представляет собой так называемую пропозициональную функцию), то строка символов означает "для всех натуральных чисел п высказывание Р (п) справедливо". Например, если высказывание Р (п) имеет вид "число п можно выразить в виде суммы квадратов трех чисел", то запись означает "любое натуральное число является суммой квадратов трех чисел", - что, вообще говоря, ложно (хотя, если мы заменим "трех" на "четырех", то это же утверждение станет истинным). Такие символы можно записывать в самых различных сочетаниях; в частности, строка символов

выражает отрицание того, что высказывание Р (п) справедливо для всех натуральных чисел п.

Условие же -непротиворечивости гласит, что если высказывание можно доказать с помощью методов формальной системы F, то это еще не означает, что в рамках этой самой системы непременно доказуемы все утверждения

Отсюда следует, что если формальная система F не является ш-непротиворечивой, мы оказываемся в аномальной ситуации, когда для некоторого Р оказывается доказуемой истинность всех высказываний Р(0), Р(1), Р(2), Р(3), Р(4), ...; и одновременно с этим можно доказать и то, что не все эти высказывания истинны! Безусловно, ни одна заслуживающая доверия формальная система подобного безобразия допустить не может. Поэтому