順序数

順序数 (ordinal number, ordinal) とは，ナイーブには整列順序と順序保存写像全体の圏の骨格である，すなわち整列順序全体における同型という同値関係に関する代表元である．しかしこれは定義として上手くいかない．順序数の正確な定義の仕方はさまざまであるが，本項では一般的なフォン・ノイマンによるものを採用する．

導入

ユーザーブログ:Kyodaisuu/順序数講座も参照．

本節の説明はあくまでも導入としての順序数の説明であり，あえて厳密でない表現を用いることで定義や註釈を削ぎ落していることに注意すること．
素朴な定義による問題点については「ブラリ=フォルティのパラドックス」節を参照．
数学的に厳密な定義は「定義」節を参照．

整列集合

順序数は，自然数全体の集合$\mathbb {N}$が持つ整列性 (well-orderedness) という性質に注目し，それを一般化・拡張したものである．このとき，自然数と同様に加算$(+)$や乗算$(\cdot )$，冪などの算術が定義でき，全体として”数っぽく”振る舞えるため，順序数は自然数の拡張とみなされる．
整列性は全順序集合に関する性質であるため，まず全順序集合を定義する．

定義1.1 (全順序集合 total order)

全順序集合 (totally ordered set) とは、2つの集合$T$と$(\preceq )$の組で，$(\preceq )$が$T\times T$の部分集合であり，くわえて以下の条件を満たすものである． 以下では、$(x,y)\in (\preceq )$であることを$x\preceq y$で表す． 任意の$x\in T$について，$x\preceq x$．（反射性 reflexivity） 任意の$x,y\in T$について，$x\preceq y$かつ$y\preceq x$ならば，$x=y$． (反対称性 antisymmetry) 任意の$x,y,z\in T$について，$x\preceq y$かつ$y\preceq z$ならば，$x\preceq z$． (推移性 transitivity) 任意の$x,y\in T$について，$x\preceq y$あるいは$y\preceq x$のいずれかが成り立つ． (比較可能性 comparability)

自然数の集合$\mathbb {N}$は，通常の順序$\leq$によって全順序集合となる．ふつう自然数上の順序は$\leq$であるが，自然数上にそうではない順序を導入することも可能であることに注意する．
例えば，以下のような順序を入れることができる：

$0\prec 2\prec 4\prec \cdots \prec 1\prec 3\prec 5\prec \cdots$

$x\preceq y$を$x=y$または$x\prec y$で定義すると，これによって定義される順序$\preceq$は全順序の要件を満たす．

定義1.2 (整列集合 well-order)
全順序集合$\langle T,(\preceq )\rangle$が整列集合 (well-ordered set)であるとは，任意の空でない部分集合$S\subseteq T$について必ず最小元$m$が存在すること，すなわち 空でない任意の$S\subseteq T$に対して，ある$m\in S$が存在して，すべての$s\in S$に対して$m\preceq s$が成り立つ． ことである．

整列集合は(ZFCで)同値な別の定義が複数存在する．全順序集合$\langle T,(\preceq )\rangle$が整列集合であるとは，例えば以下のいずれかが成り立つこととしても定義できる：

• 無限に減少する$T$の列 $t_{0}\succ t_{1}\succ t_{2}\succ \cdots$が存在しないこと
• $T$の全体が以下の2条件を満たしながら上昇する系列 $t_{0}\prec t_{1}\prec t_{2}\prec \cdots$をなしていること：

1. 最小の要素$t_{0}$が存在する．
2. 部分集合$S\subseteq T$に対して，これより大きい要素$t\in T$が存在する(任意の$s\in S$について$s\prec t$)とき，$S$の"直後の"要素($S$より大きい要素の中で最小のもの)が存在する．

• $T$の全体で，$\preceq$についての超限帰納法が有効であること．
• $T$の真な部分順序$S\subsetneq T$($S$には$\preceq$を$S$に制限した順序が入るものとする)に対して，ある$T$の始切片が存在して$S$と同型になること．

注意. $x\prec y$とは$x\preceq y$かつ$x\neq y$，$x\succ y$とは$y\prec x$のことである．以降も同様である．$\prec$が整列順序であるということを$\preceq$が整列順序であることとして定義する。逆に任意の狭義全順序$\prec$に対し、$x\prec y$と$x\preceq y$かつ$x\neq y$が同値であるような全順序$\preceq$が一意に存在するので、これにより狭義全順序に対する整列性も定義されたこととなる。

順序数という整列集合

自然数の全体$\mathbb {N}$は，通常の順序$\leq$によって整列順序をなす．整列集合$\langle \mathbb {N} ,\leq \rangle$の始切片とは，ある自然数$n$より小さい数の集合のことであるが，これを$n$と書くことにする．すなわち，$n=\{0,1,\cdots ,n-1\}$として見る．
これらの集合に対しての大小関係が$\subseteq$で導入でき，以下のような増加列を得る：

$0,1,2,\cdots ,\mathbb {N}$

これを要素に持つ集合$\{0,1,2,\cdots ,\mathbb {N} \}$を考えると，これは$\subseteq$によって整列順序をなし，さらに$\mathbb {N}$より大きい．
そこで，$\langle \mathbb {N} ,\leq \rangle$や$\{0,1,2,\cdots ,\mathbb {N} \}$などの整列集合も"数"とみなしてしまい，それらの大小を$\subseteq$ではかることにする．この全体が順序数である．

順序数としての自然数の全体を$\omega$で表す．このとき，順序数を小さい方から順に並べると

$0,1,2,\cdots ,\omega ,\omega +1,\omega +2,\cdots$

となる．

ブラリ=フォルティのパラドックス

ブラリ=フォルティのパラドックス (Burali-Forti's paradox) とは，単純に言うと「『全ての順序数の集合』は定義できない」というものである．現代公理的集合論に於いてこれはパラドックスではない，すなわち矛盾を生じさせるようなものではないことに注意せよ．パラドックスというより，「全ての順序数からなる集まり」は集合ではないという一つの定理として考えたほうが生産的である．

これは、以下の事実に起因する：

• 順序数を集めた集合に順序数の大小関係を導入したものは再び整列集合となる．
• ある順序数$\alpha$より小さい順序数すべてからなる整列集合は、$\alpha$自身に順序同型である．
• すべての整列集合は，ある順序数に順序同型である．

『全ての順序数の集合』$O$が存在すると仮定すると，これは順序数の大小関係によって整列集合となる．従ってこれと同型な順序数が存在するため，これも$O$で表すと，$O\in O$でなければならない．
一方，$O$は$O$より小さい順序数すべてからなる整列集合に順序同型である．このことから，$\alpha \in O$と$\alpha <O$は同値であることがわかる．すると$O\in O$なので$O<O$が導かれ，これは矛盾である．

集合論において，「(ある性質)が成り立つすべての集合」を素朴に導入することはできない．従って，現代の集合論では分出公理や置換公理などに見られるように，「(ある範囲)において(ある性質)が成り立つすべての集合」という形で定義することでこれを回避している．

定義

以降の内容では以下の定義によって順序数を定め，単に順序数と書いたときはこの定義によるものとする．

定義2.1 (順序数 ordinal, ordinal number)
集合$\alpha$が順序数であるとは，$\alpha$が推移的でかつ$(\alpha ,\in )$（より正確には$(\alpha ,\{(\beta ,\gamma )\in \alpha ^{2}\mid \beta \in \gamma \})$）が整列順序集合であるということである．

ここで$\alpha$が推移的 (transitive) であるとは，任意の$\beta \in \alpha$に対し$\beta \subset \alpha$が成り立つということである．

一般に$\in$を順序とみなすときは狭義順序であるとみなす．つまり，$(\alpha ,\in )$が整列順序集合であるとは，$(\alpha ,\in )$が狭義全順序集合であって、空でない任意の部分集合$S\subset \alpha$に対しある$\gamma \in S$が存在して任意の$\beta \in S$に対し$\gamma =\beta$または$\gamma \in \beta$が成り立つということである．

なお$(V,\in )$の整礎性である正則性公理を課す強い集合論（例えば${\mathsf {ZFC}}$集合論）においては，推移的集合$\alpha$が$(\alpha ,\in )$が整列順序集合であることと$(\alpha ,\in )$が狭義全順序集合であることが同値であるため，この条件は様々な言い換えを持つ．

${\mathsf {ZF}}$集合論を始めとする多くの集合論では一般に，$0=\emptyset ,\ n+1=n\cup \{n\}$によって自然数が定義されるが，これは順序数でもある．「このようにして得られる」集合のことを「自然数」と総称したいが、直接的な方法では循環論法となってしまう。代わりに、$\emptyset$を元に持ち対応$x\mapsto x\cup \{x\}$で閉じる最小のクラスを$\omega$と定め、$\omega$に属する元を自然数と呼ぶ。このようにすることで、上記の方法で具体的に構成される集合はすべて自然数であることが保証される。無限公理を課す集合論においては$\omega$も順序数である．

任意の順序数$\alpha$に対して，$\alpha$の後続 (successor) を$\alpha \cup \{\alpha \}$と定義し，$\alpha +1$などと書く．順序数$\alpha$の後続はまた順序数であり、$\alpha$より大きい順序数の中で最小のものである．
$\alpha$がある順序数の後続であるとき，$\alpha$を後続順序数 (successor ordinal) という．そうでないとき，$\alpha$を極限順序数 (limit ordinal) という．

後続順序数と極限順序数については，以下のような特徴づけもできる．順序数$\alpha$に対して、$\bigcup \alpha$は$\alpha$の要素すべての和集合とする。このとき，

1. $\alpha$が後続順序数で$\alpha =\alpha '+1$のとき，$\bigcup \alpha =\alpha '$．
2. $\alpha$が極限順序数のとき，$\bigcup \alpha =\alpha$．

順序数に対する場合分けはこの2つで十分である．これは以下の定理によって示される．

定理2.2 (超限帰納法 transfinite induction)
$C$は順序数のクラス(集合とは限らない)であり，以下の条件を満たすものとする： $0\in C$ $\alpha \in C$ならば，$\alpha +1\in C$． $\alpha$が0でない極限順序数で，任意の$\beta <\alpha$に対して$\beta \in C$が成り立つとき，$\alpha \in C$． このとき，$C$は順序数全てからなるクラスに等しい．

順序数全てからなるクラスは$\mathbf {Ord}$や$\mathrm {On}$などで表記される．

順序数の算術

自然数上の算術を拡張することで，順序数上の算術を定義することができる．極限順序数$\alpha$以下の順序数によって添え字づけられた順序数の非減少列$\{\gamma _{\xi }\}_{\xi <\alpha }$に対して，その極限$\lim _{\xi <\alpha }\gamma _{\xi }$を以下で定める：

$\lim _{\xi <\alpha }\gamma _{\xi }=\sup\{\gamma _{\xi }\ |\ \xi <\alpha \}=\min\{\gamma \in \mathbf {Ord} \ |\ \forall \xi <\alpha .\gamma _{\xi }<\gamma \}$

定義3.1 (順序数の算術)
(加法) 順序数$\alpha ,\beta$に対して，和$\alpha +\beta$を以下で定義する： $\alpha +0=\alpha$， $\alpha +(\beta +1)=(\alpha +\beta )+1$， $\beta$が0でない極限順序数のとき，$\alpha +\beta =\lim _{\xi <\beta }(\alpha +\xi )$．
(乗法) 順序数$\alpha ,\beta$に対して，積$\alpha \cdot \beta$を以下で定義する： $\alpha \cdot 0=0$， $\alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha$， $\beta$が0でない極限順序数のとき，$\alpha \cdot \beta =\lim _{\xi <\beta }(\alpha \cdot \xi )$．
(冪) 順序数$\alpha ,\beta$に対して，冪$\alpha ^{\beta }$を以下で定義する： $\alpha ^{0}=1$， $\alpha ^{\beta +1}=\alpha ^{\beta }\cdot \alpha$， $\beta$が0でない極限順序数のとき，$\alpha ^{\beta }=\lim _{\xi <\beta }\alpha ^{\xi }$．

加算と乗算は結合的だが，可換ではない．すなわち，順序数の和や積には左右の区別があることに注意．
任意の順序数は，以下のカントール標準形を一意に持つことがカントール標準形定理によって示されている．

定理3.2 (カントール標準形定理 Cantor's normal form theorem)
順序数$\alpha$に対して，$(0\leq )n<\omega$，0でない自然数$k_{1},\cdots ,k_{n}(<\omega )$，順序数$\alpha _{1},\cdots ,\alpha _{n}$が存在して$\alpha \geq \alpha _{1}>\cdots >\alpha _{n}$を満たし， $\alpha =\omega ^{\alpha _{1}}\cdot k_{1}+\cdots +\omega ^{\alpha _{n}}\cdot k_{n}$ が成り立つ．（$n=0$の場合，上式は$\alpha =0$を表す．）

基数

定義4.1 (基数 cardinal number, cardinal)
順序数$\kappa$が基数あるいは始数 (initial number) であるとは，すべての$\alpha <\kappa$に対して$\alpha$と$\kappa$の間に全単射が存在しないことを言う．

2つの集合$X$と$Y$の間に全単射が存在するとき，2つの集合の濃度が等しい，等濃，対等 (equinumerous) と言う．ここから，ナイーブには濃度とは全単射という同値関係で割った代表元と思うことができるが，これはもっと厳密に，選択公理を用いて以下のように定義できる．

定義4.2 (濃度 cardinality, 独:mächtigkeit, kardinalität)
集合$X$の濃度を，$X$と全単射が存在する最小の順序数とする．

明らかに集合の濃度は基数であり，これにより集合の濃度は基数によって表される．

有限順序数すべてと$\omega$は基数である．また，$\omega$は自然数全体の集合であるため，その濃度$\aleph _{0}$とはこの定義に従うと$\omega$のことである．
基数に対しても「後続」と「基数列の極限」である基数が存在するため，順序数で添え字づけられた基数の列

$\aleph _{0},\aleph _{1},\cdots ,\aleph _{\omega },\cdots$

が存在する．各集合を基数として扱うときは$\aleph _{\alpha }$，順序数として扱うときは$\omega _{\alpha }$と一般に表記される．（集合としては$\aleph _{\alpha }=\omega _{\alpha }$である．）

注意：

• 選択公理を仮定しない集合論である${\mathsf {ZF}}$の場合，任意の集合に対して濃度の等しい順序数があることは保証されない．このとき，集合の濃度は先程のナイーブなアイデアを精緻化したスコットのからくりを用いて定義されることが多い．なおこの手法は正則性公理を仮定しない集合論では必ずしも通用しない．なぜなら全ての集合が$\mathrm {WF}$に含まれることは正則性公理と十分に強い集合論上で同値であり，$\mathrm {WF}$に含まれる集合に対してしかスコットのからくりは適用できないからである．
• 「$X$と$Y$は濃度が等しい」といったとき，「$X$と$Y$は等濃である」と「$X$の基数と$Y$の基数は等しい」という2種類の意味にとらえられるが，この2つは同値なので特に問題はない．
• $\omega _{1}$は最小の非可算順序数であるが，これはハルトークスの定理によって${\mathsf {ZF}}$上で必ず定義できる．しかし一般の後続基数の定義は${\mathsf {ZF}}$では同値性を示せないものが複数存在する．
• 一方，連続体仮説の${\mathsf {ZFC}}$との独立性が示す通り，これが連続体濃度$\aleph$に等しいかどうかは${\mathsf {ZFC}}$上では不明である．

歴史

カントールによる導入(1883～1897頃)

順序数を初めて導入したのはゲオルク・カントールである。彼は実数の濃度が自然数全体の濃度よりも真に大きいことを（さらに言えば濃度という概念も彼が導入したものであるが）示し、無限が単一の存在でないことを示した。さらに、この無限の濃度を表した基数が無数に存在し、さらにそれらは大きさの順に並べることができ

$0<1<\cdots <\aleph _{0}<\aleph _{1}<\cdots <\aleph _{\omega }<\cdots$

が整列であるべきだと示唆した。

カントールは整列集合の持つ特異な性質を見抜き、整列集合および順序数における基本的な性質を多く証明している。特に重要なのはイプシロン数の発見、カントール標準形定理、そして整列集合の三分律(以下に記載)であろう。

定理 (整列集合の三分律)
$W_{1}$と$W_{2}$が整列集合であるとき、以下の3つのうちでただ1つのみが成り立つ： $W_{1}$と$W_{2}$は順序同型。 $W_{1}$はある$W_{2}$の始切片に順序同型。 (すなわち、ある$w\in W_{2}$が存在して、$W_{1}\simeq \{x\in W_{2}|x<w\}$.) $W_{2}$はある$W_{1}$の始切片に順序同型。

整列性自体が強力な性質だが，これにより順序数を大小比較のできるある種"数"のような扱いをすることができる．

証明論と順序数解析 (1934～)

詳細は証明論的順序数，順序数崩壊関数を参照