整列順序

$\mathbb{N}$ 上の数学的帰納法が機能するのは、$\cdots < n_2 < n_1 < n_0$ のような無限下降列が存在しないからだ。自然数の空でない部分集合には必ず最小元がある。この性質を整列順序（せいれつじゅんじょ、well-ordering）と呼ぶ。整列順序は全順序より真に強く、論理的には帰納法そのものと同値であることがわかる。

定義

全順序 $(S, \leq)$ が整列順序（または整列集合）であるとは、$S$ の空でないすべての部分集合が最小元を持つことを言う：

$$\forall A \subseteq S,\quad A \neq \emptyset \;\Longrightarrow\; \exists\, m \in A \;\text{ s.t. }\; \forall a \in A,\; m \leq a$$

ペア $(S, \leq)$ はそのとき整列集合（well-ordered set）と呼ばれる。

「最小元の存在」という条件は、無限下降列の不存在という条件と同値だ：

$(S, \leq)$ が整列順序であることと、$S$ 内に無限列 $a_0 > a_1 > a_2 > \cdots$ が存在しないことは同値。

2つの定式化はそれぞれ異なる文脈で役に立つ。「最小元の存在」は存在論証に便利で、「下降列の不存在」は背理法に便利だ。

例

$\leq$ による自然数

$(\mathbb{N}, \leq)$ は典型的な整列順序だ。空でない $A \subseteq \mathbb{N}$ を任意に取り、$a_0 \in A$ を一つ選ぼう。$a_0$ が $A$ の最小元でなければ、それより真に小さい $a_1 \in A$ が存在する。$a_1$ が最小元でなければさらに小さい $a_2$ が存在する、という具合だ。すべての元が非負整数なので、この狭義単調減少列 $a_0 > a_1 > a_2 > \cdots$ は無限に続かない――自然数から $1$ をいつまでも引き続けることはできない。列は $A$ の最小元で終わらなければならない。

この整列性が数学的帰納法の土台となっている。

有限全順序集合

空でない有限全順序集合はすべて整列順序だ。有限集合の空でない部分集合もまた有限なので、すべての元を走査してこれまでの最小元を記録することで最小元を求められる。

$\mathbb{N}$ の初期切片

任意の $n \in \mathbb{N}$ に対して集合 $\{0, 1, 2, \ldots, n\}$ に通常の $\leq$ を入れたものは、有限全順序集合として整列順序になる。

反例

$\leq$ による整数

$(\mathbb{Z}, \leq)$ は全順序だが、整列順序ではない。$\mathbb{Z}$ 自身に最小元が存在しない：任意の $n \in \mathbb{Z}$ に対して $n - 1$ は真に小さい。より明示的には、部分集合 $\{\ldots, -3, -2, -1, 0\}$ に最小元がない。

$\leq$ による有理数と実数

$(\mathbb{Q}, \leq)$ と $(\mathbb{R}, \leq)$ は全順序だが、どちらも整列順序ではない。開区間 $(0, 1)$ は両方の空でない部分集合だが、最小元を持たない。任意の $q \in (0, 1)$ に対して $q/2$ は真に小さく、かつ $(0, 1)$ に含まれる。

整列順序と数学的帰納法

$\mathbb{N}$ では、整列順序原理と数学的帰納法の原理は論理的に同値だ――それぞれが他方を含意する。

整列順序 $\Rightarrow$ 帰納法. $P$ を自然数の性質とする。$P(0)$ が成り立ち、かつすべての $k \in \mathbb{N}$ に対して $P(k) \Rightarrow P(k+1)$ が成り立つとする。失敗集合を定義する：

$$F \;\coloneqq\; \{n \in \mathbb{N} \mid \neg P(n)\}$$

$F$ が空でないと仮定して矛盾を導く。整列順序より $F$ には最小元 $m$ が存在する。$P(0)$ が成り立つので $m \neq 0$ であり、$m \geq 1$ かつ $m - 1 \in \mathbb{N}$。$m$ は $F$ の最小元なので $m - 1 \notin F$、つまり $P(m - 1)$ が成り立つ。帰納段から $P(m)$ が得られ、$m \in F$ に矛盾する。よって $F = \emptyset$ であり $P$ は普遍的に成り立つ。

帰納法 $\Rightarrow$ 整列順序. 強帰納法により、「任意の $n \in \mathbb{N}$ に対して $\{0, 1, \ldots, n\}$ の空でない部分集合は最小元を持つ」を証明できる。これらの場合を合わせると $\mathbb{N}$ 全体をカバーし、整列順序が確立される。

この同値性は、$\mathbb{N}$ の整列性が独立した仮定ではなく、別の角度から見た帰納法と同じ事実であることを示している。

整列順序定理

自然な疑問として、$\mathbb{R}$ のような非可算集合も含む任意の集合に整列順序を入れられるだろうか？

驚くべきことに、答えはイエスだ――ただし証明には選択公理（AC、Axiom of Choice）が必要となる。選択公理は、空でない集合の任意のコレクションから各集合に対して同時に1つの要素を選べることを主張する。ACからは次の定理が従う：

整列順序定理. 任意の集合は整列順序を入れられる。

整列順序定理は集合論の標準的な公理系ツェルメロ＝フレンケル公理系（ZF）のもとでACと同値だ：互いに他を含意する。つまり $\mathbb{R}$ は原理的には整列順序を持てるが、その整列順序を明示的に書き下すことはできない――その存在は非構成的だ。どの実数が先頭に来るかを教えてくれる式は存在しない。

まとめ

• 整列順序は、すべての空でない部分集合が最小元を持つ全順序だ。同値な言い方として、無限狭義下降列が存在しない。
• $(\mathbb{N}, \leq)$ が典型的な整列順序であり、有限全順序集合もすべて整列順序だ。
• $(\mathbb{Z}, \leq)$、$(\mathbb{Q}, \leq)$、$(\mathbb{R}, \leq)$ は全順序だが、整列順序ではない。
• $\mathbb{N}$ 上の整列順序原理は数学的帰納法と論理的に同値だ。
• 整列順序定理は任意の集合に整列順序を入れられることを主張するが、これには選択公理が必要であり、実際に選択公理と同値だ。