直接には手がかりの無い主張でも、否定を仮定すると具体的な式が手に入ることがあります。それを利用する証明の方法を定めます。
1 背理法の手順
定義 1.1 (背理法). 証明したい主張を否定して仮定し、その仮定と既知の事実とから矛盾を導くことによって、もとの主張が正しいと結論する証明の方法を 背理法 (proof by contradiction) という。
否定を仮定すると矛盾が出るのだから否定は誤りであり、したがってもとの主張が正しい、という筋道です。
主張を証明するとき、次の順に進めます。
- の否定を仮定します。「もしでないとすると」と書き出し、が具体的に何を主張しているのかを、式や条件の形で書き下します。
- その仮定と、すでに示されている事実とから推論を進めます。
- 矛盾に到達します。矛盾とは、ある命題についてとの両方が導かれること、またはのように偽であることが分かっている命題が導かれることです。
- 矛盾がどの仮定から出たのかを明示します。証明の中で用いた仮定は、もとの主張の前提と、手順1で置いたの二つです。前提は正しいものとして与えられているので、誤っているのはのほうです。
- が誤りであると結論し、が正しいとします。
手順1と手順4を省略しないことが重要です。手順1で否定を正確に書き下すことができなければ、その後の推論は別の主張についての議論になってしまいます。手順4を書かなければ、読み手は、導かれた矛盾がどの仮定を否定する根拠になるのかを判断することができません。
2 対偶による証明との違い
命題を対偶によって証明するときは、を仮定してを導きます。背理法によって証明するときは、とを仮定して、両立しない二つの命題を導きます。が成り立つという前提の下で矛盾が生じるため、追加した仮定を棄却し、が成り立つと結論します。
対偶による証明では、導くべき命題はと定まっています。背理法では、との両方を用いることができますが、導く矛盾がどの二つの命題の間に生じるかは、個々の議論によって異なります。
証明の方法を選ぶときは、結論を否定するとどのような式や条件を得ることができるかを調べます。からを導く手がかりがある場合は対偶を用い、否定した結論と前提から両立しない命題を導く手がかりがある場合は背理法を用います。
3 の無理性
定理 3.1 (の無理性).は無理数である。
直接示そうとすると、無理数であることは「有理数として表すことができない」という否定的な主張なので、手がかりを取り出すことが困難です。否定を仮定すると、逆に手がかりが増えます。
証明 (背理法による).が有理数であると仮定する。互いに素な整数を取り、かつと書く。両辺を2乗すると
である。は偶数なので、§A3.6 定理 2.1によりは偶数である。となる整数を取ると、よりとなる。再び§A3.6 定理 2.1によりも偶数である。はともに2で割り切れるので、互いに素であることに矛盾する。したがって、が有理数であるという仮定は誤りであり、は無理数である。▨
否定を仮定したことによって「と書くことができる」という具体的な式が手に入り、以降は整数の計算として進めることができました。背理法は、直接には手がかりのない主張について、計算することができる形の仮定を作り出す方法です。
例 3.2. 正の有理数の中に最小の数は存在しない。最小の正の有理数が存在すると仮定する。最小性から、どの正の有理数に対してもである。は正の有理数なので、も正の有理数であり、である。ところがとするととなり、矛盾する。したがって、最小の正の有理数は存在しない。
閑話休題：無理数がもたらした最初の衝撃が無理数であるというこの背理法の証明は、数学史上もっとも古い衝撃の一つでした。古代ギリシャのピタゴラス学派は、万物は整数の比によって表すことができると考えていましたが、正方形の対角線と一辺の比（）がどのような整数比によっても表すことができないことが、この証明によって明らかになります。伝説では、この事実を学派の外へ漏らしたヒッパソスが、海に投げ込まれて命を落としたと伝えられています。
背理法は、とのどちらか一方は必ず正しいという排中律と深く結び付いています。存在を示す証明には、条件を満たす実物を一つ作って見せるものと、存在だけを保証するものがあります。たとえば、無理数、でが有理数になる組が存在します。を考え、が有理数であればとすれば済みます。無理数であれば、とすると
で有理数です。どちらの場合にも組は存在するのに、どちらが本当であるかは言い当てていません。排中律を認めない立場は、こうした「作らずに、あるとだけ言う」証明を疑い、実際に構成することを求めます。