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

Доведення від супротивного (зведення до абсурду, Шаблон:Lang-la) — один із поширених методів доведення тверджень в математичній логіці. Доведення від супротивного — вид доведення, при якому доведення деякого твердження відбувається через спростування заперечення цього твердження — антитезису. Метод ґрунтується на правильності формули $((A\Rightarrow B)\wedge \mathrm{\neg }B)\Rightarrow \mathrm{\neg }A$ в численні висловлень та законі подвійного заперечення. Це приклад слабшого логічного спростування — доведення до абсурду.

Припускаємо, що A є істинним твердженням, і доводимо, що, по-перше, з A виводиться B, а по-друге, що з A виводиться ¬B, що неможливо; отже, A хибне, тобто істинне ¬A.

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

Схема доведення

Доведення твердження $A$ проводиться наступним чином. Спочатку приймають припущення, що твердження$A$ невірне, а потім доводять, що при такому припущенні було б вірним деяке твердження $B$, яке завчасно невірне. Отримане протиріччя показує, що початкове твердження було невірним, і тому вірним є твердження $⌝⌝A$, яке по закону подвійного заперечення дорівнює твердженню $A$.

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

Приклад

Доведення ірраціональності числа $\sqrt{2}$.

Припустимо супротивне: $\sqrt{2}$ раціональне, тобто представляється у вигляді нескоротного дробу $\frac{m}{n}$, де $m$ — ціле число, а $n$ — натуральне. Піднесемо отриману рівність в квадрат:

$\sqrt{2}=\frac{m}{n}$ $\Rightarrow$ $2=\frac{m^2}{n^2}$, звідки $m^2=2n^2$.

Звідси витікає, що $m^2$ парне, значить, парне і $m$; звідси $m^2$ ділиться на 4, а значить, $n^2$ і $n$ теж парні. Отримане твердження суперечить нескоротності дробу $\frac{m}{n}$. Значить початкове твердження було вірним ($\sqrt{2}$ — ірраціональне число).

Довжина гіпотенузи

Метод від супротивного також використовується, щоб показати, що для будь-якого невиродженого прямокутного трикутника, довжина гіпотенузи менше, ніж сума довжин двох інших. Доказ спирається на теорему Піфагора. Припустимо c є довжиною гіпотенузи і a і b довжини ребер, твердження в тому, що a+b>c.

Заперечимо це твердження припустивши, що a+b≤c. Піднесемо обидві частини нерівності в квадрат(a + b)² ≤ c². Маємо a² + 2ab + b² ≤ c². Трикутник є невиродженим, якщо кожне ребро має додатню довжину, тому можна вважати, що a і b більше 0. Таким чином a² + b² < a² + 2ab + b² ≤ c². Транзитивне відношення може бути зведене до a² + b² < c². Як відомо з теореми Піфагора, що a² + b² = c². Це призводить до протиріччя, так як нерівність строга і рівності є взаємовиключними.

Не існує найменшого раціонального числа

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

Тепер r/2 є раціональним числом більше 0 і менше, ніж r. Але це суперечить нашому початковому припущенню: ¬P, що r було найменшим раціональним числом. Таким чином, ми можемо зробити висновок, що початкове положення, P, має бути правдою — «немає найменшого раціонального числа більше 0».

Інші приклади

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

В математичній логіці

В математичній логіці метод від супротивного представляється так: Якщо $S\cup \{P\}⊢𝔽$ тоді $S⊢\mathrm{\neg }P.$ Або, якщо $S\cup \{\mathrm{\neg }P\}⊢𝔽$ тоді $S⊢P.$

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

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

Див. також

• Доведення теорем,
• Дедукція, індукція.