背理法とは
背理法
$p$ を仮定すると矛盾が導かれるとき、$\overline{p}$ が示される。
一言で言えばこれで終わりなのですが、その意味をしっかり分かっている人は余りいないように思います。
矛盾とは
例えば「奇数を2乗すると偶数である」は偽な命題だというだけで、それ自体が矛盾しているわけではありません。
……
「物事の道筋や道理が合わないこと、つじつまが合わないこと、一貫性がないこと。」！
『命題 $p$ に対して、「$p$ かつ $\overline{p}$」を矛盾という。』
「$p$ かつ $\overline{p}$」…
そうなんです。
「$p$ かつ $\overline{p}$」つまり、両立不可能な二つの命題が示されることを矛盾と言います。
中国の故事ではどんな話でしたっけ。
$p$：矛が盾を貫く
$\overline{p}$：盾が矛を防ぐ（矛が盾を貫かない）
中国人ってめちゃ賢い！
（↑歴史的には政治的な批判か何かだったらしいけど、詳しく知らない。）
背理法 再び
$p$ を仮定すると「$q$ かつ $\overline{q}$」が導かれるとき、$\overline{p}$ が示される。
問題１
3個の箱に合計10個の玉を入れるとき、どのような分け方をしても少なくとも1つの箱には4つ以上の玉が入ることを示せ。
こんなの当たり前じゃないですか…？
その方が「背理法」が何者かが分かりやすくなります。
当たり前のことを、もっと当たり前の「矛盾」にまで落とし込むのが背理法です。
まず始めにやることは何ですか？
証明したいことを否定するから…
「どの箱にも4個以上の玉が入らない」を仮定します。
さて、「$q$ かつ $\overline{q}$」を示しにかかりましょう。これが示されると、$\overline{p}$ が示せるというのが背理法です。
ところがです。
仮定した「どの箱の玉も3個以下」から考えた場合は、玉の個数は何個になりますか？
……
10個 かつ 9個以下 が矛盾なんですね！
ということで仮定誤り。
少なくとも1つの箱には4つ以上の玉が入ります。
問題２
$a$ を有理数、$X$ を無理数とする。$a+X$ は無理数であることを示せ。
証明したいことを否定するから…
「$a+X$ は有理数」を仮定します！
よって、
$a+X=\dfrac{n}{m}$
($n,m$:整数 ただし $m\neq0$)
$X=\dfrac{n}{m}-a$
$a=\dfrac{k}{l}$
($k,l$:整数 ただし $l\neq0$)
$X=\dfrac{n}{m}-\dfrac{k}{l}$
この右辺は有理数ですか？
等式が成立するなら $X$ も有理数となるわけですが、問題の前提条件として「$X$ は無理数」がありますから、
「$X$ は無理数 かつ $X$ は有理数」となったことになります。
「これは $X$ が無理数であることと矛盾する」
でよいですかね。
どんな矛盾を見出すか
「右辺は有理数、左辺は無理数なのでこの等式は成り立たない」ではダメですか？
その表現の場合、何と何が矛盾しているか、言えますか？
「$q$ かつ $\overline{q}$」が何かということです。
$X=\frac{n}{m}-\frac{k}{l}$ という等式が成立するわけですが、「右辺は有理数、左辺は無理数」となってしまうので、この等式は成り立たないことにもなります。
つまり、「等式が成立 かつ 等式が不成立」が矛盾となりますかね。とらえかたは色々あると思いますが。
成り立たないことが問題ではなくて、成り立たない式を成り立つとしたことが問題…ということですか。
矛盾はどんなものであっても自由ですが、何と何が矛盾しているかを意識しておきたいですね。
問題３
$a，b$ が有理数、$X$ が無理数とする。
$a+bX=0$ のとき、$a=b=0$
であることを示せ。
「$a,b$ 少なくとも一方が $0$ ではない」を仮定すればいいですか？
否定しすぎると、話が複雑になることがあります。ここでは部分的に否定すると上手くいきます。
この結果、矛盾が導かれれば「$b=0$」が示せたことになります。
$a+bX=0$ で、$b=0$ が分かったら当然 $a$ も $0$ です。
でも、なんで $b$ なんですか？
先に $a$ を示すのではダメなんでしょうか…
証明
$b\neq0$ を仮定する。
$a+bX=0$ を変形すると、
$X=-\dfrac{a}{b}$
となる。
$a,b$ ともに有理数であるので $X$ は有理数となるが、これは $X$ が無理数であることと矛盾する。
よって仮定誤り。$b=0$ となり、このとき $a=0$（証明終わり）
なぜ $b$ からであったか
分母に来るのは $b$ ですから！
これで背理法の構造については大体わかったと思います。
より掘り下げた例や練習問題についてはまた別の機会に。
