ユーリの使った背理法のロジック

数学ガール/フェルマーの最終定理の10.3.2「風景から問題を見出す」(p299)でユーリが問題10-1を解いてみせています。そのとき使ったロジックについて考えてみました。

定理


命題\(P, Q, R\)に対して\((\lnot P \land Q) \Rightarrow R\)と\((\lnot P \land Q) \Rightarrow \lnot R\)がどちらも真ならば、\(Q \Rightarrow P\)は真である。

証明


命題\(A,B,C\)に対して
\[(A\Rightarrow B) \land (A \Rightarrow C) \equiv A \Rightarrow (B \land C)\]
だから
\[ ((\lnot P \land Q) \Rightarrow R) \land (\lnot P \land Q) \Rightarrow \lnot Q) \equiv
(\lnot P \land Q) \Rightarrow (R \land \lnot R)
\]
である。また、命題と対偶命題も論理的同値、つまり論理式で書けば
\[ A \Rightarrow B \equiv \lnot B \Rightarrow \lnot A\]
なので
\[
\begin{align*}
(\lnot P \land Q) \Rightarrow (R \land \lnot R)
&\equiv \lnot (R \land \lnot R) \Rightarrow \lnot (\lnot P \land Q)\\
&\equiv (\lnot R \lor R) \Rightarrow (P \lor \lnot Q)
\end{align*}
\]
である。最後の変形にはド・モルガンの法則を使った。\(\lnot R \lor R\)は常に真であることと、
\(\lnot Q \lor P \equiv Q \Rightarrow P\)を使うと
\[
(\lnot R \lor R) \Rightarrow (P \lor \lnot Q)\equiv Q \Rightarrow P
\]
である。従って
\[
((\lnot P \land Q) \Rightarrow R) \land (\lnot P \land Q) \Rightarrow \lnot Q)
\equiv Q \Rightarrow P
\]
が成り立つ。これが示したいことだった。

応用



  1. FLT(4)が成り立つ

  2. フェルマーの最終定理が成り立たず、FLT(4)が成り立つならば、ある3以上の素数pに対してFLT(p)が成り立たない

  3. すべての楕円曲線は、モジュラーである

  4. ある3以上の素数pに対してFLT(p)が成り立たないとすれば、フライ曲線は存在する

  5. フライ曲線は、楕円曲線である

  6. フライ曲線は、モジュラーではない


以上のことが成り立つとすると、フェルマーの最終定理は成り立つ。このことを証明しなさい。

命題の翻訳


まず列挙された定理を論理記号に翻訳する。

  • F:フェルマーの最終定理が成り立つ

  • Ln:FLT(n)が成り立つ

  • T:ある3以上の素数pに対してFLT(p)が成り立たない

  • Px:xは楕円曲線である

  • Qx:xはモジュラーである

  • Rx:xはフライ曲線である


という記号を使うと、上の定理は次のように書ける。

  1. \(A_{1} = L4\)

  2. \(A_{2} = \lnot F \land L4 \Rightarrow T\)

  3. \(A_{3} = \forall x(Px \Rightarrow Qx)\)

  4. \(A_{4} = T \Rightarrow \exists x Rx\)

  5. \(A_{5} = \forall x(Rx \Rightarrow Px)\)

  6. \(A_{6} = \forall x(Rx \Rightarrow \lnot Qx)\)


証明


\(A = A_{1} \land A_{2} \land A_{3} \land A_{4} \land A_{5} \land A_{6}\)とし、\(B\)をある命題とする。上の背理法を使えば\(\lnot F \land A \Rightarrow B\)かつ\(\lnot F \land \Rightarrow \lnot B\)を導けば、\(A \Rightarrow F\)が成り立つ。

i)\(\lnot F \land A \Rightarrow B\)


\(\lnot F\)とすると、\(\lnot F \land L4\)が成り立つので、これと\(\lnot F \land L4 \Rightarrow T\)から\(T\)は真になる。\(T\)と\(T \Rightarrow \exists x Rx\)から、\(Rx\)を真にする\(x\)がある。これを\(\alpha\)と呼ぶことにする。\(R\alpha\)と\(\forall x(Rx \Rightarrow Px)\)から\(P\alpha\)は真である。\(P\alpha , \forall x(Px \Rightarrow Qx)\)から\(Q\alpha\)。従って
\[\lnot F \land A \Rightarrow Q\alpha \]
が成り立つ。

ii)\(\lnot F \land A \Rightarrow \lnot B\)


また、\(R_{\alpha},~~\forall x(Rx \Rightarrow \lnot Qx)\)から\(\lnot Q\alpha\)。従って
\[\lnot F \land A \Rightarrow \lnot Q\alpha\]
である。



(i),(ii)より、\(A \Rightarrow F\)が真になることが証明された。

参考図書


数学: 物理を学び楽しむために


2章に集合と論理について扱っています。物理学を専攻にする人には、一番薦めやすいです。もちろん、他の人にもオススメです。

だれでも証明が書ける


数学の証明に使う論理や、証明の書き方について書かれています。

論理学をつくる


タイトルの通り論理学をつくっていきますが、論理学の標準的な教科書でもあると思います。練習問題には映画ネタが多くて面白いかもしれません。ただし、数学で使うような論理学を軽く超えていきます。