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

Если в доказательстве доказывается формула, в которой одна из величин — постоянная, но её значение восстановить невозможно, то это число называется неэффективной константой .

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

Природа неконструктивных доказательств

Неконструктивные доказательства, как правило, возникают при применении в ходе доказательства некоторых типичных утверждений и приёмов, самих по себе неконструктивных. Часто неконструктивные доказательства ведутся от противного .

Принцип Дирихле

Многие такие доказательства основаны на разных формах и обобщениях принципа Дирихле. Сам по себе этот принцип

Если ${\displaystyle n+1}$ элементов лежат в ${\displaystyle n}$ ячейках, то существует ячейка с не менее чем двумя элементами

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

В эту же группу можно отнести применение неравенства Маркова и вытекающих из него неравенства для обычных сумм. Например, если известно, что сумма ${\displaystyle \sum \limits _{i=1}^{n}{a_{i}}}$ достаточно велика, а элементы в ней ограничены сверху ( ${\displaystyle a_{i}<M}$ ), то можно показать, что существует много элементов, значение которых относительно велико и близко к ${\displaystyle M}$ . Это «много» означает некоторое множество ${\displaystyle A}$ элементов, и это ${\displaystyle A}$ , если оно или его элементы будут использоваться далее в доказательстве, сделает доказательство неконструктивным, поскольку ничего, кроме того что оно существует, про него узнать невозможно.

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

Может использоваться также обратная постановка принципа Дирихле для бесконечных множеств:

Если в конечном числе ящиков находится конечное число кроликов, то в каждом ящике находится конечное число кроликов

Здесь утверждения существования не возникает, но оно возникнет, если, например, вместо дискретных ящиков рассматривать отрезок ${\displaystyle (0;1)}$ и значения функции на нём. Если ${\displaystyle \int \limits _{0}^{1}\left({\sum \limits _{i=1}^{\infty }{f_{i}(x)}}\right)dx}$ сходится, то ${\displaystyle \sum \limits _{i=1}^{\infty }{f_{i}(x)}}$ сходится почти всюду , то есть множество точек, где оно не сходится имеет меру нуль. Но мы не можем ничего сказать про это множество, а значит, не можем ничего сказать и про точки, где ряд сходится. Мы доказали, что ряд сходится почти всюду, но где именно — непонятно. В этом и заключается неконструктивность.

Разность размера множеств

Если ${\displaystyle |A|<|B|}$ , то ${\displaystyle \exists x\in B:\ x\not \in A}$ .

Если переформулировать это в терминах принципа Дирихле, то получится следующее:

если из ${\displaystyle n+1}$ кроликов некоторые сидят в одной из ${\displaystyle n}$ клеток, но в каждой клетке сидит не более одного кролика, то хотя бы один кролик не сидит ни в какой клетке.

В описываемом выше примере с интегралом ряда применялся как раз этот приём, но нужно заметить, что в этом приёме не важно, были ли множества ${\displaystyle A}$ и ${\displaystyle B}$ конструктивными до этого. Даже если они были однозначно определены, то существование элемента ${\displaystyle x}$ доказано неконструктивно (в рамках множества ${\displaystyle B}$ ).

Использование существования как предпосылки

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

Например, пусть доказывается некоторое утверждение для любой непрерывной функции ${\displaystyle f}$ и некоторой точки ${\displaystyle x_{0}}$ (такой, что ${\displaystyle f(x_{0})>0}$ ). По определению непрерывности, ${\displaystyle \forall \varepsilon >0\exists \delta =\delta (\varepsilon )>0:\forall x:|x-x_{0}|<\delta \Rightarrow |f(x)-f(x_{0})|<\varepsilon }$ . Из этого легко вывести, что ${\displaystyle \exists \mu >0:\int \limits _{x_{0}}^{x_{0}+\mu }f(x)dx\leq 1.001\mu f(x)}$ . Доказательство этого можно считать конструктивным, поскольку мы можем оценить ${\displaystyle \mu }$ в терминах зависимости ${\displaystyle \delta (\varepsilon )}$ . Однако если мы потом будем использовать доказанное следствие для некоторой функции ${\displaystyle f}$ , про которую нам известно, что она непрерывна, но не известна чёткая зависимость ${\displaystyle \delta (\varepsilon )}$ (то есть непрерывность ${\displaystyle f}$ доказана неконструктивно), то получим неконструктивное доказательство, поскольку не сможем восстановить и ${\displaystyle \mu }$ .

Примеры неконструктивных доказательств

Теория вычислимости

Существование невычислимого множества — классический пример неконструктивного доказательства через разность размеров множеств.

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

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

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

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

• Проблема останова
• Десятая проблема Гильберта

Геометрия чисел

Пусть дано замкнутое выпуклое тело ${\displaystyle A\subset {\mathbb {R} }^{n}}$ объёма ${\displaystyle V(A)>2^{n}}$ , симметричное относительно начала координат . Если рассмотреть функцию

${\displaystyle f(x_{1},\dots ,x_{n})=\#\left\lbrace {(c_{1},\dots ,c_{n})\in {\mathbb {Z} _{n}}:(2c_{1}+x_{1},\dots ,2c_{n}+x_{n})\in A}\right\rbrace }$ ,

то очевидно, что ${\displaystyle \int \limits _{0}^{2}\dots \int \limits _{0}^{2}{f(x_{1},\dots ,x_{n})dx_{1}\dots dx_{n}}=V(A)>2^{n}}$ , следовательно

${\displaystyle \exists x_{1},\dots ,x_{n}:f(x_{1},\dots ,x_{n})\geq 2}$

так что существуют точки ${\displaystyle {\overline {x}},{\overline {y}}\in A}$ , разность которых является чётной точкой целочисленной решётки . Через свойства выпуклости и симметричности из этого легко вывести, что в ${\displaystyle A}$ лежит хотя бы одна целая точка кроме ${\displaystyle (0,\dots ,0)}$ . Однако о том, какая именно эта точка, ничего сказать нельзя.

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

Комбинаторная геометрия

Некоторые доказательства, касающиеся задачи Данцера — Грюнбаума были неконструктивными ввиду применения вероятностного метода .

Теория чисел

Используя критерий Вейля , можно показать, что для любой бесконечной последовательности чисел ${\displaystyle a_{1}<a_{2}<\dots <a_{n}<\dots }$ для почти всех чисел ${\displaystyle \xi \in (0;1)}$ последовательность ${\displaystyle {(a_{n}\xi )}_{n=1}^{\infty }}$ равномерно распределена по модулю 1 , то есть множество значений, для которых это не так, имеет нулевую меру . Однако такое доказательство не позволяет предъявить множество исключений (оно, очевидно, зависит от последовательности ${\displaystyle (a_{n})_{n=1}^{\infty }}$ ). то есть из него невозможно понять, распределена ли равномерно последовательность ${\displaystyle {(a_{n}\xi )}_{n=1}^{\infty }}$ для какого-то конкретного заданного ${\displaystyle \xi }$ .

См. также

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

Примечания

Литература

• К. Чандрасекхаран. . — Мир, 1968.
• Лоуренс Кейперс, Гарольд Нидеррейтер. Равномерное распределение последовательностей. — Мир, 1963. — 407 с.