背理法

同義語：proof by contradiction帰謬法

概要

前提知識: 論理と命題, 含意, 否定

$\sqrt2$ が分数で書けないことは、次のように示される。仮に $\sqrt2=a/b$（$a,b$ は正の整数で、約分しきった分数）と書けたとする。両辺を 2 乗すると $a^2=2b^2$ なので $a$ は偶数であり、$a=2c$ とおくと $b^2=2c^2$ となって $b$ も偶数になる。約分しきったはずの分数の分子と分母がともに偶数になり、矛盾する。したがって最初の「仮に」が誤りであり、$\sqrt2$ は分数で書けない。同じように、$\log_23=m/n$（$m,n$ は正の整数）と書けたとすると $2^m=3^n$ となり、左辺は偶数、右辺は奇数で矛盾する。示したい主張が偽だと仮定して矛盾を導き、主張が正しいと結論するこの論法が 背理法 である。
背理法は、「どんな分数でも表せない」「素数はどこまでも続く」のように、すべての可能性を排除しなければならない主張で特に力を発揮する。主張を否定すると「こういう分数がある」「素数はこれで全部」という具体的な出発点が手に入り、そこから議論を進められるからである。

定義

以下、命題は真・偽のいずれか一方に定まるものとし（古典論理の立場）、$\lnot P$ は $P$ の否定、$P\Rightarrow Q$ は含意を表す（記号の意味と真理値表は論理と命題の記事の定義「論理結合子と真理値表」による）。矛盾とは、ある命題 $C$ について $C$ と $\lnot C$ の両方を導くこと、すなわち命題 $C\land\lnot C$ を導くことをいう。$C\land\lnot C$ は $C$ の真偽によらず偽である。

背理法

命題 $P$ を証明するために、$\lnot P$ を仮定し、そこから正しい推論によって矛盾（ある命題 $C$ について $C\land\lnot C$）を導き、それによって $P$ が成り立つと結論する証明の方法を 背理法（proof by contradiction）または 帰謬法 という。
特に $P$ が条件文「$A$ ならば $B$」（$A\Rightarrow B$）の形のときは、$A$ と $\lnot B$ をともに仮定して矛盾を導き、$A\Rightarrow B$ が成り立つと結論する。

矛盾として導く命題 $C$ は、証明を始める時点では決まっていなくてよい。冒頭の $\sqrt2$ の例では $C$ は「$a$ と $b$ の少なくとも一方は奇数である」、$\log_23$ の例では $C$ は「$2^m$ は偶数である」（$2^m=3^n$ は奇数なので $\lnot C$ も成り立つ）であった。$C$ が仮定そのものの一部であることも、よく知られた事実（「$1$ は偶数でない」など）であることもある。ラテン語の名前 reductio ad absurdum（不合理への帰着）で呼ばれることもある。
背理法と並んでよく使われるのが、対偶による証明である。条件文 $A\Rightarrow B$ に対し、$\lnot B\Rightarrow\lnot A$ をその対偶（contrapositive）といい、$A\Rightarrow B$ を示す代わりに「$\lnot B$ を仮定して $\lnot A$ を導く」方法を 対偶による証明 という。$A\Rightarrow B$ とその対偶の真偽が一致することは、論理と命題の記事の命題「基本的な恒真式」の 2 で真理値表により示されている。条件文 $A\Rightarrow B$ を示す 3 つの型を並べると次のようになる（Lev §1.4.5、p. 74 にも同じ形の一覧がある）。

証明の型	仮定するもの	導くもの
直接証明	$A$	$B$
対偶による証明	$\lnot B$	$\lnot A$
背理法	$A$ と $\lnot B$	ある命題 $C$ について $C\land\lnot C$

対偶 $\lnot B\Rightarrow\lnot A$ を、逆 $B\Rightarrow A$ や裏 $\lnot A\Rightarrow\lnot B$ と取り違えてはならない。逆と裏は一般に元の命題と真偽が一致しない（$A$ を「$n=2$」、$B$ を「$n$ は偶数」とすると、$A\Rightarrow B$ は真だが、逆「$n$ が偶数なら $n=2$」は $n=4$ で偽である）。

直感

背理法の筋道は、「もし $P$ が偽なら、ありえないことが起こる。ありえないことは起こらないので、$P$ は偽ではない」というものである。正しい推論は真の前提から偽の結論を導かないので、偽の結論（矛盾）が出たなら、前提のどこかが偽である。正しいと分かっている事実と、ただ 1 つの仮定 $\lnot P$ から矛盾が出たのだから、偽なのは $\lnot P$ であり、$P$ は真である（Lev §1.4.4、p. 71 はこの説明を真理値表の言葉で与えている）。
直接証明では「何を仮定して始めるか」が主張から決まるが、「$\sqrt2$ は無理数である」のように否定の形をした主張では、直接には何も仮定できない。背理法は、主張を否定することで「$\sqrt2=a/b$」という扱える等式を出発点として与える（Ham 第 6 章 §6.1、p. 140）。その代わり、どの命題 $C$ で矛盾が出るかは前もって分からず、証明は探索になる。

例と反例

2 の平方根は無理数

$\sqrt2$ は無理数である。すなわち $\sqrt2=a/b$ となる整数 $a,b$（$b\neq0$）は存在しない。
背理法で示す。$\sqrt2=a/b$ となる整数 $a,b$ があると仮定する。$\sqrt2>0$ なので $a,b$ は正にとれ、約分して $a$ と $b$ がともに偶数ではないとしてよい。両辺を 2 乗して分母を払うと
$$ a^2=2b^2 $$
である。$a$ が奇数なら $a=2k+1$ と書けて $a^2=2(2k^2+2k)+1$ は奇数となり、偶数 $2b^2$ に等しいことに反するので、$a$ は偶数である。$a=2c$ とおくと $4c^2=2b^2$、すなわち $b^2=2c^2$ であり、同じ理由で $b$ も偶数である。これは「$a$ と $b$ はともに偶数ではない」に反する。よって仮定は誤りで、$\sqrt2$ は無理数である。
これは Ham 第 6 章 §6.1（p. 139）、Lev Example 1.4.15（p. 73）の証明と同じ筋である。有理数の記事の命題「2の平方根は有理数でない」、無理数の記事の定理「冪根の無理性」（素因数を使う一般化）も参照。

素数は無限にある

素数は無限に多く存在する。
背理法で示す。素数が有限個しかないと仮定し、それらを全部並べて $p_1,\dots,p_r$ とする（$p_1=2$ なので $r\ge1$）。
$$ N:=p_1p_2\cdots p_r+1 $$
とおくと $N\ge3$ であり、$N$ はある素数 $q$ で割り切れる（素数の記事の命題「素因数の存在」。下の ex-pbc-least-counterexample でも示す）。素数は $p_1,\dots,p_r$ で全部なので $q=p_i$ となる $i$ がある。$q$ は $N$ と $p_1\cdots p_r$ をともに割り切るので、その差 $1$ を割り切る。しかし $q\ge2$ なので $q$ は $1$ を割り切らず、矛盾する。よって素数は無限に存在する。
Ham 第 6 章 §6.1（p. 140）はこの形で述べている。一方、素数の無限性の記事で証明「Euclidの証明」の直後に注意されているように、議論の中身は「与えられた有限個の素数から、そのどれとも違う素数を作る」手続きであり、背理法の形をとらなくても書ける。背理法の枠は、この手続きを「素数全部」に当てはめるために使われている。

2 を底とする 3 の対数は無理数

$\log_23$ は無理数である。
背理法で示す。$\log_23$ が有理数であると仮定する。$3>1=2^0$ なので $\log_23>0$ であり、$\log_23=m/n$（$m,n$ は正の整数）と書ける。$2^{m/n}=3$ の両辺を $n$ 乗すると
$$ 2^m=3^n $$
である。$m\ge1$ なので左辺は偶数であり、右辺は奇数の積なので奇数である。これは矛盾である。よって $\log_23$ は無理数である。
無理数の記事の例「2 を底とする対数」も同じ証明を与え、相異なる素数 $\ell_1,\ell_2$ について $\log_{\ell_1}\ell_2$ が無理数であることへ一般化している。

反例：否定の取り違え

主張「すべての整数 $n$ について $n^2\ge n+1$」を背理法で「証明」しようとして、次のように書いたとする。「主張が偽であると仮定すると、すべての整数 $n$ について $n^2< n+1$ である。しかし $n=2$ では $4<3$ となり矛盾する。よって主張は正しい。」
この主張は偽である（$n=0$ では $0\ge1$、$n=1$ では $1\ge2$ がいずれも成り立たない）。誤りは最初の行の否定にある。「すべての $n$ について $Q(n)$」の否定は「ある $n$ について $\lnot Q(n)$」であり（De Morganの法則の記事の命題「量化子のDe Morganの法則」）、「すべての $n$ について $\lnot Q(n)$」ではない。正しい否定「ある整数 $n$ について $n^2< n+1$」は $n=0$ で実際に成り立つので、そこからは矛盾が導けない。この例は、「$\lnot P$ でない命題 $R$ を仮定して矛盾が出れば $P$ が成り立つ」という含意を破っている。矛盾から否定できるのは仮定した命題 $R$ だけであり、$R$ が $\lnot P$ より強い（$R\Rightarrow\lnot P$ だが逆は成り立たない）とき、$R$ が偽であることは $P$ を意味しない。

反例：矛盾が誤った推論から出る

ex-pbc-sqrt-two をまねて、$\sqrt4$ が無理数であることを「証明」してみる。「$\sqrt4=a/b$（$a,b$ は正の整数で、ともに偶数ではない）と仮定すると $a^2=4b^2$ なので $a$ は偶数であり、$a=2c$ とおくと $b^2=c^2$ である。$\sqrt2$ の場合と同様に $b$ も偶数となり、矛盾する。」
$\sqrt4=2=2/1$ は有理数なので、この結論は偽である。誤りは「$b$ も偶数となる」の一歩にある。$b^2=c^2$ からは $b=c$ しか分からず、実際 $a=2$、$b=c=1$ は仮定をすべて満たし、$b$ は奇数である。$\sqrt2$ の証明で $b$ が偶数になったのは $b^2=2c^2$ の右辺に因数 $2$ が残ったからであり、その一歩は $2$ が平方数でないことを使っていた。背理法の結論が正しいのは、$\lnot P$ から矛盾に至る各段が正しい推論であるときに限る。誤った一歩で矛盾を「導いた」なら、偽である責任を $\lnot P$ に負わせることはできない。この例は「$\lnot P$ から矛盾らしきものが出れば $P$ は真」という含意を破っており、欠けているのは推論の正しさである。

性質

背理法の論理的な根拠

背理法の正しさ

任意の命題 $P,C$ について、命題 $\lnot P\Rightarrow(C\land\lnot C)$ の真偽は $P$ の真偽と一致する。また任意の命題 $A,B,C$ について、命題 $(A\land\lnot B)\Rightarrow(C\land\lnot C)$ の真偽は $A\Rightarrow B$ の真偽と一致する。

真理値表による

論理と命題の記事の定義「論理結合子と真理値表」による。$C\land\lnot C$ が真であるには $C$ と $\lnot C$ がともに真でなければならないが、$C$ が真なら $\lnot C$ は偽なので、$C\land\lnot C$ は $C$ の真偽によらず偽である。含意 $X\Rightarrow Y$ は $X$ が真で $Y$ が偽のときに限り偽なので、$Y$ がつねに偽のとき、$X\Rightarrow Y$ は $X$ が偽のときに真、$X$ が真のときに偽である。
前半：$X=\lnot P$ とすると、$\lnot P\Rightarrow(C\land\lnot C)$ が真であることは $\lnot P$ が偽であること、すなわち $P$ が真であることと同値である。
後半：$X=A\land\lnot B$ とすると、$(A\land\lnot B)\Rightarrow(C\land\lnot C)$ が偽であることは $A\land\lnot B$ が真であること、すなわち $A$ が真で $B$ が偽であることと同値である。一方 $A\Rightarrow B$ が偽であるのも、$A$ が真で $B$ が偽のときに限る。両者は同じ場合に偽、残りの場合に真なので、真偽が一致する。$\square$

背理法による証明は、$\lnot P$ を仮定して $C\land\lnot C$ を導くことで命題 $\lnot P\Rightarrow(C\land\lnot C)$ を（直接証明で）示している。prop-pbc-validity によりこれは $P$ を示したことと同じである（Ham 第 6 章 §6.1、p. 138 も同じ真理値表で説明している）。条件文の場合は後半を使う。$A\Rightarrow B$ が偽になるのは「$A$ が真で $B$ が偽」の場合だけなので、その場合がありえないことを示せばよい（Ham §6.2、p. 141）。

対偶による証明との関係

対偶による証明から得られる背理法

命題 $A,B$ について、$\lnot B$ を仮定して $\lnot A$ が導けるなら、$A$ と $\lnot B$ を仮定して矛盾 $A\land\lnot A$ が導ける。したがって、対偶による証明は、矛盾として導く命題 $C$ を $A$ そのものにとった背理法に書き直せる。

仮定 $A$ と導いた $\neg A$ を並べる

$A$ と $\lnot B$ を仮定する。仮定 $\lnot B$ から、与えられた推論により $\lnot A$ が導ける。一方 $A$ は仮定そのものである。よって $A\land\lnot A$ が導け、これは $C:=A$ とした矛盾 $C\land\lnot C$ である。prop-pbc-validity の後半により、これは $A\Rightarrow B$ の証明になる。$\square$

逆に、条件文 $A\Rightarrow B$ を背理法で示した証明が、仮定 $A$ を使わずに $\lnot B$ から $\lnot A$ を導き、仮定 $A$ と衝突させる形になっていることがある。そのような証明は、$A$ の仮定を消せばそのまま対偶による証明になり、そのほうが簡潔である。Ham §6.4（p. 143）はこの理由から、直接証明や対偶による証明がうまくいかないときに背理法を使うよう勧めている。Lev Example 1.4.17（p. 74）の鳩の巣原理の証明も、背理法の形で書かれているが、導いた矛盾が仮定の否定そのものなので対偶による証明と見ることもできる、と注意されている。

否定・全称・存在の主張

主張の形によって、背理法の最初の仮定は次のようになる。

否定の形 $\lnot P$ を示す：$\lnot(\lnot P)$ を仮定することになるが、これは $P$ と同値なので、$P$ を仮定して矛盾を導けばよい（Ham 第 9 章 §9.3、p. 178）。「$\sqrt2$ は有理数でない」「素数は有限個でない」はこの形である。
全称の形「すべての $x$ で $Q(x)$」を示す：その否定「ある $x$ で $\lnot Q(x)$」を仮定する。すると $\lnot Q(x)$ を満たす具体的な $x$ が 1 つ手に入り、それについて議論できる（Ham §6.1、p. 140）。否定を「すべての $x$ で $\lnot Q(x)$」と取り違えると ex-pbc-wrong-negation の誤りになる。
存在の形「ある $x$ で $Q(x)$」を示す：その否定「すべての $x$ で $\lnot Q(x)$」を仮定して矛盾を導く。この方法で得られる存在証明は、条件を満たす $x$ を具体的に示さないことがある（下の rem-pbc-intuitionistic）。

最小反例による証明

自然数についての主張「すべての $n$ で $P(n)$」を背理法で示すとき、反例（$P(n)$ が成り立たない $n$）があると仮定したら、その中で最小のものをとることができる。これは数学的帰納法の記事の定理「自然数の整列原理」（空でない自然数の部分集合は最小元をもつ）による。最小の反例 $m$ より小さい数では主張が成り立つので、それを使って $m$ でも成り立つことを示せば矛盾になる。この形を 最小反例による証明 という（Ham 第 10 章 §10.3、p. 191 は、帰納法と背理法の混成として紹介している）。

素因数の存在を最小反例で示す

$2$ 以上のすべての整数は素数で割り切れる。
$2$ 以上の整数で、どの素数でも割り切れないものがあると仮定する。そのような整数全体は $\mathbb{N}$ の空でない部分集合なので、整列原理により最小のもの $m$ がある。$m$ は $m$ 自身を割り切るので、$m$ が素数なら $m$ は素数で割り切れて $m$ のとり方に反する。よって $m$ は素数でなく、$m\ge2$ なので $m=ab$、$1< a< m$ と書ける。$2\le a< m$ なので、$m$ の最小性から $a$ はある素数 $p$ で割り切れる。$p\mid a$ かつ $a\mid m$ なので $p\mid m$ であり、$m$ のとり方に反する。よって $2$ 以上のすべての整数は素数で割り切れる。
素数の記事の命題「素因数の存在」は、同じ事実を「$1$ より大きい最小の約数は素数である」として直接示している。

直観主義論理との関係

直観主義論理では一般には使えない形

背理法の根拠 prop-pbc-validity は、命題が真か偽のどちらかに定まるという古典論理の立場（排中律 $P\lor\lnot P$）に立っている。「証明できたこと」を「真であること」とみなす直観主義論理では、2 つの形を区別する。

$P$ を仮定して矛盾を導き $\lnot P$ を結論する形は、直観主義論理でも正しい。直観主義論理では $\lnot P$ は「$P$ から矛盾が出る」ことそのものとして定義されるからである（直観主義論理の記事の定義の節、否定 $\lnot\varphi:=(\varphi\to\bot)$）。ex-pbc-sqrt-two や ex-pbc-primes はこの形であり、主張は「〜でない」という否定である。
$\lnot P$ を仮定して矛盾を導き $P$ を結論する形は、そのままでは $\lnot\lnot P$（「$P$ でないことはない」）しか示さない。$P$ を結論するには二重否定除去 $\lnot\lnot P\Rightarrow P$ が要るが、これは直観主義論理では一般には証明できず（直観主義論理の記事の系「直観主義論理で証明できない式」）、排中律を認めることと同じ強さである（同記事の命題「排中律と二重否定除去」）。
同様に、$A\Rightarrow B$ から対偶 $\lnot B\Rightarrow\lnot A$ を得る向きは直観主義論理でも証明できるが、逆向き（対偶から元の条件文を得る向き）は一般には証明できない（同記事の例「直観主義論理で証明できる式」の 3）。存在の主張 $B$ を「存在しないと仮定すると矛盾する」で示すと、$A:=\top$（真な命題）、$B$ を存在の主張として上の対偶の議論に当てはめれば、得られるのは $\lnot\lnot B$ であり、$B$ を結論するには先に述べた二重否定除去 $\lnot\lnot B\Rightarrow B$ が要る。これは直観主義論理では一般には証明できないので、「存在しないと仮定すると矛盾する」という形の証明は、直観主義論理では存在の証明にならない。同記事の冒頭にある「$a^b$ が有理数になる無理数 $a,b$ がある」の証明は、排中律に頼って、どちらの組が答えなのかを示さない典型例である。通常の数学は古典論理に立つので、背理法はどの形でも正しい証明法として使われる。