次: ある間接証明 上: 間接証明と背理法 前: 対偶を示す

背理法

古来有名な背理法を振り返ろう． これは昔から知られていることを入試問題にしたものだ． 解答を作ってみてほしい．

例題 1.15       ［00北見工業大学］

次の定理と証明について，以下の問いに答えよ．
定理         素数は無限に存在する．
証明         定理が成立しないとすると，素数は有限個である． それらの素数を $p_1,\ p_2,\ \cdots,\ p_n$ とする． このとき， $q=(p_1p_2\cdots p_n)+1$ を考えると， $q$ は $p_1,\ p_2,\ \cdots,\ p_n$ のどれでも割り切れない．${}_{(1)}$ したがって， $q$ を素数の積として表したとき， この積に現れる素数は $p_1,\ p_2,\ \cdots,\ p_n$ のいずれとも異なる． これは矛盾である．${}_{(2)}$ したがって定理が証明された．

(1)

上のように，結論が成り立たないと仮定して矛盾を導き出すことにより 命題を証明する方法を何というか．

(2)

下線(1)の主張がなぜ成り立つかを説明せよ．

(3)

下線(2)で何と何が矛盾するのかを答えよ．

(4)

$P_n$ で小さい方から $n$ 番目の素数を表すとき，不等式

$$P_{n+1} \le (P_1P_2 \cdots P_n)+1$$

が成り立つことを示せ．

解答    

(1)

背理法

(2)

$q$ は $p_1,\ p_2,\ \cdots,\ p_n$ のどれで割っても 1 余るからである．

(3)

$q$は $p_1,\ p_2,\ \cdots,\ p_n$ を因数にもたない1より大きい整数なので， その素因数は $p_1,\ p_2,\ \cdots,\ p_n$ と異なる． よって $p_1,\ p_2,\ \cdots,\ p_n$ がすべての素数であるという仮定と矛盾する．

(4)

$(P_1P_2 \cdots P_n)+1$は $P_1,\ P_2,\ \cdots,P_n$ を因数にもたない 1より大きい整数なので，その素因数 $P$ は $P_1,\ P_2,\ \cdots,P_n$ と異なる．

$P_n$ は小さい方から $n$ 番目の素数なので $P$ は $P_1,\ P_2,\ \cdots,P_n$ より大きい．$P_n$ の次に大きいのが$P_{n+1}$ なので

$$P_1<P_2 <\cdots <P_n<P_{n+1}\le P \le (P_1P_2 \cdots P_n)+1$$

よって題意が示された．□

証明がこのようにできる以上， その証明の前提となる条件がなければならない． $Q$ を「素数は無数にある」という命題として この問題を「 $P$ ならば $Q$ 」の形にするとき $P$ には何が来るのだろう． $P$ としてはこの場合「『素数』を1とそれ自身の他に約数のない数と定める」 という定義命題がとれる．つまりこの証明のなかには素数の定義が前提として入っている．

この証明は本質的にはユークリッドによってなされた． ユークリッドは『原論』のなかで， 素数の個数が三個であるとして矛盾が起こるという形で議論した． ユークリッドは歴史に残る人のなかで，はじめて背理法を用いた人である．

次の命題も， その証明は背理法の典型であるが，背理法の立て方はいくつかある．

例題 1.16  

$\sqrt{2}$ が無理数であることを示せ．

解答1 $\sqrt{2}$が無理数でない，つまり有理数とする． $\sqrt{2}=\dfrac{q}{p}$ とおく．ここで分数を約分し $p$ と $q$ は互いに素であるとする．

$$∴ \quad 2p^2=q^2$$

奇数の平方は再び奇数であるから左辺が偶数なので $q$ は偶数でなければならない． $q=2q'$ とおく．すると

$$2p^2=(2q')^2 \quad \Rightarrow \quad p^2=2{q'}^2$$

これから $p$ も偶数となり， $p$ と $q$ が互いに素であることと矛盾した． ゆえに $\sqrt{2}$は無理数である．□

解答2     $\sqrt{2}$が無理数でない，つまり有理数とする． $\sqrt{2}=\dfrac{q}{p}$ とおく．

$$∴ \quad 2p^2=q^2$$

左辺の因数分解における因数2の個数は奇数である． 右辺の因数分解における因数2の個数は偶数である これは矛盾である． ゆえに $\sqrt{2}$は無理数である．□

解答3     $\sqrt{2}$が無理数でない，つまり有理数とする． $\sqrt{2}=\dfrac{q}{p}$ とおく．

$$∴ \quad 2p^2=q^2$$

奇数の平方は再び奇数であるから左辺が偶数なので $q$ は偶数でなければならない． $q=2q'$ とおく．すると

$$2p^2=(2q')^2 \quad \Rightarrow \quad p^2=2{q'}^2$$

これから $p$ も偶数となり$p=2p'$ とおける．これから再び

$$2{p'}^2={q'}^2$$

となる．再び $p',\ q'$ とも2で割れる．これは何回でも繰り返される． つまり $p$ も $q$ も2で無限回割れる．これは $p=q=0$ 以外では不可能である． ゆえに $\sqrt{2}$は無理数である．□

「 $\sqrt{2}$は無理数である」という命題は「 $P$ ならば $Q$ 」という形はしていない． $P$ のところは少なくとも， 無理数の定義，整数，有理数の定義と性質が入っていなければならない． が，それは当然の前提として命題中には書かれていない． したがって，有理数のどのような性質との矛盾を導くのかによって，いくつかの解法がある．

例題 1.17       ［大阪市大］

次の各問に答えよ

(1)

$m,\ n$ は自然数とする． $m>n$ のとき， $2^{\frac{n}{m}}$は無理数であることを示せ．

(2)

$2^{\frac{1}{3}}$ は有理数を係数とする2次方程式の解にならないことを示せ．

解答

(1)     $2^{\frac{n}{m}}$が有理数と仮定し，既約分数 $2^{\frac{n}{m}}=\dfrac{q}{p}$とおく．これから

$$2^np^m=q^m$$

$p^m,\ q^m$も互いに素で2が素数なので$q$は2の倍数である． $q=2q'$とおく．これを代入し簡約すると

$$p^m=2^{m-n}{q'}^m$$

$m>n$なので右辺は偶数．この結果$p$も2の倍数となり， $\dfrac{q}{p}$が既約分数であること矛盾した． $2^{\frac{n}{m}}$を有理数と仮定するかぎり起こる矛盾なので， $2^{\frac{n}{m}}$は有理数でない，つまり無理数である．

(2)     $2^{\frac{1}{3}}$ は3次方程式

$$x^3-2=0$$

の解である．さらに $2^{\frac{1}{3}}$が有理数係数の2次方程式の解でもあるとする．2次方程式の$x^2$の係数で割ることにより

$$x^2+bx+c=0\quad b,\ c\ は有理数$$

の解であるとしてよい． ここで

$$x^3-2=(x^2+bx+c)(x-b)+(b^2-c)x+bc-2$$

である．ここに $x=2^{\frac{1}{3}}$を代入することにより

$$(b^2-c)2^{\frac{1}{3}}+bc-2=0$$

となる．

$b^2-c\ne 0$なら $2^{\frac{1}{3}}=-\dfrac{bc-2}{b^2-c}$となる． (1)を$n=1,\ m=3$で用いると $2^{\frac{1}{3}}$は無理数なので，矛盾である．

$b^2-c=0$なら$bc-2=0$も成り立ち，$c$を消去して$b^3-2=0$． $b$は実数なので $b=2^{\frac{1}{3}}$となり，$b$が有理数であることと矛盾した．

したがって $2^{\frac{1}{3}}$ は有理数を係数とする2次方程式の解にならないことが示された． □

次の例題もまたいろんな証明法がある．

例題 1.18       ［名大類題］

$a,\ b$ を実数とする．関数 $f(x)=x^2+ax+b \, (-1 \le x \le 1)$ の絶対値の 最大値を $g(a,\ b)$ とする．

(1)

$g(a,\ b) \ge \dfrac{1}{2}$ を示せ．

(2)

等号が成立する $(a,b)$ を求めよ．

解答1

(1)     背理法で示す． $g(a,\ b)<\dfrac12$ とする． つまり, $-1\le x\le1$ のすべての $x$ に対して, $\vert f(x)\vert<\dfrac12$ が成り立つとする． 特に $\vert f(1)\vert<\dfrac12,\ \vert f(-1)\vert<\dfrac12$ であるから

$$\vert 1+a+b\vert<\dfrac12,\ \vert 1-a+b\vert<\dfrac12$$

つまり

$$-\dfrac12<1+a+b<\dfrac12,\ -\dfrac12<1-a+b<\dfrac12$$

を得る． 辺々加えると

$$-1<2+2b<1$$

つまり

$$-\dfrac32<b<-\dfrac12$$

しかし, これは

$$\vert f(0)\vert=\vert b\vert>\dfrac12$$

を意味するので, 仮定と矛盾． よって, $g(a,\ b)\ge\dfrac12$ が示された．

(2)     $g(a,\ b)=\dfrac12$ のとき $-1\le x\le1$ のすべての $x$ に対して, $\vert f(x)\vert\le\dfrac12$ が成り立つ．

$\vert f(1)\vert<\dfrac12$ または $\vert f(-1)\vert<\dfrac12$ の少なくとも一方が成り立つと, (1)と同様に $\vert f(0)\vert=\vert b\vert>\dfrac12$ となる． これは, $g(a,\ b)=\dfrac12$ に反する． よって

$$\vert f(1)\vert=\vert 1+a+b\vert=\dfrac12,\ \vert f(-1)\vert=\vert 1-a+b\vert=\dfrac12$$

である． ここで, もし

$$1+a+b=\pm\dfrac12,\ 1-a+b=\mp\dfrac12\ (複号同順)$$

とすると, $a=\pm\dfrac12,\ b=-1$ になる． この場合 $f(x)=x^2\pm\dfrac12x-1$ となり $\vert f(0)\vert=1$ で不適． $1+a+b,\ 1-a+b$ がともに負となるときも, 明らかに不適． よって

$$1+a+b=\dfrac12,\ 1-a+b=\dfrac12$$

が必要である． このとき, $a=0,\ b=-\dfrac12$ となり, $f(x)=x^2-\dfrac12$ となるので, 確かに, $g\left(0,\ -\dfrac12\right)=\dfrac12$ である． $g(a,\ b)=\dfrac12$ となる $(a,b)$ はこれにかぎることも示された． □

解答2
(1)     $g(a,\ b)<\dfrac12$ とする． つまり, $-1\le x\le1$ のすべての $x$ に対して, $\vert f(x)\vert<\dfrac12$ が成り立つとする． 特に $\vert f(1)\vert<\dfrac12,\ \vert f(0)\vert<\dfrac12,\ \vert f(-1)\vert<\dfrac12$ であるから

$$\vert 1+a+b\vert<\dfrac{1}{2},\ \vert b\vert<\dfrac{1}{2},\ \vert 1-a+b\vert<\dfrac{1}{2}$$

この領域を $ab$ 平面に図示する．

$$\left\{ \begin{array}{l} -a-1-\dfrac{1}{2}<b<-a-1+\dfrac{1}{2}\\ a-1-\dfrac{1}{2}<b<a-1+\dfrac{1}{2} \end{array}\right.$$

の領域と， 領域 $-\dfrac{1}{2}<b<\dfrac{1}{2}$には共通部分がない．
これは関数 $f(x)$ が与えられている， つまり存在していることと矛盾する．

よって, $g(a,\ b)\ge\dfrac12$ が示された．

 

(2)    

$$\vert 1+a+b\vert\le\dfrac{1}{2},\ \vert b\vert\le\dfrac{1}{2},\ \vert 1-a+b\vert\le\dfrac{1}{2}$$

としたとき，これらの条件をみたすのは図から明らかに $\left(0,\ -\dfrac12\right)$ のみ．□

$x^2-\dfrac{1}{2}$ という関数を既知であれば次のような論証が可能である．

解答3    

(1)     $h(x)=x^2-\dfrac{1}{2}$ とおく． これを用いて， $g(a,\ b)<\dfrac{1}{2}$ として矛盾を示す．

$h(x)$ は $x=0$ で最小値 $h(0)=-\dfrac{1}{2}$ をとり， $h(-1)=h(1)=\dfrac{1}{2}$ である． $g(a,\ b)<\dfrac{1}{2}$であるから

$$\left\{ \begin{array}{l} f(-1)-h(-1)<0\\ f(0)-h(0)>0\\ f(1)-h(1)<0 \end{array} \right.$$

したがって $f(x)-h(x)=0$ は $-1<x<0<x<1$ におのおの一個， 合計二個の解を持つ．ところが

$$f(x)-h(x)=ax+b+\dfrac{1}{2}$$

となり，一次式であるから，恒等的に $f(x)-h(x)=0$ が成り立つ． つまり

$$f(x)=h(x)$$

ところが $\vert h(x)\vert$ は $\dfrac{1}{2}$ の値をとる． すなわち $g(a,\ b)<\dfrac{1}{2}$ と矛盾した．
したがって $g(a,\ b) \ge \dfrac{1}{2}$．

(2)     (1)より $g(a,\ b)= \dfrac{1}{2}$になるのが $f(x)=h(x)$ のときだから $a=0,\ b=-\dfrac{1}{2}$．

つまり $(a,\ b)=\left(0,\ -\dfrac{1}{2}\right)$． □

次: ある間接証明 上: 間接証明と背理法 前: 対偶を示す