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

Доказательство «от противного» в математике — один из самых часто используемых методов доказательства утверждений. Этот способ доказательства основывается на истинности формулы $((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}$ — иррациональное число.

cs:Důkaz sporem et:Vastuväiteline tõestus he:הוכחה בדרך השלילה nl:Reductio ad absurdum no:Reductio ad absurdum pl:Dowód nie wprost sl:Dokaz s protislovjem sr:Свођење на контрадикцију sv:Indirekt bevis zh-min-nan:Hoán-chèng-hoat