整列順序
概要
整列順序（Well-order）とは、全順序集合の中でも特に構造が強く、「空でない任意の部分集合が必ず最小元を持つ」という性質を満たす順序のことである。これは自然数 $\mathbb{N}$ が持つ性質を一般化したものであり、数学的帰納法を無限の彼方まで拡張した「超限帰納法」を適用するための基礎となる。すべての順序数（Ordinal number）は整列順序集合であり、また選択公理を仮定すれば、どのような集合にも整列順序を入れることが可能である（整列可能定理）。
定義
集合 $X$ とその上の全順序関係 $\le$ の組 $(X, \le)$ が整列順序集合（Well-ordered set）であるとは、以下の条件を満たすことをいう。
$X$ の空でない任意の部分集合 $A$ に対して、$A$ の最小元が存在する。
$$\forall A \subseteq X, (A \neq \emptyset \implies \exists m \in A \text{ s.t. } \forall x \in A, m \le x)$$
この定義は一見シンプルだが、非常に強力な制約を含んでいる。
- 最小元の存在: 全体 $X$ 自身も部分集合なので、$X$ 全体にも最小元（始点）が存在しなければならない。
- 無限降下列の禁止: $x_1 > x_2 > x_3 > \dots$ のように、無限に小さくなり続ける点列は存在し得ない（もし存在すれば、その点列の集合は最小元を持たないため）。
直感的理解と具体例
「全順序（一直線に並ぶ）」であることと、「整列順序（最小元を持つ）」であることの違いは、具体例を見ると明確になる。
- 自然数 $\mathbb{N} = \{0, 1, 2, \dots\}$:
どのような部分集合（例えば「偶数全体」「100より大きい素数」など）をとっても、必ず「一番小さい数」が存在する。これが整列順序の原型である。 - 有限な全順序集合:
有限個の要素を一列に並べれば、必ず最小元があるため、常に整列順序である。 - 順序数 $\omega + 1 = \{0, 1, 2, \dots, \omega\}$:
自然数の列の後ろに無限大 $\omega$ を一つ付けたもの。これも任意の部分集合が最小元を持つ。
- 整数 $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$:
全順序だが整列順序ではない。
理由：$\mathbb{Z}$ 自身（あるいは負の整数全体）が最小元を持たない（いくらでも小さい数が存在する）。 - 正の実数 $\mathbb{R}_{>0} = (0, \infty)$:
下に有界だが整列順序ではない。
理由：開区間 $(0, 1)$ という部分集合をとると、これに含まれる最小の実数は存在しない（どんなに小さい数をとっても、さらに小さい数が存在する）。
数学的意義：帰納法への足場
整列順序が重要視される最大の理由は、超限帰納法（Transfinite Induction）が可能になるからである。
通常の数学的帰納法は「$0$ が成立」「$n$ が成立すれば $n+1$ も成立」というドミノ倒しだが、これは「次（Successor）」が定義できる自然数のような構造に依存している。
整列順序集合においては、「最小元がある」という性質を使うことで、これを一般の順序構造まで拡張できる。
- 直観: 「反例が存在するなら、その中の最小の反例をとる」という論法（無限降下法）が使える。もし最小の反例が矛盾を生まないなら、そもそも反例は存在しないことになる。
整列可能定理
整列順序に関して、直観に反する驚くべき定理がある。
任意の集合 $X$ に対して、適切な順序 $\le$ を定義すれば、$(X, \le)$ を整列順序集合にすることができる。
これは選択公理（またはZornの補題）と同値である。
- 実数の整列化: この定理によれば、実数全体の集合 $\mathbb{R}$ にも整列順序を入れることができる。しかし、それは通常の大小関係 $\le$ とは全く異なる順序であり、具体的にどのような順序か書き下すことは人類には不可能である（非構成的証明）。
順序の階層構造
順序構造の制約の強さは以下の通りである。
- 半順序: 分岐や合流がある（比較不能あり）。
- 全順序: 一直線に並ぶ（比較不能なし）。
- 整列順序: 一直線に並び、かつ始点があり、無限に降下しない（離散的なステップの積み重ねに見える）。
