背理法

背理法とは何か

ある命題を証明するとき、その命題の否定を仮定して話をすすめると、つじつまが合わなくなること（矛盾むじゅん (contradiction)）を示し、そのことによって、もとの命題が成り立つと結論する論法がよく用いられる。この論法のことを背理法はいりほう (reduction to absurdity) という。

吹き出し背理法とは何か

背理法という言葉は、一見難しそうなイメージを与えるかもしれないが、実は私達が日常的に使っている論法である。例えば、「あなたがこの文章を読んでいる」ことの証明を考えてみよう。もし、あなたがこの文章を読んでいない（否定）と仮定すると、あなたがこの文章の内容を理解していることと矛盾する。よって、「あなたはこの文章を読んでいる」と証明できるといった具合である。

背理法

次の命題を証明せよ。

  1. 3つの整数 $a,b,c$ が $a^2+b^2=c^2$ を満たすとき、$a,b,c$ のうち少なくとも1つは偶数である。
  2. 三角形の内角のうち、少なくとも1つは $60^\circ$ 以上である。

  1. 3つの整数 $a,b,c$ の全てが奇数であると仮定する。

    $\blacktriangleleft$ 「$a,b,c$ のうち少なくとも1つは偶数である」の否定は「$a,b,c$ の全てが奇数である」となる

    このとき、$a^2,b^2,c^2$ もすべて奇数である。ここで、左辺 $a^2+b^2$ は奇数どうしの和であるから偶数となるが、右辺 $c^2$ は奇数であり、$a^2+b^2=c^2$ を満たすことと矛盾する。

    よって、$a,b,c$ のうち少なくとも1つは偶数である。

  2. 3つの内角の全てが $60^\circ$ 未満であると仮定する。

    $\blacktriangleleft$ 「少なくとも1つは $60^\circ$ 以上である」の否定は「全てが $60^\circ$ 未満である」となる

    このとき、3つの内角の和は $180^\circ$ 未満となり、三角形の内角の和が $180^\circ$ であることと矛盾する。

    三角形の内角のうち、少なくとも1つは $60^\circ$ 以上である。

暗記有名な背理法の応用例

$\sqrt{2}$ が有理数でないことを証明せよ。

$\sqrt{2}$ が有理数であると仮定する。

$\blacktriangleleft$ 整数 $a$ と $0$ でない整数 $b$ によって $\dfrac{a}{b}$ の形で表せる数を、有理数ゆうりすう (rational number) という。

つまり \[\sqrt{2}=\dfrac{a}{b}\] と表される「既約きやく分数である」と仮定する。

$\blacktriangleleft$ $\dfrac{3}{5}$ や $\dfrac{14}{27}$ のように、分母と分子の間に $1$ 以外の公約数をもたない分数のことを、既約分数 (irreducible fraction) という。簡単にいえば、もうこれ以上約分できない分数のことである。

ただし、$a$ は整数、$b$ は $0$ でない整数である。

この両辺を $2$ 乗すると \begin{align} &2=\dfrac{a^2}{b^2}\\ \therefore~~&2b^2=a^2\tag{1}\label{hairihotohananika} \end{align} ここで、左辺は $2$ の倍数なので、右辺 $a^2$ も $2$ の倍数である。したがって、 $a$ も $2$ の倍数である。そこで、$a=2a'$ （$a'$ は整数）とおくと、$\eqref{hairihotohananika}$は \begin{align} &2b^2=(2a')^2\\ \Leftrightarrow~&2b^2=4{a'}^2\\ \therefore~~&b^2=2{a'}^2 \end{align} ここで、右辺は $2$ の倍数なので、左辺 $b^2$ も $2$ の倍数となり、$b$ も $2$ の倍数となる。しかし、そうすると、$a,b$ がともに $2$ の倍数ということになり、最初の「既約分数である」という仮定に矛盾する。

「$p{\Rightarrow}q$」の形をした背理法

「ならば」のいいかえでもみたように、「$p{\Rightarrow}q$」は、「$\overline{p}$ または $q$」と同値なので、この否定は

$\blacktriangleleft$ ド・モルガンの法則（命題版）参照
\[(\overline{\overline{p}\vee{q}})\Leftrightarrow(p\wedge\overline{q})\] である。したがって、$p{\Rightarrow}q$ が真であることを背理法で証明したいときには「$p$ かつ $\overline{q}$」を仮定して矛盾を導くことになる。

$p{\Rightarrow}q$の背理法～その1～

  1. $x$ が無理数ならば $x+3$ も無理数であることを証明せよ。
  2. $x$ が無理数ならば $3x$ も無理数であることを証明せよ。

  1. $x+3$ が $a$ という有理数であると仮定すると \[x=a-3\]

    $\blacktriangleleft$ 有理数どうしの差は有理数である
    より、$x$ は有理数となる。

    これは、$x$ が無理数であることに矛盾する。よって、$x+3$ は無理数である。

  2. $3x$ が $b$ という有理数であると仮定すると \[x=\dfrac{b}{3}\]

    $\blacktriangleleft$ 有理数どうしの比（分数）は有理数である
    より、$x$ は有理数となる。

    これは、$x$ が無理数であることに矛盾する。よって、$3x$ は無理数である。

実数のうち、有理数でないものを無理数という。実数、無理数について詳しくはいろいろな数を参照のこと。

暗記$p{\Rightarrow}q$の背理法～その2～

$a,b,x,y$ が有理数のとき \[a+b\sqrt{2}=x+y\sqrt{2}ならば,a=x\wedge{b}=y\] であることを証明せよ。

$a+b\sqrt{2}=x+y\sqrt{2}$ より \[(b-y)\sqrt{2}=x-a\tag{1}\label{pkaraqnokatatiwositahairiho}\]

$\blacktriangleleft$ 有理数どうしの比（分数）は有理数である
いま、$b\neq{y}$ と過程すると、$\sqrt{2}=\dfrac{x-a}{b-y}$ となるが、$x-a,y-b$ は有理数であるから $\sqrt{2}$ は有理数となる。これは、$\sqrt{2}$ が無理数であることに矛盾する。よって、$b=y$ である。

また、このとき $\eqref{pkaraqnokatatiwositahairiho}$ から $a=x$ となる。

この例題から推測できるように、一般に次のことがいえる。

有理数と無理数は独立している

$a,b,x,y$ が有理数、$\sqrt{z}$が無理数のとき \[a+b\sqrt{z}=x+y\sqrt{z}ならば,a=x\wedge{b}=y\] が成り立つ。