Некоторые более глубокие математические соображения

Для того чтобы лучше разобраться в значении гёделевского доказательства, полезно будет вспомнить, с какой, собственно, целью оно было первоначально предпринято. На рубеже веков ученые, деятельность которых была связана с фундаментальны­ми математическими принципами, столкнулись с весьма серьез­ными проблемами. В конце XIX века — в значительной степени благодаря глубоко оригинальным математическим трудам Георга Кантора (с «диагональным доказательством» которого мы уже познакомились) — математики получили в распоряжение эф­фективные методы доказательства некоторых наиболее фундаментальных своих результатов, основанные на свойствах беско­нечных множеств. Однако с этими преимуществами оказались связаны и не менее фундаментальные трудности, проистекаю­щие из чересчур вольного обращения с концепцией бесконечно­го множества. Особо отметим парадокс Рассела (на который я вкратце ссылался в комментарии к Q9, см. также §3.4 — Кан­тор о нем также упоминает), обозначивший некоторые препят­ствия, подстерегающие склонных к опрометчивым умозаключе­ниям. Тем не менее, все понимали, что если вопрос о допустимо­сти тех или иных методов рассуждения продумать с достаточной тщательностью, то можно добиться очень и очень впечатляющих математических результатов. Проблема, по всей видимости, сво­дилась к отысканию способа, посредством которого можно было бы в каждом конкретном случае абсолютно точно определить, была ли соблюдена при выборе метода рассуждения «достаточ­ная тщательность».

Одной из главных фигур движения, поставившего перед со­бой цель достичь этой точности, был великий математик Давид Гильберт. Движение окрестили формализмом; в соответствии с его основополагающим принципом, следовало однозначно опре­делить все допустимые методы математического рассуждения в пределах той или иной конкретной области раз и навсегда, вклю­чая и те, что связаны с понятием бесконечного множества. Такая совокупность правил и математических утверждений называет­ся формальной системой. После того как определены правила формальной системы F, решение вопроса о корректности приме­нения этих правил — количество которых непременно является конечным — сводится к элементарной механической проверке. Разумеется, если мы хотим, чтобы любой выводимый с помощью таких правил результат мог считаться действительно истинным, нам придется присвоить им всем статус вполне допустимых и обоснованных форм математического рассуждения. Однако неко­торые из рассматриваемых правил могут подразумевать какие-либо манипуляции с бесконечными множествами, и в этом слу­чае математическая интуиция, подсказывающая нам, какие ме­тоды рассуждения допустимы, а какие нет, может оказаться и не достойной абсолютного доверия. Сомнения в этой связи как. нельзя более уместны, учитывая несоответствия, возникающие при столь вольном обращении с бесконечными множествами, что допустимым становится даже парадоксальное «множество всех множеств, не являющихся членами самих себя» Бертрана Рас­села. Правила системы F не должны допускать существования «множества» Рассела, но где же, в таком случае, следует про­вести границу? Вообще запретить применение бесконечных мно­жеств было бы слишком строгим ограничением (обычное евкли­дово пространство, например, содержит бесконечное множество точек, да и множество натуральных чисел является бесконеч­ным); кроме того, существуют же формальные системы, абсо­лютно в этом смысле удовлетворительные (поскольку в их рам­ках не допускается, к примеру, формулировать сущности, подоб­ные «множеству» Рассела), применяя которые можно получить большую часть необходимых математических результатов. Отку­да нам знать, каким из этих формальных систем можно верить, а каким нельзя?

Рассмотрим подробнее одну такую формальную систему F; для математических утверждений, которые можно получить с по­мощью правил системы F, введем обозначение ИСТИННЫЕ, а для утверждений, отрицания (т. е. утверждения, обратные рас­сматриваемым) которых выводятся из того же источника, — обо­значение ЛОЖНЫЕ. Любое утверждение, которое можно сфор­мулировать в рамках системы F, но которое не является в этом смысле ни истинным, ни ложным, будем полагать нераз­решимым. Кто-то, возможно, сочтет, что поскольку на деле может оказаться «бессмысленным» и само понятие бесконечного множества, то, по всей видимости, нельзя абсолютно осмысленно говорить ни об истинности, ни о ложности относящихся к ним утверждений. (Это мнение применимо, по крайней мере, к неко­торым разновидностям бесконечных множеств, если не ко всем.) Если придерживаться такой точки зрения, то нет особой разни­цы, какие именно утверждения о бесконечных множествах (неко­торых разновидностей) оказываются ИСТИННЫМИ, а какие — ЛОЖНЫМИ, лишь бы не вышло так, что одно утверждение по­лучится ИСТИННЫМ и ЛОЖНЫМ одновременно, т.е. система F должна все же быть непротиворечивой. Собственно говоря, в этом и состоит суть истинного формализма, а в отношении формальной системы F первостепенно важно знать лишь следующее: (а) является ли она непротиворечивой и (Ь) является ли она полной. Система F называется полной, если любое мате­матическое утверждение, должным образом сформулированное в рамках F, всегда оказывается либо истинным, либо ЛОЖНЫМ (т. е. НЕРАЗРЕШИМЫХ утверждений система F не содержит).

Для строгого формалиста вопрос о том, является ли то или иное утверждение о бесконечных множествах действительно истинным в сколько угодно абсолютном смысле, не обязательно имеет смысл и, уж конечно же, не имеет никакого существенно­го отношения к процедурам формалистской математики. Таким образом, поиски абсолютной математической истины в отноше­нии утверждений, связанных с упомянутыми бесконечными ве­личинами, заменяются стремлением продемонстрировать непро­тиворечивость и полноту соответствующих формальных систем. Какие же математические правила допустимо использовать для такой демонстрации? Достойные доверия, прежде всего, причем формулировка этих правил никоим образом не должна основы­ваться на сомнительных рассуждениях с привлечением слишком вольно определяемых бесконечных множеств (типа множества Рассела). Была надежда на то, что в рамках некоторых срав­нительно простых и очевидно обоснованных формальных систем (например, такой достаточно элементарной системы, как ариф­метика Пеано) отыщутся логические процедуры, которых будет достаточно для того, чтобы доказать непротиворечивость других, более сложных, формальных систем — скажем, системы F, — непротиворечивость которых уже не столь бесспорна и в рам­ках которых допускаются формальные рассуждения об очень «больших» бесконечных множествах. Если принять философию формалистов, то подобное доказательство непротиворечивости для F, как минимум, даст основание для использования мето­дов рассуждения, допустимых в рамках системы F. Затем можно доказывать математические теоремы, применяя концепцию бес­конечных множеств тем или иным непротиворечивым образом, а может, удастся и вовсе избавиться от необходимости отвечать на вопрос о реальном «смысле» таких множеств. Более того, если удастся показать, что система F является еще и полной, то мож­но будет вполне резонно счесть, что эта система действительно содержит абсолютно все допустимые математические процедуры; т. е. представляет собой, в некотором смысле, полное описание математического аппарата рассматриваемой области.

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

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

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

Наиболее известная форма теоремы Гёделя гласит, что фор­мальная система F (достаточно обширная) не может быть од­новременно полной и непротиворечивой. Это не совсем та зна­менитая «теорема о неполноте», которую Гёдель первоначаль­но представил на конференции в Кенигсберге (см. §§2.1 и 2.7), а ее несколько более сильный вариант, который был позднее получен американским логиком Дж. Баркли Россером(1936). По своей сути, первоначальный вариант теоремы Гёделя оказыва­ется эквивалентен утверждению, что система F не может быть одновременно полной и -непротиворечивой. Условие же -непротиворечивости несколько строже, нежели условие непроти­воречивости обыкновенной. Для объяснения его смысла нам по­требуется ввести некоторые новые обозначения. В систему обо­значений формальной системы F необходимо включить символы некоторых логических операций. Нам, в частности, потребуется символ, выражающий отрицание («не»); можно выбрать для этого символ «~». Таким образом, если Q есть некое высказы­вание, формулируемое в рамках F, то последовательность сим­волов ~ Q означает «не Q». Нужен также символ, означающий «для всех [натуральных чисел]» и называемый квантор общно­сти', он имеет вид «V». Если Р (п) есть некое высказывание, за­висящее от натурального числа п (т. е. Р представляет собой так называемую пропозициональную функцию), то строка симво­лов Vn [Р (п)] означает «для всех натуральных чисел п высказы­вание Р (п) справедливо». Например, если высказывание Р (п) имеет вид «число п можно выразить в виде суммы квадратов трех чисел», то запись Vn [Р (п)] означает «любое натуральное число является суммой квадратов трех чисел», — что, вообще говоря, ложно (хотя, если мы заменим «трех» на «четырех», то это же утверждение станет истинным). Такие символы можно записывать в самых различных сочетаниях; в частности, строка символов

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

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

Р(0),Р(1),Р(2),Р(3),Р(4),....

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

В дальнейшем утверждения «формальная система F явля­ется непротиворечивой» и «формальная система F является -непротиворечивой» я буду обозначать, соответственно, символа­ми «G (F)» и «П (F)». В сущности (если полагать систему F до­статочно обширной), сами утверждения (? (F) и П (F) формулиру­ются как операции этой системы. Согласно знаменитой теореме Гёделя о неполноте, утверждение G (F) не является теоремой системы F (т. е. его нельзя доказать с помощью процедур, допу­стимых в рамках системы F), не является теоремой и утвержде­ние fi (F) — если, разумеется, система F действительно непро­тиворечива. Несколько более строгий вариант теоремы Гёделя, сформулированный позднее Россером, гласит, что если система F непротиворечива, то утверждение ~ G (F) также не является те­оремой этой системы. В оставшейся части этой главы я буду фор­мулировать свои доводы не столько исходя из утверждения fi (F), сколько на основе более привычного нам G (F), хотя для большей части наших рассуждений в равной степени сгодится любое из них. (В некоторых наиболее явных аргументах главы 3 я буду иногда обозначать через «G(F)» конкретное утверждение «вы­числение Ck (k) не завершается» (см. §2.5); надеюсь, никто не сочтет это слишком большой вольностью с моей стороны.)

В большей части предлагаемых рассуждений я не стану проводить четкую границу между непротиворечивостью и -непротиворечивостью, однако тот вариант теоремы Гёделя, что представлен в § 2.5, по сути, гласит, что если формальная систе­ма F непротиворечива, то она не может быть полной, так как не может включать в себя в качестве теоремы утверждение G(F). Здесь я всего этого демонстрировать не буду (интересующиеся же могут обратиться к [222]). Вообще говоря, для того чтобы эту форму гёделевского доказательства можно было свести к дока­зательству в моей формулировке, система F должна содержать в себе нечто большее, нежели просто «арифметику и обыкно­венную логику». Необходимо, чтобы система F была обширной настолько, чтобы включать в себя действия любой машины Тью­ринга. Иначе говоря, среди утверждений, корректно формулиру­емых с помощью символов системы F, должны присутствовать утверждения типа: «Такая-то машина Тьюринга, оперируя над натуральным числом п, дает на выходе натуральное число р». Более того, имеется теорема (см. [222], главы 11 и 13), согласно которой так оно само собой и получается, если, помимо обыч­ных арифметических операций, система F содержит следующую операцию (так называемую /u-операцию, или операцию мини­мизации): «найти наименьшее натуральное число, обладающее таким-то арифметическим свойством». Вспомним, что в нашем первом вычислительном примере, (А), предложенная процедура действительно позволяла отыскать наименьшее число, не явля­ющееся суммой трех квадратов. То есть, вообще говоря, право на подобные вещи за вычислительными процедурами следует сохра­нить. С другой стороны, именно благодаря этой их особенности мы и сталкиваемся с вычислениями, которые принципиально не завершаются, — например, вычисление (В), где мы пытаемся отыскать наименьшее число, не являющееся суммой четырех квадратов, а такого числа в природе не существует.