整列順序
概要
整列順序（well-order）とは、集合 $P$ 上の全順序 $\leq$ であって、$P$ の空でない任意の部分集合が最小元を持つもののことであり、整列順序を備えた集合を整列集合という。自然数全体 $\mathbb{N}$ の通常の大小関係が典型例であり、整数全体や実数の開区間 $(0,1)$ のように、全順序ではあるが最小元を持たない部分集合を含む順序とは区別される。整列律を課せば全順序律は自動的に従い、部分集合への制限で保たれ、真に減少する無限列を持たない。最大の意義は、数学的帰納法を一般の整列集合へ拡張した超限帰納法が成り立つことにあり、順序数・超限再帰の理論の基礎となる。選択公理のもとでは任意の集合に整列順序が入る（整列可能定理）。
定義
集合 $P$ 上の二項関係 $\leq$ が $P$ 上の整列順序（well-order, well-ordering）であるとは、次の条件を満たすことをいう。
- $\leq$ は $P$ 上の全順序である。すなわち反射律（$x\leq x$）、反対称律（$x\leq y$ かつ $y\leq x$ ならば $x=y$）、推移律（$x\leq y$ かつ $y\leq z$ ならば $x\leq z$）、全順序律（任意の $x,y$ について $x\leq y$ または $y\leq x$）を満たす。
- 整列律（well-ordering property）：$P$ の空でない任意の部分集合 $S$ は最小元を持つ。すなわち、任意の $x\in S$ に対して $m\leq x$ となる $m\in S$ が存在する。
$\leq$ が $P$ 上の整列順序であるとき、組 $(P,\leq)$ を整列集合（well-ordered set）といい、$P$ は $\leq$ によって整列されているという。
最小元は存在すれば一意である（$m,m'$ がともに $S$ の最小元なら $m\leq m'$ かつ $m'\leq m$、反対称律から $m=m'$）。したがって整列律は、空でない各部分集合 $S$ にちょうど一つの最小元 $\min S$ を対応させる。$x< y$ は「$x\leq y$ かつ $x\neq y$」を表す。空集合上の空な関係は全順序律も整列律も空虚に満たすので、空集合は整列集合である。
$(P,\leq)$ を整列集合、$a\in P$ とする。$a$ より真に小さい元全体
$$
P_{< a}:=\{x\in P\mid x< a\}
$$
を $a$ の定める始切片（initial segment）という。より一般に、部分集合 $I\subset P$ が「$x\in I$ かつ $y\leq x$ ならば $y\in I$」を満たすとき $I$ を $P$ の下方集合（down-set）という。
直感
全順序集合ではすべての元が一列に並ぶが、整数全体 $\mathbb{Z}$ のように「下に果てがない」列や、開区間 $(0,1)$ のように「どこまでも小さい元がある」列も許される。整列順序は、そのような部分集合が一切現れないように、空でない部分集合すべてに最小元を要求した全順序である。その結果、元を最小のものから順に一つずつ取り出して尽くしていくことができ、自然数の数学的帰納法を一般の整列集合へ拡張した超限帰納法が成り立つ。「反例があれば最小の反例をとれる」という論法が使えることが、整列順序の本質である。
例と反例
自然数全体 $\mathbb{N}=\{0,1,2,\ldots\}$ に通常の大小関係を入れると整列集合である（整列性の原理）。これは数学的帰納法から次のように従う。$S\subset\mathbb{N}$ が空でなく最小元を持たないとして、「$S$ には $n$ 以下の元がない」という主張を $n$ について帰納的に示す。$n=0$ のとき、$0\in S$ なら $0$ は $\mathbb{N}$ の最小元なので $S$ の最小元になり矛盾するから、$0\notin S$ である。$n$ まで正しいとき、もし $m\in S$ で $m\leq n+1$ なら、$m\leq n$ ではないので $m=n+1$ であり、$S$ の元はすべて $n$ より大きい、すなわち $n+1$ 以上なので $n+1$ が $S$ の最小元となって矛盾する。よってすべての $n$ について $S$ に $n$ 以下の元はなく、$S=\emptyset$ となって仮定に反する。
$\infty\notin\mathbb{N}$ とし、$P:=\mathbb{N}\cup\{\infty\}$ に、$\mathbb{N}$ 上では通常の大小関係を、任意の $n\in\mathbb{N}$ に対して $n<\infty$ を成り立たせる順序を入れる。これは全順序であり、さらに整列順序である。実際、空でない $S\subset P$ について、$S\cap\mathbb{N}\neq\emptyset$ ならその最小元（ex-well-order-natural-numbers）が $S$ の最小元であり、$S\cap\mathbb{N}=\emptyset$ なら $S=\{\infty\}$ で $\infty$ が最小元である。$\infty$ は最大元だが「直前の元」を持たず、$P$ は $\mathbb{N}$ とは異なる形の整列集合である。こうした形（順序同型類、すなわち順序型（順序型））を分類する言葉が順序数であり、$\mathbb{N}$ は順序数 $\omega$、この $P$ は $\omega+1$ に対応する。
$\mathbb{N}\times\mathbb{N}$ に辞書式順序 $(a,b)\leq(a',b')\iff a< a'$ または（$a=a'$ かつ $b\leq b'$）を入れると整列集合である。全順序であることは 全順序 の辞書式順序の命題による。整列律：空でない $S\subset\mathbb{N}\times\mathbb{N}$ に対し、第1成分の集合 $\{a\mid (a,b)\in S\}$ は空でない $\mathbb{N}$ の部分集合なので最小元 $a_0$ を持ち、次に $\{b\mid (a_0,b)\in S\}$ も空でないので最小元 $b_0$ を持つ。$(a_0,b_0)\in S$ であり、任意の $(a,b)\in S$ について $a_0< a$ か、$a=a_0$ かつ $b_0\leq b$ なので $(a_0,b_0)\leq(a,b)$ である。この整列集合では、たとえば $(1,0)$ より小さい元 $(0,b)$ が無限個あり、整列集合の元は「有限個の元の後に来る」とは限らない。
次の各順序は全順序であるが整列律を満たさず、したがって「全順序ならば整列順序」という含意は成り立たない。
- 整数全体 $\mathbb{Z}$ の通常の大小関係。$\mathbb{Z}$ 自身（あるいは負の整数全体）が最小元を持たない。任意の $n\in\mathbb{Z}$ に対して $n-1< n$ だからである。
- 正の実数全体 $\mathbb{R}_{>0}$ の通常の大小関係。部分集合 $(0,1)$ は下に有界（$0$ が下界）だが最小元を持たない。$x\in(0,1)$ に対して $x/2\in(0,1)$ かつ $x/2< x$ だからである。「下に有界である」ことと「最小元を持つ」ことは異なり、整列律が要求するのは後者である。
- 有理数全体 $\mathbb{Q}$ の通常の大小関係。$\mathbb{Q}$ 自身が最小元を持たず、また $\{q\in\mathbb{Q}\mid q>0\}$ も最小元を持たない。
性質
$(P,\leq)$ を順序集合（全順序であることは仮定しない）とし、$P$ の空でない任意の部分集合が最小元を持つとする。このとき $\leq$ は $P$ 上の全順序であり、したがって整列順序である。
$x,y\in P$ を任意にとり、$S:=\{x,y\}$ とおく。$S$ は空でないので最小元 $m\in S$ を持つ。$m=x$ なら、$m$ が最小元であることから $x\leq y$ である。$m=y$ なら同様に $y\leq x$ である。いずれにせよ $x,y$ は比較可能なので $\leq$ は全順序律を満たす。$\square$
この命題により、整列律を課せば全順序律は自動的に従う。したがって「順序集合であって空でない任意の部分集合が最小元を持つもの」を整列集合の定義とする流儀と、本記事の定義は同じ構造を与える。
$(P,\leq)$ を整列集合、$S\subset P$ とする。$\leq$ を $S\times S$ に制限した誘導順序は $S$ 上の整列順序である。特に、始切片 $P_{< a}$ と下方集合はいずれも整列集合である。
誘導順序が $S$ 上の全順序であることは 全順序 の部分集合への制限の命題による。$T\subset S$ を空でない部分集合とすると、$T$ は $P$ の空でない部分集合でもあるので、$P$ の整列律から最小元 $m\in T$ を持つ。任意の $x\in T$ に対して $m\leq x$ が成り立つという関係は誘導順序でもそのまま成り立つので、$m$ は誘導順序に関しても $T$ の最小元である。$\square$
$(P,\leq)$ を整列集合とし、$\varphi(x)$ を $P$ の元 $x$ についての命題とする。次の条件（帰納段階）を仮定する。
任意の $x\in P$ について、「任意の $y< x$ に対して $\varphi(y)$ が成り立つ」ならば $\varphi(x)$ が成り立つ。
このとき、すべての $x\in P$ について $\varphi(x)$ が成り立つ。
$S:=\{x\in P\mid \varphi(x)\text{ が成り立たない}\}$ とおき、$S\neq\emptyset$ と仮定する。整列律から $S$ は最小元 $m$ を持つ。$y< m$ とすると、$y\in S$ なら $m$ の最小性から $m\leq y$ となり、$y\leq m$ とあわせて反対称律から $y=m$ となって $y< m$ に反するので、$y\notin S$、すなわち $\varphi(y)$ が成り立つ。よって $m$ は「任意の $y< m$ に対して $\varphi(y)$ が成り立つ」を満たし、帰納段階の仮定から $\varphi(m)$ が成り立つ。これは $m\in S$ に反する。ゆえに $S=\emptyset$ である。$\square$
この原理は、$P=\mathbb{N}$ のとき「$n$ 未満のすべての $k$ で $\varphi(k)$ が成り立てば $\varphi(n)$ が成り立つ」という形の数学的帰納法（累積帰納法）であり、一般の整列集合や順序数に対する形を超限帰納法という。帰納段階の仮定には「最小元で $\varphi$ が成り立つ」という出発点が含まれていることに注意する。最小元 $m_0$ については $y< m_0$ となる $y$ が存在しないので、仮定は無条件に $\varphi(m_0)$ を要求している。
$(P,\leq)$ を整列集合とする。各 $n\in\mathbb{N}$ に対して $x_{n+1}< x_n$ を満たす列 $x_0,x_1,x_2,\ldots\in P$（真に減少する無限列）は存在しない。
そのような列が存在したとして、$S:=\{x_n\mid n\in\mathbb{N}\}$ とおく。$S$ は空でないので最小元 $m$ を持ち、$m=x_k$ となる $k\in\mathbb{N}$ がある。すると $x_{k+1}\in S$ かつ $x_{k+1}< x_k=m$ であり、これは $m\leq x_{k+1}$ に反する（$x_{k+1}< m$ かつ $m\leq x_{k+1}$ なら反対称律から $x_{k+1}=m$ となり $x_{k+1}< m$ に矛盾する）。$\square$
$(P,\leq)$ を整列集合とする。
- 任意の $a\in P$ について、始切片 $P_{< a}$ は $P$ の下方集合であり、$a\notin P_{< a}$ である。
- $P$ の下方集合 $I$ で $I\neq P$ となるものは、ある $a\in P$ について $I=P_{< a}$ と一意に表される。すなわち、$P$ 自身でない下方集合は始切片にほかならない。
- $x\in P_{< a}$ かつ $y\leq x$ なら $y\leq x< a$ より $y\leq a$ かつ $y\neq a$（$y=a$ なら $a\leq x$ となり $x< a$ と反対称律から $x=a$ となって矛盾）、すなわち $y< a$ である。$a< a$ は成り立たないので $a\notin P_{< a}$ である。
- $I\neq P$ なので $P\setminus I$ は空でなく、最小元 $a$ を持つ。$x< a$ なら $a$ の最小性から $x\notin P\setminus I$、すなわち $x\in I$ である。逆に $x\in I$ とすると、全順序律から $x< a$ または $a\leq x$ であり、後者なら $I$ が下方集合であることから $a\in I$ となって $a\in P\setminus I$ に反する。よって $x< a$ である。ゆえに $I=P_{< a}$。一意性：$P_{< a}=P_{< b}$ かつ $a\neq b$ とすると、全順序律から $a< b$ または $b< a$ であり、前者なら $a\in P_{< b}=P_{< a}$ となって (1) に反する。後者も同様である。$\square$
補足
整列集合 $(P,\leq)$ と $(Q,\leq)$ が順序同型であるとは、順序を保つ全単射 $P\to Q$ が存在することをいう。任意の整列集合は、ちょうど一つの順序数と順序同型であり、順序数は整列集合の「形」を代表する（Jec03 Chapter 2）。また、整列集合はその真の始切片と順序同型にならず、二つの整列集合が与えられれば一方が他方の始切片（または全体）と順序同型になる。これらの証明は Jec03 Chapter 2 に譲る（順序数も参照）。整列集合の各元に、それより小さいすべての元での値から値を定めて写像を構成する方法が超限再帰であり、thm-well-order-induction によって正当化される。
「整列順序」は順序関係そのものを指す語であり、それを備えた集合 $(P,\leq)$ は「整列集合」と呼び分ける（全順序と全順序集合の関係と同じ）。Mat68 第3章では「整列集合」を主に用いる。文献によっては全順序を仮定せず、順序集合に整列律だけを課して整列順序を定義する流儀もあり（例：Hal60 §17）、prop-well-order-from-poset により同じ構造が得られる。また集合論の文献（Jec03 Chapter 2）では狭義順序 $<$ を出発点とし、整列順序を「三分律を満たす狭義順序で、空でない部分集合が最小元を持つもの」と定義する。反対称律を仮定せず「空でない部分集合が極小元を持つ」ことだけを課した二項関係は整礎関係といい、整列順序とは、その狭義順序 $<$ が整礎関係であるような全順序である。
集合論では、thm-well-order-induction を順序数へ拡張した超限帰納法と超限再帰が、順序数・基数の理論全体の基礎になる。計算機科学では、再帰的なアルゴリズムの停止性を、各ステップで整列集合（典型的には $\mathbb{N}$ や辞書式順序を入れた $\mathbb{N}^k$）の値が真に減少することを示して証明する。prop-well-order-no-infinite-descent は、この手法が機能する理由を述べたものである。代数では、多項式環の単項式全体に入れる単項式順序に整列順序であることが要求され、この整列性がGröbner基底を求める割り算アルゴリズムの停止を保証する。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
