Доведення від супротивного

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

Тривіальний приклад

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

Це ми й використаємо, шукаючи суперечність. Якщо все ж таки знайдемо число, менше за q, яке ми можемо вибрати довільно, то дійдемо суперечності, а отже, заперечене твердження хибне. Якщо за найменше число вибрати, наприклад, 0,1, то бачимо, що 0,01 менше. Далі 0,001 ще менше, 0,0001 знову менше і так далі. Досить поділити число q на десять, і ми отримаємо менше число. Власне, його досить поділити на будь-яке число, більше за одиницю, скажімо, на два: половина числа q напевно менша за саме число q.

Отже, число q/2 безперечно менше за q і водночас є додатним раціональним числом. Так ми дійшли суперечності із запереченим твердженням, тобто заперечене твердження хибне, а отже, істинне початкове, незаперечене твердження.

Цікаві числа

Класичний жартівливий приклад, що ілюструє принцип суперечності, такий. Припустімо, що існують натуральні числа, які чимось цікаві. Наприклад, число 2 цікаве, бо 2 · 2 = 2 + 2 — це досить незвична властивість. Число 42 цікаве, бо це відповідь на все. І так далі. Питання таке: чи існує нескінченно багато цікавих чисел?

Припустімо протилежне: цікавих чисел лише скінченно багато, а деякі числа нецікаві. Зберімо ці нецікаві натуральні числа в множину нецікавих чисел. Тепер виберемо найменше нецікаве число. Стривай, найменше нецікаве число? Це звучить доволі цікаво, чи не так? :-)

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

Звісно, це нісенітниця: ми не визначили як слід, що таке цікаве число, але сам хід доведення правильний.

Доведення нескінченності простих чисел

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

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

Розклад на прості множники, або факторизація, — це подання натурального числа, крім одиниці, у вигляді добутку простих чисел. Це доволі цікава властивість натуральних чисел. Яке натуральне число (крім одиниці) не взяти, його можна розкласти на добуток кількох (можливо, однакових) простих чисел. Приклади:

$$\begin{eqnarray} 8&=&2\cdot2\cdot2\\15&=&3\cdot5\\26&=&2\cdot13\\1800&=&2^3\cdot3^2\cdot5^2 \end{eqnarray}$$

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

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

$$a_1, a_2, a_3,,\ldots,a_n$$

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

Щоб дійти суперечності, треба побудувати якесь просте число, якого в цій послідовності немає. У цьому нам допоможе число q. Побудуємо його так: перемножимо всі прості числа послідовності й додамо одиницю:

$$q=a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1$$

Тепер треба показати, що це число або просте, або якимось чином породжує просте число. Ми знаємо, що q — натуральне число і що кожне натуральне число можна подати як добуток простих чисел. Проте жодне просте число a_i не ділить число q націло: завжди після ділення залишається одиниця. Якщо спробуємо поділити число q, наприклад, на просте число a₂, отримаємо таке:

$$\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1}{a_2}=\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1 \cdot a_3 \cdot a_4 \cdot \ldots \cdot a_n+\frac{1}{a_2}$$

Спершу розіб'ємо дріб на два. У першому дробі скоротимо a₂, і лишиться якийсь добуток простих чисел, тобто просто якесь інше, неістотне ціле число. У другому дробі скорочувати нічого, цей дріб завжди буде нецілим числом (бо знаменник не може дорівнювати одиниці, одиниця не є простим числом). У сумі ми отримаємо число, яке не є цілим, тож просте число a₂ не ділить число q.

Так ми довели, що жодне з простих чисел послідовності a_n не ділить число q. (Зауваження: ми показали це лише для a₂, але це легко узагальнити, якщо замінити a₂ на загальне a_i.) Але оскільки кожне натуральне число можна розкласти на добуток простих чисел, то мають існувати інші прості числа, яких немає в послідовності a_n, але які входять до розкладу числа q. При цьому саме число q цілком може бути простим, і тоді розклад на прості множники міститиме лише число q. Отже, ще раз підсумуймо хід міркувань:

1. Кожне натуральне число можна подати як якийсь добуток простих чисел.
2. За припущенням послідовність a_n містить усі існуючі прості числа.
3. Перефразуємо перше твердження: кожне натуральне число можна подати як добуток вибраних членів послідовності a_n, адже вона містить усі прості числа.
4. Ми довели, що жодне число з послідовності a_n не ділить число q.
5. Так виникла суперечність із припущенням $\rightarrow$ якщо кожне натуральне число мусить розкладатися на добуток простих чисел, а послідовність a_n не містить жодного числа, яке ділить q, то мають існувати інші прості числа, які ділять q і є розкладом числа q на прості множники.

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