背理法

背理法は、よく使われる証明の方法です。ある命題が成り立つことを証明したいとき、その命題を否定し、否定した命題が正しいと仮定して、矛盾を導こうとします。目的は、選んだ仮定から何かおかしな結論が出てくることを示すことです。

簡単な例

「最小の正の有理数は存在しない」という命題を考えます。この命題を背理法で証明するには、まず命題を否定します。「最小の正の有理数が存在する」とし、その数を q とします。q が最小の正の有理数なら、それより小さい正の有理数は見つからないはずです。もし見つかったら、q は最小ではなくなってしまうからです。

これを使って矛盾を探します。q より小さい数が見つかれば（最小の数として何を選んでもかまいません）、矛盾が導かれ、否定した命題は成り立たないことになります。例えば、最小の数として0.1を選ぶと、0.01のほうが小さいことがわかります。さらに0.001はもっと小さく、0.0001はそれよりも小さく、以下同様です。q を10で割れば、もっと小さい数が得られます。実は、1より大きい数ならどんな数で割ってもかまいません。例えば2で割ると、q の半分は当然 q そのものより小さくなります。

つまり、q/2 は当然 q より小さく、しかも正の有理数です。これで否定した命題との矛盾が導かれたので、否定した命題は成り立たず、もとの命題が成り立つことになります。

おもしろい数

背理法の考え方をよく表す、ゆかいな「証明」として、次の例が有名です。自然数の中には、何らかの意味でおもしろい数があるとします。例えば、2はおもしろい数です。2 · 2 = 2 + 2 が成り立つという、かなり珍しい性質をもっているからです。42もおもしろい数です。究極の疑問の答えだからです。ほかの数についても同じように考えます。では、おもしろい数は無限にあるでしょうか。

逆を仮定します。つまり、おもしろい数は有限個しかなく、おもしろくない数もあるとします。おもしろくない自然数を集めて、おもしろくない数の集合をつくります。そして、その中で最小のおもしろくない数を選びます。ちょっと待ってください。最小のおもしろくない数ですか。それはなかなかおもしろいですよね。

これで矛盾が導かれました。最小のおもしろくない数は実はなかなかおもしろいので、最小のおもしろくない数は存在しえません。したがって、おもしろくない数の集合は空集合でなければなりません。

もちろん、これはこじつけです。おもしろい数とは何かがきちんと定義されていないからです。それでも、証明の進め方そのものは正しいのです。

素数が無限にあることの証明

この例では、前の節と似た方法を使いますが、今度はあらゆる点で正しい証明になります。

素数とは、1とその数自身という2つの異なる数でしか割り切れない数です。この定義には、1はあてはまらず、2はあてはまることに注意しましょう。

素因数分解とは、1以外の自然数を素数の積に分解することです。これは自然数のなかなかおもしろい性質です。1以外のどんな自然数を選んでも、いくつかの（同じものがあってもよい）素数の積に分解できます。例を挙げます。

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

素因数分解についてのこの定理を、算術の基本定理といいます。この定理からは特に、素因数分解がただ1通りであること、つまり1つの自然数に2通りの異なる素因数分解はないことがわかります。また、素因数分解が1つの数だけからなるのは素数だけで、その数はその素数自身です。例えば、7の素因数分解は7だけです。これらの事実を使って、次の命題の証明を組み立てます。

では、「素数は無限にある」という命題を証明しましょう。前と同じように、まず命題を否定します。「素数は有限個しかない」とします。そして、次の数列がすべての素数を表していると仮定します。

$$a_1,a_2,a_3,\dots ,a_n$$

この数列にすべての素数が入っているなら、素数でありながらこの数列に入っていない数は、もう見つからないはずです。すべての素数が数列に入っているので、数列の外に素数があってはいけません。

矛盾を導くには、この数列に入っていない素数をつくらなければなりません。そのために、数列のすべての素数をかけ合わせて1を足した数 q を使います。

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

ここで、この数が素数であるか、または何らかの形で新しい素数を生み出すことを示さなければなりません。q は自然数で、どの自然数も素数の積で表せることはわかっています。ところが、どの素数 a_i も q を割り切りません。割ると、必ず1が余ります。例えば、q を素数 a₂ で割ろうとすると、次のようになります。

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

まず、分数を2つに分けます。1つ目の分数では a₂ を約分でき、素数の積が残ります。これは何かの整数ですが、その値は重要ではありません。2つ目の分数は約分できず、いつも整数ではありません（分母は1にならないからです。1は素数ではありません）。したがって、和は整数ではありません。つまり、素数 a₂ は q を割り切りません。

これで、数列 a_n のどの素数も q を割り切らないことが証明できました。（注：ここでは a₂ の場合しか示していませんが、a₂ を一般の a_i に置きかえれば、簡単に一般化できます。）ところが、どの自然数も素数の積に分解できるので、数列 a_n に入っていない別の素数があって、それが q の素因数分解に現れるはずです。このとき、q 自身が素数であってもかまいません。その場合、素因数分解は q だけからなります。では、最後にもう一度、考えの流れをまとめます。

1. どの自然数も、何らかの素数の積で表せます。
2. 仮定から、数列 a_n にはすべての素数が入っています。
3. 数列にはすべての素数が入っているので、1つ目の主張は「どの自然数も、数列 a_n からいくつかの項を選んだ積で表せる」と言いかえられます。
4. 数列 a_n のどの数も q を割り切らないことを証明しました。
5. これは仮定と矛盾します → どの自然数も素数の積に分解できなければならず、数列 a_n には q を割り切る数がないので、q を割り切り、q の素因数分解に現れる別の素数があるはずです。

これで矛盾が導かれました。q の素因数分解には、すべての素数が入っていると仮定した数列に入っていない素数が含まれます。したがって、否定した命題は成り立たず、もとの命題が成り立ちます。素数は無限にあります。