Доказательство от противного

Доказательство «от противного» (лат. Contradictio in contrarium) в математике — один из самых часто используемых методов доказательства утверждений. Этот способ доказательства основывается на истинности формулы $((A\Rightarrow B) \land \neg B) \Rightarrow \neg A$ в классической логике и законе двойного отрицания.

Схема доказательства

Доказательство утверждения $A$ проводится следующим образом. Сначала принимают предположение, что утверждение $A$ неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение $B$, которое заведомо неверно. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение $\neg\neg A$, которое по закону двойного отрицания равносильно утверждению $A$.

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

Пример

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

Допустим противное: $\sqrt{2}$ рационален, то есть представляется в виде несократимой дроби $\frac{m}{n}$, где $m$ и $n$ — целые числа. Возведём предполагаемое равенство в квадрат:

$\sqrt{2} = \frac{m}{n} \Rightarrow 2 = \frac{m^2}{n^2} \Rightarrow m^2 = 2n^2$.

Отсюда следует, что $m^2$ чётно, значит, чётно и $m$; следовательно, $m^2$ делится на 4, а значит, $n^2$ и $n$ тоже чётны. Полученное утверждение противоречит несократимости дроби $\frac{m}{n}$. Значит, исходное предположение было неверным, и $\sqrt{2}$ — иррациональное число.

См. также

• Апагогия
• Приведение к абсурду
• Метод бесконечного спуска