Що таке доведення

Доведення — це фундамент усієї математики: завдяки їм із кількох невеликих камінців можна збудувати цілу піраміду, та ще й догори дриґом.

Навіщо потрібні доведення

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

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

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

Отже, під час вивчення будь-якої теми доведення відповідають на запитання «чому це так працює?». Якщо ти зрозумієш, чому щось працює, то легше це запам'ятаєш і з часом розумітимеш тему значно краще, ніж той, хто вчився за принципом «вивчив — здав — забув». Питання лише в тому, чи це твоя мета.

Що таке доведення

Що таке доведення, формально визначається в математичній логіці, наприклад, через синтаксичне виведення, але нам вистачить набагато простішого означення.

На початку кожного доведення ми маємо твердження, яке хочемо довести. Позначимо його магічним символом $\phi$. Це грецька літера, яку читаємо «фі». Далі нам знадобиться якась множина аксіом і припущень, позначимо її Ax, за допомогою якої ми доведемо твердження $\phi$. Множина аксіом — це те, що ми вже знаємо, що вважаємо істинним. Це можуть бути, наприклад, такі речі, як «кожне парне число ділиться на два». Крім того, ця множина може містити, наприклад, формули для перетворення виразів, які доведено деінде і які ми вже вважаємо істинними, скажімо:

$$(a+b)^2=a^2+2ab+b^2;\qquad a,b\in\mathbb{R}$$

Тепер ми поступово перетворюватимемо твердження з множини Ax, доки не отримаємо твердження $\phi$. Усі перетворення мають бути логічно правильними, вони мають відповідати основам логіки висловлень. Наприклад, якщо ми захочемо довести попередню формулу, діятимемо так: вираз

$$(a+b)^2$$

перетворюватимемо рівносильними перетвореннями, доки не отримаємо вираз у правій частині. Покажу:

$$(a+b)^2=(a+b)\cdot(a+b)=a\cdot a+a\cdot b + b\cdot a + b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

На першому кроці ми розписали степінь у вигляді добутку, на другому — розкрили дужки, на третьому — звели подібні доданки, а на останньому — записали добуток як степінь. Кожен крок був якимось елементарним перетворенням, яке ми могли собі дозволити, і ми вважаємо, що кожне з цих елементарних перетворень міститься в множині Ax.

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

Тривіальні доведення

Тривіальне доведення (або очевидне доведення) — це технічний термін для доведення, яке не вміщується на дошці, тому його пропускають, а студент вивчає його з підручника як домашнє завдання. :-) А тепер серйозно: тривіальні доведення — це доведення, які зазвичай випливають із якогось означення за один тривіальний крок.

Спробуймо показати це на прикладі: розгляньмо множину натуральних чисел, тобто множину чисел ℕ = {1, 2, 3, …}. Тепер можемо стверджувати, що кожен дріб виду

$$\frac{q}{p}; \qquad q,p\in\mathbb{N}$$

є коректним, тобто не існує жодної пари чисел q, p, для якої цей дріб не мав би сенсу. Як це довести? Спершу треба з'ясувати, коли дріб не має сенсу. Дріб не має сенсу, коли в знаменнику нуль (на нуль ділити не можна). Отже, треба довести, що p≠0 для всіх можливих p. Але ми знаємо, що p беремо з натуральних чисел, які ми визначили як ℕ = {1, 2, 3, …}. Множина натуральних чисел не містить нуля, тому число p завжди буде відмінне від нуля.

$$\forall p\in\mathbb{N}: p\ne 0$$

І доведення закінчено. Ми знаємо, що коли і чисельник, і знаменник дробу — натуральні числа, то дріб коректний.

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

Контрприклад

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

Приклад: «кожне натуральне число більше за десять». Як довести, що це неправда? Контрприклад до нашого твердження — наприклад, число п'ять. Число п'ять натуральне й не більше за десять. Це твердження неможливо довести тим, що ми перелічимо кілька натуральних чисел, які більші за десять. Не можна сказати: «натуральні числа 11, 12, 13, 123 і 5345 більші за 10, тож твердження істинне». Так не можна. Ми лише вибрали кілька прикладів, для яких наше твердження виконується, а це нічого не говорить про інші числа, про які ми взагалі не згадали.

Другий приклад: кожен чоловік, вищий за два метри, має карі або блакитні очі. Гадаю, що мало хто здатен знайти контрприклад. Що це нам каже про саме твердження? Та нічого. Якщо ми не можемо знайти контрприклад, це зовсім не означає, що твердження істинне. Контрприклад десь може існувати, просто ми його зараз не можемо знайти. Нездатність знайти контрприклад не доводить, що твердження істинне.

Пряме доведення

Основний вид доведення — пряме доведення. Ми сухо дотримуємося означення й перетворюємо вихідне висловлення, доки не отримаємо те, яке хочемо отримати. Зазвичай ми хочемо довести висловлення у вигляді імплікації $A\Rightarrow B$, де A — якась відправна точка, припущення, а B — висловлення, яке хочемо вивести, довести. Якщо виконується висловлення A, то виконується й висловлення B. Часто нам задано лише висловлення B, тобто те, що треба довести, а висловлення A ми маємо вдало вибрати самі.

Далі йде послідовність, у якій за допомогою імплікацій ми виводимо наступні висловлення, а останнім стоїть висловлення B. Схематично це можна записати так:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow\ldots \Rightarrow A_n \Rightarrow B$$

Як приклад доведемо, що виконується висловлення

$$a>1\Rightarrow a^2>1$$

А тепер по кроках:

1. Оскільки a>1, то, звісно, виконується також a>0 і a≠0 (фактично ми лише послаблюємо умову).
2. Оскільки a не дорівнює нулю й додатне, ми можемо без побоювань помножити на змінну a обидві частини нерівності. Якби a дорівнювало нулю, строга нерівність не зберіглася б (ми отримали б 0>0), а якби воно було від'ємним, довелося б змінити знак нерівності на протилежний. Після множення на a отримуємо вираз a²>a.
3. Зараз ми знаємо, що a>1, і водночас знаємо, що a²>a. Якщо поєднати ці два вирази, отримаємо: a²>a>1.
4. Звідси ми просто прибираємо середній вираз і маємо a²>1. Ми могли це зробити, тому що a більше за одиницю, а a² більше за a. Якщо a² більше за a, а a водночас більше за одиницю, то a² безперечно більше за одиницю.

Символічно це можна записати так:

$$a>1\Rightarrow a>0 \Rightarrow a^2>a \Rightarrow a^2>a>1 \Rightarrow a^2>1.$$

Непряме доведення

Непряме доведення більше використовує властивості імплікації. Якщо треба довести твердження у вигляді $A\Rightarrow B$, можна скористатися контрапозицією (імплікацією, оберненою до протилежної) й довести

$$\neg B \Rightarrow \neg A.$$

Такий підхід іноді буває зручнішим, ніж, наприклад, пряме доведення. Подібний прийом застосовує доведення від супротивного, до якого можна звести кожне непряме доведення. Спробуймо непрямо довести твердження

$$a-b=0\Rightarrow a=b.$$

Тепер перейдемо до контрапозиції:

$$\begin{eqnarray} \neg(a=b)&\Rightarrow&\neg(a-b=0)\\ a\ne b&\Rightarrow&a-b\ne0 \end{eqnarray}$$

Якщо a≠ b, можемо подати b у вигляді суми b = a + x, де x — відстань від числа a до числа b. Вираз зміниться так:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne0;\quad x\ne0$$

Скоротимо ті a, які можна скоротити:

$$0\ne x\Rightarrow -x\ne 0; \quad x\ne0$$

Оскільки x≠0, то й −x≠0, тож імплікація виконується. Твердження доведено, а отже, виконується й початкове висловлення

$$a-b=0\Rightarrow a=b.$$

Інші способи доведення — це, наприклад, уже згадане доведення від супротивного або доведення методом індукції.