книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

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

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

ствимого построения объекта с требуемым свойством. Традиционная логика разрешает в таких случаях дока­ зывать существование искомого объекта косвенными средствами, например, приведением к противоречию до­ пущения о его несуществовании. Таким образом, тра­ диционная логика пренебрегает различиями суждений вида Эх$(х) и ~~| ~\3х38(х), тогда как конструктивная логика считает эти различия существенными; второе суждение с конструктивной точки зрения, вообще го­ воря, слабее первого. (Мы используем обычные обо­ значения логических связок и кванторов: V —дизъюнк­

ция, & — конъюнкция, =э — импликация, == — эквива­ лентность, ~! — отрицание, V — квантор общности, 3 — квантор существования.) Чтобы подчеркнуть эту новую трактовку существования, мы часто будем употреблять при формулировании экзистенциальных предположений

*) Мнение, что изучение различных объектов может требовать различных логик, высказывалось математиками, придерживающи­

противного». Согласно этому принципу, если опроверг­ нуто утверждение о неприменимости алгорифма к не­ которому исходному данному х, то этот алгорифм при­ меним к х. Если выражать применимость алгорифма 91 к х записью

Ш(х),

то принцип Маркова запишется так:

~] ~] Ш (х) => 191 (х).

Интуитивное основание, оправдывающее в рамках абстракции потенциальной осуществимости этот прин­

жаться неограниченно долго и, следовательно, есть возможность получить результат применения 91 к х, выполняя шаг за шагом этот алгорифм и ожидая окон­ чания его работы.

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

на понимание суждений более сложной структуры при­ водит к задаче построения конструктивной логики. Эта

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

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

ближении можно толковать средствами традиционной логики, тол­ кование же формул второго вида объяснялось выше.

В последние годы М а р к о в ы м [8]—[9] разработан под­ ход к построению конструктивной логики «снизу», предлагающий

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

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

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

аудиторией не раз было источником возникавших вокруг конструк­ тивной математики недоразумений; в самом деле, из (12) по пра­ вилам традиционной логики немедленно получается «верное» суж­ дение

Э * ( Я , ( * ) А П Я , ( х ) ) ) .

В действительности же выражаемая суждением (12) невозможность некоторого алгорифма не имеет ничего парадоксального.

7. Говоря о месте понятия множества в конструк­ тивной математике, следует подчеркнуть его подчинен­ ную, техническую роль; по существу, речь идет лишь об

рассматриваются множества слов в некотором алфавите) состоит в формулировании свойства объектов этого типа, а принадлежность конструктивного объекта мно­ жеству просто означает, что этот объект обладает со­ ответствующим свойством. Ясно, что такая трактовка

Строгое использование множеств предполагает фик­ сацию формализованного логико-математического языка (см., например, Ш а н и н [4]), средствами которого фор­ мулируются свойства (под свойствами понимаются однопараметрические формулы данного языка). При этом сами множества оказываются конструктивными объек­ тами (словами в некотором алфавите) и, в частности, могут выступать в качестве исходных данных алгориф-

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

Мы будем обращаться с множествами нестрого, формулируя задающие их свойства на обычном есте­ ственном языке. При этом подразумевается, что фор­ мальный язык, в рамках которого оправдываются наши действия, может быть построен. (Действительное по­ строение и последовательное использование точных языков ввело бы в изложение большое число формаль­ но-логических деталей, что несомненно нежелательно при первом знакомстве с предметом. С построением основных разделов конструктивного анализа на базе логико-математических языков можно ознакомиться в работе Ш а н и н а [6].)

Мы будем использовать обычные теоретико-множе­ ственные обозначения. Принадлежность элемента мно­

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

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

дополнения множеств используются обычные обозначе­ ния: JC\[\Jd, Ж\[}Ль Отметим, что свойствам

38 ВВЕДЕНИЕ

традиционной операции объединения ближе соответ­ ствует «слабое объединение»

Ж\ Л Л%-

Использование а-систем (п. 4 ) , где а —буква, не принадлежащая исходному алфавиту, позволяет легко

это не может повлечь недоразумений, это обозначение

(в наперед фиксированном алфавите) имеет некоторый

алгорифм. Говоря о множествах алгорифмов, мы будем

ными.) На практике же часто оказывается удобным использование переменных («подчиненные» переменные), допустимыми значениями

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

В первом случае множество Ж и переменная х называются нор­ мальными. Для нормальных переменных (а также в тех случаях, когда множество Ж равно нормальному) мы сохраняем старую интерпретацию. Во втором случае дело обстоит сложнее — установ­ ление принадлежности слова У множеству Ж связано с решением конструктивной задачи, — именно, с построением соответствующего слова Z. Грубо говоря, идея интерпретации заключается здесь в