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

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

2. КОНСТРУКТИВНАЯ СЕМАНИТКА КАК СОВОКУПНОСТЬ СПОСОБОВ ПОНИМАНИЯ СУЖДЕНИЙ В КОНСТРУКТИВНОЙ МАТЕМАТИКЕ.

Небоходимость в особой семантике вызвана различием общих принципов, лежащих в основе традиционной (классической) и конструктивной математики. Особое внимание конструктивная семантика уделяет суждениям о конструктивных объектах в языках первого порядка, то есть, по существу, арифметическим суждениям. Принципиальные различия с традиционной семантикой в понимании дизъюнкций A 0 Ú A 1 сформулированы Л. Брауэром. Контструктивное обоснование таких сужднеий требует решения задачи: найти число i £ 1 такое, что верно A i (соответственно найти число n такое, что А( n)). Общие принципы описания задач, соответствующих более сложным формулам юыли намечены А. Гейтингом и А.Н.. Колмогоровым. Точная формулировка (которая стала возможна после появления математического определения алгоритма) была дана С. Клини в виде понятия реализации замкнутой арифметической формулы. Реализация вернорго равенства t=r есть фиксированнная константа, например число 0, а ложное равенство не имеет реализаций. Реализация конъюнкции А &В –это пара ( a,b) ,где a – реализация А, а b – реализация В . Реализация дизъюнкции A 0 Ú A 1 - это пара (i,a) , где i =0,1 и a - реализация суждения A 1 . Реализация суждения $ х A (х) - это пара (n,a) , где n – число, a – реализация суждения А(n). Реализация суждения " х A (х) - этообщий метод ¦ , который по всякому натуральному n выдаёт реализацию ¦ (n) суждения А(n). Реализация суждения А É В – это общий метод ¦ , который по всякой реализации а суждения А выдаёт реализацию ¦ (а) суждения В (и может быть не определён для аргументов а, не являющихся реализациями А ). При этом общий метод понимается как алгоритм (частично рекурсивная функция). Используя кодирование алгоритмов числами, можно записать условие «число е есть реализация формулы А» в виде арифметической формулы (erA) , не содержащей дизъюнкции V и содержащей существование $ только перед равенствами. Такие формулы называются почти нормальными. Суждение $ e (erA) (читаемое «А реализуемая») может служить конструктивным разъяснением суждения А. При таком понимании закон исключённого третьего " х ( A (х) Úù А (х)) опровергается, например, для A (x) = E y T (x,x,y), где T (e,x,y) означает, что алгоритм (с кодом) е заканчивает работу над аргументом x за у шагов. Опровергается и закон двойного отрицания " х ( ù ù В (х) É В (х)), например для В (х)= A (х) Úù А (х). Приведенное определение связывает конструктивную задачу (поиск реализации) со всяким суждением A , даже если А не содержит Ú, $. Предложенный Н.А. Шаниным алгоритм выявления конструктивной задачи не меняет формул без Ú, $ (нормальных формул) и эквивалентен реализуемости в формальной интуиционистической арифметике с бескванторной индукцией. Произвольные формулы сводятся к почти нормальным, так как основания для почти нормальных формул, содержащих Ú и нетривиальное $.

А.А. Марков определяет истинность для почти нормальных формул с помощью выводимости по обычным правилам для рассматриваемых логических связок плюс эффективное w-правило: если имеется общий метод, позволяющий для любого n устанавливать выводимость А( n) из суждения К, то " х A(х) выводимо из К.. Истинность определяется постепенно. Язык Я w , состоящий из из формул без É , " ; язык Я n+1 , n ³ 1 , включая Я n и формулы, которые можно построить из формул языка Я n одним применением импликации и любым числом применений А, &. Истинность для Я 1 – формул – это выводимость по обычным правилам для &, $, Ú. Истинность для Я 2 - формул определяется через допустимость соответствующего правила. Например, истинность $ х R (х ) É $ y T (y) означает наличие алгоритма j такого, что R (n) É T ( j ( n ) ) для любого числа n. Для Я n+1 – формул при n>1 истинность конъюкций и " - формул определяется обычным образом через истинность компонента, а истинность импликации А É В означает выводимость В из А по некоторым правилам S n , о которых уже доказано, что они сохраняют истинность Я n – формул. Системы S n содержат w-правило, а в качестве аксиом – все истинные Я n – формулы. Понятие выводимости в S n вводится обобщенным индуктивным определением, а для доказательства метатеорем применяется соответствующий принцип индукции. Индукцией по S 2 – выводу доказывается допустимость правила " É ù ù $ х R - А É $ х R . Оно включается в S 3 и даёт принцип Маркова ù ù $ х R É $ х R.. Системы S n+3 , n ³ 1, состоят из обычных правил для рассматриваемых связок, включая w -правило. Оказывается, что почти нормальная формула А истинна по Маркову тогда и только тогда, когда примитивно рекурсивное дерево T а поиска вывода формулы А без сечения (но с w -правилом и принципом Маркова) является выводом в смысле индуктивного определения. Это эквивалентно (в рамках классической математики) классической истинности А .

В мажоритальной семантике Н.А. Шанина для каждой почти нормальной формулы А определяется трансвинитная иерархия {А ^a } формул простой структуры, причём А ^a É А доказуемо в подходящей формальной системе. Формула А ^a называется мажоритарной для А, и А считается истинной формулой ранга a, если А ^a верна. Точность аппроксимации растёт с ростом a : a < b É ( А ^a É А ^b ). Если отвлечься от технических деталей, то формула А строится с помощью a - кратного вынесения кванторов, согласно эквивалентности

ù ù (В Ú ù ù $ u " vC (u, v)) « $ u " v ù ù (B Ú ù ù $ u " vC(u, v) Ú C(u, v)),

и сворачивания цепочек кванторов с помощью алгоритма выявления конструктивной задачи. Это даёт доказуемую в арифметике с транксфинитной индукцией до a эквивалентность

А « $ u " v ù ù ( ù ù $ w С a Ú D a )

с бесквантовой формулой С a , так что

А ^a = $ u " v $ w С a (u, v, w)

оказывается мажорантой для А. Суждение оказывается с точностью до технических деталей, эквивалентным утверждению о существовании вывода высоты < a исходной формулы с использованием w-правила. В этом смысле мажоритарная семантика эквивалентна ступенчатой семантике А.А. Маркова. После фиксации некоторого класса q общекурсивных функций (например, класса всех функций, определимых пекурсией до a ) определяются мажоранты ещё более простой структуры:

$ u " v С a (u, v, j ( v)) для j Î q .

Если К – бесквантовое исчисление для класса q , то К - истинность $ u " v C (u, v) определяется как выводимость формулы С ( t, v) c переменной v для некоторого постоянного терма t . Если в качестве К взято стандартное исчисление равенств для функций, определимых рекурсией до ординалов, меньших a , то К - истинными оказываются формулы, выводимые в формальной интуиционной арифметике, пополненной принципом Маркова, соотношениями, определяющими алгоритм выявления конструктивной задачи, и правилом индукции до ординалов b таких, что e (b) – первое e - число, большее b. В частности, a = e0 для b=w, т.е. для обычной индукции.

Доведение обоснования до бескванторного уровня (К- истинность) связано со стремлением остаться по возможности в рамках финитизма, т.е. бескванторного языка и соответствующих логических средств. С этим же связано стремление ограничиться небольшими a .. Для большей части «работающего» конструктивного анализа (включая теорему о непрерывности эффективных операторов) достаточно конечных a ..

1).КОНСТРУКТИВНОЕ ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО.

Конструктивное действительное число – понятие действительного числа, употребляемое в конструктивной математике. В более широком смысле – действительное число, конструируемое в соответствии с тем или иным кругом конструктивных средств. Близкое значение имеет термин «вычислимое действительное число», обычно употребляемый в тех случаях, когда не ставится цель изначального, нетрадиционного, нетрадиционного построения континуума, а речь идёт просто о классических действительных числах, вычислимых в том или ином смысле посредством некоторых алгоритмов.

2) КОНСТРУКТИВНЫЙ ОБЪЕКТ.

КОНСТРУКТИВНЫЙ ОБЪЕКТ — название, установившееся за математич. объектами, возникающими в результате развертывания так называемых конструктивных процессов. При описании того или иного конкретного конструктивного процесса обычно «...предполагается, что отчетливо охарактеризованы объекты, которые в данном рассмотрении фигурируют в качестве нерасчленяемых на части исходных объектов; предполагается, что задан список тех правил образования новых объектов из ранее построенных, которые в данном рассмотрении фигурируют в качестве описаний допустимых шагов конструктивных процессов; предполагается, что процессы построения осуществляются отдельными шагами, причем выбор каждого очередного

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

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

3). КОНСТРУКТИВНОЕ МЕТРИЧЕСКОЕ ПРОСТРАНСТВО.

Концепция метрич. пространства используется в конструктивной математике. Близкий смысл имеет также понятие рекурсивного метрического пространства.

Список { ,р}, где - некоторое множество конструктивных объектов (обычно слов в том или ином алфавите), р - алгоритм, переводящий любую пару элементов в конструктивное действительное число, названный Конструктивным математическим пространством, если при любых X, У, Z Î

выполняется: 1) р(Х, Х)=0, 2) р(Х, У) £р(Х, Z)+р(У, Z) (здесь и ниже термин "алгоритм" употребляется в смысле одного из точных понятий алгоритма). Множество и алгоритм р называются носителем и метрическим алгоритмом соответствующего Конструктивного метрического пространства, а элементы - точками этого Конструктивного метрического пространства. Из аксиом 1), 2) следует, что всегда р(Х, У)³0 и р(Х, У)= р(У, X). Две точки, X, YÎназываются эквивалентными (различными)в Конструктивном метрическом пространстве { , р}, если р(Х, У)=0 (соответственно р(Х,У)¹0).

III. ЗАКЛЮЧЕНИЕ

Роль «конструирования» в математике.

Математики действуют, применяя процесс «конструирования»; они «конструируют» сочетания все более и более сложные. Возвращаясь затем путем анализа этих сочетаний — этих, так сказать, совокупностей — к их первоначальным элементам, они раскрывают отношения этих элементов и выводят отсюда отношения самих совокупностей.

Это — процесс чисто аналитический, однако он направлен не от общего к частному, ибо совокупности, очевидно, не могут быть рассматриваемы как нечто более частное, чем их составные элементы.

Этому процессу «конструирования» справедливо приписывали большое значение и желали в нем видеть необходимое и достаточное условие прогресса точных наук.

Несомненно, что оно необходимо; но оно не является достаточным.

Для того чтобы конструирование- могло быть полезным,чтобы оно не