第178回 背理法をめぐって(後編)

「それでは《A<αにならない》ことは証明できるだろうか」とミルカさんは微笑みながら尋ねる。 「論理と証明」第4章後編。
登場人物紹介
:数学が好きな高校生。
テトラちゃんの後輩。好奇心旺盛で根気強い《元気少女》。
ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。
瑞谷先生:司書の先生。定時になると下校時間を宣言する。
$ \newcommand{\LRARROW}{\Leftrightarrow} \newcommand{\SETL}{\bigl\{} \newcommand{\SETM}{\bigm|} \newcommand{\SETR}{\bigr\}} \newcommand{\LAND}{\mathrel{\land}} \newcommand{\LOR}{\mathrel{\lor}} \newcommand{\LNOT}{\lnot} \newcommand{\BITAND}{\mathrel{\&}} \newcommand{\BITOR}{\mathrel{|}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\RELATED}{\dashleftarrow\dashrightarrow} \newcommand{\REAL}{{\mathbb R}} \newcommand{\MINILOGL}{\bigl[\,} \newcommand{\MINILOGR}{\,\bigr]} \newcommand{\LOGL}{\Bigl[\,} \newcommand{\LOGR}{\,\Bigr]} \newcommand{\LOGDOTL}{\Bigl.} \newcommand{\LOGDOTR}{\Bigr.} \newcommand{\BIGLOGL}{\bigg[\,} \newcommand{\BIGLOGR}{\,\bigg]} \newcommand{\BIGBIGLOGL}{\Bigg[\,} \newcommand{\BIGBIGLOGR}{\,\Bigg]} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\IMPLIES}{\Rightarrow} \newcommand{\NATURAL}{{\mathbb N}} \newcommand{\ABS}[1]{\bigl|#1\bigr|} $

図書室にて

テトラちゃんは《$\SQRT{2}$が有理数ではない》ことの証明をめぐって数学トークをしていた(第177回参照)

テトラ「《$\SQRT{2}$が有理数ではない》ことの証明はできたのですが、これ以外にも背理法が使われる証明はあるんでしょうか?」

「それはもちろんあるよ。背理法を使った証明はほんとうに頻繁に出てくるから」

テトラ「そうなんですね……」

テトラちゃんが大きな目をきらきらさせてを見る。

「……え?」

テトラ「……え?」

「どうしたの?」

テトラ「あ、あの……他の問題を出してくださるのかな、と思いまして」

「ああ、そういうこと? うーん、よく出てくるけど、改めて言われると……うん、このあいだこんな問題を見たよ。 簡単な問題だけど」

問題1
$a,b,c$は整数で、 $$ a^2 + b^2 = c^2 $$ が成り立っているとする。 このとき、$a,b,c$のいずれかは偶数になることを証明せよ。

テトラ「$a^2 + b^2 = c^2$というと、三平方の定理ですね? 直角三角形の三辺」

「うん、そう考えてもいいけれど、それ以前に重要な条件があるよね」

テトラ「条件……ああ、《$a,b,c$は整数》ですか?」

「そうだね。使われている文字$a,b,c$がすべて整数であるというのは、とても重要な条件だよ」

テトラ「はい。それで《$a,b,c$は整数》として、$a^2 + b^2 = c^2$が成り立っているとき、$a,b,c$のどれかが偶数だと」

「そうだね。それを証明すればいいんだ」

テトラ「……たとえば、$a = 3, b = 4, c = 5$とすると、$$ \begin{array}{ccccc} a^2 &+& b^2 &=& c^2 \\ \vdots && \vdots && \vdots \\ 3^2 &+& 4^2 &=& 5^2 \\ \vdots && \vdots && \vdots \\ 9 &+& 16 &=& 25 \\ \end{array} $$ ということで、確かに$b = 4$という偶数がありますね」

「うん?」

テトラ「え、まちがっていました?」

「いや、そうじゃなくて、いまテトラちゃんは《試しにやってみた》ってことだよね。 《証明した》と言いたいわけじゃなくて」

テトラ「はい、そうですが……何か、まずかったでしょうか」

「いやいや、それならいいんだよ。問題が与えられたときに、具体的な数を試しに当てはめてみるというのはとてもいいことだから」

テトラ「はいっ! 《例示は理解の試金石》ですものね」

「そう、具体例はとても大切。証明と勘違いしなければね」

テトラ「あの……すみません、先輩がわざわざそのようにおっしゃる理由をお尋ねしてもいいでしょうか」

「うん。あのね、さっきの問題1はこうだよね」

問題1(再掲)
$a,b,c$は整数で、 $$ a^2 + b^2 = c^2 $$ が成り立っているとする。 このとき、$a,b,c$のいずれかは偶数になることを証明せよ。

テトラ「はい」

「整数$a,b,c$の組を$(a,b,c)$と書くと、さっきテトラちゃんが考えたのは$(a,b,c) = (3,4,5)$という一つの組だったわけだね」

テトラ「はい、そうですね。直角三角形の三辺で$3,4,5$というのを覚えていたので、それで確かに$4$という偶数があると思ったんです」

「うん。その確かめはいいんだけど、たった一つの組に対して《$a,b,c$のいずれかは偶数になる》といえても証明が終わったわけじゃない……とそれを言いたかっただけだよ。 もしかしたら、$(3,4,5)$とは別の$(a,b,c)$という組があって、 それは$a^2 + b^2 = c^2$を満たすのにすべてが奇数かもしれないから」

テトラ「はいはい、それはわかっております。大丈夫ですっ! 一つを調べても、ぜんぶを調べたことにはなりませんから」

「そうだね。ところで、この問題1はこんなふうにすれば証明できるよ」

解答1
背理法で証明する。
整数$a,b,c$のすべてが奇数であると仮定して、 左辺と右辺の偶奇に注目する。
 ・左辺:$a$は奇数なので、$a^2$も奇数になる。同様に$b$は奇数なので、$b^2$も奇数になる。 よって、$a^2 + b^2$は奇数と奇数を加えて偶数になる。
 ・右辺:$c$は奇数なので、$c^2$も奇数になる。
すなわち左辺は偶数で、右辺は奇数になり、矛盾する。
よって、整数$a,b,c$のどれかは偶数になる。
(証明終わり)

テトラ「はい、わかります。《証明したいことの否定を仮定して、矛盾を導く》……ですよね?」

「そうだね。証明したいことは、

 《整数$a,b,c$のどれかは偶数である》

だった。$a,b,c$の少なくとも一つは偶数ということだね。言い換えると、

 《$a$は偶数》または《$b$は偶数》または《$c$は偶数》

が証明したいこと。これを否定すると、$a,b,c$は整数だから、

 《$a$は奇数》かつ《$b$は奇数》かつ《$c$は奇数》

つまり、

 《整数$a,b,c$はすべて奇数である》

が背理法の仮定になるね」

テトラ「はいはい」

「あとは左辺と右辺の偶奇に注目して計算するだけ。この証明の中では、$b = 4$のような具体的な数はまったく出さずに、 すべての整数について成り立つような論理を重ねてきたことになるね。 そして、最後に矛盾を導けば、背理法で証明ができたことになる……という流れ」

テトラ「はい、分かります。左辺は偶数、右辺は奇数になって矛盾……あれ? 矛盾?」

「そうだよ」

テトラ「質問です! 矛盾というのは、《$Q$である》と《$Q$ではない》が両方いえることですよね? 左辺は偶数で、 右辺は奇数というのも矛盾なんでしょうか?」

「ああ、そうだね。確かにそこには省略があるといえばあるね。もともと前提として、

《$a^2 + b^2 = c^2$である》

といえていた。 ところが、すべて奇数だと仮定すると、 左辺と右辺の偶奇が異なる。 偶奇が異なるなら、左辺と右辺は等しくない。 つまり、

《$a^2 + b^2 = c^2$ではない》

といえる。 矛盾しているよね?」

テトラ「確かに!

 《$a^2 + b^2 = c^2$である》と《$a^2 + b^2 = c^2$ではない》

がいえてますね。《$Q$である》と《$Q$ではない》という形……納得です!」

「さっきの解答1では省略があるといえばあるけれど、証明としては問題ないと思うよ。もっと省略して書いてもいいくらい。 こんなふうに」

解答1a
整数$a,b,c$のすべてが奇数であると仮定すると、 $a^2 + b^2$は偶数になるが、$c^2$は奇数になって矛盾。 よって、整数$a,b,c$のどれかは偶数になる。
(証明終わり)

テトラ「短いですね!」

「短く書くときでも《仮定したこと》と《矛盾が起きたところ》ははっきりさせたほうがいいと僕は思うよ。もっと極端に短く書くなら『背理法を使う。両辺の偶奇を考えれば明らか』とでもなるかなあ。 これはまちがいとはいえないけど、証明というよりも証明の方針っぽいね。 問題集の答えだとよく《略解》とか《略証》みたいに書かれてる」

場合分け

テトラ「はい……先輩、あたし、ちょっと違う方法がありそうって思ったんですが」

「この問題1で?」

テトラ「そうです。整数というのは偶数か奇数かどちらかですよね」

「そうだね。だからさっきも偶奇を考えたわけだし」

テトラ「ということはですよ。$a,b,c$のそれぞれが偶数か奇数かの《場合の数》は、全部で、ええと、$2 \times 2 \times 2$で$8$通りですよね。そのすべてを考えるというのはどうでしょう!」

「お?」

テトラ「表を作ればいいですよね……こうでしょうか」

$a,b,c$の偶奇の全パターンを考える
$$ \begin{array}{|c|c|c|} \hline a & b & c \\ \hline \text{偶数} & \text{偶数} & \text{偶数} \\ \text{偶数} & \text{偶数} & \text{奇数} \\ \text{偶数} & \text{奇数} & \text{偶数} \\ \text{偶数} & \text{奇数} & \text{奇数} \\ \text{奇数} & \text{偶数} & \text{偶数} \\ \text{奇数} & \text{偶数} & \text{奇数} \\ \text{奇数} & \text{奇数} & \text{偶数} \\ \text{奇数} & \text{奇数} & \text{奇数} \\ \hline \end{array} $$

「それはそれでいいけど……」

テトラ「ええと、これで、$a^2 + b^2 = c^2$を……あれれ?」

「ねえ、テトラちゃん。こんなふうに$a,b,c$すべての偶奇を考えるのはいいけれど、結局ね《$a,b,c$すべてが奇数というパターン》以外では、 《整数$a,b,c$のどれかは偶数になる》がすぐに成り立つ。 だから、ちゃんと考えなくちゃいけないのは《整数$a,b,c$すべてが奇数である》というパターンだけ。 《整数$a,b,c$すべてが奇数である》というパターンを考えたらどうなるか、 というのは、まさにさっき僕が書いた解答1や解答1aになるよね」

テトラ「あちゃちゃ……そうですね。遠回りして同じ所に来ちゃいました」

「うん。でも、この表はこの表でおもしろいよ。だって、さっきから考えていたのは否定を作ることだから。《(1)整数$a,b,c$のどれかは偶数になる》を否定して、 《(2)整数$a,b,c$すべてが奇数である》を背理法の仮定にした。 テトラちゃんの表を見ると(1)が$7$パターンあって、(2)が$1$パターンあるということがよくわかる」

$a,b,c$の偶奇の全パターンを考える
《(1)整数$a,b,c$のどれかは偶数になる》
《(2)整数$a,b,c$すべてが奇数である》 $$ \begin{array}{|c|c|c|l|} \hline a & b & c & \\ \hline \text{偶数} & \text{偶数} & \text{偶数} & \text{(1)} \\ \text{偶数} & \text{偶数} & \text{奇数} & \text{(1)} \\ \text{偶数} & \text{奇数} & \text{偶数} & \text{(1)} \\ \text{偶数} & \text{奇数} & \text{奇数} & \text{(1)} \\ \text{奇数} & \text{偶数} & \text{偶数} & \text{(1)} \\ \text{奇数} & \text{偶数} & \text{奇数} & \text{(1)} \\ \text{奇数} & \text{奇数} & \text{偶数} & \text{(1)} \\ \text{奇数} & \text{奇数} & \text{奇数} & \text{(2)} \\ \hline \end{array} $$

テトラ「確かにそうですね」

「うん。《(2)整数$a,b,c$すべてが奇数である》というパターンがありえないとわかると、 残りのパターンしか起こりえない。でも、 それらはすべて《(1)整数$a,b,c$のどれかは偶数になる》を満たしている。 すべてのパターンが尽くされているから証明完了」

テトラ「ですね!」

ミルカさん

そこにミルカさんがやってくる。

ミルカ「今日は整数問題?」

「というか、証明問題かな」

テトラ「背理法を使って証明する練習をしていたんです。《証明したいことの否定を仮定して、矛盾を導く》」

ミルカ「ふむ。それなら、こんな問題は?」

問題2
実数$\alpha$(アルファ)に収束する実数列$a_1,a_2,a_3,\ldots$を考える。 すなわち、 $$ \lim_{n \to \infty} a_n = \alpha $$ である。
この数列に対して、ある定数$A$が存在し、 $1$以上の任意の整数$n$について、 $$ a_n < A $$ が成り立つとする。このとき、 $$ \alpha \LEQ A $$ であることを証明せよ。


テトラ「……」

「これは……ああ、なるほど? これ、けっこうきわどい話じゃない?」

ミルカ「意味不明だな。どこがきわどい?」

「たとえばね……」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに11巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

hyuki 金曜日は『数学ガールの秘密ノート』の日。最新回はお休み。無料リンク2個をツイート。公式 「論理と証明」第4章(後編) 【01/06 13:35まで無料 】 https://t.co/UT6c5kYyUG 3年弱前 replyretweetfavorite

aramisakihime 今回の問題については、僕はテトラちゃんレベルでしたね。イプシロンを決めるのが苦手だったと思い出しました。 約3年前 replyretweetfavorite

pad_alex6 イメージできるのは大切だなと思う。 約3年前 replyretweetfavorite

kazzzarion 「ε-Nなのか。僕はδ-εで習った。」って書こうとしてたら気がついた。自然数だからか。 約3年前 replyretweetfavorite