Математика. Утрата определенности.

Клайн Морис

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

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

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

f(1) = 1, f( n+ 1) = f( n) + 3.

Тогда

f(2) = f(1) + 3 = 1 + 3 = 4, f(3) = f(2) + 3 = 4 + 3 = 7.

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

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

141

Доступен и начинающему рассказ [88] о работе Ю. Матиясевича; несколько больших знаний требуют комментарии к 10-й проблеме Гильберта в [51] (освещение ситуации, какой она представлялась до решения проблемы) и в [89], где статья о 10-й проблеме Гильберта, принадлежит основным участникам ее решения М. Девису, Ю. Матиясевичу и Дж. Робинсон. (Видный логик Джулия Робинсон, заложившая первые камни в основание построенного Матиясевичем здания, является сестрой создателя нестандартного анализа Абрахама Робинсона (см. далее), Мартин Девис — автор одного из лучших учебников нестандартного анализа [86].

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

Нерешенные проблемы могут оказаться неразрешимыми, но далеко не всегда это известно заранее. Например, задача о трисекции угла с помощью циркуля и линейки в течение по крайней мере нескольких столетий ошибочно считалась неразрешимой. Но трисекция оказалась невозможной. Теорема Черча утверждает, что не существует способа, позволяющего заранее определить, можно ли доказать или опровергнуть утверждение. Одни утверждения можно доказать и опровергнуть одновременно, другие нельзя ни доказать, ни опровергнуть — они неразрешимы, но их неразрешимость, как и неразрешимость всех известных неразрешимых проблем, заранее отнюдь не очевидна. Гипотеза Гольдбаха о том, что любое четное число представимо в виде суммы двух простых чисел, пока не доказана. Она может оказаться неразрешимой в системе аксиом арифметики, но ее неразрешимость, конечно, не очевидна. Не исключено, что когда-нибудь гипотезу Гольдбаха удастся доказать или опровергнуть.

Не успели математики оправиться от потрясений, вызванных теоремой Гёделя о неполноте и о невозможности доказать непротиворечивость арифметики, как через десять лет возникла новая серьезная угроза развитию математики. И опять «виной» тому был Гёдель, который явился инициатором серии исследований, которые внесли еще большую неразбериху в вопрос о том, что такое математика, имеющая под собой надежную основу, и в каком направлении она может развиваться. Напомним, что сторонники одного из подходов к основаниям математики, возникшего в начале XX в., намеревались построить математику, исходя из теории множеств (гл. XI); с этой целью была разработана система аксиом Цермело — Френкеля.

В работе «Совместимость аксиомы выбора и обобщенной гипотезы континуума с аксиомами теории множеств» (1940) Гёдель доказал, что если система аксиом Цермело — Френкеля без аксиомы выбора непротиворечива, то добавление аксиомы выбора не нарушает непротиворечивости, т.е. аксиома выбора в рамках этой аксиоматики не может быть доказана. Аналогично он установил, что предположение Кантора — гипотеза континуума о том, что не существует кардинальных чисел, заключенных

между N ₀и 2 ^N0(т.е. кардинальным числом c,соответствующим множеству всех вещественных чисел), или, иначе говоря, что не существует несчетного множества действительных чисел с кардинальным числом, меньшим 2 ^N0, и обобщенная гипотеза континуума {142} не противоречит системе аксиом Цермело — Френкеля, даже если последнюю дополнить аксиомой выбора. Другими словами, гипотезу континуума как в обычном, так и в обобщенном варианте нельзя опровергнуть. Для доказательства своих утверждений Гёдель построил модели, в которых оба утверждения выполняются.

142

Обобщенная гипотеза континуума утверждает, что кардинальное число множества всех подмножеств некоторого множества, обладающего кардинальным числом N _n , равно N _n+1 (т.е. 2 ^{N n} = N _n+1 ). Кантор доказал, что 2 ^{N n} > N _n .

Непротиворечивость обоих утверждений — аксиомы выбора и гипотезы континуума — несколько обнадежила математиков: обеими теоремами можно было пользоваться по крайней мере с не меньшей уверенностью, чем остальными аксиомами Цермело — Френкеля.

Однако благодушие математиков (если только оно действительно было) быстро развеяли последующие события. Результаты Гёделя не исключали возможности того, что аксиома выбора и гипотеза континуума — порознь или вместе — могут быть доказаны на основе остальных аксиом Цермело — Френкеля. Мысль о том, что по крайней мере аксиому выбора невозможно вывести из остальных аксиом Цермело — Френкеля, была высказана еще в 1922 г. Тогда же и несколько позднее некоторые ученые, в том числе и Френкель, доказали независимость аксиомы выбора, но каждый из них счел необходимым дополнить систему Цермело — Френкеля вспомогательной аксиомой, которая, собственно, и позволила им осуществить доказательство. Примерно такое же возражение выдвигалось и против более поздних доказательств. В 1947 г. Гёдель предположил, что гипотеза континуума независима от аксиом Цермело — Френкеля и от аксиомы выбора.

В 1963 г. профессор математики Станфордского университета Пол Коэн (р. 1934) доказал, что и аксиома выбора, и гипотеза континуума независимы от остальных аксиом Цермело — Френкеля, если те непротиворечивы, т.е. иначе говоря, аксиома выбора и гипотеза континуума не могут быть доказаны на основе остальных аксиом Цермело — Френкеля. Более того, гипотеза континуума и тем более обобщенная гипотеза континуума не могут быть доказаны в системе Цермело — Френкеля, даже если ее дополнить аксиомой выбора. (Аксиома выбора следует из системы аксиом Цермело — Френкеля, не содержащей аксиомы выбора, но дополненной обобщенной гипотезой континуума.) Эти два результата по независимости означают, что в системе Цермело — Френкеля аксиома выбора и гипотеза континуума неразрешимы. В частности, для гипотезы континуума результат Коэна означает, что может существовать трансфинитное число, заключенное между N ₀и 2 ^N0(или c), хотя такое трансфинитное число не соответствует ни одному известному множеству.

В принципе метод Коэна, получивший название метода форсинга,не отличался от других доказательств независимости. {143} Напомним, что для доказательства независимости аксиомы Евклида о параллельных на основе остальных аксиом евклидовой геометрии требуется найти интерпретацию, или модель, которая удовлетворяла бы всем остальным аксиомам, кроме аксиомы о параллельных. {144} Такая модель должна быть непротиворечивой, так как в противном случае она может также удовлетворять аксиоме, независимость которой нас интересует. В своем доказательстве Коэн усовершенствовал более ранние работы Френкеля, Гёделя и других авторов, использовав без каких-либо вспомогательных условий только аксиомы Цермело — Френкеля. Доказательства независимости аксиомы выбора, хотя и менее удовлетворительные, были известны до Коэна, но вопрос о независимости гипотезы континуума до появления его работы оставался открытым.

143

Помимо статьи [17]*, рассчитанной на самую широкую аудиторию, можно назвать обстоятельную книгу [90] и обзор [91].

144

В теории групп аксиома коммутативности умножения не зависит от остальных аксиом группы. Существуют модели группы, удовлетворяющие аксиоме коммутативности (например, обычные положительные и отрицательные числа); другие же модели (скажем, кватернионы) аксиоме коммутативности не удовлетворяют.