Конструктивне доведення

Розглянемо спочатку теорему, згідно з якою множина простих чисел є нескінченною. Доказ Евкліда конструктивний. Але загальний вид спрощеного Евклідового доказу стверджує, що, всупереч твердженням в теоремі, кількість їх обмежена, і в цьому випадку найбільше число позначається n. Тоді розглянемо число (n! + 1) (1 + добуток перших n чисел). Або це число є простим, або сума всіх його простих множників більша, ніж n.  Без встановлення конкретного простого числа це доводить, що існує принаймні одне, що більше, ніж n, всупереч початковому постулату.

Розглянемо тепер таку теорему: «Існують два ірраціональні числа a і b, такі, що ${\displaystyle a^{b}}$  раціональне». Цю теорему можна довести за допомогою як конструктивного доведення, так і неконструктивного.

Наступний доказ, сформульований Довом Джарденом в 1953 році, широко використовується як приклад неконструктивного доведення принаймні з 1970 року:[1][2]

CURIOSA 339. Простий доказ, що результат піднесення ірраціонального числа до степеня з ірраціональним показником може бути раціональним числом. ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ є або раціональним, або ірраціональним. Якщо воно раціональне, наше твердження доведено. Якщо воно ірраціональне,  ${\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2}$ доводить наше твердження.    Дов Джарден, Єрусалим

Детальніше:

• Нагадаємо, що ${\displaystyle {\sqrt {2}}}$ ірраціональне число, а 2 раціональне. Розглянемо число ${\displaystyle q={\sqrt {2}}^{\sqrt {2}}}$. Воно або раціональне, або ірраціональне.
• Якщо ${\displaystyle q}$ раціональне, то теорема вірна, бо  ${\displaystyle a}$ і ${\displaystyle b}$ обидва дорівнюють ${\displaystyle {\sqrt {2}}}$.
• Якщо ${\displaystyle q}$ ірраціональне, то теорема вірна, бо, ${\displaystyle a}$ дорівнює ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$, а ${\displaystyle b}$ дорівнює ${\displaystyle {\sqrt {2}}}$, так як

${\displaystyle \left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{({\sqrt {2}}\cdot {\sqrt {2}})}={\sqrt {2}}^{2}=2.}$

Це доведення є неконструктивним, оскільки воно спирається на твердження «Або q раціональне, або ірраціональне» — приклад до закону виключеного третього, який не діє в конструктивному доведенні. Неконструктивне доведення не наводить приклад a і b; воно просто надає ряд можливостей (у цьому випадку, дві взаємовиключні можливості) і показує, що одна з них — незрозуміло яка — повинна задовольнити потрібний приклад.

(Виявляється, що ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$  є ірраціональним через теорему Гельфонда-Шнайдера, але цей факт не має ніякого відношення до правильності неконструктивного доведення.)

Конструктивне доведення сформульованої вище теореми про ірраціональні степені ірраціональних надає конкретний приклад:

${\displaystyle a={\sqrt {2}}\,,\quad b=\log _{2}9\,,\quad a^{b}=3\,.}$

Квадратний корінь з 2 є ірраціональним, а число 3 — раціональним. ${\displaystyle \log _{2}9}$ також ірраціональний: якби він дорівнював ${\displaystyle m \over n}$, то, за властивістю логарифмів, 9ⁿ дорівнювало б 2^m, але перше є непарним, а останнє парним.

Більш суттєвим прикладом може служити теорема теорема про мінор графу. З теореми випливає, що графік можна намалювати на торі тоді і тільки тоді, коли жоден з його мінорів не належить до деякої скінченної множини «заборонених мінорів». Проте доказ існування цієї скінченної множини не є конструктивним, і заборонені мінори фактично не вказані. Вони до цих пір невідомі.