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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Абстракции конструктивной математики[править | править вики-текст]

Абстрактность конструктивной математики проявляется в систематическом применении двух основных отвлечений: абстракции отождествления и абстракции потенциальной осуществимости.

Абстракция отождествления состоит в предположении о возможности однозначного и не вызывающего сомнений решения вопроса о (графическом) равенстве или различии любых двух рассматриваемых нами конструктивных объектов, а также о возможности полного отвлечения от мелких различий, имеющихся между графически равными объектами. Случаи, когда указанные предположения не выполняются, заранее исключаются из рассмотрения. Так, при рассмотрении слов в кириллическом алфавите мы исключаем из рассмотрения случаи, когда не можем прочитать слово (вследствие неразборчивости почерка или, например, вследствие повреждения запоминающего устройства ЭВМ, в которое слово было занесено).

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

Основные объекты рассмотрения[править | править вики-текст]

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

Особенности логики конструктивной математики[править | править вики-текст]

Характерной чертой конструктивных объектов является то обстоятельство, что они не существуют извечно. Они рождаются в результате развёртывания некоторых конструктивных процессов, а затем исчезают (в силу самых различных естественных причин). Алгебраическое выражение, написанное мелом на доске, находилось на этой доске не всегда — и просуществует на ней ровно до того момента, пока его не сотрут. Таблица, сохранённая на жёстком диске персональной ЭВМ, также заведомо не существовала до момента изготовления этого диска — и также рано или поздно будет уничтожена (или в результате переформатирования, или в результате выхода диска из строя).

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

Понимание существования объекта как потенциальной осуществимости приводит к тому, что логические законы, действующие в конструктивной математике, оказываются отличными от классических. В частности, теряет универсальную применимость закон исключённого третьего. Действительно, формула (A\lor(\neg A)) при конструктивном понимании выражает суждение

«среди формул A и (\neg A) потенциально осуществима верная»,

однако классический вывод дизъюнкции (A\lor(\neg A)) не даёт никакого способа построить её верный член. Аналогичным образом, логическое опровержение предположения, что любой конструктивный объект рассматриваемого вида обладает некоторым свойством T — считающееся в теоретико-множественной математике достаточным основанием признать «существующим» объект со свойством (\neg T), — не может само по себе служить поводом для признания объекта со свойством (\neg T) потенциально осуществимым. Следует заметить, однако, что за такого рода логическими опровержениями всё же признаётся определённая эвристическая ценность (так как они, хотя и не дают никакого способа построения искомого объекта, всё же указывают на осмысленность попыток такого построения). Конструктивные объекты, для которых удалось в рамках классической логики доказать их «существование», принято называть квазиосуществимыми.

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

«для любого конструктивного объекта X рассматриваемого вида потенциально осуществим конструктивный объект Y, находящийся в отношении T к объекту X»

означает наличие в нашем распоряжении единого общего метода (алгоритма) переработки объекта X в отвечающий ему объект Y. Поэтому такое суждение может быть заведомо неверным даже в случае верности суждения

«для любого конструктивного объекта X рассматриваемого вида квазиосуществим конструктивный объект Y, находящийся в отношении T к объекту X».

Некоторые конкретные теории конструктивной математики[править | править вики-текст]

Конкретные математические теории, развиваемые в рамках представлений конструктивной математики, обладают рядом существенных отличий от соответствующих теоретико-множественных теорий.

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

\forall n\in\mathbb N\, |\mathfrak A(n)-\mathfrak A(n+1)|\le 2^{-n-1}.

Такие записи представляют собой конструктивные объекты и допускаются к рассмотрению в конструктивной математике. Как обычно, два вещественных числа \mathfrak A и \mathfrak B считаются равными, если выполняется условие

\forall n\in\mathbb N\, |\mathfrak A(n)-\mathfrak B(n)|\le 2^{-n+1}.

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

«любые два вещественных числа или равны, или не равны»

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

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

С другой стороны, в конструктивном анализе доказывается ряд утверждений, не имеющих теоретико-множественных аналогов. Одним из наиболее ярких примеров здесь является теорема Г. С. Цейтина о непрерывности любого отображения из сепарабельного метрического пространства в метрическое пространство. Из этой теоремы следует, в частности, что любое отображение метрических пространств является непрерывным по Гейне. Следует заметить, что известны примеры отображений из несепарабельных пространств, которые не являются непрерывными по Коши. Таким образом, в конструктивной математике может быть опровергнуто на примерах утверждение об эквивалентности непрерывности отображения по Коши и по Гейне, доказываемое в классическом анализе на основе привлечения сильных теоретико-множественных средств (в частности, аксиомы выбора).

Литература[править | править вики-текст]

  • Марков А. А. Избранные труды. — М.: Изд-во МЦНМО, 2003. — Т. II. Теория алгоритмов и конструктивная математика, математическая логика, информатика и смежные вопросы. — 626 с. — ISBN 5-94057-113-1.
  • Марков А. А., Нагорный Н. М. Теория алгорифмов. — 2-е изд.. — М.: ФАЗИС, 1996.
  • Нагорный Н. М. Абстракция актуальной бесконечности, Абстракция отождествления, Абстракция потенциальной осуществимости // Математическая энциклопедия / И. М. Виноградов (гл. ред.). — М.: Советская энциклопедия, 1977. — Т. 1. — С. 43, 44. — 576 с. — 150 000 экз.
  • Кушнер Б. А. Лекции по конструктивному математическому анализу. — М.: Наука, 1973. — 447 с.
  • Кушнер Б. А. Конструктивная математика, Математическая энциклопедия. — М.: Советская энциклопедия, 1979. — Т. 2. — 1042 с.
  • Кондаков Н. И. Логический словарь-справочник. — М.: Наука, 1975. — 259 с.
  • Рузавин Г. И. О природе математического знания. — М.: Мысль, 1968. — 302 с.
  • Акимов О. Е. Дискретная математика: логика, группы, графы. — 2-е изд. — М.: «Лаборатория Базовых Знаний», 2003. — 376 с.

См. также[править | править вики-текст]