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

Конструктивное доказательство — доказательство, в котором существование математического объекта доказывается путем прямого построения — в отличие от неконструктивного доказательства (также известного как чистая теорема существования), которое доказывает существование объекта с определёнными свойствами без предоставления конкретного примера. 

Конструктивная математика отвергает всё, кроме конструктивного доказательства. Это приводит к ограничению на допустимые методы доказательства (в частности, закон исключенного третьего не используется), а также другому пониманию терминов. Например, термин «или» имеет более сильное значение в конструктивной математике, чем в классической.

Иногда используется эквивалентный термин «эффективное доказательство».

Примеры

Бесконечность множества простых чисел

Сначала рассмотрим теорему о том, что существует бесконечное множество простых чисел. Доказательство Евклида является конструктивным.

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

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

Предположим, что M — самое большое простое число. Тогда M! + 1 не делится ни на одно из имеющихся простых чисел — а значит, новое простое число.

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

Возьмём какое-то простое число, например, a₁ = 2. Строим последовательность a₂ = 2! + 1, a₃ = a₂! + 1, и т. д. Все эти числа будут простыми.

Иррациональная степень иррационального

Теперь рассмотрим теорему

• Существуют иррациональные числа $a$ и $b$ такие, что $a^{b}$ является рациональным.

Эта теорема может быть доказана конструктивно и неконструктивнo.

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

Следующее доказательство Дова Джардена 1953 года широко использовалось в качестве примера неконструктивного доказательства, по крайней мере с 1970 года.

Напомним, что ${\sqrt {2}}$ иррационален. Заметим, что ${\sqrt {2}}^{\sqrt {2}}$ рационально либо иррационально. Если ${\sqrt {2}}^{\sqrt {2}}$ рационально, то теорема верна, с $a={\sqrt {2}}$ и $b={\sqrt {2}}$. Если ${\sqrt {2}}^{\sqrt {2}}$ иррационально, то теорема верна, с $a={\sqrt {2}}^{\sqrt {2}}$ и $b={\sqrt {2}}$ поскольку

$({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}={\sqrt {2}}^{2}=2$

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

Заметим, что неконструктивное доказательство не даёт пример $a$ и $b$; оно лишь дает несколько возможностей (в данном случае двух) и показывает, что одно из них есть нужный пример, но не говорит, какой.

• На самом деле, ${\sqrt {2}}^{\sqrt {2}}$ иррационально по теореме Гельфонда — Шнайдера, но этот факт не имеет отношения к справедливости неконструктивного доказательства приведённого выше.

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

Пусть

$a={\sqrt {2}},\quad b=\log _{2}9,\quad {\text{тогда}}\quad a^{b}=3.$

Оба числа иррациональны; $a$ — квадратный корень из 2 и если $b={\tfrac {m}{n}}$, то $3^{2\cdot n}=2^{m}$, что невозможно, так как первое число нечетное, а второе четное.

См. также

• Теорема Робертсона — Сеймура
• Теорема существования
• Вероятностный метод