📂集合論

背理法の数理論理的証明

法則 ¹

$$ (p \land \lnot q) \to c \iff p \to q $$

---

• $c$ は矛盾を意味する。

説明

背理法 あるいは 帰謬法 は、数学全般で本当によく使われる証明法だ。しかし、初めて背理法に接する人は、この言葉自体が生見で拒絶感があるかもしれない。または、ただ慣れただけで、どうして背理法が機能するのか理解していない人もいるだろう。

下の文章を読んで、背理法を理解してみよう：

• (1) 結論 $q$ は真か偽かのどちらかだ。排中律²によって当然だ。
• (2) しかし、$\lnot q$ が真である場合に矛盾が発生するなら、少なくとも $\lnot q$ が真ではないことがわかる。
• (3) (1)では、$q$ は真か偽かのどちらかと言ったけど、$\lnot q$ が偽ならば $q$ は真でなければならない。
• (4) よって、$p \to q$ だ。

理解が難しいなら、数学を抜きにした例で確認してみよう：

• $p$：俺は腕が二本ある。
• $q$：俺は少なくとも腕が一本はある。
• $p \to q$：俺の腕が二本なら、少なくとも一本はある。

まず、言葉だけ見れば背理法も何も、あまりにも当然の事実だ。腕が少なくとも一本ないとどうやって腕が二本あるだろうか？でも、この当たり前の論理がまさに背理法そのものなんだ：

• まず、結論 $q$ を否定して、自分には腕が一本もないと仮定してみよう。
• しかし、仮定 $p$ で、自分の腕は二本と言ったが、これは矛盾だ。
• それならば、自分に腕が一本もないという $\lnot q$ が間違っていると考えるしかない。もちろんこれは、自分に腕が二本あるという仮定 $p$ が成り立つときの話だが、$p \to q$ だ。

証明

$$ \begin{align*} (p \land \lnot q) \to c \iff & \lnot ( p \land \lnot q ) \lor c \\ \iff & \lnot (p \land \lnot q) \\ \iff & \lnot p \lor q \\ \iff & p \to q \end{align*} $$

■