次: 対偶を示す 上: 論証の推進 前: 考え方

間接証明と背理法

間接証明

間接証明というのは広い概念である． 命題$P$が成立することを示すのに， 直接$P$の成立を示すのではなく， 「このような理由で$P$が成立する以外にありえない」 ということを示すのである． 多くの場合，根拠になっているのは排中律，つまり命題$A$か その否定$\overline{A}$のいずれか一方がつねに成立し， $A$でもなければ$\overline{A}$でもないという第三の場合はない， ということである．

代表的な間接証明は対偶証明と背理法である．

対偶証明

命題：「 $P$ ならば $Q$ である」の真偽と， その対偶命題：「 $Q$ でなければ $P$ でない」の真偽は一致する． したっがて［ $P$ ならば $Q$ ］を証明するためには ［$Q$ でなければ $P$ でない］を証明すればよい． 対偶が成立することを示すことで，もとの命題が成立することを示す証明は， 直接に［ $P$ ならば $Q$ ］を証明するのではないから間接証明の一つである．

背理法

この対偶を用いた証明法の応用として背理法がある． 「$Q$ でないと仮定する．すると前提条件 $A$と矛盾が起こる．したがって $Q$が成立する．」 このような証明法を 背理法という．

しかし背理法は「対偶による証明」より応用が広い． $Q$ を示したい，しかし明示的には $A$ が書かれていない． このようなときにも$A$ を適切にとって何らかの矛盾に持ち込めばいいからだ．

その他の間接証明

対象$X$が条件$A$を満たし，対象$Y$も条件$A$を満たす． かつ条件$A$を満たすものはただ一つに定まる． ゆえに$X=Y$である．

これも$X=Y$を直接に示すのではないので， 間接証明である．

その他，「存在の証明」で扱う「鳩の巣原理」$n+1$ 個以上のボールのそれぞれが$n$個の箱のいずれかに入っている．2個以上のボールが入っているはこが存在する．」

あるいは数学的帰納法も間接証明であるし， ある命題 $P\Rightarrow Q$が偽であることを示すのに，反例：$P$であって$Q$ではない例をあげるのも間接証明である．

• 対偶を示す
• 背理法
• ある間接証明
• 問題と考え方