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

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

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

В эту же группу можно отнести применение неравенства Маркова и вытекающих из него неравенства для обычных сумм. Например, если известно, что сумма ${\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}$ и ${\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)}$. Однако о том, какая именно эта точка, ничего сказать нельзя.

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

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

Используя критерий Вейля, можно показать, что для любой бесконечной последовательности чисел ${\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 }$.[5]