Неконструктивное доказательство

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

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

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

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

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

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

Основная статья: Принцип Дирихле (комбинаторика)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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$,

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

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

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

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

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

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

Теория чисел

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

См. также

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

Литература

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