Формальные системы и алгоритмическое доказательство

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

Напротив, располагая некоторой заданной вычислитель­ной процедурой Е, предназначенной для установления истинно­сти определенных математических утверждений, мы можем по­строить формальную систему Е, которая эффективно выражает как ИСТИННЫЕ все те истины, что можно получить с помощью процедуры Е. Имеется, впрочем, и небольшая оговорка: как пра­вило, формальная система должна содержать стандартные логические операции, однако заданная процедура Е может оказаться недостаточно обширной, чтобы непосредственно включить и их. Если сама заданная процедура Е не содержит этих элементарных логических операций, то при построении системы Е уместно будет присоединить их к Е с тем, чтобы ИСТИННЫМИ положениями системы Е оказались не только утверждения, получаемые непо­средственно из процедуры Е, но и утверждения, являющиеся эле­ментарными логическими следствиями утверждений, получаемых непосредственно из Е. При таком построении система Е не будет строго эквивалентна процедуре Е, но вместо этого приобретет несколько большую мощность.

(Среди таких логических операций могут, к примеру, ока­заться следующие: «если Р&Q, то Р»; «если Р и Р => Q, то Q»; «если , то Р(п)»; «если , то » и т. п. Символы «&», «=>», «», «», «~» означают здесь, соот­ветственно, «и», «следует», «для всех [натуральных чисел]», «су­ществует [натуральное число]», «не»; в этот ряд можно включить и некоторые другие аналогичные символы.)

Поставив перед собой задачу построить на основе проце­дуры Е формальную систему Е, мы можем начать с некоторой в высшей степени фундаментальной (и, со всей очевидностью, непротиворечивой) формальной системы L, в рамках которой выражаются лишь вышеупомянутые простейшие правила логи­ческого вывода, — например, с так называемого исчисления предикатов (см. [222]), которое только на это и способно, — и построить систему Е посредством присоединения к системе L процедуры Е в виде дополнительных аксиом и правил процедуры для L, переведя тем самым всякое высказывание Р, получае­мое из процедуры Е, в разряд ИСТИННЫХ. Это, впрочем, вовсе не обязательно окажется легко достижимым на практике. Если процедура Е задается всего лишь в виде спецификации машины Тьюринга, то нам, возможно, придется присоединить к систе­ме L (как часть ее алфавита и правил процедуры) все необхо­димые обозначения и операции машины Тьюринга, прежде чем мы сможем присоединить саму процедуру Е в качестве, по су­ти, дополнительной аксиомы. (См. окончание §2.8; подробности в [222].)

Собственно говоря, в нашем случае не имеет большого зна­чения, содержит ли система Е, которую мы таким образом стро­им, ИСТИННЫЕ предположения, отличные от тех, что можно получить непосредственно из процедуры Е (да и примитивные логические правила системы L вовсе не обязательно должны яв­ляться частью заданной процедуры Е). В § 2.5 мы рассматривали гипотетический алгоритм А, который по определению включал в себя все процедуры (известные или познаваемые), которыми располагают математики для установления факта незавершаемости вычислений. Любому подобному алгоритму неизбежно при­дется, помимо всего прочего, включать в себя и все основные операции простого логического вывода. Поэтому в дальнейшем я буду подразумевать, что все эти вещи в алгоритме А изначально присутствуют.

Следовательно, как процедуры для установления математи­ческих истин, алгоритмы (т. е. вычислительные процессы) и фор­мальные системы для нужд моего доказательства, в сущности, эквивалентны. Таким образом, несмотря на то, что представ­ленное в §2.5 доказательство было сформулировано исключи­тельно для вычислений, оно сгодится и для общих формальных систем. В том доказательстве, если помните, речь шла о сово­купности всех вычислениях (действий машины Тьюринга) C_q (п). Следовательно, для того чтобы оно оказалось во всех отношени­ях применимо к формальной системе F, эта система должна быть достаточно обширной для того, чтобы включать в себя действия всех машин Тьюринга. Алгоритмическую процедуру А, предна­значенную для установления факта незавершаемости некоторых вычислений, мы можем теперь добавить к правилам системы F с тем, чтобы вычисления, предположения о незавершающемся характере которых устанавливаются в рамках F как ИСТИННЫЕ, были бы тождественны всем тем вычислениям, незавершаемость которых определяется с помощью процедуры А.

Как же первоначальное кенигсбергское доказательство Гёде-ля связано с тем, что я представил в § 2.5? Не будем углубляться в детали, укажем лишь на наиболее существенные моменты. В роли формальной системы F из исходной теоремы Гёделя выступает наша алгоритмическая процедура А:

алгоритм А < —> правила системы F.

Роль же представленного Гёделем в Кенигсберге предположения G (F), которое в действительности утверждает непротиворе­чивость системы F, играет полученное в §2.5 конкретное пред­положение «вычисление Ck (k) не завершается», недоказуемое посредством процедуры А, но интуитивно представляющееся ис­тинным, коль скоро процедуру A мы полагаем обоснованной:

утверждение «вычисление Ck (k) не завершается» <—> утверждение «система F непротиворечива».

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

не все предположения Р (0), Р (1), Р (2), Р(3), Р (4),... могут быть ИСТИННЫМИ, если утверждение «предположение Р (п) справедливо для всех натуральных чисел п» ЛОЖНО, что в точности совпадает с условием -непротиворечивости.

Однако убежденность в w-непротиворечивости формальной системы F может происходить не только из убежденности в об­основанности этой системы, но и из убежденности в ее обыкно­венной непротиворечивости. Поскольку если под «истинным» понимать «истинное», а под «ЛОЖНЫМ» — «ложное», то, несо­мненно, выполняется следующее условие:

ни одно предположение Р не может быть одновременно и ИСТИННЫМ, и ЛОЖНЫМ,

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

Сущность гёделевского доказательства в нашем случае со­стоит в том, что оно показывает, как выйти за рамки любого заданного набора вычислительных правил, полагаемых обосно­ванными, и получить некое дополнительное правило, в исходном наборе отсутствующее, которое также должно полагать обосно­ванным, — т. е. правило, утверждающее непротиворечивость исходных правил. Важно уяснить следующий существенный мо­мент:

убежденность в обоснованности равносильна убежденности в непротиворечивости.

Мы имеем право применять правила формальной системы F и полагать, что выводимые из нее результаты действительно ис­тинны, только в том случае, если мы также полагаем, что эта формальная система непротиворечива. (Например, если бы си­стема F не была непротиворечивой, то мы могли бы вывести, как ИСТИННОЕ, утверждение «1 = 2», которое истинным, разу­меется, не является!) Таким образом, если мы уверены, что при­менение правил некоторой формальной системы F действительно эквивалентно математическому рассуждению, то следует быть готовым принять и рассуждение, выходящее за рамки системы F, какой бы эта система F ни была.

2.10. Возможные формальные возражения против (продолжение)

Продолжим рассмотрение различных математических воз­ражений, высказываемых время от времени в отношении моей трактовки доказательства Гёделя—Тьюринга. Многие из них тес­но связаны друг с другом, однако я полагаю, что в любом случае их будет полезно разъяснить по отдельности.

Q10. Абсолютна ли математическая истина? Как мы уже видели, существуют различные мнения относительно абсолютной истинности утверждений о» бесконечных множествах. Можем ли мы доверять доказательствам, опирающимся на какую-то рас­плывчатую концепцию «математической истины», а не на, скажем, четко определенное понятие формальной ИСТИНЫ?

Что касается формальной системы F, описывающей общую теорию множеств, то, действительно, не всегда ясно, можно ли вообще говорить о каком-то абсолютном смысле, в котором то или иное утверждение о множествах является либо «истинным», либо «ложным», — вследствие чего под сомнение может попасть и само понятие «обоснованности» формальной системы, подоб­ной F. В качестве поясняющего примера приведем один извест­ный результат, полученный Гёделем (1940) и Коэном (J 966). Они показали, что определенные математические утверждения (так называемые континуум-гипотеза Кантора и аксиома выбо­ра) никак не зависят от теоретике-множественных аксиом си­стемы Цермело--Френкеля — стандартной формальной систе­мы, обозначаемой здесь через ZF. (Аксиома выбора гласит, что для любой совокупности непустых множеств существует еще од­но множество, которое содержит ровно один элемент из каждо­го множества совокупности^. Согласно же континуум-гипотезе Кантора, количество подмножеств натуральных чисел — рав­ное количеству вещественных чисел — представляет собой вторую по величине бесконечность после множества собствен­но натуральных чисел^. Читателю нет нужды вникать в скры­тый смысл этих утверждений прямо сейчас. Равно как нет ну­жды и мне углубляться в подробное изложение аксиом и пра­вил процедуры системы ZF.) Некоторые математики убеждены в том, что система ZF охватывает все методы математического рассуждения, необходимые для обычной математики. Некоторые даже утверждают, будто приемлемым математическим доказа­тельством можно считать только такое доказательство, какое можно, в принципе, сформулировать и доказать в рамках систе­мы ZF. (См. комментарий к возражению Q14, где дается оценка применимости к таким субъектам гёделевского доказательства.) Иными словами, эти математики настаивают на том, что ИСТИННЫМИ, ЛОЖНЫМИ и НЕРАЗРЕШИМЫМИ в рамках систе­мы ZF математическими утверждениями можно считать только те утверждения, истинность, ложность и неразрешимость, соответ­ственно, которых, в принципе, устанавливается математически­ми средствами. Для таких людей аксиома выбора и континуум-гипотеза являются математически неразрешимыми (что, по их мнению, и доказывается выводом Гёделя—Коэна), и они наверня­ка будут утверждать, что истинность или ложность этих двух ма­тематических утверждений суть предметы достаточно условные. Влияют ли эти кажущиеся неопределенности в отношении абсолютного характера математической истины на выводы, ко­торые мы сделали из доказательства Гёделя—Тьюринга? Никоим образом, так как мы имеем здесь дело с классом математиче­ских проблем гораздо более ограниченной природы, нежели те, что, подобно аксиоме выбора и континуум-гипотезе, относятся к неконструктивно-бесконечным множествам. В данном случае нас занимают лишь утверждения вида

«такое-то вычисление никогда не завершается»,

причем рассматриваемые вычисления можно задать совершен­но точно через действия машины Тьюринга. Такие утвержде­ния в логике называются Hi-высказываниями (или, точнее, П5-высказываниями). В пределах формальной системы F утвержде­ние G (F) является Щ-высказыванием, а вот П (F) таковым не является (см. §2.8). По всей видимости, не существует каких-либо разумных доводов против того, что истинный/ложный ха­рактер любого Щ-высказывания есть предмет абсолютный и никак не зависит от избранного нами мнения относитель­но предположений, касающихся неконструктивно-бесконечных множеств — таких, например, как аксиома выбора и континуум-гипотеза. (С другой стороны, как мы вскоре убедимся, выбор метода рассуждения, принимаемого нами в качестве инструмента для получения убедительных доказательств hi -высказываний, действительно может определяться мнением, которого мы при­держиваемся в отношении неконструктивно-бесконечных мно­жеств; см. возражение Q11.) Очевидно, если не считать крайней позиции, занимаемой отдельными интуиционистами(см. коммен­тарий к Q9), единственное здравое возражение по поводу абсо­лютного характера истинности таких утверждений может быть связано с тем обстоятельством, что некоторые принципиально завершающиеся вычисления могут потребовать для своего вы­полнения столь непомерно долгого времени, что на практике, вполне возможно, не завершатся и, скажем, за все время жизни вселенной; может случиться и так, что для записи самого вычис­ления (пусть и конечного) потребуется так много символов, что физически невозможным окажется составить даже его описание. Впрочем, все эти вопросы были исчерпывающим образом про­анализированы выше, в обсуждении возражения Q8, там же мы выяснили, что на наш основной вывод <£ они никоим образом не влияют. Вспомним и о возражении Q9, рассмотрение которого показало, что позиция интуиционистов в этом случае также не избегает вывода Ш.

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

Q11. Существуют определенные П1-высказывания, которые можно доказать с помощью теории беско­нечных множеств, однако не известно ни одного до­казательства, которое использовало бы стандарт­ные «конечные» методы. Не означает ли это, что даже к таким четко определенным проблемам ма­тематики, на деле, подходят субъективно? Различ­ные математики, придерживающиеся в отношении теории множеств разных убеждений, могут применять к оценке математической истинности П1-высказываний неэквивалентные критерии.

Этот момент может оказаться существенным в том, что касается моих собственных выводов из доказательства Гёделя (—Тьюринга), и я, возможно, уделил ему недостаточно много вни­мания в кратком изложении, представленном в НРК. Как ни странно, но возражение QM, похоже, никого, кроме меня, не обеспокоило — по крайней мере, никто мне на него не указал! В НРК (с. 417, 418), как и здесь, я сформулировал доказатель­ство Гёделя(—Тьюринга) исходя из того, что посредством разума и понимания способны установить все «математики» или «мате­матическое сообщество». Преимущество подобной формулиров­ки, в отличие от рассмотрения вопроса о способности какого-либо конкретного индивидуума к установлению математиче­ских истин посредством своего разума и понимания, заключается в том, что первый способ позволяет избежать некоторых воз­ражений, которые нередко выдвигают в отношении той версии доказательства Гёделя, которую предложил Лукас (196 J). Самые разные ученые^³-¹ указывали, к примеру, на то, что «сам Лукас» никак не мог обладать знанием о своем собственном алгоритме. (Некоторые из них говорили то же самое и о варианте дока­зательства, предложенном много-, не обратив, судя по всему, внимания на тот факт, что моя формулировка вовсе не настолько «личностна».) Именно возможность сослаться на способности к рассуждению и пониманию, присущие всем «математикам» вооб­ще или «математическому сообществу», позволяет нам избежать необходимости считаться с предположением о том, что различные индивидуумы могут воспринимать математическую истину по-разному, каждый в соответствии с личным непознаваемым алго­ритмом. Значительно сложнее смириться с тем, что результатом выполнения некоего непостижимого алгоритма может оказаться коллективное понимание математического сообщества в целом, нежели с тем, что этот самый алгоритм обусловливает матема­тическое понимание всего лишь какого-то конкретного индиви­дуума. Суть возражения QJI как раз и заключается в том, что упомянутое коллективное понимание может оказаться совсем не таким универсальным и безличным, каким счел его я.

Утверждения, о каких говорится в Q11, действительно, су­ществуют. То есть существуют Щ -высказывания, единственные известные доказательства которых опираются на то или иное применение теории бесконечных множеств. Такое Щ -высказы­вание может быть результатом арифметического кодирования утверждения типа «аксиомы формальной системы F являются непротиворечивыми», где система F подразумевает манипуля­ции обширными бесконечными множествами, само существова­ние которых может быть сомнительным. Математик, убежденный в реальном существовании некоторого достаточно обширного неконструктивного множества S, придет к выводу, что система F действительно непротиворечива, тогда как другой математик, ко­торый полагает, что множества S не существует, вовсе не обя­зан считать систему F непротиворечивой. Таким образом, даже ограничив рассмотрение одним вполне определенным вопросом о завершении или незавершении работы машины Тьюринга (т. е. ложности или истинности П₁-высказываний), мы не можем се­бе позволить не учитывать субъективности убеждений в от­ношении, скажем, существования некоторого обширного некон­структивно-бесконечного множества S. Если различные матема­тики используют для установления истинности определенных П₁ -высказываний неэквивалентные «персональные алгоритмы», то, по-видимому, с моей стороны несправедливо говорить о про-. сто «математиках» или «математическом сообществе».

Полагаю, что в строгом смысле это действительно может быть несколько несправедливо; и читатель может при желании перефразировать вывод следующим образом:

* Для установления математической истины ни один отдельно взятый математик не применяет только те алгоритмы, какие он (или она) полагает обоснованными. j

Представленные мною доводы по-прежнему остаются в силе, од­нако, мне кажется, некоторые из более поздних утратят значи­тельную часть своей силы, если представить ситуацию в таком виде. Более того, в случае формулировки * все доказатель­ство уходит в направлении, на мой взгляд, бесперспективном, сосредоточенном, в большей степени, на конкретных механизмах, управляющих действиями конкретных индивидуумов, нежели на принципах, лежащих в основе действий любого из нас. Меня же на данном этапе интересует не столько различия подходов от­дельных математиков к той или иной математической проблеме, сколько то общее, что есть между нашим пониманием и нашим математическим восприятием.

Попытаемся разобраться, действительно ли мы вынужде­ны принять формулировку *. В самом ли деле суждения мате­матиков настолько субъективны, что они могут принципиально расходиться при установлении истинности какого-то конкрет­ного III-высказывания? (Разумеется, доказательство, устанав­ливающее истинность hi-высказывания, может быть просто-напросто быть слишком громоздким или слишком сложным, что­бы его мог воспроизвести тот или иной математик (см. ниже по тексту возражение Q12), т.е. на практике математики вполне могут разойтись во мнениях. Однако в данном случае нас ин­тересует вовсе не это. Мы занимаемся исключительно принци­пиальными вопросами.) Вообще говоря, математическое дока­зательство есть вещь не настолько субъективная, как может по­казаться на основании вышесказанного. Математики могут при­держиваться самых разных — и, на их взгляд, неопровержимо истинных — точек зрения по тем или иным фундаментальным вопросам и во всеуслышание объявлять об этом, однако едва дело доходит до доказательств или опровержений каких-либо вполне определенных конкретных hi-высказываний, все разно­гласия тут же куда-то исчезают. Никто не воспримет всерьез доказательство hi-высказывания, утверждающего, по сути сво­ей, непротиворечивость некоторой формальной системы F, если математик будет основывать его только лишь на существовании некоего спорного бесконечного множества S. То, что при этом в действительности доказывается, можно сформулировать следу­ющим, куда более приемлемым, образом: «Если множество S су­ществует, то формальная система F является непротиворечивой, и в этом случае данное П₁-высказывание истинно».

Тем не менее, могут быть и исключения: например, один ма­тематик полагает, что некоторое неконструктивно-бесконечное множество S «с очевидностью» существует — или, по крайней мере, что допущение о его существовании никоим образом не приводит к противоречию, — другой же математик никакой оче­видности здесь не усматривает. Дискуссии математиков по таким фундаментальным вопросам могут порой принимать поистине неразрешимый характер. При этом обе стороны могут оказаться, в принципе, неспособны сколько-нибудь убедительно изложить свои доказательства, даже в отношении П₁-высказываний. Воз­можно, каждому математику и в самом деле присуще некое осо­бое внутреннее восприятие истинности утверждений, связанных с неконструктивно-бесконечными множествами. Конечно же, ма­тематики нередко заявляют о том, что их восприятие таких вещей в корне отличается от восприятия коллег. Однако я по­лагаю, что такие различия, по сути своей, подобны различиям в ожиданиях, которые различные математики могут иметь и в отношении истинности обычных математических высказываний. Эти ожидания суть всего лишь предварительные предположения. До тех пор, пока не представлено убедительного доказательства или опровержения, математики могут спорить друг с другом об ожидаемой или предполагаемой истинности того или иного по­ложения, однако представление такого доказательства одним из математиков убеждает (в принципе) всех. Что до фундаменталь­ных вопросов, то там этих доказательств как раз нет. Возможно, и не будет. Быть может, их нельзя отыскать по той причине, что их просто-напросто нет, а фундаментальные вопросы допускают существование различных, но равно справедливых точек зрения. Здесь, однако, следует подчеркнуть еще один связанный с hi-высказываниями момент. Возможность наличия у матема­тика ошибочной точки зрения — т. е. такой точки зрения, кото­рая вынуждает его делать неверные выводы в отношении истин­ности тех или иных П₁-высказываний, — нас в данный момент не интересует. Нет ничего невероятного в том, что математики порой опираются на неверное в фактическом отношении «пони­мание» — а то и на необоснованные алгоритмы, — только к настоящему обсуждению это никакого отношения не имеет, поскольку согласуется с выводом У. Впрочем, эту ситуацию мы подробно рассмотрим ниже, в § 3.4. Следовательно, дело в данном случае заключается не в том, могут ли разные математи­ки придерживаться противоречащих, одна другой точек зрения, а скорее в том, может ли одна точка зрения оказаться, в принципе, мощнее другой. Каждая такая точка зрения будет совершенно справедлива в том, что касается установления истинности П₁-высказываний, однако какая-то из них сможет, в принципе, дать своим последователям возможность установить, что те или иные вычисления не завершаются, тогда как другие, более слабые, точки зрения на это неспособны; то есть одни математики будут обладать существенно большей способностью к пониманию, нежели другие.

Не думаю, что такая возможность представляет собой сколь­ко-нибудь серьезную угрозу для моей первоначальной формули­ровки . Хотя в отношении бесконечных множеств математики и вправе придерживаться различных точек зрения, этих самых точек зрения вовсе не так много: по всей видимости, не бо­лее пяти. Существенные в этом смысле расхождения могут быть обусловлены лишь утверждениями, подобными аксиоме выбора (о ней говорилось в комментарии к возражению Q10), которую одни полагают «очевидной», другие же напрочь отвергают свя­занную с ней неконструктивность. Любопытно, что эти различ­ные точки зрения на собственно аксиому выбора не приводят непосредственно к тому П₁-высказыванию, относительно спра­ведливости которого возникают разногласия. Ибо, независимо от своей предполагаемой «истинности» или «ложности», аксиома выбора, как показывает теорема Гёделя—Коэна(см. комментарий к Q10), не вступает в противоречие со стандартными аксиома­ми системы ZF. Могут, однако, существовать и другие спорные аксиомы, соответствующей теоремы для которых нет. Впрочем, обыкновенно, когда речь заходит о принятии или опровержении той или иной теоретико-множественной аксиомы — назовем ее аксиомой Q, — утверждения математиков принимают следую­щий вид: «Из допущения справедливости аксиомы Q следует, что...». Такое утверждение при всем желании не сможет стать предметом спора между математиками. Аксиома выбора, похоже, является исключением в том смысле, что ее справедливость часто подразумевается без приведения упомянутой оговорки, однако это обстоятельство, по-видимому, никак не противоречит моей общей объективной формулировке вывода — при условии, что мы ограничимся только П₁-высказываниями:

Для установления истинности П₁-высказываний математики-люди не применяют заведомо обоснован­ные алгоритмы, а этого нам в любом случае вполне достаточно.

Есть ли другие спорные аксиомы, которые одни математи­ки считают «очевидными», а другие ставят под сомнение? Ду­маю, будет огромным преувеличением сказать, что имеется хотя бы десять существенно различных точек зрения на теоретико-множественные допущения, которые в явном виде как допущения не формулируются. Положим, что их не более десяти, и рассмот­рим следствия из этого допущения. Это означает, что существует порядка десяти, по сути, различных классов математиков, раз­личаемых по типу рассуждения в отношении бесконечных мно­жеств, который они полагают «очевидно» истинным. Каждого та­кого математика можно назвать математиком n-го класса, где nизменяется в весьма узком диапазоне — не более десяти значе­ний. (Чем больше номер класса, тем мощнее будет точка зрения принадлежащих к нему математиков.) Вывод ** принимает в этом случае следующий вид:

Для установления истинности ГЦ –высказываний математики-люди n-го класса (где n может принимать лишь несколько значений) не применяют только те алгоритмы, какие они полагают обоснованными.

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

Q12. Вне зависимости оттого, насколько различных точек зрения придерживаются математики в прин­ципе, на практике те же математики обладают весьма разными способностями к воспроизведению доказательств, разве не так? Не менее различны и их способности к пониманию, позволяющие им совершать математические открытия.

Безусловно, так оно и есть, однако к рассматриваемому во­просу все эти вещи не имеют ну абсолютно никакого отноше­ния. Меня не интересует, какие именно и насколько сложные до­казательства математик способен воспроизвести на практике. Еще меньше меня занимает вопрос о том, какие доказательства математик может на практике открыть или какие понимание и вдохновение могут ему в этом способствовать. Здесь мы говорим исключительно о том, доказательства какого типа математики могут, в принципе, воспринимать как обоснованные.

Оговорка «в принципе» используется в наших рассужде­ниях отнюдь не просто так. Если допустить, что некий матема­тик располагает доказательством или опровержением некоторо­го III -высказывания, то его разногласия с другими математиками касательно обоснованности данного доказательства разрешимы только в том случае, если у этих самых других математиков хватит времени, терпения, объективности, способностей и решимости с вниманием и пониманием воспроизвести всю — возможно, длин­ную и хитроумную — цепочку его рассуждений. На практике же математики вполне могут отказаться от всех этих трудов еще до полного разрешения спорных вопросов. Однако подобные про­блемы к данному исследованию отношения не имеют. Так как, по всей видимости, существует все же некий вполне определенный смысл, в котором то, что в принципе постижимо для одного мате­матика, оказывается равным образом (если отвлечься на время от возражения Q11) постижимо и для другого, — вообще, для лю­бого человека, способного мыслить. Рассуждения бывают весьма громоздкими, а участвующие в них концепции могут показаться чересчур тонкими или туманными, и тем не менее существуют достаточно убедительные основания полагать, что способность к пониманию одного человека не включает в себя ничего такого, что в принципе недоступно другому человеку. Это применимо и к тем случаям, когда для воспроизведения во всех подробностях чисто вычислительной части доказательства может потребовать­ся помощь компьютера. Возможно, не совсем разумно ожидать, что математик-человек будет лично выполнять все необходимые для такого доказательства вычисления, и все же он, вне всякого сомнения, сможет без особого труда понять и проверить каждый отдельный его этап.

Здесь я говорю исключительно о сложности математическо­го доказательства и ни в коем случае не о возможных существен­ных и принципиальных вопросах, которые могут вызвать среди математиков разногласия в отношении выбора допустимых ме­тодов рассуждения. Разумеется, я встречал математиков, утвер­ждавших, что они в своей практике сталкивались с такими ма­тематическими доказательствами, которые были совершенно вне их компетенции: «Я уверен, что, сколько бы я ни старался, мне никогда не понять того-то или такого-то; этот метод рассужде­ния мне не по зубам». В каждом конкретном случае подобного заявления необходимо индивидуально решать, действительно ли данный метод рассуждения в принципе выходит за рамки систе­мы убеждений этого математика — каковой случай мы рассмат­ривали в комментарии к возражению Q11, — или он вообще-то смог бы разобраться в принципах, на которых основано это доказательство, если бы только приложил больше сил и затра­тил больше времени. Как правило, справедливым оказывается последнее. Более того, источником отчаяния нашего математи­ка чаще всего становится туманный стиль изложения или огра­ниченные лекторские способности «такого-то», а вовсе не то, что какие-то существенные и принципиальные моменты «того-то» действительно выходят за рамки его способностей. Толковое изложение, на первый взгляд, непонятного предмета чудесным образом устраняет все прежние недоразумения.

Чтобы еще раз подчеркнуть, что я имею в виду, скажу сле­дующее: сам я часто посещаю математические семинары, на ко­торых не слежу (а иногда и не пытаюсь следить) за подробно­стями представляемых доказательств. Наверное, если бы я сел где-нибудь и обстоятельно изучил эти самые доказательства, я и в самом деле смог бы проследить за мыслью автора — хотя, возможно, это удалось бы мне лишь при наличии дополнитель­ной литературы или устных пояснений, которые восполнили бы возможные пробелы в моем образовании или же в материалах самого семинара. Я знаю, что в действительности я этого делать не стану. У меня почти наверняка не окажется на это ни време­ни, ни достаточного количества внимания, ни, впрочем, особого желания. Но при этом я вполне могу принять представленный на семинаре результат на веру по всевозможным «несущественным» причинам — например, потому что полученный результат правдоподобно «выглядит», или потому что у лектора надежная репутация, или потому что другие слушатели, которых я считаю более сведущими в таких делах, нежели я сам, этот результат оспаривать не стали. Конечно, я могу ошибиться во всех своих умозаключениях, а результат вполне может оказаться ложным — либо истинным, но никоим образом не следующим из представ­ленного доказательства. Все эти тонкости никак не влияют на ту принципиальную позицию, которую я здесь представляю. Ре­зультат может оказаться истинным и адекватно доказанным, и в таком случае я, в принципе, могу проследить за ходом всего доказательства — или же ошибочным, в каковом случае, как уже упоминалось, он нас в данном контексте не интересует (см. § 3.2 и § 3.4). Возможные исключения могут составить лишь те случаи, когда представляемый материал касается каких-либо спорных аспектов теории бесконечных множеств или опирается на какой-то необычный метод рассуждения, который может быть признан сомнительным в соответствии с теми или иными математически­ми воззрениями (что, само по себе, может заинтриговать меня до такой степени, что я впоследствии действительно попытаюсь это доказательство повторить). Как раз такие исключительные ситуации мы обсуждали выше, в комментарии к возражению Q11. Что касается подобных соображений относительно природы математической точки зрения, на практике многие математики могут и не иметь четкого представления о том, каких именно фундаментальных принципов они в действительности придержи­ваются. Однако, как уже было сказано выше, в комментарии к QI1, если математик, у которого нет определенной позиции в отношении того, следует ли принимать, скажем, некую «аксиому Q», желает проявить осмотрительность, то ничто не мешает ему изложить требующие принятия аксиомы Q результаты в следую­щем виде: «Из принятия аксиомы Q следует, что...». Разумеет­ся, математики, несмотря на всю их пресловутую педантичность, проявляют в подобных вопросах должную осмотрительность да­леко не всегда. Нельзя отрицать и того, что время от времени им удается допускать и вовсе очевидные ошибки. И все же все эти ошибки — если они допущены по недосмотру, а не следуют из тех или иных непоколебимых принципов — являются исправимыми. (Как упоминалось ранее, возможность действительного примене­ния математиками в качестве основы для своих решений необоснованного алгоритма будет подробно рассмотрена в §3.2 и §3.4. Поскольку эта возможность не противоречит выводу , она не является предметом настоящего обсуждения.) В данном слу­чае нас не занимают исправимые ошибки, так как к вопросу о принципиальной достижимости тех или иных результатов они ни­какого отношения не имеют. А вот возможные неопределенно­сти в действительных взглядах математиков, безусловно, требуют дальнейшего обсуждения, которое и приводится ниже.

QI3. У математиков нет абсолютно определен­ных убеждений относительно обоснованности или непротиворечивости используемых ими формальных систем — как нет и однозначного ответа на вопрос о том, «пользователями» каких именно формальных систем они себя полагают. Не подвергаются ли их убеждения постепенному размыванию по мере того, как формальные системы все более удаляются от области феноменов, доступных непосредственному интуитивному или эксперименталь­ному восприятию?

И правда, нечасто встретишь математика, способного по­хвалиться прочно устоявшимися и непоколебимо непротиворе­чивыми убеждениями, когда речь заходит об основах предмета. Кроме того, по мере накопления опыта математик вполне может изменить свои взгляды относительно того, что считать неопро­вержимо истинным, если он вообще склонен считать неопровер­жимо истинным что бы то ни было. Можно ли, например, быть совершенно и полностью уверенным в том, что число 1 отлично от числа 2? Если говорить о некоей абсолютной человеческой уверенности, то не совсем ясно, можно ли подобное понятие как-то однозначно определить. Однако какую-то точку опоры все же выбрать необходимо. Вполне приемлемой точкой опоры может стать принятие в качестве неопровержимо истинной некоторой системы убеждений и принципов, от которой уже можно двигать­ся в своих рассуждениях дальше. Разумеется, нельзя забывать и о том, что многие математики вовсе не имеют определенного мнения относительно того, что именно можно считать неопро­вержимо истинным. Таких математиков я попросил бы какую-никакую опору для себя все же выбрать и просто быть готовы­ми при необходимости впоследствии ее сменить. Как показывает доказательство Гёделя, какую бы позицию математик в этом случае ни занял, ее все равно невозможно полностью уместить в рамки правил любой постижимой формальной системы (а если и возможно, то этот факт невозможно однозначно установить). И дело даже не в том, что та или иная конкретная позиция по­стоянно изменяется; система убеждений, полностью охватыва­емая рамками любой (достаточно обширной) формальной си­стемы F, неизбежно должна также простирается и за пределы доступной F области. Любая позиция, среди неопровержимых убеждений которой имеется и убеждение в обоснованности си­стемы F, должна также включать в себя и убежденность в ис­тинности гёделевского предположения G(F). Убежденность в истинности G(F) не представляет собой изменения позиции; эта убежденность уже подразумевается неявно в исходной позиции, допускающей принятие истинности формальной системы F, пусть даже поначалу это и не очевидно.

Безусловно, всегда существует возможность того, что в вы­воды, получаемые математиком на основании исходных посылок какой-либо конкретной точки зрения, закрадется ошибка. Од­на только возможность возникновения такой ошибки — даже если в действительности никакой ошибки допущено не было — может привести к уменьшению степени убежденности, которую математик питает в отношении своих выводов. Однако такое «по­степенное размывание» нас, вообще говоря, не занимает. По­добно действительным ошибкам, оно «исправимо». Более того, если доказательство было проведено действительно корректно, то чем дольше его изучаешь, тем, как правило, более убедитель­ными представляются полученные в нем выводы. «Постепенное размывание» математик может испытать на практике, но не в принципе, что возвращает нас к обсуждению возражения Q12.

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

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

Надеюсь, читатель понимает, что возможность возникнове­ния таких ошибок не существенна, когда речь заходит о том, что мы подразумеваем здесь под принятием предположения G (F) в качестве неопровержимой истины. Я, разумеется, говорю о дей­ствительном предположении G (F), а не о возможном случай­ном предположении, непреднамеренно сформулированном бла­годаря опечатке или незначительной ошибке. В этой связи мне вспоминается одна история о великом американском физике Ри­чарде Фейнмане. Фейнман, по-видимому, объяснял одному из студентов какое-то понятие, но оговорился. Когда студент выра­зил недоумение, Фейнман вспылил: «Не слушайте, что я говорю; слушайте, что я имею в виду!».

Один из возможных способов такого явного кодирования состоит в использовании представленных еще в НРК специфика­ций машин Тьюринга и точном воспроизведении доказательства гёделевского типа, описанного в §2.5 (пример такого кодиро­вания приводится в Приложении А). Впрочем, даже и в этом случае об абсолютной «явности» говорить нельзя, поскольку нам понадобится еще и каким-то явным образом закодировать пра­вила формальной системы F в системе обозначений действий ма­шин Тьюринга; обозначим такой код, скажем, через Ту. (Код tf должен удовлетворять определенному свойству: если некоторому высказыванию Р, выводимому в рамках системы F, ставится в соответствие некоторое число р, то необходимо, скажем, чтобы равенство tf (р) — 1 выполнялось всякий раз, когда высказы­вание Р является теоремой системы F, в противном же случае вычисление Tf(p) не должно завершаться вовсе.) Безусловно, все это открывает широкий простор для формальных ошибок. Помимо возможных трудностей, связанных с практическим по­строением кода Ту на основе системы F и отысканием числа р на основе высказывания Р, отсутствует ясность и в отношении другого вопроса: а не ошибся ли я сам где-нибудь в специфи­кациях машин Тьюринга, — иными словами, можем ли мы быть полностью уверены в корректности приведенного в Приложении А этой книги кода, если вдруг решим использовать для отыска­ния вычисления Ck (k) именно это определение? Лично я думаю, что ошибок там нет, однако в собственной непогрешимости я уверен куда как меньше, нежели в первоначальных построениях Гёделя (пусть и более сложных). Впрочем, всякому дочитавшему до этого места, смею надеяться, уже ясно, что возможные ошибки подобного рода существенной роли здесь не играют. Помните, что говорил Фейнман?

Что же касается собственно моих спецификаций, следует упомянуть еще один формальный момент. Представленный мною в §2.5 вариант доказательства Гёделя(-Тьюринга) опирается не на непротиворечивость системы F, а на обоснованность алго­ритма А, и являет собой критерий для установления незавершаемости вычислений (т.е. истинности ГЦ-высказываний). Этот вариант подходит нам ничуть не хуже любых других, посколь­ку известно, что из обоснованности алгоритма А следует ис­тинность утверждения о незавершаемости вычисления Ck (k), каковое явное утверждение (тоже П₁-высказывание) мы име­ем полное право использовать вместо высказывания G(F). Бо­лее того, как отмечали выше (см. §2.8), доказательство, вообще говоря, зависит не от непротиворечивости формальной систе­мы F, а от ее -непротиворечивости. Из обоснованности систе­мы F очевидно следует ее непротиворечивость, равно как и - непротиворечивость. Если допустить, что система F обоснована, то ни fi (F), ни G (F) из ее правил (см. §2.8) не следуют, однако оба эти высказывания являются истинными.

Думаю, можно с уверенностью заключить, что какое бы «по­степенное размывание» убежденности того или иного матема­тика ни сопровождало переход от убеждения в обоснованности формальной системы F к убеждению в истинности высказыва­ния G(F) (или О (F)), оно будет целиком и полностью обуслов­лено возможностью ошибки в точной формулировке получен­ного им высказывания «G(F)». (To же применимо и к выска­зыванию fi(F).) Все это не имеет непосредственного отноше­ния к настоящему обсуждению — при наличии подлинной (не случайной) формулировки высказывания G (F) никакого размы­вания убежденности происходить не должно. Если формальная система F неопровержимо обоснована, то ее высказывание G (F) столь же неопровержимо истинно. Все формы заключения (, ) остаются неизменными при условии, что под «истин­ностью» подразумевается «неопровержимая истинность».

Q14. Нет никаких сомнений в том, что формальная система ZF — или некоторая стандартная ее модификация (обозначим ее через ZF*)—действительно включает в себя все необходимое для серьезной математической деятельности. Почему бы просто не принять эту систему за основу, смириться с недоказуемостью ее непротиворечивости и продолжить свои математические изыскания?

Полагаю, такая точка зрения весьма и весьма распростра­нена среди практикующих математиков, особенно тех, кто не слишком углубляется в фундаментальные основы или филосо­фию своего предмета. Подобное отношение вполне естественно для людей, главной заботой которых является просто хорошее выполнение серьезной, пусть и математической, работы (хотя в действительности такие люди крайне редко выражают свои результаты в рамках строгих правил формальных систем, по­добных ZF). Согласно этой точке зрения, математика имеет де­ло лишь с тем, что можно доказать или опровергнуть в рам­ках некоей конкретной формальной системы — такой, напри­мер, как ZF (или какая-либо ее модификация ZF*). С высоты такой позиции математическая деятельность и в самом деле на­поминает своего рода «игру». Назовем ее ZF-игрой (или ZF*-игрой), причем играть в эту игру следует в соответствии с пра­вилами, установленными в рамках данной системы. Такой подход характерен для формалиста, подлинный же формалист мыслит исключительно в терминах ИСТИННОГО и ЛОЖНОГО, которые не обязательно совпадают с истинным и ложным в их повсе­дневном смысле. Если формальная система обоснованна, то все, что является ИСТИННЫМ, и будет истинным, а все, что ЛОЖ­НО, будет ложным. Однако наверняка найдутся высказывания, формализуемые в рамках данной системы, которые, будучи ис­тинными, не являются ИСТИННЫМИ, и другие, которые, буду­чи ложными, не являются ЛОЖНЫМИ, иными словами, в обо­их случаях эти высказывания оказываются НЕРАЗРЕШИМЫМИ. Если система ZF непротиворечива, то в ZF-игре гёделевское высказывание G (ZF) и его отрицание ~ G (ZF) принадле­жат, соответственно, к этим двум категориям. (Более того, ока­жись система ZF противоречивой, то и высказывание G(ZF), и его отрицание ~ G(ZF) были бы истинными и ложными одновременно!)

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

Q15. Выбранная нами формальная система F может и не оказаться непротиворечивой — по крайней ме­ре, мы не можем быть вполне уверены в ее непро­тиворечивости; по какому же, в таком случае, праву мы утверждаем, что высказывание G (F) «очевидно» истинно?

Хотя этот вопрос был достаточно исчерпывающе рассмотрен в предыдущих обсуждениях, я полагаю, что суть того рассмот­рения полезно будет изложить еще раз, поскольку возражения, подобные Q15, чаще всего оказываются среди нападок на наше с Лукасом приложение теоремы Гёделя. Суть же в том, что мы вовсе не утверждаем, что высказывание G(F) непременно ис­тинно для любой формальной системы F, мы утверждаем лишь, что высказывание G (F) настолько же достоверно, насколько до­стоверна любая другая истина, получаемая применением правил самой системы F. (Вообще говоря, высказывание G (F) оказыва­ется более достоверным, нежели утверждения, получаемые дей­ствительным применением правил F, так как система F, даже будучи непротиворечивой, не обязательно будет обоснованной!) Если мы верим в истинность любого утверждения Р, выводимого исключительно с помощью правил системы F, то мы должны верить и в истинность G (F), по крайней мере, в той же степени, в какой мы верим в истинность Р. Таким образом, ни одна по­стижимая формальная система F — или эквивалентный ей алго­ритм F — не может послужить абсолютно полной основой для подлинного математического познания или формирования убе­ждений. Как отмечалось в комментариях к Q5 и Q6, наше дока­зательство построено как reductio ad absurdum: мы выдвигаем предположение, что система F действительно является абсолют­ной основой для формирования убеждений; а затем показываем, что такое предположение приводит к противоречию, т. е. является неверным.

Мы, конечно же, можем, как в Q14, выбрать для удобства какую-то конкретную систему F, хотя уверенности в том, что она обоснована, а потому непротиворечива, это нам не добавит. Впрочем, при наличии действительных сомнений в обоснован­ности системы F любой получаемый в рамках F результат Р сле­дует формулировать в виде

«высказывание Р выводимо в рамках системы F»

(или, что то же самое, «высказывание Р ИСТИННО»), избегая утверждений вида «высказывание Р истинно». Такое утвержде­ние в математическом смысле вполне приемлемо и может быть либо действительно истинным, либо действительно ложным. Со­вершенно законным образом мы можем свести все наши мате­матические высказывания к утверждениям такого рода, однако и в этом случае нам никуда не деться от утверждений об абсо­лютных математических истинах. При случае мы можем прийти к убеждению, будто мы установили, что какое-то утверждение вышеприведенного вида является в действительности ложным, т. е. получить следующий результат:

«высказывание Р невыводимо в рамках системы F».

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

Q16. Заключение об истинности высказывания G(F) для непротиворечивой формальной системы F мы делаем, исходя из допущения, что те символы системы F, которые, как мы полагаем, служат для представления натуральных чисел, действително представляют натуральные числа. Окажись на их месте другие числа — скажем, некие экзотические «сверхнатуральные» числа, — мы вполне могли бы обнаружить, что высказывание G(F) ложно. Откуда мы знаем, что в нашей системе F мы имеем дело с натуральными, а не со сверхнатуральными числами?

В самом деле, конечного аксиоматического способа убедить­ся в том, что «числа», о которых идет речь, и есть те самые подразумеваемые натуральные числа, а не какие-то посторон­ние «сверхнатуральные», не существует^⁵'. Однако, в некотором смысле, в этом и состоит вся суть гёделевского рассуждения. Неважно, какую именно схему аксиом формальной системы F мы построим, пытаясь охарактеризовать натуральные числа, одних лишь правил системы F будет недостаточно, чтобы определить, является ли высказывание G (F) действительно истинным или же ложным. Полагая систему F непротиворечивой, мы знаем, что в высказывании G (F) подразумевается все же наличие некоего истинного смысла. Это, однако, происходит лишь в том случае, если символы, составляющие в действительности формальное выражение, обозначаемое «G (F)», имеют подразумеваемые зна­чения. Если эти символы интерпретировать как-либо иначе, то полученная в результате интерпретация «G(F)>> вполне может оказаться ложной.

Для того чтобы разобраться, откуда берутся все эти дву­смысленности, рассмотрим новые формальные системы F* и F**, где F* получается путем присоединения к аксиомам системы F высказывания G (F), a F** — путем аналогичного присоединения высказывания ~ G (F). Если система F обоснована, то обе систе­мы F* и F** непротиворечивы (т. к. высказывание G(F) истинно, а ~ G (F) из правил системы F) вывести невозможно. При этом в случае подразумеваемой (или стандартной) интерпретации символов F из обоснованности системы F следует, что система F* обоснована, а система F** — нет. Впрочем, одним из харак­терных свойств непротиворечивых формальных систем являет­ся возможность отыскания так называемых нестандартных реинтерпретаций символов таким образом, что высказывания, которые являются ложными в стандартной интерпретации, ока­зываются истинными в нестандартной; соответственно, в такой нестандартной интерпретации обоснованными могут быть систе­мы F и F**, а система F* обоснованной не будет. Можно вообра­зить, что такая реинтерпретация может повлиять на смысл логи­ческих символов (таких как «~» и «&», которые в стандартной интерпретации означают, соответственно, «не» и «и»), однако в данном случае нас занимают символы, обозначающие неопре­деленные числа («от», «у», «z», «ж'», «х"» и т.д.), и значения применяемых к ним логических кванторов (V, 3). В стандартной интерпретации символы «Vx» и «Эх» означают, соответственно, «для всех натуральных чисел х» и «существует такое натураль­ное число х, что»; в нестандартной же интерпретации эти симво­лы могут относится не к натуральным числам, а к числам какого-то иного вида с иными свойствами упорядочения (такие числа действительно можно назвать «сверхнатуральными», или даже «ультранатуральными», как это сделал Хофштадтер [200]).

Дело, однако, в том, что мы-то знаем, что такое на самом деле представляют собой натуральные числа, и для нас не со­ставит никакого труда отличить от каких-то непонятных сверхна­туральных чисел. Натуральные числа суть самые обыденные ве­щи, обозначаемые, как правило, символами 0, 1, 2, 3, 4, 5, 6, — С этой концепцией мы знакомимся еще в детском возрасте и легко отличим ее от надуманной концепции сверхнатурального числа (см. § 1.21). Есть что-то таинственное в том, что мы, по­хоже, и впрямь обладаем каким-то инстинктивным пониманием действительного смысла понятия натурального числа. Все, что мы получаем в этом смысле в детском (или уже взрослом) возра­сте, сводится к сравнительно небольшому количеству описаний понятий «нуля», «единицы», «двух», «трех» и т.д. («три апель­сина», «один банан» и т.п.), однако при этом, несмотря на всю неадекватность такого описания, мы как-то умудряемся постичь всю концепцию в целом. В некотором платоническом смысле на­туральные числа видятся своего рода категориями, обладающи­ми абсолютным концептуальным существованием, от нас никак не зависящим. И все же, несмотря на «человеконезависимость» натуральных чисел, мы оказываемся способны установить ин­теллектуальную связь с действительной концепцией натуральных чисел, опираясь лишь на неоднозначные и, на первый взгляд, неадекватные описания. С другой стороны, не существует ко­нечного набора аксиом, с помощью которого можно было бы провести четкую границу между множеством натуральных чисел и альтернативным ему множеством так называемых «сверхнату­ральных» чисел.

Более того, такое специфическое свойство всей совокупно­сти натуральных чисел, как их бесконечное количество, мы так­же можем каким-то образом воспринимать непосредственно, то­гда как система, действие которой ограничено точными конечны­ми правилами, не способна отличить данную конкретную беско­нечность натуральных чисел от других возможных («сверхнату­ральных») вариантов. Мы же легко понимаем бесконечность, ха­рактеризующую натуральные числа, пусть и обозначаем ее про­сто точками «...» —

«0, 1,2,3,4,5,6,...»,

либо сокращением «и т. д.»—

«ноль, один, два, три и т. д.».

Нам не нужно объяснять на языке каких-то точных правил, что именно представляет собой натуральное число. В этом смысле можно считать, что нам повезло, так как такое объяснение дать невозможно. Как только нам приблизительно укажут верное на­правление, мы тут же обнаруживаем, что уже откуда-то знаем, что это за штука такая — натуральное число!

Возможно, некоторые читатели знакомы с аксиомами Пеано для арифметики натуральных чисел (об арифметике Пеано я вкратце упоминал в §2.7), и, возможно, теперь эти читатели находятся в некотором недоумении: почему же аксиомы Пеано не да­ют адекватного определения натуральных чисел. Согласно опре­делению Пеано, мы начинаем ряд натуральных чисел с символа О и затем добавляем слева особый «оператор следования», обо­значаемый S и осуществляющий простое прибавление единицы к числу, над которым совершается действие, т. е. I определяется как SO, 2 как S1 или SSO и т. д. В качестве правил мы располагаем следующими утверждениями: если Sa=Sb, то а=Ь; и ни при ка­ком х число 0 нельзя записать в