証明の基本パターン | 集合と論理

1 主張の形が証明の方法を決める

示すべき主張の形ごとに、何を仮定して何を示せば証明が完成するのかをまとめます。

示すべき主張	方法	何を仮定するか	何を示せば完成するか
$P \Rightarrow Q$	直接証明	$P$	$Q$
$P \Rightarrow Q$	対偶による証明	$\lnot Q$	$\lnot P$
$P$ （形を問わない）	背理法	$\lnot P$	矛盾
すべての $x$ で $P(x)$	全称の証明	$x$ が範囲に属すること（他は何も仮定しない）	$P(x)$
ある $x$ で $P(x)$	存在の証明	なし	具体的な $x_0$ を作り、 $P(x_0)$
場合が分かれる主張	場合分け	各場合の条件	各場合で結論、および場合が全体を覆うこと
ただ一つ存在する	一意性の証明	条件を満たす対象が二つあること	その二つが一致すること

以下、それぞれについて要点を述べます。直接証明、対偶による証明、背理法の詳細は、「逆・裏・対偶」と「背理法」で扱いました。

2 含意を示す三つの方法

$P \Rightarrow Q$ を示す方法は三つあります。

直接証明では、 $P$ を仮定して $Q$ を導きます。まず $P$ が主張している内容を、式や条件として書き下すところから始めます。
対偶による証明では、 $\lnot Q$ を仮定して $\lnot P$ を導きます。結論を否定したほうが具体的な形を書き下しやすいときに選びます。
背理法では、 $P$ と $\lnot Q$ の両方を仮定して矛盾を導きます。直接にも対偶にも手がかりが見つからないときに選びます。

三つのあいだに優劣はありません。 $P$ と $\lnot Q$ のどちらから具体的な情報を取り出すことができるかによって選びます。

3 「すべて」と「ある」では進め方が入れ替わる

証明の進め方は、主張に含まれる量化子によって決まります。

「範囲内のすべての $x$ について $P(x)$ が成り立つ」を示すには、範囲から $x$ を一つ取り、その $x$ について、範囲に属すること以外は何も仮定せずに $P(x)$ を示します。こうして書いた議論は、範囲内のどの $x$ に対しても同じように通用します。途中で「 $x$ は正である」のような追加の条件を使ってしまうと、その場合しか示したことになりません。
「 $P(x)$ を満たす $x$ が存在する」を示すには、条件を満たす $x_0$ を一つ作って示し、 $x_0$ が範囲に属することと $P(x_0)$ が成り立つことを確かめます。

これらを否定するときは、進め方が入れ替わります。全称命題を否定するには反例を一つ挙げれば足り、存在命題を否定するには、範囲内のすべての対象について条件が成り立たないことを示します。証明するときに一つ作れば済むほうは、否定するときに全体を見なければならなくなります。

4 場合分け

主張の対象が、いくつかの場合に分かれるときは、場合ごとに結論を示します。このとき、分けた場合の全体が、もとの範囲を覆っていることを必ず確かめます。覆っていなければ、証明されていない場合が残ります。重複することは差し支えありません。

たとえば、すべての実数 $x$ について $|x| \ge x$ が成り立つことを示すには、 $x \ge 0$ の場合と $x < 0$ の場合に分けます。前者では $|x| = x$ なので $|x| \ge x$ が成り立ち、後者では $|x| = -x > 0 > x$ が成り立ちます。この二つの場合は実数全体を覆っているので、証明が完成します。

5 一意性の証明

「条件 $P$ を満たす $x$ がただ一つ存在する」という主張は、存在と一意性という二つの主張の組です。二つを別々に示します。

存在は、条件を満たす対象 $x_0$ を一つ作って示します。
一意性は、条件を満たす対象が $a$ 、 $b$ の二つあると仮定して、 $a = b$ を導きます。

一意性の証明で、はじめから対象が一つしかないと仮定してはなりません。それは示すべきことです。「 $a$ と $b$ が条件を満たす」という仮定だけから $a = b$ を導きます。

定理 5.1 (一次方程式の解の一意存在). 実数 $a \ne 0$ と実数 $b$ について、 $ax + b = 0$ を満たす実数 $x$ がただ一つ存在する。

証明. 存在。 $x_0 = -\dfrac{b}{a}$ とおくと $a x_0 + b = -b + b = 0$ となります。

一意性。 $a\alpha + b = 0$ と $a\beta + b = 0$ を仮定します。辺々を引くと $a(\alpha - \beta) = 0$ となり、 $a \ne 0$ から $\alpha - \beta = 0$ 、すなわち $\alpha = \beta$ が従います。▨

$a \ne 0$ という仮定を落とすと一意性は成り立ちません。 $a = b = 0$ のとき、 $0 \cdot x + 0 = 0$ はすべての実数 $x$ について成り立つからです。

6 自分で確かめる

次の三つは、それぞれ別の方法で示すことができます。示すべき主張の形から方法を選び、何を仮定して何を示すのかを先に書き出してから、証明を書いてください。

整数 $n$ について、 $n^2$ が $3$ の倍数ならば $n$ は $3$ の倍数である。
$n^2 + n + 1$ が素数でないような正の整数 $n$ が存在する。
すべての実数 $x$ について $x^2 - 2x + 3 > 0$ である。

方法の選び方は、1が対偶による証明（ $n$ を $3$ で割った余りによって場合分けします）、 2が存在の証明（条件を満たす $n$ を一つ挙げ、 $n^2+n+1$ が素数でないことを確かめます）、 3が全称の証明（任意の実数 $x$ を取り、平方完成によって示します）です。

閑話休題：人間が読み切ることのできない証明 場合分けは、分けた場合の全体がもとの範囲を覆っていれば、場合の数がいくつであっても正しい証明になります。では、場合が千を超えたらどうでしょうか。

$1976$ 年、アッペルとハーケンは四色定理——平面上のどのような地図も、隣り合う国が異なる色になるように4色で塗り分けることができる——を証明しました。その方法は、起こりうる地図の形を有限個の配置へ帰着させ、その一つひとつについて 4色で塗ることができることを確かめるというものです。確かめるべき配置は千を超え、検証はコンピュータによって行われました。人間が手で全部を読み切ることはできません。

この証明は、数学の共同体に一つの問いを突き付けました。証明とは、人間が読んで納得するものなのか、それとも規則に従って検証することができるものなのか、という問いです。証明の骨格（配置の一覧が起こりうる場合を覆っていること）は人間が組み立てたものですが、各配置の検証はプログラムが実行しており、そのプログラム自体にも誤りがないことを確かめる必要があります。その後、確かめるべき配置の数を減らす改良が重ねられ、 $2005$ 年にはゴンティエが、証明全体を証明支援系 Coq の上で形式化して機械的に検証しました。

場合分けを尽くすという、本記事で扱った素朴な手順が、証明とは何かという問いにまで届いています。

7 つまずいたら

手を動かす前に、示すべき主張の形（含意であるか、全称であるか、存在であるか、一意存在であるか）を見て方法を選んでください。何を仮定して何を示せばよいのかを、上の表から書き出してから始めると、途中で目標を見失いません。
直接証明で行き詰まったら対偶を、対偶でも行き詰まったら背理法を試してください。行き詰まりは、仮定として置く命題の選び方の問題であることが多くあります。
場合分けでは、分けた場合の全体がもとの範囲を覆っているかどうかを必ず確かめてください。重複は差し支えありませんが、抜けがあれば証明になりません。
一意性の証明では、条件を満たす対象を $a$ 、 $b$ と二つ置いて $a = b$ を示します。はじめから一つしかないと書いてしまうと、示すべきことを仮定したことになります。

§A3.9証明の基本パターン