背理法での方法

質問

40代冴えないサラリーマン。

数学を再勉強中。
　「背理法」で証明した命題は、背理法を使わずに証明できる
この命題は真でしょうか？
それとも背理法でしか証明できない命題はあるのでしょうか？

回答No.3

tmppassenger · ベストアンサー

一応書いておくが、例えば

「√2を有理数と仮定すると、矛盾が生じるので、√2は無理数」

という証明の流れは、（この証明の中の補題で何を使っているかは一先ずおいておいて）、これは「否定の導入」であって、直観論理の議論でいう所の「背理法」では（厳密に言うと）ない。
（繰り返しになるが、証明の途中で背理法を使う補題を使う必要があるかは、ここでは議論しない）
命題Pに対して、「Pを仮定すると矛盾が生じるなら、¬Pを導出して良い」というのは、これは「否定の導入則」で、ある意味否定の『定義』である。背理法を許さない論理体系（直観論理とか）でも、否定の導入は許される。

それに対し、背理法というのは、先ほども書いた通り「¬Pを仮定すると矛盾が生じるなら、Pを導出してよい」というもの。
この例で言うと、「√2を『無理数でない』と仮定すると、矛盾が生じるので、√2は無理数」という証明が背理法にあたる。

ここで、「無理数でない」というのは「有理数でなくない」という事だが、この「有理数でなくない」というのを「有理数である」という風に書き換えることに「二重否定除去則」が必要で、既に書いた通り、二重否定除去則は背理法と同値な論理規則である。なので、背理法が使えないと（例えば直観論理では）、この「無理数でない」というのを「有理数である」と書き換えることが許されない。

で繰り返しになるが、最初から「√2を有理数と仮定すると、矛盾が生じるので、√2は無理数」という風に書いておくと、この証明の流れは、これは否定の導入で、背理法では（厳密には）ない。

.... ここまで読んで「何を言っているのか分からない」という状態であれば、ご質問の内容は一旦考えない方がいいと思います。何かしらの本を読んだ上でのこの質問を思いついたのであれば、多分その本が「否定の導入」と「背理法」を区別していない。

回答No.2

tmppassenger

先程の例を補足すると、

無理数は普通「実数のうち有理数でないもの」。で、実数で無理数でないものは、実数で「有理数でなくない」。で、この「でなくない」を「である」と書き換えてよいのが二重否定除去則。これは背理法と同値な論理規則で、背理法を使わないと、この二重否定除去を使った論理が許されない。

回答No.1

tmppassenger

直観論理の元で考えると：
背理法というのは、「¬Pから矛盾が導かれるなら、Pを導出して良い」という論理規則。
これは二重否定除去則（¬¬PからPを導出して良い）と同値で、排中律（Pか¬Pかのいずれかが成立する）+爆発律（矛盾からは何の命題を導出しても良い）と同値なので、背理法を使わないと、排中律を使うほとんどの命題が証明できない。

例えば、普通無理数は実数のうち有理数でないもの、と定義されているが、この定義だと、「無理数でない実数は有理数」という当たり前の事実が証明できない。