Теорія доведення

При прямому доведенні висновок встановлюється через логічну комбінацію аксіом, визначень і раніше доведених теорем. Для прикладу розглянемо доведення, що сума двох парних цілих чисел також є парною:

кожне з двох парних чисел x та y ми можемо за визначенням записати у вигляді x = 2a та y = 2b, де a і b — деякі цілі числа, бо x та y діляться на 2. Але тоді сума x + y = 2a + 2b = 2(a + b) також ділиться на 2, так що вона є парною за визначенням.

Цей доказ використовує визначення парних цілих чисел, і також дистрибутивний закон додавання.

Припустимо, що потрібно встановити справедливість нескінченної послідовності тверджень, занумерованих натуральними числами: ${\displaystyle P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots }$. Припустимо, що

1. Встановлене, що P₁ вірно. (Це твердження називається базою індукції.)
2. Для будь-якого n доведено, що якщо вірно P_n, то вірно P_{n + 1}. (Це твердження називається індукційним переходом.)

Тоді всі твердження нашої послідовності вірні.

Метод перестановки встановлює істинність твердження Якщо А, то Б доведенням еквівалентного твердження Якщо не Б, то не А.

Цей метод доведення відомий також як приведення до абсурду (лат. reductio ad absurdum). Доказ твердження A проводиться таким чином. Спочатку приймають припущення, що твердження A невірно, а потім доводять, що за такого припущення було б вірне деяке твердження B, яке заздалегідь невірне. Отримана суперечність показує, що початкове припущення було невірним, і тому вірне твердження ¬¬A, яке за законом подвійного заперечення рівносильно твердженню A.

Конструктивне доведення або доведення наданням прикладу — це конструювання конкретного прикладу з властивостями, для того щоб довести, що існують приклади з цими властивостями. Наприклад, Жозеф Ліувілль, для того щоб довести існування трансцендентних чисел, явно сконструював таке число.

При доведенні методом витягів висновок про істинність твердження досягається розділенням твердження на скінчену кількість випадків і доведенням кожного такого випадку окремо. Кількість таких випадків може бути дуже великою. Наприклад, перший доказ проблеми чотирьох фарб складався з розгляду 1936 випадків. Більшість цих випадків розглядала комп'ютерна програма, а не людина. Сучасніші коротші докази теореми про чотири фарби все одно вимагають розгляду понад 600 випадків.

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

Суть комбінаторного доказу полягає у встановлені еквівалентності різних виразів, так що вони представляють той самий об'єкт, але в різний спосіб. Звичайно, для того щоб показати, що дві інтерпретації дають той самий об'єкт, використовується бієкція.

Неконструктивне доведення встановлює, що певний математичний об'єкт повинен існувати (тобто певний X, що задовольняє f(X)), без пояснення, як цей об'єкт може бути встановлений. Часто це робиться приведенням до протиріччя твердження, що такого об'єкта не існує. На противагу цьому, конструктивне доведення встановлює існування об'єкта представленням способу визначення об'єкта.

Відомим прикладом неконструктивного доведення є доказ існування двох ірраціональних чисел a і b, таких що a^b є числом раціональним.

• Або ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ є раціональним числом і ми маємо приклад (де ${\displaystyle a=b={\sqrt {2}}}$),
• або ж ${\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}={\sqrt {2}}^{2}=2}$ показує, що ми маємо ${\displaystyle a={\sqrt {2}}^{\sqrt {2}}}$ та ${\displaystyle b={\sqrt {2}}}$.

Існує клас математичних тверджень, для яких не існує ані доказу, ані спростування (тобто доведення зворотного твердження) в рамках аксіоматики Цермело — Френкеля, стандартної основи теорії множин. Як приклад можна навести континуум-гіпотезу. Якщо погодитися з непротивоічністю аксіом Френкеля — Цермело, існування таких прикладів нам гарантує перша теорема неповноти Геделя. Чи можна довести певне твердження чи його спростування, не завжди очевидно і може вимагати надзвичайної техніки для встановлення цього факту.

Елементарним доведенням називають докази, що не потребують складного аналізу.

В деяких випадках теореми, як наприклад теорема про асимптотичний розподіл простих чисел, вимагала застосування «вищої» математики. Але з часом були отримані нові докази з використанням елементарної техніки.