2.2 整列原理を使った証明のテンプレート

目次

前節の議論を一般化すると、整列原理を使って命題「全ての非負整数 \(n\) で何らかの条件 \(P(n)\) が成り立つ」を証明するための標準的な手法が得られる:

整列原理を使った証明

整列原理を利用して命題「全ての \(n \in \mathbb{N}\) で \(P(n)\) が成り立つ」を証明するには、次のようにする:

  • \(P\) に対する反例 (counterexample) となる非負整数を全て集めた集合 \(C\) を定義する。具体的に言えば、\(C\) を次のように定める:

    \[ C ::= \left\{n \in \mathbb{N} \; | \; \operatorname{\text{\footnotesize NOT}} (P(n)) \text{ が成り立つ} \right\} \]

  • 矛盾を導くために \(C\) が非空だと仮定する。

  • 整列原理より、\(C\) には最小要素 \(n\) が存在する。

  • 何らかの方法で矛盾を導く ── \(P(n)\) が実際には正しいと示す、または \(n\) より小さい要素が \(C\) に属することを示す場合が多い。この部分は証明ごとに大きく異なる。

  • \(C\) は空集合である、つまり反例は存在しないと結論付ける。

2.2.1 整数の和

このテンプレートを使って次の定理を証明してみよう:

定理 2.2.1

全ての非負整数 \(n\) に対して、次の等式が成り立つ

\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \tag{2.1}\]

証明に入る前に、和の記法に関して説明しておく。等式 \(\text{(2.1)}\) の左辺で使われている記法には、曖昧な特殊ケースが二つある:

このように、三つのドットを使った記法は便利であるものの、分かりづらく注意が必要な特殊ケースが存在する。一般に、ドットが含まれる式を見たときは、自分がパターンを理解できているかどうかを確認し、先頭と末尾に特に注意して解釈するべきである。

等式 \(\text{(2.1)}\) の左辺を次に示す総和 (summation) と呼ばれる記法で書き直すと、三つのドットを使ったときに生じる曖昧なケースを除去できる:

\[ \sum_{i=1}^{n}i \quad \text{または} \quad \sum_{1 \leq i \leq n} i \]

どちらの記法も「変数 \(i\) の値を \(1\) から \(n\) まで変化させたときの、シグマ (\(\Sigma\)) の右側にある式の値の和」を表す。\(n = 1\) のときの意味は両方の記法で明らかである。二つ目の記法では \(n = 0\) のときの意味も分かりやすくなる。和に含まれる項が存在しないので、\(0\) 個の項の和を \(0\) と定める慣習さえ知っていれば正しい値 \(0\) が導ける (ところで、\(0\) 個の項の積は \(1\) である)。

OK、では証明に戻ろう。

証明 背理法で示す。定理 2.2.1 が成り立たないと仮定する。このとき、定理の反例となる非負整数が存在するので、それらを全て集めた集合を \(C\) とする:

\[ C ::= \left\{n\in \mathbb{N} \; | \; 1 + 2 + 3 + \cdots + n \neq \frac{n(n+1)}{2} \right\} \]

仮定より反例は存在するので、\(C\) は非負整数の非空集合である。よって整列原理より \(C\) には最小要素が存在するので、それを \(c\) とする。つまり、等式 \(\text{(2.1)}\) に対する反例となる最小の非負整数が \(c\) である。

\(c\) は最小の反例なので、等式 \(\text{(2.1)}\) は \(n = c\) のとき成り立たず、\(n\) が \(c\) より小さい任意の非負整数のとき成り立つ。ところで \(n = 0\) のとき等式 \(\text{(2.1)}\) は成り立つから \(c > 0\) である。よって \(c - 1\) は非負整数であり、そして明らかに \(c\) より小さい。従って等式 \(\text{(2.1)}\) は \(c - 1\) で成り立つ。言い換えれば、次の等式が成り立つ:

\[ 1 + 2 + 3 + \cdots + (c - 1) = \frac{(c - 1)c}{2} \]

このとき、次の等式も成り立つ:

\[ \begin{aligned} 1 + 2 + 3 + \cdots + (c - 1) + c &= \frac{(c-1)c}{2} + c \\ &= \frac{c^{2} - c + 2c}{2} \\ &= \frac{c(c + 1)}{2} \end{aligned} \]

つまり等式 \(\text{(2.1)}\) は \(n=c\) のとき成り立つ！ これは矛盾だから、定理 2.2.1 は証明された。 ■

広告