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

背理法

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


例題 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$ 番目の素数を表すとき,不等式

\begin{displaymath}
P_{n+1} \le (P_1P_2 \cdots P_n)+1
\end{displaymath}

が成り立つことを示せ.


解答    

(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}$ なので

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

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

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

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

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


例題 1.16  

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


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

\begin{displaymath}
∴ \quad 2p^2=q^2
\end{displaymath}

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

\begin{displaymath}
2p^2=(2q')^2 \quad \Rightarrow \quad p^2=2{q'}^2
\end{displaymath}

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

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

\begin{displaymath}
∴ \quad 2p^2=q^2
\end{displaymath}

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

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

\begin{displaymath}
∴ \quad 2p^2=q^2
\end{displaymath}

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

\begin{displaymath}
2p^2=(2q')^2 \quad \Rightarrow \quad p^2=2{q'}^2
\end{displaymath}

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

\begin{displaymath}
2{p'}^2={q'}^2
\end{displaymath}

となる.再び $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}$とおく.これから

\begin{displaymath}
2^np^m=q^m
\end{displaymath}

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

\begin{displaymath}
p^m=2^{m-n}{q'}^m
\end{displaymath}

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

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

\begin{displaymath}
x^3-2=0
\end{displaymath}

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

\begin{displaymath}
x^2+bx+c=0\quad b,\ c\ は有理数
\end{displaymath}

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

\begin{displaymath}
x^3-2=(x^2+bx+c)(x-b)+(b^2-c)x+bc-2
\end{displaymath}

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

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

となる.

$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$ であるから

\begin{displaymath}
\vert 1+a+b\vert<\dfrac12,\ \vert 1-a+b\vert<\dfrac12
\end{displaymath}

つまり

\begin{displaymath}
-\dfrac12<1+a+b<\dfrac12,\ -\dfrac12<1-a+b<\dfrac12
\end{displaymath}

を得る. 辺々加えると

\begin{displaymath}
-1<2+2b<1
\end{displaymath}

つまり

\begin{displaymath}
-\dfrac32<b<-\dfrac12
\end{displaymath}

しかし, これは

\begin{displaymath}
\vert f(0)\vert=\vert b\vert>\dfrac12
\end{displaymath}

を意味するので, 仮定と矛盾. よって, $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$ に反する. よって

\begin{displaymath}
\vert f(1)\vert=\vert 1+a+b\vert=\dfrac12,\ \vert f(-1)\vert=\vert 1-a+b\vert=\dfrac12
\end{displaymath}

である. ここで, もし

\begin{displaymath}
1+a+b=\pm\dfrac12,\ 1-a+b=\mp\dfrac12\ (複号同順)
\end{displaymath}

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

\begin{displaymath}
1+a+b=\dfrac12,\ 1-a+b=\dfrac12
\end{displaymath}

が必要である. このとき, $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$ であるから

\begin{displaymath}
\vert 1+a+b\vert<\dfrac{1}{2},\
\vert b\vert<\dfrac{1}{2},\ \vert 1-a+b\vert<\dfrac{1}{2}
\end{displaymath}

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

\begin{displaymath}
\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.
\end{displaymath}
の領域と, 領域 $ -\dfrac{1}{2}<b<\dfrac{1}{2}$には共通部分がない.
これは関数 $f(x)$ が与えられている, つまり存在していることと矛盾する.

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

 

(2)    

\begin{displaymath}
\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}
\end{displaymath}

としたとき,これらの条件をみたすのは図から明らかに $\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}$であるから

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

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

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

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

\begin{displaymath}
f(x)=h(x)
\end{displaymath}

ところが $\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)$. □


next up previous 次: ある間接証明 上: 間接証明と背理法 前: 対偶を示す
Aozora Gakuen