背理法のしくみ - 廃人になれなかった人のために

背理法とは: 命題 $p\to q$ が真であることを証明するために、もしその命題が真でないと仮定すれば矛盾が生じることを示して、もとの命題が真であるという証明法

ですが、自分が高校生のとき[その命題が真でない]→[矛盾]→[もとの命題が真]というプロセスがなんとなくもやもやしていました。なぜそれが正しいのか説明できなかったわけです。

まず、命題 $p\to q$ の否定について考えてみます。高校のとき、 $p\to q$ という文章について、「 $p$ ならば $q$ 」と習いましたが、正確には「 $p$ が正しいとき $q$ も正しいならば、正しい」であり、これについてさらに正確には

$q$ が無条件に正しければ、 $p$ の正否に関わらず $p\to q$ は正しい;
$p$ が正しくないならば、 $q$ の正否に関わらず $p\to q$ は正しい;

となります。つまり、高校のとき自分は $p\to q$ について $p$ が正しくないときを考えておらず、その場合 $p\to q$ の正否がどうなるのかわからなかったわけです。まとめれば

$p$ が真、 $q$ が真で $p \to q$ が真
$p$ が真、 $q$ が偽で $p \to q$ が偽
$p$ が偽、 $q$ が真で $p \to q$ が真
$p$ が偽、 $q$ が偽で $p \to q$ が真

以上より、「命題 $p \to q$ が真でない」とき「 $p$ が真かつ $q$ が偽」となります。これに「矛盾」が生じるとき「 $q$ が偽ならば $p$ は偽」がいえる。これは命題の対偶であり、対偶が真のとき「もとの命題が真」だといえることは高校でも習いました。よって命題が真であることがいえるわけです。つまり

背理法とは: 命題 $p\to q$ が真であることを証明するとき、 $p\to q$ と同等な他の命題である対偶 $\overline{q} \to \overline{p}$ を証明して命題を証明するという間接証明法の一種

だったわけです。