«Конструктивная математика»

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

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

Понятия конструктивного процесса и конструктивного объекта не определяются в К. м. В таких общих определениях и нет надобности, поскольку в К. м. обычно имеют дело не с конструктивными процессами и конструктивными объектами вообще, а с определёнными видами тех и других.

Простейшим видом конструктивных объектов являются слова в фиксированном алфавите, т. е. ряды букв этого алфавита (слово «буква» понимается здесь как «элементарный знак», т. е. как «знак, частями которого мы не интересуемся»; алфавит — это набор букв). Конструктивный процесс, результатом которого является слово, состоит в данном случае в выписывании этого слова буква за буквой. Частным случаем слов являются натуральные числа, которые мы рассматриваем как слова в алфавите 01, начинающиеся с нуля и, кроме того, нуля не содержащие, т. е. как слова 0, 01, 011, 0111,... Добавляя к этому алфавиту знак минус «—» и знак дроби «/», получают возможность строить рациональные числа как некоторые слова в алфавите 01 — /. Т. о., рациональные числа оказываются конструктивными объектами.

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

Конструктивной последовательностью рациональных (натуральных) чисел будет называться алгорифм, перерабатывающий всякое натуральное число в рациональное (натуральное) число. Без существенного ограничения общности можно считать конструктивную последовательность рациональных чисел алгорифмом в алфавите 01 — /ab. Запись такого алгорифма будет осуществляться как слово в алфавите 01. О конструктивной последовательности рациональных чисел n соблюдается условие

|n) - n+1)|≤ 2^-n-1.

Записи регулярно сходящихся последовательностей рациональных чисел называют конструктивными действительными числами (КДЧ). Естественным образом определяются равенство двух КДЧ, порядковые отношения между ними, а также арифметическими действия над ними и операция взятия абсолютной величины. Арифметические операции оказываются алгорифмическими: имеется, например, алгорифм, перерабатывающий всякую пару КДЧ в сумму этих КДЧ. С другой стороны, невозможен алгорифм, распознающий КДЧ среди слов в алфавите 01; невозможен алгорифм, распознающий равенство КДЧ.

Далее, на основе алгоритмов теории (См. Алгоритмов теория)можно определить понятие конструктивной последовательности КДЧ. Для всякой такой последовательности оказывается возможным построить КДЧ, не равное ни одному члену этой последовательности. Это — конструктивный аналог теоремы Кантора о несчётности континуума.

Могут быть определены понятия конструктивной сходимости конструктивной последовательности КДЧ в себе и к КДЧ. Имеет место теорема полноты, утверждающая, что всякая конструктивная последовательность КДЧ, конструктивно сходящаяся в себе, конструктивно сходится к некоторому КДЧ. Однако конструктивный аналог известной теоремы о сходимости ограниченной возрастающей последовательности опровергается на примере.

Согласно определению, КДЧ — слова в алфавите 01. Алгорифмы над этим алфавитом можно применять к КДЧ, что открывает возможность строить функцию от действительного переменного как алгорифм, перерабатывающий КДЧ в КДЧ. Надо только, чтобы такой алгорифм был согласован с равенством — равные КДЧ он должен перерабатывать в равные КДЧ. Т. о., получается следующее определение — алгорифм F над алфавитом 01 есть конструктивная функция действительного переменного, если соблюдаются следующие условия: 1) F перерабатывает всякое КДЧ, к которому он применим, в КДЧ; 2) всякий раз, когда F применим к каким-либо КДЧ х, он применим и ко всякому КДЧ у,равному х, и КДЧ F(x) и F(y) равны.

На основе этого определения была разработана конструктивная теория функций действительного переменного. Одним из наиболее интересных её результатов является теорема о непрерывности конструктивных функций: всякая конструктивная функция действительного переменного непрерывна всюду, где она определена. Вместе с тем выяснено, что в теории конструктивных функций не имеют место аналоги классических теорем Вейерштрасса и Кантора о непрерывных функциях на сегменте. В частности, были построены: 1) неограниченная конструктивная (и потому непрерывная) функция на сегменте [0,1]; 2) ограниченная на этом сегменте конструктивная функция, не имеющая точной верхней границы; 3) конструктивная функция, имеющая на сегменте [0,1] точную верхнюю границу, но не достигающая её; 4) ограниченная на сегменте [0,1] конструктивная функция, не являющаяся равномерно непрерывной ни на каком сегменте, содержащемся в сегменте [0,1]. Эти результаты выявляют глубокое отличие конструктивного математического анализа от анализа теоретико-множественного.

В настоящее время (70-е гг. 20 в.) успешно разрабатываются многие отделы К. м.: конструктивные теории дифференцирования и интегрирования, конструктивная теория метрических пространств, конструктивный функциональный анализ, конструктивная теория функций комплексного переменного и др.

Лит.: Марков А. А., Теория алгорифмов, «Тр. Математического института АН СССР», 1954, т. 42; Проблемы конструктивного направления в математике, в. 1—5, там же, 1958, т. 52; 1962, т. 67; 1964, т. 72; 1967, т. 93; 1970, т. 113; Фан Динь Зиеу, Некоторые вопросы конструктивного функционального анализа, там же, 1970, т. 114.

А. А. Марков.

конструктивное направление в математике,- математика, строящаяся в соответствии с тем или иным конструктивным математич. мировоззрением, обыкновенно стремящимся связывать утверждения о существовании математнч. объектов с возможностью их построения и отвергающим в силу этого ряд установок традиционной теоретико-множественной математики, приводящих к появлению чистых теорем существования (в частности, абстракцию актуальной бесконечности и универсальный характер исключенного третьего закона). Конструктивная тенденция в математике проявлялась в той или иной форме на протяжении всей ее истории, хотя, по-видимому, только К. Гаусс (С. Gauss) впервые отчетливо выразил принципиальное для К. м. различие становящейся (потенциальной) и актуальной математнч. бесконечности и возразил против употребления последней. Дальнейшие критические шаги в этом направлении были сделаны Л. Кронекером (L. Кrоnесkеr), А. Пуанкаре (Н. Poincare) и особенно Л. Брауэром (L. Brouwer). В критике Л. Брауэра, совпавшей по времени с кризисом оснований математики конца 19 - нач. 20 вв., энергично, отвергалась как вера в экзистенциальный характер бесконечных множеств, так и убеждение в допустимости неограниченной экстраполяции классических логических принципов, в особенности закона исключенного третьего. В качестве альтернативы теоретико-множественному подходу Л. Брауэр, а затем и его последователи, разработали оригинальную программу построения математики, известную ныне под названием интуиционизм. Интуиционистскую математику Л. Брауэра можно считать первой систематич. попыткой построения математики на конструктивной основе. Параллельно успехам интуиционистов в созданной Д. Гильбертом (D. Hilbert) с целью обоснования теоретико-множественной математики доказательств теории был четко выявлен ряд первоначальных понятий, послуживший впоследствии отправной точкой отличных от интуиционизма конструктивных течений. Значительная часть соответствующих работ (при этом обнаружился достаточно широкий спектр толкования различными исследователями терминов "конструктивный", "эффективный" и пр.) опиралась на успехи, достигнутые (опять-таки под влиянием идей Д. Гильберта) в изучении математич. понятия алгоритма. Один из наиболее последовательных и законченных подходов к построению К. м. на этой основе доставляется основанной А. А. Марковым советской школой К. м., формирование основных понятий к-рой относится к 50-м гг. 20 в. Сам термин "К. м." (конструктивное направление в математике) часто употребляется в узком смысле слова для именования математики, строящейся советским конструктивным направлением; ниже этот термин будет использоваться именно в указанном только что смысле.

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

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

Рассмотрение слов (это понятие также представляется первоначальным) происходит на следующей основе.

Вначале фиксируется нек-рый алфавит, т. е. список неразложимых, уверенно отличимых друг от друга элементарных знаков (букв). Каждая буква алфавита может копироваться; возникающие в результате последовательных актов такого копирования прямолинейные цепочки знаков считаются словами в исходном алфавите. К словам в данном алфавите удобно отнести также и пустое слово, т. е. цепочку, не содержащую ни одного знака. Напр., цепочки (5) "авввссд" и (6) "книга" являются словами в русском алфавите. При обращении со словами К. м.- и в этом проявляется ее абстрактный характер - использует абстракции отождествления и потенциальной осуществимости. Первая из них позволяет, отвлекаясь от различий копий и оригинала, говорить о разных копиях данной буквы и о ней самой, как об одной букве. Напр., говорят, что в слово (5) три раза входит буква "в" русского алфавита, тогда как в действительности при написании данного слова воспроизводились три различных конкретных копии исходной буквы. Это соглашение естественным образом распространяется на одинаковые по написанию (графически равные) слова. Напр., о двух конкретных словах: слове "книга" и слове (6) говорят как об одном слове. В допущении абстракции отождествления проявляется предполагаемая К. м. первоначальная способность человека к "чтению" слов, т. е. к многократному и устойчивому опознанию знаковых цепочек как одинаковых или различных. На это обстоятельство как минимальную предпосылку любой научной деятельности указывал Д. Гильберт. Абстракция потенциальной осуществимости позволяет пренебрегать в рассуждениях о написании слов реальными ограничениями в пространстве, времени и материале. Таким образом, о воображаемых очень длинных словах начинают рассуждать как о реально существующих, в частности считается возможным к любому данному слову приписать справа (или слева) любое другое слово. Отсюда вытекает и возможность рассмотрения сколь угодно больших натуральных чисел, а также сложения любых двух натуральных чисел, поскольку натуральными числами можно, напр., считать слова вида 0, 0|, 0|| и т. д. в алфавите 0|. Вместе с тем абстракция потенциальной осуществимости не позволяет рассматривать как своего рода завершенные объекты "бесконечные" слова и совокупность "всех" слов в данном алфавите (в частности, не рассматривается как завершенный объект и натуральный ряд). Такого рода рассмотрения требуют привлечения более сильной абстракции - абстракции актуальной бесконечности, к-рая отвергается К. м.

Принятие абстракции потенциальной осуществимости приводит к тому, что наряду с элементарными, целиком обозримыми конструктивными процессами (напр., написанием коротких слов) рассматриваются воображаемые, не подлежащие реальному воспроизведению конструктивные процессы. Такие процессы задаются своими предписаниями; сами эти предписания по существу и становятся предметом исследования. Задающее конструктивный процесс предписание (для простоты речь идет о процессах, оперирующих со словами) должно быть общепонятным и совершенно однозначно определять шаг за шагом последовательное построение слов, причем шаги должны быть элементарными, т. е. не предполагать ничего, кроме умения читать, писать (и стирать) слова. Шаги эти, таким образом, сводятся к написанию и графическому сравнению нек-рых слов, а также к замене вхождений одних слов в другие третьими словами. Окончание процесса определяется самим предписанием и может зависеть от результатов, полученных на шагах, предшествующих заключительному, причем принятие решения о заключительном характере данного шага также должно носить описанный только что элементарный характер. Возможна ситуация, когда никакой шаг не оказывается заключительным, т. е. после каждого совершенного шага данное предписание требует совершить следующий шаг. Такому предписанию не соответствует никакой потенциально выполнимый конструктивный процесс, однако здесь оказывается удобной условная терминология, согласно к-рой соответствующее предписание определяет неограниченно продолжаемый (потенциально бесконечный) процесс. Для оправдания этой терминологии можно было бы также расширить исходные представления о конструктивных процессах, рассматривая наряду с потенциально реализуемыми процессами более абстрактные образования - процессы, отождествляемые с их предписаниями. В связи с появлением неограниченно продолжаемых конструктивных процессов возникает вопрос о средствах, при помощи к-рых можно убедиться в обрываемости задаваемого данным предписанием конструктивного процесса. К. м. принимает здесь важный принцип, называемый конструктивного подбора принципом и позволяющий устанавливать такие факты методом от противного, т. е. приводя к нелепости предположение о неограниченной продолжаемости соответствующего конструктивного процесса. Примеры предписаний: (7) написать|; (8) к произвольному слову в алфавите 0| приписать справа|; (9) п. 1: написать| и перейти к п. 2; п. 2: стереть| (т. е. заменить эту букву пустым словом) и перейти к п. 1; (10) п. 1: к произвольному слову в алфавите 0| приписать справа J и перейти к п. 2; п. 2: если обрабатываемое в данный момент слово совпадает с 0||, то закончить процесс, в противном случае вернуться к п. 1; (11) п. 1: написать 0 и перейти к п. 2; п. 2: к обрабатываемому в данный момент слову приписать справа| и перейти к п. 3; п. 3: если получилось совершенное натуральное число, то закончить процесс, в противном случае приписать к обрабатываемому в данный момент слову справа| и перейти к п. 2. Предписание (7) задает конструктивный процесс, оканчивающийся за один шаг написанием однобуквенного слова|. Процесс выполнения (9) неограниченно продолжаем. В настоящее время (к 1978) неизвестно, заканчивается ли конструктивный процесс, задаваемый (11) (в (11) для краткости использовались понятия теории чисел; ясно, что возможно более длинное предписание этого рода, опирающееся исключительно на возможности чтения, написания и сравнения слов в алфавите 0|). Несколько особый характер имеют предписания (8) и (10): их выполнение может начинаться с любого слова в указанном алфавите, при этом конструктивный процесс, определяемый (8), всегда заканчивается, в то время как в случае предписания (10) он неограниченно продолжаем при нек-рых исходных словах. Предписания указанных типов принято называть алгоритмами (в данном контексте речь идет об алгоритмах, оперирующих со словами).

К необходимости рассмотрения алгоритмов приводит конструктивная трактовка экзистенциальных утверждений. Утверждение о существовании конструктивного объекта с данным свойством, т. е. утверждение вида (12) в соответствии с представлениями о конструктивных объектах как результатах конструктивных процессов считается в К. м. установленным только в том случае, когда указан потенциально выполнимый конструктивный процесс, заканчивающийся построением искомого объекта. Соответственно установление параметрического утверждения существования (13) " хEyА( х, у)("для всякого хсуществует утакой, что ( х, у)")предполагает указание "общего" конструктивного процесса, начинающегося с произвольного конструктивного объекта хданного исходного типа и заканчивающегося построением искомого у. Другими словами, (13) выражает существование алгоритма, находящего у, исходя из х. Из такой трактовки существования вытекает и конструктивное понимание дизъюнкции:суждение АЪВ("А или В") считается установленным, только если предъявлен конструктивный процесс, заканчивающийся указанием его верного члена. Дальнейшее разъяснение смысла суждений более сложной структуры и выработка правил обращения с ними, соответствующих исходным конструктивным установкам, составляет задачу конструктивной семантики и конструктивной логики. Приведенная конструктивная трактовка утверждений существования и дизъюнкции существенно отличается от традиционной: в теоретико-множественной математике, напр., суждение (12) может быть доказано приведением к нелепости его отрицания. Такое доказательство обыкновенно не содержит никакого способа построения искомого конструктивного объекта. К. м. считает, что подобное рассуждение доказывает не (12), а его "двойное отрицание", т. <е. щщ ExА (х). Последнее суждение рассматривается в К. м. как, вообще говоря, более слабое, чем (12). Таким образом, К. м. не принимает закона снятия двойного отрицания, а, следовательно, и закона исключенного третьего (на отсутствие оснований для принятия последнего указывает и конструктивная трактовка дизъюнкции).

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

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

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

Лит.:[1] Френкель А.-А., Бар-Хиллел И. Основания теории множеств, пер. с англ., М., 1966; [2] Гейтинг А., Интуиционизм. Введение, пер. с англ., М., 1965; [3] Гильберт Д., Основания геометрии, пер. с нем., М., 1948; [4] Constructivity in mathematics, Amst., 1959; [5] Марков А. А., Теория алгорифмов, М., 1954 (Тр. Матем. ин-та АН СССР, т. 42); [6] его же, О логике конструктивной математики, М., 1972; [7] Проблемы конструктивного направления в математике, в. 1-6, М.- Л., 1958-73 (Тр. Матем. ин-та АН СССР, т. 52, 67, 72, 93, 113, 129).

См. также лит. при ст. Конструктивный анализ.

В. А. Кушнер.

конструкти́вна матема́тика

конструкти́вна матема́тика