背理法とは？ルート2が無理数である証明問題などの具体例をわかりやすく解説！【排中律】

こんにちは、ウチダです。

今日は数学Ⅰ「集合と命題」で習う

「背理法」

について、簡単に原理を説明した後、「 $\sqrt{2}$ が無理数である」ことの証明問題など、よく出る問題 $3$ 選を順に解説していきます。

また、記事の後半では、背理法と対偶証明法の原理に迫り、それらが本質的に同じであることを解説していきたいと思います。

大学内容というか、一種雑学のような位置づけですが、理解できると面白いのは間違いないです！

背理法とは

背理法を簡単に説明します。

↓↓↓

刑事ドラマや推理小説などで、「もし犯人じゃないと仮定すると、矛盾が生じるからお前が犯人だ！！」という推理をよく目にしませんか？

これ、実は背理法そのものなんですね！

この世には $2$ 種類しかないものが数多く存在します。

例えば

• コインの表裏
• 男か女か
• 甲子園で勝つか負けるか
• オセロの駒が白か黒か
• 犯人か犯人じゃないか

数え上げればキリがありませんね。

こういう思考法のことをよく「白黒思考」と呼びますが、数学において白黒思考はかなり便利です。

たとえば、全体集合が自然数であれば「偶数か奇数か」、全体集合が実数であれば「有理数か無理数か」、この $2$ 種類しかありませんね。

つまり、背理法というのは、「$p$ じゃないと仮定したら矛盾が生じたから $p$ しかあり得ない」という論理構造のもとに成り立っています。

スゴイ便利そうですが、世の中白か黒かだけじゃないし、万能ではなさそうですよね。

「なぜ万能ではないか」については、この記事の2ページ目にて詳しく解説していきたいと思います♪

命題の否定【すべて・ある】

さて、今の話を命題に置き換えていきましょう。

ある命題 $P$ について、真であるか偽であるかを考えたいとします。
※ $P$ は条件ではなく命題なので注意してください。

ここで、命題 $P$ を否定したものを「 $\overline{P}$ 」と表します。

すると、もしこれが集合であったと考えると、補集合の性質より$$P\cup \overline{P}=U$$であり、また$$P\cap \overline{P}=φ$$なので、どちらかは真でどちらかは偽であることがわかります。

⇒参考.「ド・モルガンの法則とは？ベン図・真理値表(論理式)による証明をわかりやすく解説！【練習問題アリ】」

つまり、まとめるとこういうことです。

よって、命題の否定が偽であることを示せれば、間接的に命題が真であることを証明できたことになります。

集合と結び付けて解説しているので、説明の範囲にとどまりますが、これで背理法の原理は何となくつかめたでしょうか。

背理法の簡単な具体例

ここで一度、練習問題を解いておきましょう。

「 $\sqrt{2}$ が無理数である」ことを用いてOKなので、少し易しい問題になっています。

しかし、背理法に慣れていないと、出だしの部分が中々出てこないかもしれません。

特に(2)が少し難しいですね。

(2)のポイントは「結論の一部を否定する」ことです。

【解答】

(1)　「$5-3\sqrt{2}$ は有理数である」と仮定する。

すると、ある有理数 $r$ を用いて、$$5-3\sqrt{2}=r$$と表せる。

この式を整理すると、$$\sqrt{2}=\frac{5-r}{3}$$となる。

ここで、$\frac{5-r}{3}$ は、{(有理数)ー(有理数)}÷(有理数)なので有理数であるが、左辺は問題文より無理数である。

これは矛盾である。

したがって、背理法により仮定が誤りであったことがわかったため、$5-3\sqrt{2}$ は無理数である。

(2)　「 $b≠0$ 」と仮定する。(ここがポイント！)

$2a+3b\sqrt{2}=0$ より、整理すると、$$3b\sqrt{2}=-2a$$

$3b≠0$ なので、両辺を $3b$ で割ると、$$\sqrt{2}=-\frac{2a}{3b}$$

ここで、右辺は有理数であるが、左辺は問題文より無理数である。

これは矛盾である。

よって、背理法により仮定が誤りであったことがわかったため、$b=0$ である。

次に、$b=0$ を $2a+3b\sqrt{2}=0$ に代入すると、$$2a=0$$

よって、$a=0$ である。

したがって、$2a+3b\sqrt{2}=0$ ならば $a=b=0$ である。

(解答終了)

(2)の命題は $p ⇒ q$ という「条件ならば条件」の形です。

この場合の背理法のポイントは「結論のみ否定する」ところです。

つまり、$p かつ \overline{q}$ と仮定し、それが偽であることを示せればOKです。

もう一つのポイントが、$a=b=0$ の否定は $a≠0 または b≠0$ となりますが、あえて $b≠0$ のみを仮定しているところです。

背理法は対偶証明法と違って、何か一つでも矛盾を導くことが目的なので、条件の完全な否定を考えなくても解ける場合があります。

背理法と対偶法の使い分け

今ちらっと話にあがった「対偶証明法(対偶法)」は、皆さんマスターしましたでしょうか。

「対偶法がよくわからない…」という方は、先にこちらの記事をご覧ください！

⇒⇒⇒対偶とは？命題の逆・裏・対偶の意味や証明問題の具体例を解説！【高校数学】

対偶法とは、$\overline{q} ⇒ \overline{p}$ が真であることを証明することで、$p ⇒ q$ を間接的に証明する方法でした。

よって、命題が”ならば”でつながれていないと使いづらいです。
※強引に”ならば”でつなげられる場合もあります。

したがって、”ならば”でつながれていない命題を示すには、ほとんど背理法しかありません。

では、”ならば”でつながれている命題の証明はどうしたらよいでしょうか。

少しまとめてみました。

↓↓↓

対偶法は、”ならば”が真であることを示さなくてはならないので、同値な変形や十分条件をうまく使わなければなりません。

対して、背理法は仮定が $2$ つあるにも関わらず、反例を $1$ つ挙げれば証明完了です。

仮定が $2$ つというのは、条件 $p$ と条件 $\overline{q}$ のことで、偽であることを示すのは、反例を $1$ つでも挙げる(矛盾を示す)ことと等しいです。

しかも、その”矛盾”というのは別に仮定に反さなくても、一般的に証明されている数学的事実に反していればOKです。

こうして見ると、背理法の方が「デキる奴」という印象を持たれるのではないでしょうか。

これは僕の持論ですが、対偶法を「青銅の剣」とした場合、背理法は「エクスカリバー」だと思っています。

なので、まずはコストの低い対偶法で考えてみて、うまくいかない場合はラスボスを倒す力を持つ背理法で考えてみてはいかがでしょうか＾＾

<補足>「すべて」と「ある」の否定

それでは証明問題に…と参りたいのですが、もう一つだけ押さえておきたい知識があります。

それは「すべて」と「ある」の否定です。

これまでいろんな条件の否定について考えてきました。

対偶の記事で学んだのは「かつ」と「または」の否定です。

少し発展的な内容ですが、ここで整理しておきましょう。

まず、”すべて”や”ある”の文言をつけることで、条件は命題に進化します。

たとえば、$$p : x≦2$$だけだと真偽はハッキリしませんが、「すべての $x$ について」を付ければ偽ですし、「ある $x$ について」を付ければ真ですね。

注意していただきたいのは、「すべての $x$ について $p$ 」の否定は「すべての $x$ について $\overline{p}$ 」ではないということです。

なぜならば、否定というのは命題そのものに対して行われるものなので、回りくどいですが「”すべての $x$ について $p$ “というわけではない」となるからです。

これらの意味の違いは大きいですね。

以上で、背理法の概要と補足事項の説明は終わりです。

いよいよ代表的な証明問題に触れていきましょう。

背理法を使う面白い証明問題3つ

背理法を使う問題の代表例としてよく挙げられるのが、

• $\sqrt{2}$ が無理数である
• 素数が無限個存在する

この $2$ つです。

また、「すべて」と「ある」の否定をしっかり理解しているか問うような問題もありますし、そこから面白い事実が判明することもあります。

その問題を $1$ 問用意しました。

計 $3$ 問、どれも内容の濃い重要な問題ですので、順にご覧いただきたく思います！

わからないものは飛ばしてもらって結構です！

ルート2が無理数であることの証明

シンプルながら、中々難しい問題です。

背理法を用いるまではいいのですが、「どの事実との矛盾を指摘すればいいのか」困りますよね。

先ほどの問題では、事実として認めたこの問題に挑戦していきましょう！

【証明】

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

すると、ある整数 $p,q( p≠0 )$ を用いて、$$\sqrt{2}=\frac{q}{p}$$と表すことができる。

ここで、両辺を $2$ 乗して整理すると、$$2p^2=q^2　……①$$この式を利用して矛盾を導いていこう。

(中断)

①の式から矛盾を導く方法としては、

• 互いに素であることを利用
• 素因数分解の一意性を利用
• 無限降下法

以上 $3$ つが知られています。この記事では $2$ つ目まで解説します。

【証明再開1】

有理数は、既約分数で表せる。

つまり、「$p$ と $q$ は互いに素」だと考えられる、

ここで、①の式で、左辺が $2$ の倍数であることから、$$q=2k ( k はある整数)$$

と表すことができる。

この式を①に代入すると、$$2p^2=4k^2$$

両辺を $2$ で割ると、$$p^2=2k^2　……①’$$

こうしてできた①’の式にも同じことが言えて、$$p=2l( l はある整数)$$と表すことができる。

さて、今「 $p$ と $q$ は互いに素」だと条件づけられていたが、$p$ も $q$ も $2$ で割り切れるため、これは矛盾である。

したがって、背理法より、$\sqrt{2}$ は無理数である。

(証明1終了)

証明1では、「有理数を既約分数で表せる」という事実を使う必要があります。

この方法が一番オーソドックスであり一般的ですが、実は $p$ と $q$ が互いに素であることを使わなくても証明ができます。

そのエレガントな方法が、次の証明2です。

【証明2再開】

整数の $2$ 乗を素因数分解したとき、必ず各素因数の個数は偶数個になる。

これは、例えば$$p=a^α×b^β×c^γ$$と素因数分解できたとき、指数法則により$$p^2=a^{2α}×b^{2β}×c^{2γ}$$となることから明らかである。

ここで、①の式で、右辺は $q^2$ より、各素因数の個数は偶数個である。

しかし、左辺は $2p^2$ より、$2$ の素因数の個数が奇数個になってしまう。

これは矛盾である。

したがって、背理法より、$\sqrt{2}$ は無理数である。

(証明2終了)

正確には「任意の自然数の素因数分解が一意に表せることの証明」も必要なのですが、がっつり大学数学なので省略します。

そんなこと当たり前じゃん！と感じる方のために、一つだけ例を挙げましょう。

全体集合を$$1,5,9,…$$というふうに、$4n+1$ と表せる自然数全体とします。

ここで、素数を同じように定義してみると、$$693=9×77=21×33$$と $2$ 通りの素因数分解ができてしまいます。
※この全体集合では、$9=3×3$ とできないため $9$ は素数です。他も同様です。

つまり、全体集合の違いによって、自明ではなくなってしまうから注意が必要である、ということですね。

⇒参考.Wikipedia「算術の基本定理」

もう一つの”無限降下法”については「フェルマーの最終定理の記事」にて解説しております。

⇒⇒⇒フェルマーの最終定理とは？証明の論文の理解のために超わかりやすく解説！

素数が無限個存在することの証明

こちらもシンプルながら、中々難解な問題です。

こういう問題って美しいですよね。

さて、この証明も複数発見されており、この記事では

• ユークリッド「原論」による証明(紀元前 $3$ 世紀ごろ)
• オイラーによる証明( $18$ 世紀)
• サイダックによる証明( $2006$ 年)

以上 $3$ つの証明方法について解説していきます。

<注意>
この問題を取り扱う他の方のサイトも見てみました。大体この $3$ つの方法か、もしくはフェルマー数を利用した方法について解説しているところが多いです。内容がかぶってしまうかもしれませんが、ご了承ください。

【証明1】

素数が有限個であると仮定する。

すると、素数全てを$$p_1,p_2,…,p_n$$とある自然数 $n$ を用いて表すことができる。

ここで、$$P=p_1×p_2×…×p_n+1　……①$$という数を考える。

すると、$p_1$ ～ $p_n$ いずれの素数でも割り切れないので、$P$ も素数となる。

しかし、先ほど $p_1,p_2,…,p_n$ が素数の全てだと仮定したので、新しく素数が作れるはずはない。

よって矛盾である。

したがって、背理法より、素数は無限個存在する。

(証明1終了)

新たな素数を作るプロセス(①の式)が面白いですね＾＾

ここで、誤解してほしくないのが、「素数が有限個だとすると①の式より新たな素数が作れるが、実際素数は無限個なので①が必ず素数であるとは限らない」ということです。

たとえば、有名な例として

があります。

(素数の積+1)という形ではありますが、30031という数は合成数ですね。

【証明2】

素数が有限個であると仮定する。

すると、素数全てを$$p_1,p_2,…,p_n$$とある自然数 $n$ を用いて表すことができる。

ここで、各素数 $p_i$ に対し $\frac{1}{1-\frac{1}{p_i}}$ という数を考える。

これは、初項 $1$、公比 $\frac{1}{p_i}$ の無限等比級数と考えられるので、$$\frac{1}{1-\frac{1}{p_i}}=\sum_{k=0}^{\infty} \frac{1}{{p_i}^k}$$の式が成り立つ。

ここで、$i=1,2,…,n$ までの総乗をとると、

の式が成り立つ。

②の式の左辺は、有限個の実数の積なので有限の値を取るが、右辺は調和級数と呼ばれ、無限に発散する。

よって、(有限)=(無限)の式が成り立つので、これは矛盾である。

したがって、背理法より、素数は無限個存在する。

(証明2終了)

この証明のポイントは、

• ②の式変形がなぜ成り立つのか
• ②の右辺はなぜ発散するのか

この $2$ つです。順に解説していきます。

まず、一つ目のポイントについて、これは以下のように書き表してみるとわかりやすいかと思います。

↓↓↓

※この数式は横にスクロールできます。(スマホでご覧の方対象。)

文字が多くてわかりづらいので、ひとつずつ当てはめていきます。

この式を展開した形を想像すると、「素因数 $2,3,5,…$ を何個含むか」全部バラバラですね。

また、任意の自然数は素因数分解によって一意に定まります。

この $2$ つの事実より、これですべての $\frac{1}{自然数}$ という数を表していることになります。

次に、二つ目のポイントについて、これは数学Ⅲで習う級数の中でも代表例です。

↓↓↓

※この数式は横にスクロールできます。(スマホでご覧の方対象。)

分母の数を大きくすれば、値は小さくなります。

これを利用し、たとえば$$\frac{1}{3}<\frac{1}{4}$$というふうに、すべての数を $\frac{1}{2の倍数}$ に変えます。

すると、$\frac{1}{2}$ を無限回足すことになるので、この級数は発散することがわかりました。

このような式変形のことを“評価”といい、今回は“下から評価”してみました。

“上から評価”するものの代表例としては「バーゼル問題」などが挙げられます。

⇒⇒⇒バーゼル問題とは？東工大入試にも出てきた問題を証明！【円周率に収束】

最後は、つい最近になって発見された、非常に簡潔な証明方法です！

【証明3】

$$a_1=2 , a_n=a_{n-1}(a_{n-1}+1)$$という数列を考えよう。

少しだけ具体的に考えてみると、$$a_2=a_1(a_1+1)=2×3$$$$a_3=a_2(a_2+1)=2×3×7$$$$a_4=a_3(a_3+1)=2×3×7×43$$と続いていく。

ここで、連続する自然数は互いに素である性質を用いると、例えば $a_3+1$ は $a_3$ と互いに素であるから、$a_3$ の素因数では割り切れない数となる。

すると、$a_3+1$ は素数であるかどうかはわからないが、少なくとも $a_3$ とは異なる素因数を持つことは確かだ。

よって、こうして作られた $a_4$ は、異なる素因数を $4$ つ以上持つことが判明した。

これはすべての自然数 $n$ について同様なことが言えるので、$a_n$ は異なる素因数を $n$ 個以上持つ。

したがって、$n$ を限りなく大きくとれば、素因数は無限に作ることができる。

(証明3終了)

実際の証明では、途中の解説が省かれているので、$3$ 行で終わっています！

こんな簡潔な証明が、$21$ 世紀になってからもまだ発見される数学の世界って…ホント面白いですね！

ちなみに、この証明では背理法は用いていません。

背理法を用いない証明は、使う事実をより慎重に選んで矛盾のないように議論しなくてはいけないので、個人的には難しいと思います。

ですが、証明できたときの達成感は、より一層感じられるとは思います。

互いに素な自然数の割った余り【すべて・あるの否定】

目次1.3.1「<補足>「すべて」と「ある」の否定」で学んだ知識を使うときが来ましたね！

このように、“否定”に関する正しい知識を問う問題も出題されやすいです。

「かつ・または」の否定はもちろんのこと、「すべて・ある」の否定もマスターしておいた方がいいでしょう。

【証明】

「割った余りがすべて異なる」わけではないと仮定する。

つまり、ある数において割った余りが等しい、となる。

すなわち、「割った余りが等しいものが存在する」となる。

よって、$p$ で割った余りが等しい数を $ia,ja$ と置くことができる。( $1≦i<j≦p-1$ の自然数)

ここで、$$ja-ia=(j-i)a$$という数を考えてみると、もちろんこれは $p$ の倍数になっているはずである。
∵余りが等しい数同士を引くことで、余りがきれいに消える。

しかし、$a$ と $p$ は互いに素であるため、$j-i$ が $p$ の倍数になっているはずだが、$$0<j-i<p$$より、$p$ の倍数ではない。

よって矛盾である。

したがって、背理法より、命題は真である。

(証明終了)

具体例で確認してみましょう。

たとえば$$a=8,p=5$$とすると、$a$ と $p$ は互いに素です。

ここで、$$8÷5=1あまり3$$$$16÷5=3あまり1$$$$24÷5=4あまり4$$$$32÷5=6あまり2$$なので、$p$ で割ったあまりは確かにすべて異なりますね。

この事実を用いて証明できる定理の例として、「フェルマーの小定理」が挙げられます。

⇒⇒⇒フェルマーの小定理の証明をわかりやすく解説！【東大や京大などの大学入試問題】

続きは次のページへ！

ここまでが高校数学の範囲内です。

いろいろな問題を解けるようになればなるほど、数学を面白く感じられると思います。

次のページでは、冒頭から示唆している通り、「そもそもなぜ背理法や対偶法は成り立つの？」という疑問に真正面からぶつかり、なるべく高校生が読んでもわかりやすい記事にしていきたいと思います。

続きは2ページ目で！！