第 2 章 整列原理
命題
非負整数の非空集合は最小要素を持つ。
この命題を整列原理 (well ordering principle, WOP) と呼ぶ。正しいと納得できるだろうか？ 何となく正しいと思えるのではないだろうか？ この命題の条件に注目してほしい: 非空集合が要求されている ── 空集合は要素を持たないので、最小要素も持たない。また、非負整数の集合も要求されている ── 負の整数の集合、あるいは正の有理数の集合に対しては成り立たない。つまり、非負整数の特別な性質を捉えたのが整列原理と言える。
整列原理の正しさは明らかに思えるのに対して、その有用性はそれほど明らかではない。しかし実際には、離散数学において最も重要な証明パターンが整列原理によって提供される。本章では整列原理を使った証明技法の有用性をいくつかの例を共に見ていく。