Русская Википедия:Принцип Маркова

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Формулировка принципа состоит в следующем: Шаблон:Рамка Пусть для некоторого свойства <math>\mathcal Y</math> имеется алгоритм <math>\mathfrak A</math>, выясняющий для всякого натурального числа <math>N</math>, обладает ли <math>N</math> свойством <math>\mathcal Y</math>. Если опровергнуто предположение о том, что ни одно натуральное число не обладает свойством <math>\mathcal Y</math>, то имеется натуральное число со свойством <math>\mathcal Y</math>. Шаблон:Конец рамки Способ построения искомого числа состоит в последовательном переборе натуральных чисел, начиная с нуля, причём на каждом шаге процесса посредством алгоритма <math>\mathfrak A</math> устанавливается, обладает ли рассматриваемое число свойством <math>\mathcal Y</math>.

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

<math>((\forall X(D\lor (\neg D)))\supset((\neg(\neg (\exists XD)))\supset(\exists XD)))</math>.

Шаблон:Rq