背理法

背理法とは、数学における証明方法の1つである。帰謬法とも呼ばれる。

概要

ある命題Aを証明したいが直接証明するのが難しい時に使われる手法。

手順としては、

1. まずAの否定が成立すると仮定する。
2. そこから矛盾を導き出す。
3. よって、Aの否定は成立しないので、命題Aは成立する。

となる。

つまり、「Aの否定を仮定し、そこから正しい論理のみで式変形などを施すと、ありえない結論に行きついてしまう。これは最初の仮定が間違っていたからに違いない。」という証明方法である。

なお、命題Aを仮定して矛盾が導けたときに、命題Aの否定が成立する、というのは厳密には背理法ではない。これは否定の導入と呼ばれ明確に区別される。後述する「√2が無理数であることの証明」なんかがわかりやすい。

• 実数のうち、有理数はq/p(qは整数、pは自然数)で表される数である(約分の都合上、pとqは互いに素と置いても一般性を失わない)
• 実数のうち、有理数でないものを無理数と呼ぶ

このように定義されるため、「√2が有理数である」を仮定して矛盾が導けたならば、否定の導入により「√2が有理数でない」、すなわち「√2が無理数である」がいえてしまう(厳密には、√2が実数であることの確認が必須となるが、これは明らかである)。ただ、これらも含めて背理法と呼ぶことがある。

排中律

この証明方法の土台となるのは、「命題Aと命題Aの否定のどちらかが必ず成立する」という排中律という法則である。例えば、ある実数については「有理数であるか有理数でないか（無理数であるか）」のどちらかが必ず成立し、また、ある複素数については「実数であるか実数でないか（虚数であるか）」「代数的数であるか代数的数でないか（超越数であるか）」のどちらかが必ず成立することになる。

排中律は通常の論理学(古典論理学)では正しいが、直観主義論理など論理体系によっては排中律は無条件では認められず、命題毎に「命題と命題の否定のどちらかが必ず成立する」ことの証明が必要になる場合もある。

背理法と排中律と二重否定の除去が互いに同一であることの証明

背理法(「Aでない」を仮定して矛盾が導けたならば、その仮定を除去して「Aである」を導くことができる)と排中律(「AであるまたはAでない」は仮定なしに用いてもよい)と二重否定の除去(「Aでない」の否定はAである)は、すべて互いに同値である。これは、以下の手順により、それぞれ証明ができる。

背理法→排中律

1. ¬(A∨¬A)を仮定する
2. Aを仮定する
3. ∨の導入により、AからはA∨¬Aがいえる
4. ¬の省略により、A∨¬Aと¬(A∨¬A)からは矛盾が導ける
5. したがって、¬の導入により、2の仮定を消去して¬Aが導ける
6. ∨の導入により、¬AからはA∨¬Aがいえる
7. ¬の省略により、A∨¬Aと¬(A∨¬A)からは矛盾が導ける
8. 背理法により、1の仮定を消去してA∨¬Aが導ける
9. もはや何の仮定も残っていないので、A∨¬Aは仮定なしに導いてよい

排中律→背理法

1. Aを仮定する
2. ¬Aから矛盾が導けたとする
3. 矛盾ルールにより、¬Aから矛盾が導けたところからAは導ける
4. ∨の省略により、Aと¬Aを仮定から除去してA∨¬Aを仮定した場合にAが導けるとすることができる
5. ここで、A∨¬Aは排中律により仮定なしに導いてよいので、仮定は何も残らない

背理法→二重否定の除去

1. ¬¬Aを仮定する
2. ¬Aを仮定する
3. ¬の省略により、¬Aと¬¬Aからは矛盾が導ける
4. 背理法により、2の仮定を除去してAが導ける

二重否定の除去→背理法

1. ¬Aを仮定し、矛盾が導けたとする
2. ¬の導入により、¬Aの仮定を除去して¬¬Aが導ける
3. 二重否定の除去により、Aが導ける

二重否定の除去と排中律が等価である

以上の4つにより、排中律、二重否定の除去がそれぞれ背理法と等価であることが示せているわけだから、背理法を媒介してこの2つの間の等価性も示せる。

主だった用途

この証明方法がよく使われるパターンとして、「ある数が無理数や超越数であることの証明」「ある条件を満たす数が無数に存在することの証明・存在しないことの証明」などが挙げられる。これは、それらの否定である「有理数である」「代数的数である」「有限個しかない」「存在する」などが数式で表しやすいのに対し、「無理数である」「超越数である」「無限個存在する」「存在しない」ことを数式で表すのが困難であるからである。

証明における使用例

√2が無理数であることの証明

おそらく、一番有名な背理法による証明である。

1. √2が無理数であることの証明のため、仮に命題が成り立たないとし、「√2が有理数である」と仮定する。
2. 有理数は必ず既約分数（これ以上約分できない分数）で表されるので、互いに素な正の整数a、bを用いて、√2=b/aと表せると仮定する。（√2は正の数なので、あらかじめa,bは正の整数としてよい。）
3. √2=b/aの両辺を2乗して2=b²/a²、両辺にa²を掛けて2a²=b²とする。
4. ここで、b²は「2×整数」で表されているので偶数となるので、bも偶数となる。（対偶の「bが奇数ならばb²は奇数」が成立するので、「b²が偶数ならばbは偶数」も成立する。）
5. bが偶数となるので、ある正の整数cを用いてb=2cと表すことができる。2a²=b²に代入して2a²=4c²、つまり2c²=a²となる。
6. ここでbと同様の議論によりaも偶数となり、aもbも偶数であることが示された。
7. しかし、aもbも偶数であることは、「aとbが互いに素」という仮定に反する。
8. この矛盾は、そもそも「√2=b/aと表すことができる有理数」と仮定したことで起きるので、「√2は有理数」という仮定は間違っている。よって√2は無理数である。

√2が無理数であることの証明：別証

素因数分解の一意性（任意の正の整数はただ1通りの素数の積に表すことができる）を利用する。

1. 互いに素な正の整数a,bを用いて、√2=b/aと表せると仮定し、2a²=b²を導くところまでは同じ。
2. aを素因数分解した際に2がm回掛けられているとし、bを素因数分解した際に2がn回掛けられているとする。
3. 2a²=b²の左辺の2a²には2の因数が2m+1個含まれ、右辺のb²には2の因数が2n個含まれていることになる。
4. 2m+1は明らかに奇数、2nは明らかに偶数なので、2a²=b²の両辺の2の因数の個数が異なることになるが、これは素因数分解の一意性に反する。
5. よって「√2=b/aと表すことができる有理数」という仮定が間違っていることになり、√2は無理数となる。

log₁₀2が無理数であることの証明

1. 互いに素な正の整数a,bを用いて、log₁₀2=b/aと表せると仮定する。（log₁₀2は正の数なので、あらかじめa,bは正の整数としてよい。）
2. 対数の定義より10^b/a=2となり、両辺をa乗して10^b=2^a、すなわち2^b・5^b=2^aとなる。
3. 2^b・5^b=2^aの左辺に5の因数はb個含まれるが、右辺には5の因数は含まれず、素因数分解の一意性に反する。
4. よって「log₁₀2=b/aと表すことができる有理数」という仮定が間違っていることになり、log₁₀2は無理数となる。

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

1. 素数が有限個と仮定し、最大の素数をMと仮定する。
2. 全ての素数の積に1を加えた数P=2×3×5×7×…×M+1を考える。
3. このとき、Pが素数ならば、明らかにP>Mなので、「Mが最大の素数」という仮定に反する。また、Pが合成数ならば、Pは明らかにM以下の素数を因数に持たない（式の形より、M以下のどの素数で割っても1余る）ので、PはMより大きい素数を因数に持つことになるが、これも「Mが最大の素数」という仮定に反する。
4. いずれの場合も「Mが最大の素数」という仮定が成立しないので、この仮定が間違っていることになり、最大の素数は存在せず、素数は無数に存在する。

関連動画

関連項目

• 数学
• 論理学
• 対偶
• 数学関連用語の一覧