競技数学と問題解決

背理法

主張の否定を仮定し、矛盾を導くことで証明する技法。

直観反対を仮定し、それが崩れるのを見る

刑事が容疑者が犯行現場にいたことを証明したいとしよう。直接の証拠を探す代わりに、刑事はこう言う:「容疑者が現場にいなかったと仮定しよう。すると彼だけが残せるこの足跡を残せなかったはずだ。しかし足跡はここにある——矛盾だ。だから容疑者はそこにいたに違いない。」これはまさに背理法の形である:命題 $P$ を証明するために、その反対 $\neg P$ を仮定し、論理的帰結を忠実にたどり、それがすでに真と分かっていることと衝突することを示す。誤った仮定だけが不可能な結論に至る唯一の道であるため、 $\neg P$ は偽でなければならず、したがって $P$ が成り立つ。

曲線

y=x^2-2

はちょうど

x=\sqrt{2}

でゼロを横切る;以下の背理法による証明は、この交点が決して二つの整数の比になり得ないことを示す。

中高背理法の論理的な形

定義: 背理法

命題 $P$ を背理法で証明するには、 $\neg P$ ( $P$ の反対)を仮定し、そこから有効な論理的手順と既に確立された事実のみを用いて、ある命題 $Q$ とその否定 $\neg Q$ を導く。 $Q \wedge \neg Q$ は常に偽であるため、それを導いた仮定 $\neg P$ は偽でなければならず、したがって $P$ は真である。

\neg P \Rightarrow (Q \wedge \neg Q)

ここで $P$ は証明したい命題であり、 $Q$ はその真偽の両方を $\neg P$ から導ける任意の命題である——多くの場合 $Q$ はすでに真と分かっている事実(「 $\gcd(p,q)=1$ 」など)であり、その否定を意図せず導いてしまう。 $\neg P \Rightarrow (Q \wedge \neg Q)$ が確立され $Q \wedge \neg Q$ が不可能であれば、論理は $\neg P$ 自体が不可能であることを強制する、すなわち $P$ が成り立つ。

\sqrt{2} = \frac{p}{q}, \quad \gcd(p,q)=1

この二番目の式は、 $\sqrt{2}$ が無理数であるという古典的証明を始めるための具体的な仮定である:ここで $p$ と $q$ は $q \neq 0$ を満たす整数であり、 $\gcd(p,q)=1$ という要求は分数 $\frac{p}{q}$ がすでに既約分数として書かれていることを意味する。証明(以下で完全に示す)は、この仮定が $p$ と $q$ の両方を偶数にすることを強制し、 $\gcd(p,q)=1$ と矛盾することを示す。

証明戦略の比較
方法	仮定	目標
直接証明	$P$	既知の事実を用いて $P$ から直接 $Q$ を導く
背理法	$\neg P$	$\neg P$ から $Q$ と $\neg Q$ の両方を導く
無限降下法	最小の反例が存在する	厳密により小さい反例を構成し、最小性と矛盾させる

大学二つの古典的な背理法証明

定理:

\sqrt{2}

の無理性

$\sqrt{2}$ は無理数である。すなわち $q \neq 0$ を満たす整数 $p,q$ で $\sqrt{2} = \frac{p}{q}$ となるものは存在しない。

なぜ正しいのか?

ある数が整数の比ではないことを直接代数的に示す方法はない。それは無限に多くの分数を確認することを意味するからである;背理法はそのような分数が既約分数として存在すると仮定し、その一つの仮定から不可能な偶奇性の事実を引き出すことでこれを回避する。

証明

背理法として、 $\sqrt{2}$ が有理数であると仮定する。すると $q \neq 0$ を満たす整数 $p,q$ で $\sqrt{2} = \frac{p}{q}$ と書け、共通因数を約分することで $\gcd(p,q)=1$ (既約分数)と仮定してよい。

両辺を2乗すると $2 = \frac{p^2}{q^2}$ となり、 $p^2 = 2q^2$ を得る。これは $p^2$ が偶数であることを意味する。奇数の平方は奇数であるため、 $p$ 自身が偶数でなければならない;ある整数 $k$ について $p = 2k$ と書く。

代入すると $(2k)^2 = 2q^2$ となり、 $4k^2 = 2q^2$ 、これは $q^2 = 2k^2$ に簡約される。これは $q^2$ が偶数であることを意味し、同じ推論により $q$ も偶数でなければならない。

しかし今や $p$ と $q$ の両方が偶数であるため、 $2$ は両方を割り切り、 $\gcd(p,q)=1$ という仮定と矛盾する。この矛盾は、 $\sqrt{2}$ が $\frac{p}{q}$ と書けるという当初の仮定が偽でなければならないことを示す。したがって $\sqrt{2}$ は無理数である。

定理: 素数が無限に存在するというユークリッドの証明

素数は無限に存在する。

なぜ正しいのか?

無限に多くの素数を直接列挙して主張を検証することは不可能であるため、代わりに背理法では有限の完全なリストが存在すると仮定し、まさにそのリストから、リストが不完全であることを暴く数を作り出す。

証明

背理法として、素数が有限個しかないと仮定し、 $p_1, p_2, \dots, p_n$ をそのすべての完全なリストとする。

数 $N = p_1 p_2 \cdots p_n + 1$ を考える。 $N > 1$ であるため、少なくとも一つの素因数を持たなければならない;それを $p$ と呼ぶ( $1$ より大きいすべての整数は素因数を持つ)。

仮定より $p_1, \dots, p_n$ はすべての素数のリストであるため、 $p$ はある $i$ について $p_i$ に等しくなければならない。特に $p$ は積 $p_1 p_2 \cdots p_n$ を割り切る。

しかし $p$ は $N = p_1 p_2 \cdots p_n + 1$ も割り切る。 $p$ が $p_1 p_2 \cdots p_n$ と $N$ の両方を割り切るならば、 $p$ はそれらの差 $p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1$ も割り切る。

どの素数も $1$ を割り切ることはできない、なぜならすべての素数は $1$ より大きいからである。これは矛盾である。したがって当初の仮定——素数が有限個しかない——は偽でなければならず、素数は無限に存在する。

大学実世界での応用と具体例

背理法は競技数学をはるかに超えて働く道具である:計算機科学者はそれを用いて不可能性結果を証明し(停止性問題を解けるアルゴリズムは存在しない、最悪の場合に $n\log n$ を超える比較ソートは存在しない)、暗号研究者はそれに頼って、ある方式を破ることが困難だと信じられている問題を解くことを意味すると論じ、技術者は安全上重要な不可能性の主張を論じるのに使う(「もし圧力がこの値を超えていれば封が破れていたはずだが、封は無傷である、よって圧力は一度も超えていない」)。最小の反例を仮定してそれを縮小する変種である無限降下法は、数論やアルゴリズムの停止性の議論で特によく見られる。以下の二つの例は、背理法と無限降下法を具体的な組合せ問題に適用したものである。

例: 欠陥のあるチェス盤:タイル張りにおける矛盾

$8 \times 8$ のチェス盤から対角の2つの隅のマスを取り除き、 $62$ マスが残る。このボードが、それぞれちょうど $2$ 個の隣接マスを覆う $31$ 個のドミノで完全に覆えないことを証明せよ。

解答

背理法として、そのような $31$ 個のドミノによるタイル張りが存在すると仮定する。

チェス盤を通常の黒白交互パターンで彩色すると、 $32$ マスの黒と $32$ マスの白を持つ。各ドミノは隣接する2マスを覆うため、常にちょうど1つの黒マスと1つの白マスを覆う(隣接するマスは常に反対の色を持つ)。

したがって、 $31$ 個のドミノを用いたタイル張りは、ちょうど $31$ 個の黒マスと $31$ 個の白マスを覆うことになる——合計 $62$ マスが色によって均等に分かれる。

しかし、標準的なチェス盤の対角の2つの隅は常に同じ色である(これは標準彩色の性質である)。それらを取り除くと一方の色の $2$ マスが失われ、その色の $30$ マスともう一方の色の $32$ マスが残る。

これはボードが実際には一方の色の $30$ マスともう一方の色の $32$ マスを持つことを意味し、どのようなタイル張りによっても $31$ 対 $31$ に分けることはできない。これはステップ3の数え(各色ちょうど $31$ )と矛盾するため、仮定したタイル張りは存在し得ない。

例: 無限降下法: $a^2=2b^2$ の非自明解は存在しない

無限降下法を用いて、方程式 $a^2 = 2b^2$ が正の整数 $a,b$ における解を持たないことを証明せよ。

解答

背理法として、正の整数解が存在すると仮定する。すべての正の整数解 $(a,b)$ の中から、 $b$ が可能な限り最小のものを選ぶ——これは正の整数が整列順序を持つため可能である(正の整数の空でない任意の集合には最小元が存在する)。

$a^2 = 2b^2$ より右辺は偶数なので $a^2$ は偶数であり、したがって $a$ 自身も偶数である(奇数の平方は奇数である)。ある正の整数 $a_1$ について $a = 2a_1$ と書く。

代入すると $(2a_1)^2 = 2b^2$ より $4a_1^2 = 2b^2$ 、すなわち $b^2 = 2a_1^2$ を得る。先と同じ推論により $b^2$ は偶数なので $b$ は偶数である; $b = 2b_1$ と書く。

再び代入すると $2a_1^2 = (2b_1)^2 = 4b_1^2$ より $a_1^2 = 2b_1^2$ を得る。これは $(a_1,b_1)$ も同じ方程式 $a_1^2=2b_1^2$ の正の整数解であることを意味し、 $b = 2b_1$ であるから $b_1 = b/2 < b$ である。

これは $(a,b)$ を $b$ が最小の解として選んだことと矛盾する。なぜなら $(a_1,b_1)$ はさらに小さい第二座標を持つ解だからである。この矛盾は、 $a^2=2b^2$ の正の整数解が存在し得ないことを示す。

背理法は命題 $P$ を、 $\neg P$ を仮定してどのような形の矛盾を導くことで証明するか:

$\sqrt{2}$ が無理数であるという古典的証明で、 $\sqrt{2} = \frac{p}{q}$ を既約分数と仮定し2乗すると $p^2 = 2q^2$ を得る。 $p$ について直ちに結論されることは何か?

ユークリッドの証明で、素数 $p_1,\dots,p_n$ がすべての素数であると仮定すると、数 $N=p_1p_2\cdots p_n+1$ が矛盾を導くのはなぜか:

対角の2隅を取り除いた欠陥チェス盤について、ドミノ張りの証明における矛盾が生じるのは、タイル張りが次を必要とするからである: