КОНСТРУКТИВНОГО ПОДБОРА ПРИНЦИП


КОНСТРУКТИВНОГО ПОДБОРА ПРИНЦИП

принцип Маркова,- логико-философский принцип конструктивной математики, выдвинутый А. А. Марковым [1], [2] и в общей форме утверждающий, что если конструктивный процесс, заданный нек-рым предписанием, не является неограниченно продолжаемым, то он заканчивается. В конструктивной математике получили применение несколько конкретных, содержательно эквивалентных разновидностей этого принципа. 1) Пусть W- нормальный алгорифм, Р- слово в его алфавите. Тогда, если опровергнуто предположение о неприменимости Y к Р, то Y применим к Р;символически

2) В арифметике формальной К. п. п. может быть выражен следующей арифметич. формулой

где T1 - примитивно рекурсивный предикат такой, что частично рекурсивная функция с гёделевым номером z определена на хтогда и только тогда, когда EyT1(z, х, у )(ср. [3]). 3) Если рекурсивно перечислимое множество непусто, то оно содержит нек-рый элемент. 4) Пусть А- алгоритмически проверяемое свойство натуральных чисел. Тогда, если опровергнуто предположение о том, что не существует числа со свойством А, то найдется натуральное число со свойством А. Соответствующая логическая схема записывается в виде

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

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

К. п. п. безусловно допустим с точки зрения классич. логики, поскольку он является частным случаем общего закона снятия двойного отрицания и закона исключенного третьего. Применение этих логических законов сводится к К. п. п. во многих конструкциях теории рекурсивных функций, что делает эти конструкции достоянием конструктивной математики. Использование К. п. п. позволяет также получить ряд значительных результатов в конструктивном анализе, в частности теорему о непрерывности алгоритмич. операторов и о продолжимости эффективных функционалов до частично рекурсивных функционалов (см. также Конструктивное метрическое пространство). Другой сферой приложений К. п. п. является конструктивная семантика [4]. Еще задолго до формулировки К. п. п. в качестве общего принципа конструктивной математики проводились исследования по обоснованию различных форм этого принципа в рамках того или иного круга допускаемых конструктивных средств. Здесь следует указать следующий основополагающий результат П. С. Новикова, полученный в 1943 (см. [5]): пусть для формулы (х)с одной переменной в конструктивной формальной арифметике выводимо для каждого пи в классической арифметике выводимо E хА (х);тогда формула выводима и в конструктивной арифметике. В работе [6] было получено обоснование К. п. п. в рамках новой системы конструктивной семантики, развиваемой в последние годы А. А. Марковым.

Являясь, по-видимому, наименее непосредственной из первоначальных установок конструктивной математики, К. п. п. принимается нек-рыми сторонниками последней с известными оговорками. К. п. п. отвергается также интуиционистской математикой как недостаточно убедительный интуитивно. С другой стороны, в связи с формализацией ряда разделов интуиционистской математики детально изучались вопросы о соотношениях соответствующих систем с формальными схемами, выражающими К. п. п. В частности, установлена независимость схем (2) и (4) от аксиом интуиционистского исчисления предикатов, арифметики и анализа (см. [2], [7], [8]).

Лит.:[1] Марков А. А., "Успехи матем. наук", 1954, т. 9, в. 3, с. 226-30; [2] его же, в кн.: Тр. 3 Всесоюзного математического съезда, т. 2, М., 1956, с. 146-47; [3] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [4] Шанин Н. А., "Тр. матем. ин-та АН СССР", 1958, т. 52, с. 226-311; [5] Новиков П. С, "Матем. сб.", 1943, т. 12, в. 2, с. 231-61; [6] Марков А. А., "Докл. АН СССР", 1974, т. 214, № 4, с. 765-68, т. 215, № 1, с. 57-60; [7] Клини С, Весли Р., Основания интуиционистской математики с точки зрения теории рекурсивных функций, пер. с англ., М., 1978; [8] Тrое1stra A. S., в кн.: ISILC. Proof theory symposion, В., 1975, p. 370-83.

Б. А. Кушнер.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "КОНСТРУКТИВНОГО ПОДБОРА ПРИНЦИП" в других словарях:

  • Принцип Маркова — один из основных принципов логики конструктивной математики, сформулированный в начале 1950 х годов А. А. Марковым. Известен также под названиями «ленинградский принцип» и «принцип конструктивного подбора». Представляет собой… …   Википедия

  • ИНТУИЦИОНИСТСКАЯ ЛОГИКА — совокупность приемлемых с точки зрения интуиционизма методов доказательства утверждений. В более узком смысле под И. л. понимается интуиционистское исчисление предикатов, сформулированное А. Рейтингом (A. Heyting) в 1930. Это исчисление… …   Математическая энциклопедия

  • КОНСТРУКТИВНАЯ ЛОГИКА — раздел математической логики, изучающий рассуждения о конструктивных объектах и конструкциях. При таком понимании К. л. шире, чем логика конструктивной математики. Самое заметное отличие от традиционной (классической) логики состоит в отсутствии… …   Математическая энциклопедия

  • ИНТУИЦИОНИЗМ — совокупность философских и математич. идей и методов, рассматривающих математику как науку об умственных построениях. С точки зрения И., основным критерием истинности математич. суждения является интуитивная убедительность возможности построения… …   Математическая энциклопедия

  • ДВОЙНОГО ОТРИЦАНИЯ ЗАКОН — логический принцип, согласно к рому если неверно, что неверно А, то верно Л . Д. о. з. наз. также законом снятия двойного отрицания. В формализованном языке логики высказываний Д. о. з. выражается формулой и в таком виде (или в виде… …   Математическая энциклопедия

  • КОНСТРУКТИВНОЕ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ — логическое исчисление, описывающее способы вывода высказываний, истинных с точки зрения конструктивной математики. Обычно этот термин рассматривается как синоним термина интуиционистское исчисление высказываний. Однако, при нек рых специальных… …   Математическая энциклопедия

  • КОНСТРУКТИВНАЯ ЛОГИКА —         1) то же, что и интуиционистская логика; 2) ветвь логики, в которой изучаются финитные (см. Финитизм) рассуждения о конструктивных объектах и процессах (см. Конструктивное направление) и строится соответств. семантика. В К. л. отвергается …   Философская энциклопедия

  • КОНСТРУКТИВНАЯ МАТЕМАТИКА — конструктивное направление в математике, математика, строящаяся в соответствии с тем или иным конструктивным математич. мировоззрением, обыкновенно стремящимся связывать утверждения о существовании математнч. объектов с возможностью их построения …   Математическая энциклопедия

  • конструктивная логика —         КОНСТРУКТИВНАЯ ЛОГИКА (от лат. constructio построение) совокупность логических принципов, признаваемых приемлемыми представителями конструктивизма в математике. Предметом конструктивизма являются конструктивные объекты и конструктивные… …   Энциклопедия эпистемологии и философии науки

  • МАРКОВ —         Андрей Андреевич [р. 9(22).9.1903, Петербург, 11.10.1979, Москва], сов. математик и логик, чл. корр. АН СССР (1953). Чл. КПСС с 1953. Осн. тру ды по топологии, топологич. алгебре, теории динамич систем, теории алгорифмов и конструктивной… …   Философская энциклопедия