順序数

集合論

集合 T が推移的(transitive)であるとは, T の要素が T の部分集合になること.
例えば, T=\{\emptyset,\{\emptyset\}\} に対し, \{\emptyset\} \in T かつ \{\emptyset\} \subset T です.
このような集合は普通の数学では普通は現れませんが, 集合論では大活躍することになります.
推移的であることを次のように言い換えることもできます.
a \in b \in T ならば a \in T.
さて, 集合論における最も基本的な概念である順序数(ordinal number)は, 次のように定義されます.
集合 A が順序数であるとは, A が推移的であり, \in について整列順序であること.
例えば, A=\{\emptyset,\{\emptyset\}\,\{\emptyset,\{\emptyset\}\}} は順序数です.
順序数全体を Ord で表すことにします.
また, \alpha < \beta を \alpha \in \beta で定義します.
順序数には他にも同値な定義が知られています.


補題
(i) \emptyset は順序数.
(ii) \alpha が順序数で \beta \in \alpha ならば \beta も順序数.
(iii) \alpha \neq \beta がともに順序数で \alpha \subset \beta ならば \alpha \in \beta
(iv) \alpha, \beta が順序数ならば, \alpha \subset \beta か \beta \subset \alpha のいずれかが成り立つ.

証明
(i) \emptyset は要素を一つももたないので自動的に条件を満たします.
(ii) \beta \in \alpha なので \alpha が推移的であることにより \beta \subset \alpha.
整列順序の部分集合はまた整列順序になることが容易に確かめられるので \beta も \in による整列順序.
また, x \in y \in \beta のとき, \alpha が推移的であることにより x \in \alpha.
ここで x \notin \beta とすると x \in y \in \beta \in x \in \alpha となって矛盾.
(iii) \alpha \subset \beta のとき, \gamma を \beta \setminus \alpha における最小元とします(\beta \setminus \alpha は整列順序 \beta の空でない部分集合なので最小元をもちます).
\alpha は推移的なので, \alpha は \beta の始切片で, \alpha = \{\xi \in \beta:\xi<\gamma\} = \gamma \in \beta.
(iv) \alpha \cap \beta は順序数です.
実際, x \in y \in \alpha \cap \beta のとき y \in \alpha より y \subset \alpha であり, 同様に y \subset \beta.
したがって, x \in y \subset \alpha \cap \beta なので x \in \alpha \cap \beta.
\alpha \cap \beta が整列順序であることは明らか.
さて, \gamma = \alpha \cap \beta とおくと, \gamma = \alpha または \gamma = \beta になります.
そうでないとすると, \gamma \in \alpha かつ \gamma \in \beta が (iii) より帰結します.
すると \gamma \in \alpha \cap \beta = \gamma となって順序数の定義に矛盾します.

この補題によって, 以下のことが示されます.

(i) < が Ord における全順序.
(ii) 任意の順序数 \alpha について \alpha = \{\beta : \beta < \alpha\}
(iii) C が順序数の空でないクラスのとき, \bigcap C は順序数になり, \bigcap C = \rm{inf}C \in C.
(iv) X が順序数の空でない集合のとき, \bigcup X は順序数になり, \bigcup X = \rm{sup}X.
(v) 任意の順序数 \alpha について \alpha \cup \{\alpha\} は順序数で, \alpha \cup \{\alpha\} = \rm{inf}\{\beta : \beta > \alpha\}.

\alpha+1=\alpha \cup \{\alpha\} と定義し, これを \alpha の後続(successor)といいます.
次の定理はとっても大切です.

定理
任意の整列順序はある順序数に同型であり, そのような順序数はユニークである.

証明
ユニークであることは, 整列順序がそれ自身の始切片とは同型にならないことから導かれます.
W を整列順序とします.
a \in W のうち, W の始切片 W(a) からある順序数(これを \alpha_a とおく)への同型写像が存在するもの全体からなる集合を A とおきます.
また, S = \{\alpha_a : a \in A\} とおきます.
まず, S が順序数であることを示します.
S は順序数の集合なので, \rm{sup}S は順序数になり, S \subset \rm{sup}S であることから S は \in による整列順序.
また, \gamma \in \alpha_a \in S のとき, \varphi を W(a) から \alpha_a への同型写像とします.
すると, ある c \in W が存在して W(c) と \gamma は同型になるので \gamma \in S.
以上により, S は \in による整列順序で推移的なので順序数です.
\alpha = S とおいておきます.
次に, A=W であることを示します.
まず, 上と同様の議論によって b < a \in A ならば b \in A であることが分かるので, A=W であるか, 適当な c \in W について A = W(c) であることが分かります.
今, f を A から \alpha への写像とすると, これが全単射で順序を保つことは明らか.
つまり, f は A から \alpha への同型写像です.
ここで, A=W(c) と仮定すると, f は W(c) から \alpha への同型写像になるので, A の定義から c \in A = W(c) = \{x \in W : x < c\} となって矛盾.
以上により, f は W から \alpha への同型写像です.

いやはや.
順序数の定義がうまくできているからこそ, 証明もうまくいくものなのですね.
ここで, 用語を色々と定義しておきます.
順序数 \alpha が適当な順序数 \beta について \alpha = \beta + 1 となるとき, \alpha は後続順序数(successor ordinal)と呼ばれます.
そうでないとき, \alpha は極限順序数(limit ordinal)と呼ばれます.
このとき, \alpha = \rm{sup}\{\beta : \beta < \alpha\} = \bigcup \alpha です.
0 = \emptyset も極限順序数と考え, \rm{sup}\emptyset = 0 と定義します.
0 以外の極限順序数が存在することは無限の公理によります.
そして, 0 以外の極限順序数のうち最小のものを \omega と定義します.
\omega より小さい順序数として自然数(natural number)を定義します.
自然数を一つ一つ要素を書き並べて書くと面倒なので省略します.
集合 X が有限(finite)であるとは, X とある自然数との間に全単射が存在することとします.
全単射が存在しないとき, X は無限(infinite)であるといいます.
自然数の定義の仕方には, 他にも色々な方法があるようです.