Это значит, что за счет расширения набора допустимых операций иногда можно часть проблем, для которых нет алгоритма, сделать разрешимыми. Конечно, если ничем не ограничиваться при определении допустимых операций, то многие проблемы станут разрешимыми (но все ли? об этом см. в § 1 гл. 5).
В конце второй главы мы снова пришли к вопросу о том, сколь сложны или, лучше, сколь просты должны быть операции, выполнение которых может быть рассматриваемо как отдельный шаг алгоритмического процесса. Во всяком случае, нельзя считать допустимой такую операцию, способ получения результата которой нам неизвестен. Иначе многие нерешенные проблемы мы стали бы ошибочно считать решенными.
§ 4. Антиномии
В то время, когда А. Пуанкаре провозгласил, что математика обрела, наконец, надежный фундамент, сама арифметика пошатнулась из-за того, что в теории множеств были обнаружены противоречия (парадоксы), вошедшие в историю математики под названием антиномий.
Парадокс Рассела (открыт в 1902 г.). Если парадокс Кантора возникает для множества, которое содержит себя в качестве своего элемента, то парадокс Рассела связан с множествами, не содержащими себя в качестве своих элементов. Для удобства будем множество, не содержащее себя в качестве элемента, называть обычным, а множество, содержащее себя в качестве элемента,— необычным.
Парадоксальным является множество всех обычных и только обычных множеств. Чтобы в этом убедиться, проверим, является ли оно само обычным или необычным. Сперва предположим, что оно обычное. Но тогда, будучи множеством всех обычных множеств, оно содержит и себя. Стало быть, оно необычное. Предположив, что оно обычное, мы получили противоречие.
Но, может быть, оно необычное, и дело с концом? Проверим. Если оно необычное, то, будучи множеством только обычных, оно себя в качестве элемента не содержит, а значит, является обычным. Опять противоречие.
Интересно, что парадокс Рассела может возникнуть и для каталогов, которыми мы уже пользовались для построения парадокса Кантора.
Парадоксальным оказывается каталог всех несамоназыващихся и только несамоназывающихся каталогов. Он не может быть самоназывающимся (содержать сведения о самом себе), так как является каталогом только несамоназывающихся каталогов. Точно так же он не может быть и несамоназывающимся, так как при этом не содержал бы сведений о себе (несамоназывающемся), но должен был бы содержать.
Парадокс брадобрея. Парадокс Рассела можно сформулировать без привлечения понятия множества. Представим себе, что один из солдат оказался по профессии парикмахером. Узнав об этом, командир полка приказал ему брить всех тех и только тех, кто сам себя не бреет. Все было хорошо, пока не пришло время побрить самого себя. Оказалось, что побрить себя нельзя, так как приказано брить только тех, кто себя не бреет; не брить себя тоже нельзя, потому что приказано брить всех, кто себя не бреет.
Не кажется ли читателю, что положение брадобрея подобно положению юноши, решившего купить костюм, цена которого меньше 50 рублей (потому что это дешевый костюм) и больше 150 рублей (потому что это хороший костюм)? Разница лишь в том, что условия для покупки костюма всегда противоречивы (не зависят от объекта покупки), а условия, при которых следует брить, не всегда: их противоречивость или непротиворечивость зависит от объекта бритья.
§ 5. Выводы из антиномий
Открытие антиномий потрясло математику и математиков как землетрясение. Их наличие, и при этом в такой области, как теория множеств (и логика, потому что парадокс брадобрея имеет логический характер), заставило опасаться того, что многие результаты, полученные в математике, тоже противоречивы. Можно было ожидать, что в дальнейшем будут появляться еще новые парадоксы. Все в математике стало казаться неустойчивым, потому что самый ее фундамент дал трещину.
Нужно сказать, что математики реагировали на землетрясение по-разному. Одни стали во всем сомневаться. Известный математик Ю. Дедекинд после опубликования антиномии Рассела на некоторое время прекратил публикацию своих работ. Математик Г. Фреге кончал в это время издание своего большого труда, подготовке которого он посвятил десять лет жизни. В первой же фразе послесловия он говорит, что фундамент построенного им здания поколеблен парадоксом Рассела. А. Пуанкаре, о котором мы уже говорили, изменил свое отношение к теории множеств. Были, конечно, и такие математики, которые на открытие антиномий никак не реагировали и бездумно продолжали применять теорию множеств, правда, в той ее части, в которой не обнаружено антиномий. Этих математиков обычно называют последователями классицизма. Но многие математики стали искать пути устранения противоречий.
Некоторые полагали, что противоречия возникают благодаря дефектам самой логики и стали пересматривать именно ее.
Другие предполагали, что парадоксы возникают из-за некорректности понятия множества, и занялись поиском такого определения множества, которое было бы свободно от внутренних противоречий.
Третьи — получившие название формалистов — пришли к выводу, что математика должна быть аксиоматизирована, а затем все теоремы совершенно формально доказаны. При этом возник вопрос о формальном языке для математики, таком, чтобы с аксиомами, изложенными на нем, можно было поступать как с определенными комбинациями символов. Доказательство теорем при этом принимало вид переработки исходных аксиом с помощью правил вывода в новые комбинации символов — теоремы. Эти математики разработали новую дисциплину — теорию математического вывода, называемую метаматематикой .
Четвертые усмотрели причину кризиса математики в том, что ряд математических объектов и методов являются неконструктивными. Разъясним последнюю точку зрения.
В теории множеств допускаются «готовые» бесконечные множества, уже существующие, уже завершенные. Завершенное бесконечное множество называют актуально бесконечным. Расходуя ограниченное количество ресурсов на каждом шаге, имеющем фиксированную длительность, построить такое множество ни реально, ни потенциально нельзя. Проверить, обладают ли все элементы такого множества каким-либо свойством, тоже нельзя, так как никакая ограниченная скорость проверки не дает возможности охватить их все. Другое дело, потенциально бесконечное, или потенциально осуществимое множество. Такое множество в каждый момент конечно, но есть прием, позволяющий добавить к нему всегда еще несколько (а потом еще несколько, и еще несколько, и так далее и, значит, сколько угодно) элементов. Анализ элементов такого множества можно провести исследованием правила, которое позволяет получать все новые и новые элементы этого «конструктивного» множества.
Актуально бесконечное множество, будучи недоступно ни построению, ни проверке, обязывает нас слепо доверять тем правилам логики, с помощью которых мы определили свойства его элементов. Указанные правила логики не основываются ни на каких фактах, доступных проверке, во всяком случае в смысле их правильности для актуально бесконечных множеств. Значит, говорят математики, придерживающиеся этой четвертой точки зрения, всей части теории множеств, имеющей деле с актуальной бесконечностью, доверять нельзя.
Будучи едины в своем отношении к актуальной бесконечности и в своем требовании конструктивности, сторонники четвертой точки зрения неодинаково решают вопрос о том, что допустимо в качестве исходного материала для конструкций. Таким образом, эта точка зрения делится на две группы.
Математики первой группы считают, что главным основанием для выбора какого-либо математического объекта в качестве исходного для дальнейших построений является его интуитивная очевидность. Читатель, вероятно, согласится, что выбор, опирающийся на интуицию, не может не быть субъективным. То, что интуитивно ясно одному, совершенно неясно другому. Это течение в математике получило название интуиционизма.
Математики второй группы считают, что исходным материалом для построений могут быть лишь наиболее простые математические объекты, применение которых оправдано всей практикой человечества, причем количество их типов должно быть ограничено. В качестве основного средства получения новых математических объектов должны служить алгоритмы. Это направление получило название конструктивного.
Нужно признать, что ученые всех перечисленных направлений внесли большой вклад в сокровищницу математики, получили большое число очень интересных, глубоких и важных научных результатов. Нужно также подчеркнуть, что наше описание различных точек зрения, возникающих в результате обнаружения антиномий, является упрощенным и неточным. Но более подробно осветить этот вопрос автор не имеет возможности.
Из всех указанных направлений мы выделим последнее — конструктивное, поскольку оно для обоснования математики приняло на вооружение алгоритмы, и его сторонники стали разрабатывать теорию алгоритмов.
Итак, мы ознакомились со второй причиной для разработки теории алгоритмов: необходимостью обоснования математики.
На этом автор хотел закончить главу, но вдруг понял, что любознательный читатель, узнав о том, что произошло в математическом мире в начале XX в., несомненно захочет узнать — а как же дело обстоит сейчас? Рассыпалась ли математика, как карточный домик, или она устояла, преодолела свой кризис?