Философско-методологические проблемы математики в работах А. А. Маркова. Андрей Андреевич Марков 1903

Андрей Андреевич Марков (1903 – 1979) — известный советский математик, член-корреспондент Академии Наук СССР с 1953 года. Родился в семье русского математика А. А. Маркова в Петербурге, 9 сентября 1903 года. Окончил Ленинградский университет в 1924 году. В 1933 – 55 годах работал в Ленинградском университете, с 1939 — в математическом институте АН СССР. С 1959 года заведовал кафедрой математической логики Московского университета. Длительное время находился на посту вице-президента отделения логики, методологии и философии науки международного союза истории и философии науки, был вице-президентом этого союза.

Андрей Андреевич Марков был человеком весьма разносторонних интересов, которые у него непрерывно менялись на протяжении всей жизни. Начав с химии и перейдя вскоре к теоретической физике, а затем — к небесной механике, он в дальнейшем внес выдающийся вклад в развитие многих разделов современной математики, занимаясь как чисто научными исследованиями, так и вопросами их практического применения. Последний, более чем тридцатилетний период своей научной деятельности он посвятил в основном исследованиям в области теории алгоритмов, математической логики и оснований математики. Вместе со своими учениками он внёс большой вклад в развитие конструктивного анализа, конструктивной логики, в осмысление проблем и понятий, лежащих в основании математической науки.

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

Как и любая другая наука, математика не может считать интуицию основным критерием истины. Интуиция имеет слишком субъективную природу, она у каждого человека своя, а критерий истины должен быть объективным. К счастью, он существует. В естественных науках таким критерием является опыт, а в математике — наличие доказательства. Доказательство представляет собой последовательность утверждений, каждое из которых получается из предыдущих при помощи определенных правил вывода (например, аристотелевских силлогизмов) либо принимается за аксиому. Причем всегда можно однозначно сказать, является ли какое-нибудь утверждение следствием других или нет. Таким образом, для каждой последовательности утверждений можно совершенно однозначно сказать, является оно доказательством или нет. Следовательно, если обнаружено доказательство некоторого факта, то доказуемость этого факта настолько же объективна, насколько объективны данные любого эмпирического опыта.

На рубеже XIX – XX веков две старейшие науки — физика и математика, пережили кризис своих оснований. Эти два кризиса оснований были чем-то похожи друг на друга. В физике причиной кризиса было несоответствие между теоретической картиной мира и данными экспериментов — объективным критерием истины. В математике кризис констатировали тогда, когда были обнаружены совершенно правильные доказательства интуитивно ложных утверждений. Вскрылся неприятный факт: доказуемость и истинность — не одно и то же.

Способы логических рассуждений зависят от того, к каким объектам они применяются. Ни аристотелевская, ни какая-либо другая логика не является абсолютной. Игнорирование этого факта, который в конце XX столетия кажется очевидным, а на протяжении десятков веков никогда в явном виде не осознавался, и привело математику к кризису.

Доказательство, как известно, впервые ввели в математику древние греки. В догреческий период вся математика была интуитивна. То небольшое количество знаний, которое она содержала, сводилось к набору алгоритмических предписаний, позволяющих вычислять или измерять характеристики тех или иных геометрических объектов. Природа этих объектов всегда была проста и интуитивно понятна, способ их построения — очевиден, уверенность в истинности тех или иных соотношений возникала в процессе их непосредственного созерцания.

Греки изобрели абстракцию и, как уже было отмечено, доказательство. Правила вывода, на которых эти доказательства основывались, отражали законы соотношения между геометрическими объектами, а также между частями конечных объектов. Убедившись в истинности этих законов (интуитивным образом, при помощи чего-нибудь вроде кантовского "чистого созерцания"), можно было без риска впасть в противоречие с собственной интуицией проводить рассуждения. Но — только о свойствах упомянутых выше объектов!

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

Геометрические теоремы древних греков были слишком сложны для того, чтобы путем непосредственного созерцания можно было убедиться в их истинности. По крайней мере, на это способен не каждый. В такой ситуации доказательство приобретало все большую и большую привлекательность: оно открывало глаза человеческой интуиции. Вскоре оно настолько вошло в привычку, что подменило собой наглядность и стало абсолютным критерием истины. Из инструмента прояснения истины оно превратилось в инструмент создания иллюзий. И до тех пор, пока иллюзии совпадали с истиной, это было не страшно. Однако начало было положено: уверенность в истинности математических утверждений начала появляться после того, как к этим утверждениям предъявлялось доказательство. Срабатывал эффект гипнотического внушения.

Со временем ситуация изменилась и математики стали рассматривать объекты совершенно другого рода. Однако авторитет греков был столь велик, а убежденность в непогрешимости аристотелевской логики столь сильна, что никому не приходило в голову усомниться в правильности их методов. И эти методы продолжали применять к неподходящим для этого объектам, что рано или поздно должно было привести к противоречию: рациональные аргументы уже не имели под собой рационального основания.

Кризис разразился в конце XIX века. В сравнительно молодой тогда отрасли математики — теории множеств — были обнаружены парадоксы. Разберем самый известный из них: парадокс Рассела. Он формулируется следующим образом: "Пусть R — множество таких множеств, которые не являются своими элементами. Тогда неверно, что множество R является своим элементом и неверно, что множество R не является своим элементом".

Если воспринимать множество на интуитивном уровне, как некоторую произвольную совокупность объектов, то нельзя найти никаких причин тому, что объект вида {x : xx} — не множество. Однако очевидно, что и утверждение вида ¬(RRRR) не может быть истинным. А раз так, то парадокс Рассела показывает, что к такой "интуитивной" теории множеств аристотелевская логика не приложима: силлогизмы уже не отражают реального положения вещей. В мире этих множеств, как в искаженном мире Роберта Шекли, "доказательство истинно лишь для самого себя; оно не свидетельствует ни о чем, кроме наличия доказательств, а это ничего не доказывает".

В связи с подобными парадоксами возникает следующая альтернатива: либо отказаться от доказательств, либо ограничить мир рассматриваемых объектов так, чтобы к ним были применимы законы логики. Отказаться от доказательств было бы чересчур непрактично: объекты современной математики столь сложны, что ни о какой наглядности не может быть и речи, а другой альтернативы доказательству пока не известно. Поэтому математика пошла по второму пути. Было предложено несколько путей выхода из кризиса; некоторые из них будут рассмотрены ниже.

Разногласия между математиками возникли опять же по поводу теории множеств. Если воспринимать множество как некоторую абстрактную совокупность, то это неизбежно ведет к парадоксам. Если же ограничить мир этих совокупностей, то понятие множества теряет смысл. Математика, построенная на теории множеств, в этом случае превращается в ряд высказываний "ни о чем". А незадолго до обнаружения парадоксов Г. Кантор переложил математику на язык теории множеств, причем это переложение оказалось весьма удачным. Теперь же приходилось либо отказываться от теоретико-множественной интерпретации математических объектов, либо признавать наличие в математике бессмысленных утверждений.

Давид Гильберт предложил пойти по второму пути. "Никто не может изгнать нас из рая, который создал нам Кантор" — заявил он. Вместо выбрасывания из математики бессмысленных утверждений он предложил отказаться от самой категории смысла и обосновывать не истинность отдельных доказуемых суждений, а непротиворечивость всей теории в целом (непротиворечивость у Гильберта понимается очень широко, как непротиворечивость со здравым смыслом тех утверждений теории, которые допускают осмысленную интерпретацию). Относительно некоторого широкого класса обоснований непротиворечивости программа Гильберта провалилась в связи с теоремами Гёделя о неполноте, однако в общем случае вопрос о выполнимости этой программы остается открытым (см. [8]).

Представители неклассического направления в математике стоят на другой позиции: они предлагают оставить в ней лишь утверждения, имеющие непосредственный смысл. Неклассических направлений два: интуиционизм и конструктивизм. Их позиции очень сходны: оба они предлагают ограничить математические рассмотрения классом объектов, которые могут быть получены при помощи эффективных построений, исходя из натуральных чисел. Различаются они в понимании эффективности. Интуиционизм существенно опирается на неполноту наших знаний и не желает давать некоторым понятиям чёткого и однозначного определения. Конструктивизм в этом вопросе ближе к классической математике: класс рассматриваемых объектов он чётко формулирует, опираясь на точное понятие алгоритма.

И конструктивисты, и интуиционисты пользуются логикой, отличной от аристотелевской. Этого требует специфика изучаемых ими объектов. В отличие от них представители классического направления, составляющие основную массу математиков, продолжают пользоваться традиционной логикой. Классическая математика, основанная на аксиоматической теории множеств, до сегодняшнего времени так и не получила обоснования. Она превосходит неклассические направления в эффективности методов, однако не застрахована от парадоксов.

"Науки принято классифицировать на “естественные” и “гуманитарные”. Первые изучают природу, вторые — “человеческое общество”. Где-то посередине помещаются ещё “технические науки”, помогающие человеческому обществу “покорять природу”. Какое же место занимает в этой классификации математика? … Математика — “техническая наука" [5].

"Можно, конечно, начать спорить о том, исчерпывается ли цель математики её конструктивной функцией. Мы полагаем, что да, в основном исчерпывается" [4].

"Конструктивная математика может быть коротко охарактеризована как абстрактная умозрительная наука о конструктивных процессах, о нашей способности осуществлять такие процессы и об их результатах — конструктивных объектах" [4].

Наиболее важное место в системе Маркова занимает логическое обоснование конструктивной математики. "Конструктивная математика нуждается в своей логике, отличной от логики классической — в конструктивной математической логике" — пишет он. В ряде своих работ он предпринимает попытку разработать эту логику. Так, статья [4] — "эскизное и беглое описание того, как, по мнению автора, должна строиться логика конструктивной математики". В статье [2] он дает это описание на более профессиональном уровне, с построением формального исчисления. Дадим краткую характеристику его логической системы.

В конструктивной математике утверждение считается истинным тогда и только тогда, когда в его истинности можно убедиться при помощи некоторого конструктивного процесса. Так, например, истинным признаётся утверждение о существовании объекта, если и только если для этого объекта можно указать способ его построения. Дизъюнкция полагается истинной не тогда, когда истинен один из дизъюнктивных членов, а когда существует конструктивный процесс, способный в результате работы указать этот истинный член. Всё это резко отличается от того, что можно видеть в классической математике. Вот простой пример: предложение (x)[(x=0  A)  (x=1  ¬A)] истинно в классической математике и ложно в конструктивной, если A — не доказуемое и не опровергаемое утверждение. В общем случае в конструктивной логике не верны и закон исключённого третьего (A  ¬A), и закон снятия двойного отрицания (¬¬A  A). Общим с классической логикой у Маркова является лишь понимание конъюнкции. Истинность универсального утверждения вида xA(x) равносильна у него существованию алгоритма, позволяющего по слову  получать доказательство утверждения A(). Импликация и отрицание понимаются у него в трех смыслах: материальном, усиленном и дедуктивном. Не останавливаясь на первых двух, рассмотрим третий. Импликация вида A  B считается истинной (в дедуктивном смысле), если в некотором формальном исчислении, построенным Марковым, имеет место выводимость A  B. Дедуктивное отрицание ¬A понимается как дедуктивная импликация A  , где  — заведомо ложное утверждение. Конструкция упомянутого формального исчисления, имеющая вид башни языков первого порядка (L₀, L₁, …, L_, …), довольно интересна, но мы на ней задерживаться не будем.

В заключение следует сказать о предложенном Марковым методе конструктивного подбора. В этом методе, основанном на принципе конструктивного подбора, утверждается, что алгоритм завершит свою работу, если предположение о том, что этот алгоритм не окончит свою работу ни на каком шаге, опровергнуто. В общем виде принцип конструктивного подбора формулируется следующим образом: "Пусть для свойства D имеется алгоритм, выясняющий для всякого натурального числа n, обладает ли n свойством D. Если опровергнуто предположение о том, что ни одно число не обладает свойством D, то имеется натуральное число со свойством D", или, формально: ¬xD(x)  xD(x), где D — рекурсивный предикат. На первый взгляд принцип конструктивного подбора не конструктивен, но на самом деле это не так: ведь имеется алгоритм, позволяющий находить число n, такое что истинно утверждение D(n). Вот этот алгоритм: "Перебирая по очереди числа 0, 1 ,2, …, проверять, обладают ли они свойством D. Как только окажется, что какое-то n обладает свойством D, выдать его в качестве результата работы алгоритма".

А. Марков высказывается за включение в конструктивную математику принципа конструктивного подбора. Вот что он пишет по этому поводу:

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

Однако это второе, главное, достоинство системы Маркова оборачивается и её главным недостатком. Недостаток этот — непоследовательность. Марковская конструктивная математика не столь сильно отличается от классической, как интуиционизм: Марков строит свою систему как бы "на фоне" системы классической.

Это видно хотя бы из того, что Марков в своих работах обнаруживает склонность подчёркивать различия между классическим и конструктивным пониманием терминов. Можно, конечно, объяснить это тем, что он вынужден постоянно бороться с классическими предрассудками и следить, чтобы они не проникли в конструктивизм. Но мне кажется, что всё не так просто. Приведу два примера.
Пример 1. Существуют утверждения, которые нельзя ни доказать, ни опровергнуть. Более того, такие утверждения не просто существуют, но и выписываются в явном виде конструктивным образом (то есть существуют даже в конструктивном смысле). Но показать, что эти утверждения не доказуемы и не опровергаемы, можно лишь методом "от противного". Для человека, мыслящего конструктивно, эти утверждения не доказуемыми и не опровергаемыми не являются. А Марков признаёт существование таких утверждений и даже использует их в примере, иллюстрирующем различие между классическим и конструктивным пониманием дизъюнкции (A Ú ¬A — утверждение, истинное в классической математики и не истинное в конструктивной, если A не доказуемо и не опровергаемо).
Пример 2. По Маркову вычислительный процесс называется конструктивным, если он описывается алгоритмом, то есть если существует алгоритм, следуя которому мы осуществляем упомянутый выше процесс. Да, но в каком смысле существует: в конструктивном или в классическом? Марков понимает такое существование в классическом смысле. Да существование в конструктивном смысле здесь и просто невозможно, что следует из следующего рассуждения.

Предположим, что мы хотим доказать существование некоторого алгоритма. Для этого мы должны будем показать, что существует алгоритм №2, который даёт результатом своей работы доказательство существования нашего алгоритма (алгоритма №1), или, говоря короче, делает возможным существование алгоритма №1. Но тогда должен существовать алгоритм №3, делающий возможным существование алгоритма №2. Существуют также алгоритмы №4, №5 и т.д. Воспользовавшись принципом конструктивного подбора, можно заключить, что для каждого натурального числа n существует алгоритм с номером n+1, делающий возможным существование алгоритма с номером n (в конструктивном смысле, то есть существует алгоритм lxD(x), такой что D(n) — алгоритм с номером n+1), ведь, в самом деле, условие "x — алгоритм D(n)" конструктивно и можно отыскать его доказательство для некоторого конкретного x=x₀, перебирая все числа x₀ и все доказательства. Продолжая рассуждать подобным образом и пользуясь необходимое число раз принципом конструктивного подбора, можно заключить, что для каждого набора чисел n₁,…,n_k существует алгоритм D(n₁,…,n_k), такой что D(0,n₂,…,n_k) выдаёт в качестве результата своей работы алгоритм D(n₂,…,n_k), а D(n+1,n₂,…,n_k) выдаёт D(n,n₂,…,n_k) для произвольного натурального n. Но опять же по принципу конструктивного подбора существует алгоритм xD'(x), для которого D'(α) = D(n₁,…,n_k), если α = "n₁,…,n_k". И так далее. Нетрудно видеть, что каждому конструктивному ординалу  ставится в соответствие алгоритм D_ и, наоборот, каждый полученный описанным выше способом алгоритм ставится в соответствие некоторому конструктивному ординалу. А поскольку множество конструктивных ординалов не имеет максимального элемента, то не существует алгоритма, делающего возможным существование любого другого алгоритма. Значит, для доказательства существования алгоритма №1 требуется доказать существование бесконечного множества других алгоритмов, что, очевидно, невозможно: множество конструктивных ординалов не конструктивно, не описывается алгоритмически и, следовательно, не может существовать без привлечения абстракции актуальной бесконечности. А поскольку в конструктивной математике существование понимается как возможность эффективного построения, то такой вещи, как доказательство существования алгоритма, в конструктивизме Маркова просто не существует.

Приведённое выше рассуждение, использующее принцип конструктивного подбора и приводящее к парадоксальной ситуации, является, по сути дела, доказательством от противного. Как же опровергает его Марков? А никак. Он то ли его просто не замечает, то ли неожиданно вспоминает о том, что он конструктивист и со своей, чисто конструктивистской точки зрения, не видит здесь никакого парадокса. А ведь, как показывает это рассуждение, с точки зрения последователей Аристотеля принцип конструктивного подбора ставит под сомнение всю конструктивную онтологию.
Нетрудно понять, чем руководствовался А. А. Марков, предлагая включить в конструктивную математику принцип конструктивного подбора. А именно, чисто практическими соображениями: слишком многое он позволяет. Принцип конструктивного подбора — эта такая мощная вещь, что … ну, в общем, в математике без неё никуда. Особенно если приходится иметь дело с формальным определением алгоритма.

Однако аргументация Маркова в пользу принципа конструктивного подбора выдаёт его с головой. Если рассуждать строго, утверждение "ПКП верен" истинно в классическом понимании понятия "истинность утверждений" и ложно в конструктивном. Когда Марков приходит к выводу о существовании алгоритма, позволяющего находить n, такое что истинно D(n) (см. выше), он приходит к этому выводу при помощи неконструктивных рассуждений. Марков не конструктивист, он исследует конструктивность классическими методами. В ходе своих исследований он не приходит ни к каким выводам, он смотрит, к каким выводам пришёл бы конструктивист.

И всё же, конструктивен ли принцип конструктивного подбора? По-видимому, ставить вопрос таким образом просто бессмысленно. То, что мы называем принципом конструктивного подбора, не является ни математическим объектом, ни вычислительным процессом. Правильнее всего было бы сказать, что ПКП является аксиомой конструктивной математики. Последовательный конструктивист должен принимать эту аксиому на веру: то рассуждение, которое обосновывает ПКП, для конструктивиста доказательством не является.

Но даже и это не совсем верно. Для полной ясности в этом вопросе хотелось бы понять, чем же всё-таки занимаются конструктивисты: сознательно и целенаправленно обкрадывают свой ум или пытаются вылечить математиков от сумасшествия, именуемого "доказательство от противного"? Методы классической математики кажутся им сомнительными? Превосходно. Но зачем тогда класть в основание своей науки утверждение, в истинности которого можно убедиться лишь этими самыми сомнительными методами?

Интересно, способен ли прийти к идее принципа конструктивного подбора ортодоксально мыслящий конструктивист? Не тот, который пытается доказать неконструктивными методами конструктивность некоторых из существующих объектов, а тот, для которого конструктивность равносильна существованию. Мне кажется, что нет, не сможет. Для ортодоксального конструктивиста понятия конструктивности не существует. Если же он попытается его ввести, то оно окажется равносильным таким понятиям, как "Сущее", "Мир", "Вселенная". Неконструктивный — значит абсурдный. Абсурдный — значит способный существовать лишь в воображении. В больном воображении. В мире конструктивистов нет места таким понятиям, как принцип конструктивного подбора: люди, отвергающие по идейным соображениям абстракцию актуальной бесконечности, обязаны мыслить более конкретно.

Таким образом, по интересующему нас вопросу существуют следующие мнения:

[2]  Марков А. А. Попытка построения логики конструктивной математики. // Исследования по теории алгоритмов и математической логике. т. 2. М. 1976.

[3]  Марков А. А. Математическая логика и вычислительная математика. // Математизация научного знания. М. 1972.

[4]  Марков А. А. О логике конструктивной математики. // Вестник МГУ, Сер. 1 Математика, механика. 1970. №2.

[5]  Марков А. А. Что такое конструктивная математика. // Закономерности развития современной математики. М. 1987.

[6]  Нагорный Н. М. Современные основания математики: восхождение к конструктивности. // Закономерности развития современной математики. М. 1987.

[7]  Непейвода Н. М. Становление понятия конструктивности в математике. // Закономерности развития современной математики. М. 1987.

[8]  Ершов Ю. Л., Самохвалов К. Ф. О новом подходе к методологии математики. // Закономерности развития современной математики. М. 1987.

[9]  Философская энциклопедия. М. 1964. ст. "Конструктивное направление", "Интуиционизм".

[10] Математическая энциклопедия. М. 1979. ст. "Абстракция актуальной бесконечности", "Интуиционизм", "Конструктивная логика", "Конструктивная математика", "Конструктивная семантика", "Конструктивного подбора принцип", "Конструктивный объект".