ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

背理法と前提の関係

まず、背理法の定義を確認します。

背理法(はいりほう、英: proof by contradiction, reduction to the absurd, indirect proof, apagogical argument など、羅: reductio ad absurdum)とは、ある命題 P を証明したいときに、P が偽であると仮定して、そこから矛盾を導くことにより、P が偽であるという仮定が誤り、つまり P は真であると結論付けることである。

背理法 - Wikipedia

Wikipediaに限らず、多くの本・資料で背理法はこのように説明されています。この定義には前提に対する説明がありません。また、「P が偽であると仮定して、そこから矛盾を導く」とあります。これらから以下の疑問を持つかもしれません。

  • そもそも背理法での証明に前提を置いてよいのか?
  • 背理法は仮定から導いた結果と前提との矛盾を導くことでも証明できるのか?
  • 前提が複数あるとき、背理法は仮定から導いた結果と前提の一つが矛盾すると導ければ証明できるのか?

結論としてはいずれも「できる」です。これを記号論理学の証明例を用いて説明します。
説明には「記号論理入門(金子 洋之・著)」を参照します。

記号論理入門 (哲学教科書シリーズ)

記号論理入門 (哲学教科書シリーズ)


背理法は¬-導入則とDN規則の組み合わせです。以下に導出の流れを示します。

1 (1) ¬P 仮定
a1,...,an,1 (i)
a1,...,an (j) ¬¬P 1-i.¬-導入
a1,...,an (k) P j.DN規則

この導出の流れは「P が偽であると仮定して、そこから矛盾を導くことにより、P が偽であるという仮定が誤り、つまり P は真であると結論付ける」となっています。

¬-導入則:
ある式 A を仮定して論証を進めた結果、矛盾が導かれたならば、最初に仮定した式の否定 ¬A を導いてよい。

¬-除去則:
ある式とその否定の両方が導かれるとき、矛盾を表す式 ⊥ を導いてよい。

DN規則:
前もって ¬¬A が導かれているとき、A を導いてもよい。


これを踏まえて次の式の証明を見ます。
 P ⇒ Q, ¬Q ⊢ ¬P

この式の証明は以下の通りです。

1 (1) P ⇒ Q 前提
2 (2) ¬Q 前提
3 (3) P 仮定
1,3 (4) Q 1,3.⇒-除去
1,2,3 (5) 2,4.¬-除去
1,2 (6) ¬P 3-5.¬-導入

P を仮定して矛盾 ⊥ を導き、仮定した式の否定 ¬P を導くという¬-導入則を利用しています。

ここで注目していただきたいのが、仮定 P から導いた Q と前提 ¬Q から¬-除去則を利用して矛盾 ⊥ を導いたということです。つまり、矛盾を導くために前提を利用しています。

背理法は¬-導入則とDN規則の組み合わせであり、この証明の¬-導入則で導く流れを利用できます。つまり、この証明例から以下のことが言えます。

  • 背理法での証明に前提を置いてよい
  • 背理法は仮定から導いた結果と前提の矛盾を導くことでも証明できる
  • 前提が複数あるとき、背理法は仮定から導いた結果と前提の一つが矛盾すると導ければ証明できる


もし、前提だけで矛盾が導ける場合はどう扱うべきでしょうか。例えば、次の式です。
 P, ¬P ⊢ Q
これは爆発律(Principle of explosion)と呼ばれ、前提が矛盾していればどんな式も成り立つことを示しています。
参考:
矛盾許容論理 - Wikipedia
Principle of explosion - Wikipedia

背理法は「P が偽であると仮定して、そこから矛盾を導く」とあり、仮定から矛盾を導くことが必要です。この点が前提の矛盾だけで導く爆発律と異なります。


仮定から導いた結果と前提の一つとの矛盾を導くことで証明(背理法)した例を引用します。

前提 1 カツオが鉢植えを壊していないならば、カツオは野球ボールを持っていない。
前提 2 カツオは野球ボールを持っている。
結論 カツオが鉢植えを壊した。

  1. ここで、結論である「カツオが鉢植えを壊した」を導くために、そうでないと暫定的に仮定してみる。すなわち、「カツオは鉢植えを壊していない」と仮定してみる。
  2. すると、前提 1 から → 除去規則により、「カツオは野球ボールを持っていない」ことが帰結する。
  3. しかし、それは前提 2 の「カツオは野球ボールを持っている」と矛盾する。
  4. すなわち、「カツオは鉢植えを壊していない」と仮定すると、矛盾に陥る。

したがってその仮定が間違っていたのであり、「カツオは鉢植えを壊した」と結論することができる。(この最後のステップが背理法。)

http://abelard.flet.keio.ac.jp/person/takemura/class/2013/3-print-nk.pdf