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

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)$
場合が分かれる主張	場合分け	各場合の条件	各場合で結論、および場合が全体を覆うこと
条件を満たす対象がただ一つ存在する	存在と一意性の証明	一意性では、条件を満たす任意の二つの対象$u,v$を取る	条件を満たす対象を一つ示し、さらに$u=v$を示す

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

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 存在と一意性

条件$P(x)$を満たす対象がただ一つ存在することを示すには、存在と一意性を別々に示します。

• 存在は、条件を満たす対象$x_0$を一つ作って示します。
• 一意性は、範囲内の任意の二つの対象$u,v$がともに条件を満たすと仮定して、$u=v$を導きます。

一意性の証明では、はじめから対象が一つしかないと仮定しません。$u$と$v$が異なるとも仮定しません。条件$P(u)$と$P(v)$から$u=v$を導きます。

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

5 場合分け

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

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

6 証明の練習

解答.

(1)では対偶を示す。整数$n$が$3$の倍数でなければ、ある整数$k$を用いて$n=3k+1$または$n=3k+2$と表すことができる。前者では$n^2=3(3k^2+2k)+1$、後者では$n^2=3(3k^2+4k+1)+1$となる。いずれも$n^2$は$3$の倍数でない。対偶律により、もとの主張も成り立つ。

(2)では正の整数$n=4$を取る。$n^2+n+1=21=3\cdot7$であり、$21$は$1$と自身以外の正の約数$3$を持つ。したがって、条件を満たす正の整数$n$が存在する。

(3)では実数$x$を任意に取る。$x^2-2x+3=(x-1)^2+2\ge2>0$である。$x$に追加の条件を課していないので、すべての実数$x$について主張が成り立つ。▨