背理法で証明する：否定を使った証明テクニック - 記号論理学

否定（¬）の扱いは、自然演繹の中でも特に興味深い部分です。否定を導入するには背理法を使い、否定を除去するには矛盾から任意の命題を導きます。これらの規則は、数学の証明で頻繁に使われる重要なテクニックです。

矛盾と爆発律

まず、矛盾について確認しましょう。p と ¬p が同時に成り立つ状況を矛盾といいます。記号では ⊥（ボトム、falsum）で矛盾を表すことがあります。

矛盾からは何でも導けます。これを爆発律（ex falso quodlibet）といいます。

$$\frac{p\neg p}{q}(\perp E)\text{または}\frac{\perp }{q}$ p と ¬p が両方成り立つなら、任意の q を結論できます。これは奇妙に見えるかもしれませんが、「偽の前提からは何でも従う」という含意の性質から自然に導かれます。 <!-- outer_0 --> ## 否定導入（¬I）：背理法 否定導入は、背理法（reductio ad absurdum）に対応します。p を仮定し、そこから矛盾が導かれるなら、¬p を結論できます。 $\frac{[p]⋮\perp }{\neg p}(\neg I)$ 「p を仮定したら矛盾に至った。だから p は偽である」という推論です。数学の証明で「p と仮定すると...となり矛盾。よって p でない」というパターンはこの規則に対応します。 <!-- outer_1 --> ## 否定除去（¬E） 否定除去は、二重否定を除去する規則です。¬¬p から p を導きます。 $\frac{\neg \neg p}{p}(\neg \neg E)$$

「p でないことはない」なら「p」だ、という推論です。これは古典論理では当然ですが、直観主義論理では認められない規則です（後で触れます）。

背理法による証明の例

排中律 p ∨ ¬p を背理法で証明してみましょう。

まず ¬(p ∨ ¬p) を仮定します。p を仮定すると、選言導入で p ∨ ¬p が導け、仮定 ¬(p ∨ ¬p) と矛盾します。よって ¬p が導けます。

¬p から選言導入で p ∨ ¬p が導け、再び ¬(p ∨ ¬p) と矛盾します。つまり ¬(p ∨ ¬p) を仮定すると矛盾に至ります。

よって ¬¬(p ∨ ¬p) が導け、二重否定除去で p ∨ ¬p を得ます。

対偶を使った証明

p → q から ¬q → ¬p を証明するのにも、否定の規則を使います。

¬q を仮定し、p を仮定します。p と p → q から q を導きます。q と ¬q で矛盾になるので、¬p を結論します。含意導入で ¬q → ¬p を得ます。

これがモーダストレンスの正当化でもあります。

背理法の強力さ

背理法は非常に強力な証明手法です。直接証明が難しいとき、否定を仮定して矛盾を導くことで、元の命題を証明できます。

無理数の存在証明（√2 が無理数であることの証明）は、有理数と仮定して矛盾を導く背理法の典型例です。このように、数学全体で背理法は広く使われています。

次回は、これまで学んだ規則を公理系としてまとめる方法を学びます。