0-4 定義・定理・証明の組み立て方
読み始める前の問い
正しい主張を知ることと、その主張が必ず正しいと説明できることの間には何が足りないだろうか。
このページでできるようになること
直接証明・対偶・背理法・帰納法を、主張の形に応じて選べるようになる。
大学数学では、計算結果だけでなく「なぜすべての場合に正しいか」を説明します。このページでは、本書で用いる代表的な証明方法を小さな例で確認します。
定義と定理の役割
定義は語の意味を固定します。定理は、その定義と既知の結果から必ず従う新しい主張です。例を何個確かめても一般の証明にはなりませんが、例は定理の意味を理解し、証明方針を発見するために必要です。
名称は重要度や役割を示しますが、論理的には定理・補題・命題・系はいずれも証明を必要とする主張です。
証明を始める前の型判定
主張の形を見て、最初に何を任意に取り、最後に何を示すかを決めます。
| 主張の形 | 証明の入口 | 証明の出口 |
|---|---|---|
| $A\subset B$ | 任意の $x\in A$ を取る | $x\in B$ を示す |
| $A=B$ | 二方向の包含を別々に示す | $A\subset B$ と $B\subset A$ |
| $P\Rightarrow Q$ | $P$ を仮定する | $Q$ を導く |
| 存在 | 候補を構成する | 条件を満たすと検算する |
| 一意性 | 二つの候補を仮定する | 両者が等しいと示す |
| 同値 | 二つの含意に分ける | $P\Rightarrow Q$ と $Q\Rightarrow P$ |
この型判定は、後の長い証明でも変わりません。
直接証明
証明を読む前の見取り図
結論から必要な中間地点を逆算し、仮定からそこへ到達する論理を一行ずつつなぐ。
二つの偶数の和は偶数である。
整数 $m,n$ が存在して $a=2m,b=2n$ と書けることが偶数の定義である。したがって
$$
a+b=2m+2n=2(m+n).
$$
$m+n$ は整数なので、偶数の定義から $a+b$ は偶数である。
この証明では、仮定を定義によって書き換え、結論の定義と同じ形へ変形しました。
対偶
$P\Rightarrow Q$ の対偶は「$Q$ でないなら $P$ でない」です。両者は同値です。
証明を読む前の見取り図
結論から必要な中間地点を逆算し、仮定からそこへ到達する論理を一行ずつつなぐ。
整数 $n$ について、$n^2$ が偶数なら $n$ は偶数である。
対偶「$n$ が奇数なら $n^2$ は奇数」を示す。$n$ が奇数なら、ある整数 $k$ により $n=2k+1$ と書ける。よって
$$
n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1.
$$
括弧内は整数なので $n^2$ は奇数である。対偶が示されたから元の命題も成り立つ。
背理法
結論が偽だと仮定し、仮定と両立しない結論を導きます。線形独立性の証明では「非自明な関係がある」と仮定して矛盾を導く形を頻繁に使います。
$\sqrt2$ は有理数ではない。
$\sqrt2$ が有理数であると仮定する。すると互いに素な正整数 $p,q$ を用いて
$$
\sqrt2=\frac pq
$$
と書ける。両辺を二乗すると
$$
p^2=2q^2
$$
であるから $p^2$ は偶数である。前の命題より $p$ は偶数なので、ある整数 $r$ により $p=2r$ と書ける。代入して
$$
4r^2=2q^2,
\qquad
q^2=2r^2
$$
を得る。よって $q^2$、したがって $q$ も偶数である。
$p,q$ はともに2で割り切れ、互いに素としたことに反する。したがって最初の仮定が誤りで、$\sqrt2$ は無理数である。
数学的帰納法
自然数 $n$ に関する命題 $P(n)$ を示すには、最初の値で確かめ、$P(n)$ から $P(n+1)$ を導きます。
数学的帰納法とは、自然数 $n\ge n_0$ に関する命題 $P(n)$ について、
- $P(n_0)$ が成り立つ。
- 任意の $k\ge n_0$ について、$P(k)$ が成り立つと仮定すれば $P(k+1)$ が成り立つ。
の二点を示せば、すべての $n\ge n_0$ について $P(n)$ が成り立つ。
証明を読む前の見取り図
結論から必要な中間地点を逆算し、仮定からそこへ到達する論理を一行ずつつなぐ。
$n\ge1$ に対して
$$
1+2+\cdots+n=\frac{n(n+1)}{2}.
$$
$n=1$ では左辺も右辺も1である。ある $n$ で式が成り立つと仮定する。すると
$$
1+\cdots+n+(n+1)
=\frac{n(n+1)}2+(n+1)
=\frac{(n+1)(n+2)}2.
$$
これは $n+1$ の場合の式である。したがって数学的帰納法によりすべての $n\ge1$ で成り立つ。
存在と一意性を分ける
「ただ一つ存在する」を証明するときは、少なくとも一つ存在することと、二つあれば等しいことを別々に示します。逆行列、座標、直交射影などでこの形式を使います。
反例はどこまで証明するか
全称命題
$$
\forall x\in A,\ P(x)
$$
を否定するには、$P(x)$ が成り立たない具体的な $x\in A$ を一つ示せば十分です。しかし、候補を書くだけではなく、次の二点を検算します。
- 候補が仮定をすべて満たしている。
- 結論だけが実際に破れている。
たとえば「$AB=BA$ はすべての $2\times2$ 行列で成り立つ」という主張に対して
$$ A=\begin{pmatrix}1&0\\0&0\end{pmatrix}, \qquad B=\begin{pmatrix}0&1\\0&0\end{pmatrix} $$
を取ると
$$ AB=\begin{pmatrix}0&1\\0&0\end{pmatrix}, \qquad BA=\begin{pmatrix}0&0\\0&0\end{pmatrix} $$
です。両方とも確かに $2\times2$ 行列であり、積が異なるので反例になっています。
二本の直線が図で交わって見えても、係数によっては平行または一致する。図は予想を与えるが、存在と一意性は方程式または定理で確認する。
演習
加法単位元が二つ $0,0'$ あるなら $0=0'$ を示せ。
$0$ が単位元なので $0+0'=0'$ である。一方、$0'$ も単位元なので $0+0'=0$ である。両式の左辺は同じだから $0=0'$ である。
集合 $A,B$ について
$$
A\subset B
\quad\Longleftrightarrow\quad
A\cap B=A
$$
を証明せよ。
まず $A\subset B$ とする。任意の $x\in A\cap B$ は定義から $x\in A$ なので $A\cap B\subset A$。逆に任意の $x\in A$ は、仮定 $A\subset B$ により $x\in B$ でもあるから $x\in A\cap B$。よって $A\subset A\cap B$ であり、$A\cap B=A$ である。
逆に $A\cap B=A$ とする。任意の $x\in A$ を取る。等式から $x\in A\cap B$ なので、共通部分の定義により $x\in B$ である。したがって $A\subset B$ である。
Fibonacci数列を $F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$ で定める。すべての $n\ge1$ について
$$
F_1+F_2+\cdots+F_n=F_{n+2}-1
$$
を証明せよ。
$n=1$ では左辺は $F_1=1$、右辺は $F_3-1=2-1=1$ で一致する。
ある $n\ge1$ で式が成り立つと仮定する。すると
$$
\begin{aligned}
F_1+\cdots+F_n+F_{n+1}
&=(F_{n+2}-1)+F_{n+1}\\
&=F_{n+3}-1
\end{aligned}
$$
である。最後の等号にFibonacci数列の漸化式を使った。これは $n+1$ の場合の式なので、数学的帰納法によりすべての $n\ge1$ で成り立つ。
この準備を終え、次章から行列と連立一次方程式を体系的に扱います。
このページで回収したもの
証明を暗記するのでなく設計できるようになった。以後は長い証明も「入口・中間地点・出口」に分けて読む。
次へ持ち越す問い
この見方を、次のページではより広い対象またはより計算しやすい形へ移す。
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
