順序数
概要
順序数（ordinal number）とは、整列集合の「並び方の形」（順序同型類）を代表する標準的な集合であり、von Neumann の定義では、推移的で帰属関係 $\in$ によって整列されている集合のことである。各順序数は自分より小さい順序数すべての集合に等しく、$0=\emptyset$、$1=\{0\}$、$\ldots$、$\omega=\{0,1,2,\ldots\}$、$\omega+1=\omega\cup\{\omega\}$ と続く。大小 $\alpha<\beta$ は $\alpha\in\beta$ で与えられ、順序数全体は整列された真のクラスをなす。任意の整列集合はちょうど一つの順序数と順序同型であり、超限帰納法と超限再帰の基盤となる。和と積は非可換で $1+\omega=\omega\neq\omega+1$ であり、大きさを測る基数とは区別される。
前提知識: 集合, 整列順序, 順序同型, 推移的集合, ZFC公理系
定義
本記事は公理的集合論 ZF（ZFC公理系から選択公理を除いたもの）の枠組みで議論し、選択公理は用いない。集合 $x$ に対して $x^{+}:=x\cup\{x\}$ を $x$ の後続者という。
集合 $t$ が推移的（transitive）であるとは、$t$ の任意の元が $t$ の部分集合であること、すなわち $y\in x\in t$ ならば $y\in t$ が成り立つことをいう（推移的集合）。
集合 $\alpha$ が順序数（ordinal number, ordinal）であるとは、次の二条件を満たすことをいう。
- $\alpha$ は推移的である。
- $\alpha$ は帰属関係 $\in$ によって整列されている。すなわち、$\alpha$ 上の二項関係 $x< y:\iff x\in y$ は狭義順序（$x\in x$ となる $x\in\alpha$ はなく、$x\in y\in z$ ならば $x\in z$）であって、$\alpha$ の任意の二元 $x\neq y$ について $x\in y$ または $y\in x$ が成り立ち（三分律）、$\alpha$ の空でない任意の部分集合 $S$ は $\in$ に関する最小元（$S$ の元 $m$ で、任意の $x\in S\setminus\{m\}$ について $m\in x$ となるもの）を持つ（整列順序）。
順序数全体の集まりを $\mathrm{Ord}$ と書く。順序数 $\alpha,\beta$ に対して
$$ \alpha<\beta:\iff\alpha\in\beta,\qquad \alpha\leq\beta:\iff\alpha\in\beta\text{ または }\alpha=\beta $$
と定める。この定義は von Neumann による（vN23、Jec03 Chapter 2）。
順序数 $\alpha$ に対し、$\alpha+1:=\alpha^{+}=\alpha\cup\{\alpha\}$ と書く（これが順序数であることは prop-ordinal-class で示す）。
- 順序数 $\alpha$ が後続順序数（successor ordinal）であるとは、ある順序数 $\beta$ について $\alpha=\beta+1$ となることをいう。
- 順序数 $\alpha$ が極限順序数（limit ordinal）であるとは、$\alpha\neq0:=\emptyset$ であり、かつ後続順序数でないことをいう。
- $0$ を含み後続者をとる操作で閉じた集合を帰納的集合といい、最小の帰納的集合を $\omega$ と書く（存在は無限公理による）。$\omega$ の元を有限順序数または自然数といい、$\omega$ の元でない順序数を超限順序数（transfinite ordinal）という。
整列集合 $(W,<)$（整列順序）に対し、$W$ と順序同型な順序数（thm-ordinal-representation によりちょうど一つ存在する）を $W$ の順序型（order type）といい、$\operatorname{type}(W)$ と書く。
直感
順序数は「番号をつけて一列に並べる」という操作を、有限個を超えて続けたときに現れる「長さ」の目盛りである。$0,1,2,\ldots$ と数えたあとに「全部の次」として $\omega$ を置き、さらに $\omega+1,\omega+2,\ldots$ と続けられる。von Neumann の定義は、各順序数を「自分より小さい順序数すべての集合」として実現する。$0=\emptyset$、$1=\{0\}$、$2=\{0,1\}$、$\omega=\{0,1,2,\ldots\}$、$\omega+1=\omega\cup\{\omega\}$ であり、順序数の大小は帰属関係 $\in$ そのものになる。こうして、整列集合の「形」（順序同型類）ごとに標準的な代表を一つずつ選ぶことができ、それが順序型である。順序数は「大きさ」ではなく「並び方」を測るので、同じ個数の元を持つ集合でも並べ方が違えば異なる順序数が対応する（rem-ordinal-vs-cardinal）。
例と反例
$0:=\emptyset$、$1:=0+1=\{0\}$、$2:=1+1=\{0,1\}$、$3:=2+1=\{0,1,2\}$ とおくと、いずれも順序数である。たとえば $2=\{\emptyset,\{\emptyset\}\}$ は推移的（$\emptyset\subset2$、$\{\emptyset\}\subset2$）であり、$\emptyset\in\{\emptyset\}$ なので二元は $\in$ で比較可能、空でない部分集合 $\{\emptyset\}$、$\{\{\emptyset\}\}$、$2$ はそれぞれ最小元 $\emptyset$、$\{\emptyset\}$、$\emptyset$ を持つ。数学的帰納法により、一般に $n+1=\{0,1,\ldots,n\}$ であり、自然数 $n$ は「$n$ 個の元を $\in$ で一列に並べた」順序数である（後続者、帰納的集合）。
$\omega=\{0,1,2,\ldots\}$ は順序数であり（thm-ordinal-omega）、最小の極限順序数である。$\omega+1=\omega\cup\{\omega\}=\{0,1,2,\ldots,\omega\}$ は、自然数の列の「後ろ」に一つ元を置いた並び方に対応する順序数で、最大元 $\omega$ を持つ。$\omega+2=\{0,1,2,\ldots,\omega,\omega+1\}$ 以下同様であり、$\omega+\omega=\omega\cdot2=\{0,1,2,\ldots,\omega,\omega+1,\omega+2,\ldots\}$ は自然数の列を二つ並べた順序数、$\omega\cdot\omega=\omega^{2}$ は自然数の列を $\omega$ 個並べた順序数である（def-ordinal-arithmetic）。$\omega+\omega$ と $\omega^{2}$ は極限順序数である。
自然数全体 $\mathbb{N}$ の通常の順序の順序型は $\omega$ である。整列順序の例にある $\mathbb{N}\cup\{\infty\}$（すべての $n$ について $n<\infty$）の順序型は $\omega+1$、$\mathbb{N}\times\mathbb{N}$ の辞書式順序の順序型は $\omega\cdot\omega=\omega^{2}$ である。実際、$(a,b)\mapsto\omega\cdot a+b$ が順序同型を与える（ex-ordinal-noncommutative の末尾を参照）。有限な整列集合の順序型はその元の個数 $n$ である。
次の各集合は、順序数の二条件のうち一方を満たし、他方を満たさない。したがってどちらの条件も他方から従わない。
- 推移的でない：$\{1\}=\{\{\emptyset\}\}$。一元集合なので $\in$ による整列の条件は満たすが、$0\in1\in\{1\}$ なのに $0\notin\{1\}$ なので推移的でない。
- $\in$ で整列されない：$t:=\{0,1,\{1\}\}=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\}\}$。$0\subset t$、$1=\{0\}\subset t$、$\{1\}\subset t$ なので推移的だが、$0$ と $\{1\}$ は $0\notin\{1\}$ かつ $\{1\}\notin0$ なので $\in$ で比較できず、三分律を満たさない。
また、整列集合を順序数と混同してはならない。$\mathbb{N}$ の通常の順序と、$\mathbb{N}$ の元を「偶数を先に、次に奇数を」並べた順序（$0<2<4<\cdots<1<3<5<\cdots$）は、どちらも $\mathbb{N}$ 上の整列順序であるが順序型は $\omega$ と $\omega+\omega$ で異なる。順序数は台集合ではなく並べ方の形を表す。
性質
$\alpha,\beta$ を順序数とする。
- $\alpha\notin\alpha$。
- $\alpha$ の任意の元は順序数である。
- $\alpha\in\beta$ であることと $\alpha\subsetneq\beta$ であることは同値である。
- $\alpha\cap\beta$ は順序数である。
- $\alpha\in\beta$、$\alpha=\beta$、$\beta\in\alpha$ のうちちょうど一つが成り立つ。すなわち任意の二つの順序数は $<$ で比較可能である。
- $\alpha\in\alpha$ と仮定すると、$x:=\alpha$ は $\alpha$ の元で $x\in x$ を満たし、$\alpha$ 上の $\in$ が狭義順序であること（$x\in x$ となる元がないこと）に反する。
- $x\in\alpha$ とする。推移性：$z\in y\in x$ とすると、$\alpha$ の推移性から $y\in\alpha$、さらに $z\in\alpha$ であり、$z\in y\in x$ は $\alpha$ の三元の間の関係なので、$\alpha$ 上の $\in$ の推移律から $z\in x$ である。整列性：$\alpha$ の推移性から $x\subset\alpha$ であり、整列順序は部分集合に遺伝するので、$x$ は $\in$ で整列されている。
- $\alpha\in\beta$ とすると、$\beta$ の推移性から $\alpha\subset\beta$ であり、(1) から $\alpha\neq\beta$ である。逆に $\alpha\subsetneq\beta$ とする。$\beta\setminus\alpha$ は $\beta$ の空でない部分集合なので $\in$ に関する最小元 $\gamma$ を持つ。$\gamma=\alpha$ を示す。$\delta\in\gamma$ とすると $\delta\in\beta$（推移性）であり、$\gamma$ の最小性から $\delta\notin\beta\setminus\alpha$、よって $\delta\in\alpha$ である。逆に $\delta\in\alpha$ とすると $\delta,\gamma\in\beta$ なので三分律から $\delta\in\gamma$、$\delta=\gamma$、$\gamma\in\delta$ のいずれかが成り立つ。$\delta=\gamma$ なら $\gamma\in\alpha$ となり $\gamma\in\beta\setminus\alpha$ に反する。$\gamma\in\delta$ なら $\alpha$ の推移性から $\gamma\in\alpha$ となり同じく反する。よって $\delta\in\gamma$ である。以上から $\gamma=\alpha$、すなわち $\alpha\in\beta$ である。
- $z\in y\in\alpha\cap\beta$ なら $z\in\alpha$ かつ $z\in\beta$ なので $\alpha\cap\beta$ は推移的であり、$\alpha$ の部分集合なので $\in$ で整列されている。
- $\gamma:=\alpha\cap\beta$ は (4) により順序数で、$\gamma\subset\alpha$、$\gamma\subset\beta$ である。もし $\gamma\neq\alpha$ かつ $\gamma\neq\beta$ なら、(3) から $\gamma\in\alpha$ かつ $\gamma\in\beta$、すなわち $\gamma\in\alpha\cap\beta=\gamma$ となり (1) に反する。よって $\gamma=\alpha$ または $\gamma=\beta$、すなわち $\alpha\subset\beta$ または $\beta\subset\alpha$ であり、(3) から三つのうち少なくとも一つが成り立つ。二つ以上は成り立たない：$\alpha\in\beta$ かつ $\alpha=\beta$ は (1) に反し、$\alpha\in\beta$ かつ $\beta\in\alpha$ なら $\alpha$ の推移性から $\alpha\in\alpha$ となってやはり (1) に反する。$\square$
- 順序数からなる任意の集合 $X$ 上で $<$（すなわち $\in$）は整列順序である。特に、順序数からなる空でない任意の集合は最小元を持つ。
- 順序数からなる推移的な集合は順序数である。
- 順序数からなる任意の集合 $X$ に対し、和集合 $\bigcup X$ は順序数であり、$X$ の上限 $\sup X$ である。すなわち任意の $\alpha\in X$ について $\alpha\leq\bigcup X$ であり、任意の $\alpha\in X$ について $\alpha\leq\beta$ となる順序数 $\beta$ は $\bigcup X\leq\beta$ を満たす。
- 順序数 $\alpha$ に対し $\alpha+1=\alpha\cup\{\alpha\}$ は順序数であり、$\alpha$ より大きい最小の順序数である。
- 順序数からなる空でない任意のクラス $\mathbf{C}$ は最小元を持つ。
- $\in$ が $X$ 上の狭義順序であること（非反射律は prop-ordinal-basic の 1、推移律は $\gamma\in\beta\in\alpha$ なら $\alpha$ の推移性から $\gamma\in\alpha$）と三分律（prop-ordinal-basic の 5）は既に示した。空でない $S\subset X$ をとり、$\alpha\in S$ を一つ選ぶ。$\alpha\cap S=\emptyset$ なら、任意の $\beta\in S$ について $\beta\notin\alpha$ なので三分律から $\alpha\leq\beta$ であり、$\alpha$ が $S$ の最小元である。$\alpha\cap S\neq\emptyset$ なら、これは $\alpha$ の空でない部分集合なので $\in$ に関する最小元 $\mu$ を持つ。任意の $\beta\in S$ について、$\beta\in\alpha$ なら $\beta\in\alpha\cap S$ より $\mu\leq\beta$、$\beta\notin\alpha$ なら $\alpha\leq\beta$ と $\mu\in\alpha$ から $\mu<\beta$ である。よって $\mu$ が $S$ の最小元である。
- 順序数からなる推移的な集合 $t$ は、(1) により $\in$ で整列されているので順序数である。
- $\bigcup X$ の元は $X$ のある元（順序数）の元なので prop-ordinal-basic の 2 により順序数である。$z\in y\in\bigcup X$ とすると、$y\in\alpha$ となる $\alpha\in X$ があり、$\alpha$ の推移性から $z\in\alpha$、よって $z\in\bigcup X$ である。したがって $\bigcup X$ は順序数からなる推移的な集合であり、(2) により順序数である。$\alpha\in X$ なら $\alpha\subset\bigcup X$ なので prop-ordinal-basic の 3 により $\alpha\leq\bigcup X$ である。任意の $\alpha\in X$ について $\alpha\leq\beta$ なら各 $\alpha\subset\beta$ なので $\bigcup X\subset\beta$、よって $\bigcup X\leq\beta$ である。
- $\alpha+1$ の元は $\alpha$ の元または $\alpha$ 自身なので順序数であり、$\alpha+1$ は推移的である（$z\in y\in\alpha+1$ なら、$y\in\alpha$ のとき $z\in\alpha$、$y=\alpha$ のとき $z\in\alpha$、いずれにせよ $z\in\alpha+1$）。よって (2) により順序数である。$\alpha\in\alpha+1$ なので $\alpha<\alpha+1$ であり、$\alpha<\beta$ なら $\alpha\subset\beta$ かつ $\alpha\in\beta$ より $\alpha+1=\alpha\cup\{\alpha\}\subset\beta$、よって $\alpha+1\leq\beta$ である。
- $\alpha\in\mathbf{C}$ を一つとる。$\alpha\cap\mathbf{C}=\{\beta\in\alpha\mid\beta\in\mathbf{C}\}$ は分出公理により集合であり、(1) の議論をそのまま繰り返せば、これが空なら $\alpha$、空でなければその最小元が $\mathbf{C}$ の最小元である。$\square$
順序数全体の集まり $\mathrm{Ord}$ は集合ではない（真のクラスである）。
$\mathrm{Ord}$ が集合であると仮定する。prop-ordinal-basic の 2 により $\mathrm{Ord}$ は推移的であり、順序数からなるので、prop-ordinal-class の 2 により $\mathrm{Ord}$ は順序数である。すると $\mathrm{Ord}\in\mathrm{Ord}$ となり、prop-ordinal-basic の 1 に反する。$\square$
この矛盾は Burali-Forti が 1897 年に指摘したもので（BF97）、素朴集合論の逆理の一つである。ZF では「順序数全体」は集合ではなくクラスとして扱われる。
$\alpha$ を順序数とする。
- $\alpha$ が後続順序数 $\beta+1$ ならば、$\beta$ は $\alpha$ の最大元であり $\bigcup\alpha=\beta$ である。
- $\alpha$ が $0$ でも後続順序数でもない（極限順序数である）ことと、$\alpha\neq0$ かつ $\bigcup\alpha=\alpha$ であることとは同値である。このとき任意の $\beta<\alpha$ に対して $\beta+1<\alpha$ である。
- 順序数は $0$、後続順序数、極限順序数のいずれかちょうど一つである。
- $\alpha=\beta\cup\{\beta\}$ の元は $\beta$ の元または $\beta$ であり、$\gamma\in\beta$ なら $\gamma<\beta$ なので $\beta$ は $\alpha$ の最大元である。$\bigcup\alpha=\left(\bigcup\beta\right)\cup\beta=\beta$ である（$\beta$ の推移性から $\bigcup\beta\subset\beta$）。
- $\bigcup\alpha=\sup\alpha$（prop-ordinal-class の 3）であり、$\alpha$ の推移性から $\bigcup\alpha\subset\alpha$、すなわち $\bigcup\alpha\leq\alpha$ である。$\bigcup\alpha<\alpha$ とすると $\beta:=\bigcup\alpha\in\alpha$ であり、$\beta$ は $\alpha$ の元の上限なので $\alpha$ の最大元である。すると $\beta+1\leq\alpha$（prop-ordinal-class の 4）であり、$\gamma\in\alpha$ なら $\gamma\leq\beta$ より $\gamma\in\beta+1$ なので $\alpha\subset\beta+1$、よって $\alpha=\beta+1$ は後続順序数である。逆に $\alpha=\beta+1$ なら (1) より $\bigcup\alpha=\beta\neq\alpha$ である。したがって、$\alpha\neq0$ のとき「後続順序数でない」と「$\bigcup\alpha=\alpha$」は同値である。極限順序数 $\alpha$ と $\beta<\alpha$ について、$\beta+1\leq\alpha$ であり、$\beta+1=\alpha$ なら $\alpha$ が後続順序数になるので $\beta+1<\alpha$ である。
- 定義から、極限順序数は $0$ でも後続順序数でもない順序数である。$0=\emptyset$ は元を持たないので後続順序数ではない（$\beta+1$ は $\beta$ を元に持つ）。よって三つの場合は互いに排反で、すべてを尽くす。$\square$
最小の帰納的集合 $\omega$ は順序数であり、その元はすべて $0$ または後続順序数である。したがって $\omega$ は最小の極限順序数であり、有限順序数とは $\omega$ より小さい順序数のことである。
$\omega$ の存在と帰納的集合の性質は 帰納的集合 が扱う。$\omega$ の元が順序数であること、$\omega$ が推移的であること、$\omega$ の元が $0$ または後続順序数であることは、帰納的集合上の帰納法（$\omega$ は最小の帰納的集合なので、$0$ を含み後続者で閉じた $\omega$ の部分集合は $\omega$ に一致する）によって示される。たとえば最後の主張は、$T:=\{n\in\omega\mid n=0\text{ または }n\text{ は後続順序数}\}$ とおくと、$0\in T$ であり、$n\in T$ が順序数であることから prop-ordinal-class の 4 より $n+1$ も順序数で後続順序数なので $n+1\in T$、よって $T$ は $0$ を含み後続者で閉じた $\omega$ の部分集合となり、$\omega$ の最小性から $T=\omega$ であることによる。証明の詳細は Jec03 Chapter 2 または End77 Chapter 7 に譲る。これらを認めれば、$\omega$ が極限順序数であることは次のように従う。$\omega\neq0$ であり、もし $\omega=\beta+1$ なら $\beta\in\omega$ なので帰納的集合の条件から $\beta+1=\omega\in\omega$ となり prop-ordinal-basic の 1 に反する。$\omega$ より小さい順序数は $0$ か後続順序数なので、$\omega$ は最小の極限順序数である。
$\varphi(\alpha)$ を順序数 $\alpha$ についての命題とし、次を仮定する。
任意の順序数 $\alpha$ について、「任意の $\beta<\alpha$ に対して $\varphi(\beta)$ が成り立つ」ならば $\varphi(\alpha)$ が成り立つ。
このとき、すべての順序数 $\alpha$ について $\varphi(\alpha)$ が成り立つ。同じことは次の三段階の形でも述べられる：$\varphi(0)$ が成り立ち、任意の $\alpha$ について $\varphi(\alpha)$ ならば $\varphi(\alpha+1)$ が成り立ち、任意の極限順序数 $\lambda$ について「任意の $\beta<\lambda$ に対して $\varphi(\beta)$」ならば $\varphi(\lambda)$ が成り立つとき、すべての順序数について $\varphi$ が成り立つ。
$\varphi(\alpha)$ が成り立たない順序数 $\alpha$ があると仮定すると、そのような順序数全体のクラスは空でないので prop-ordinal-class の 5 により最小元 $\mu$ を持つ。任意の $\beta<\mu$ について $\varphi(\beta)$ が成り立つので、仮定から $\varphi(\mu)$ が成り立ち、矛盾する。三段階の形は、prop-ordinal-successor-limit の 3 により任意の順序数が $0$・後続順序数・極限順序数のいずれかであることから、最初の形の仮定を場合分けして確かめたものである。実際、$\alpha=0$ なら $\varphi(0)$ が成り立ち、$\alpha=\beta+1$ で任意の $\gamma<\alpha$ について $\varphi(\gamma)$ が成り立つなら特に $\varphi(\beta)$ から $\varphi(\alpha)$ が従い、極限の場合は仮定そのものである。$\square$
これは整列順序における帰納法の原理を、集合ではないクラス $\mathrm{Ord}$ に対して述べたものであり、超限帰納法と呼ばれる。
$\mathbf{G}$ を、集合を集合に対応させるクラス関数（任意の集合 $x$ に対し集合 $\mathbf{G}(x)$ を定める規則）とする。このとき、順序数全体で定義されたクラス関数 $\mathbf{F}$ であって、任意の順序数 $\alpha$ について
$$
\mathbf{F}(\alpha)=\mathbf{G}(\mathbf{F}|_{\alpha})
$$
（$\mathbf{F}|_{\alpha}$ は $\mathbf{F}$ の $\alpha=\{\beta\mid\beta<\alpha\}$ への制限で、置換公理により集合である）を満たすものがただ一つ存在する。
一意性は thm-ordinal-transfinite-induction により、二つの解 $\mathbf{F},\mathbf{F}'$ について $\mathbf{F}(\alpha)=\mathbf{F}'(\alpha)$ を $\alpha$ に関する超限帰納法で示せばよい。存在は、各順序数 $\alpha$ に対して $\alpha$ 上の「部分解」（$\alpha$ 上の関数 $f$ で任意の $\beta<\alpha$ について $f(\beta)=\mathbf{G}(f|_{\beta})$ を満たすもの）が一意に存在することを超限帰納法で示し、それらを貼り合わせて得られる。証明は Jec03 Chapter 2（Theorem 2.15）、End77 Chapter 7、Kun80 Chapter I §9 に譲る。超限再帰は順序数の算術（def-ordinal-arithmetic）や $\aleph$ 数（基数）、累積階層 $V_\alpha$ の定義に用いられる。
まず一般に、整列集合の順序同型写像 $g\colon W\to V$ と $x\in W$ について、$g$ は始切片 $W_{< x}$ を始切片 $V_{< g(x)}$ の上に写す。実際 $y< x\iff g(y)< g(x)$ であり、$g$ は全射だからである。
$\gamma\in\alpha$ について $f(\gamma)=\gamma$ を、$\alpha$ 上の帰納法（整列順序の帰納法の原理）で示す。任意の $\delta\in\gamma$ について $f(\delta)=\delta$ と仮定する。$\alpha$ における $\gamma$ の始切片は $\gamma$ 自身、$\beta$ における $f(\gamma)$ の始切片は $f(\gamma)$ 自身なので、上の注意から $f(\gamma)=\{f(\delta)\mid\delta\in\gamma\}=\{\delta\mid\delta\in\gamma\}=\gamma$ である。よって $f$ は恒等写像であり、$\beta=f[\alpha]=\alpha$ である。最後の主張は、$\alpha\cong\delta$ なら $\alpha=\delta\in\alpha$ となって prop-ordinal-basic の 1 に反することによる。$\square$
任意の整列集合 $(W,<)$ に対し、$W$ と順序同型な順序数がちょうど一つ存在する。
一意性：$W\cong\alpha$ かつ $W\cong\beta$ なら $\alpha\cong\beta$ であり、lem-ordinal-isomorphic-equal から $\alpha=\beta$ である。
存在：$x\in W$ が良いとは、始切片 $W_{< x}$ と順序同型な順序数が存在することとし、そのときその順序数（一意性により一つに定まる）を $\alpha_x$ と書く。すべての $x\in W$ が良いことを $W$ 上の帰納法で示す。$x\in W$ をとり、任意の $y< x$ が良いと仮定する。置換公理により $A:=\{\alpha_y\mid y< x\}$ は集合である。
(i) $y< y'< x$ とし、$g\colon W_{< y'}\to\alpha_{y'}$ を順序同型写像とする。$W_{< y}$ は $W_{< y'}$ における $y$ の始切片なので、$g$ はこれを $\alpha_{y'}$ における $g(y)$ の始切片、すなわち $g(y)$ の上に写す。よって $W_{< y}\cong g(y)$ であり、一意性から $\alpha_y=g(y)\in\alpha_{y'}$ である。したがって $y\mapsto\alpha_y$ は $W_{< x}$ から $A$ への狭義単調な全射であり、順序同型写像である。
(ii) $A$ は推移的である。実際 $\delta\in\alpha_y$（$y< x$）とし、$g\colon W_{< y}\to\alpha_y$ を順序同型写像とすると、$\delta=g(z)$ となる $z< y$ があり、$g$ は $W_{< z}$ を $\delta$ の上に写すので $W_{< z}\cong\delta$、よって $\delta=\alpha_z\in A$ である。
$A$ は順序数からなる推移的な集合なので prop-ordinal-class の 2 により順序数であり、(i) から $W_{< x}\cong A$ である。よって $x$ は良く、$\alpha_x=A$ である。
最後に $\alpha:=\{\alpha_x\mid x\in W\}$ とおく（置換公理により集合）。(i)・(ii) の議論で $W_{< x}$ を $W$ に置き換えてそのまま繰り返せば、$\alpha$ は順序数であり、$x\mapsto\alpha_x$ が $W$ から $\alpha$ への順序同型写像である。$\square$
この定理により、整列集合の順序同型類（順序型）は順序数によって一つずつ代表される（def-ordinal-order-type）。二つの整列集合が与えられれば、それぞれの順序型 $\alpha,\beta$ は prop-ordinal-basic の 5 により比較可能なので、一方が他方の始切片（または全体）と順序同型になる。
順序位相で見た後続順序数
全順序集合の順序位相は、開区間と端点を含む半開区間を基本的な開集合として生成される位相である。順序数 $\alpha$ には帰属関係による整列順序を入れ、この順序位相を考えられる。
$\alpha=\beta+1$ を後続順序数とする。順序位相を入れた位相空間 $\alpha=[0,\beta]$ はコンパクトである。
$\mathcal U$ を $\alpha$ の開被覆とする。$\gamma\le\beta$ に対し、閉区間
$$
[0,\gamma]:=\{\xi\in\alpha\mid \xi\le\gamma\}
$$
が $\mathcal U$ の有限個の成員で覆われるとき、$\gamma\in S$ と書く。$0$ を含む $U\in\mathcal U$ を一つとれば $[0,0]=\{0\}\subset U$ なので $0\in S$ である。
$\beta\notin S$ と仮定する。順序数の整列性から、$\alpha\setminus S$ は最小元 $\delta$ を持つ。$0\in S$ より $\delta>0$ である。
$\delta=\eta+1$ が後続順序数なら、$\delta$ の最小性から $\eta\in S$ である。$\delta$ を含む $U\in\mathcal U$ を一つとると、$[0,\eta]$ の有限被覆に $U$ を加えた有限族が
$$
[0,\delta]=[0,\eta]\cup\{\delta\}
$$
を覆う。従って $\delta\in S$ となり矛盾する。
$\delta$ が極限順序数なら、$\delta$ を含む $U\in\mathcal U$ をとる。順序位相の定義により、ある $\xi<\delta$ について
$$
(\xi,\delta]\subset U
$$
となる。$\delta$ は極限順序数なので $\eta:=\xi+1<\delta$ であり、$\delta$ の最小性から $\eta\in S$ である。$[0,\eta]$ の有限被覆に $U$ を加えれば、$[0,\eta]$ は前者が、$(\xi,\delta]$ は $U$ が覆うので $[0,\delta]$ の有限被覆を得る。再び $\delta\in S$ となり矛盾する。
順序数は $0$、後続順序数、極限順序数のいずれかなので、どの場合にも矛盾する。よって $\beta\in S$ であり、$[0,\beta]=\alpha$ は $\mathcal U$ の有限部分被覆を持つ。$\mathcal U$ は任意だったから $\alpha$ はコンパクトである。$\square$
極限順序数そのものは一般にコンパクトとは限らない。たとえば第1非可算順序数 $\omega_1$ は順序位相について可算コンパクトだがコンパクトでない（可算コンパクト空間）。一方、$\omega_1+1$ は後続順序数なので上の定理によりコンパクトである。標準的な別証明は Mun00 §27 を参照。
順序数 $\alpha$ を固定し、$\beta$ に関する超限再帰（thm-ordinal-transfinite-recursion）により和 $\alpha+\beta$、積 $\alpha\cdot\beta$、冪 $\alpha^{\beta}$ を次で定める。$\lambda$ は極限順序数を表す。
- $\alpha+0:=\alpha$、$\alpha+(\beta+1):=(\alpha+\beta)+1$、$\alpha+\lambda:=\sup\{\alpha+\beta\mid\beta<\lambda\}$。
- $\alpha\cdot0:=0$、$\alpha\cdot(\beta+1):=\alpha\cdot\beta+\alpha$、$\alpha\cdot\lambda:=\sup\{\alpha\cdot\beta\mid\beta<\lambda\}$。
- $\alpha^{0}:=1$、$\alpha^{\beta+1}:=\alpha^{\beta}\cdot\alpha$、$\alpha^{\lambda}:=\sup\{\alpha^{\beta}\mid\beta<\lambda\}$。
ここで $\sup$ は prop-ordinal-class の 3 の意味の上限（和集合）である。$\alpha+1$ は def-ordinal-successor-limit の記法と一致する。和と積は整列集合の順序型としても特徴付けられる：$\alpha+\beta$ は「$\alpha$ の後ろに $\beta$ を並べた」整列集合 $(\alpha\times\{0\})\cup(\beta\times\{1\})$（$(\gamma,0)<(\delta,1)$、各成分内は元の順序）の順序型であり、$\alpha\cdot\beta$ は「$\alpha$ を $\beta$ 個並べた」整列集合、すなわち $\beta\times\alpha$ に辞書式順序を入れたものの順序型である（Jec03 Chapter 2、End77 Chapter 8）。
順序数の和と積は可換でない。
- $1+\omega=\omega\neq\omega+1$。まず $n<\omega$ について $1+n=n+1$ が $n$ に関する帰納法で分かる（$1+0=1=0+1$、$1+(n+1)=(1+n)+1=(n+1)+1$）。よって $1+\omega=\sup\{n+1\mid n<\omega\}=\bigcup_{n<\omega}(n+1)=\omega$ である（各 $n+1\subset\omega$ であり、$n\in n+1$ なので $\omega\subset\bigcup(n+1)$）。一方 $\omega+1=\omega\cup\{\omega\}$ は $\omega$ を元に持つが $\omega\notin\omega$ なので $\omega+1\neq\omega$ である。「一つの点の後ろに自然数の列を置く」と全体は自然数の列と同じ形だが、「自然数の列の後ろに一つの点を置く」と最大元ができて形が変わる。
- $2\cdot\omega=\omega\neq\omega\cdot2=\omega+\omega$。$n<\omega$ について $2\cdot n$ は有限順序数で $n\leq2\cdot n$ である（帰納法：$2\cdot0=0$、$2\cdot(n+1)=2\cdot n+2=((2\cdot n)+1)+1$ は有限順序数の後続者の後続者なので有限であり、$n+1\leq(2\cdot n)+1\leq2\cdot(n+1)$）。よって $2\cdot\omega=\sup\{2\cdot n\mid n<\omega\}=\omega$ である。一方 $\omega\cdot2=\omega\cdot1+\omega=\omega+\omega$ であり、$\omega+\omega\geq\omega+1>\omega$ なので $\omega\cdot2\neq\omega$ である。「長さ $2$ の列を $\omega$ 個並べる」と自然数の列と同じ形だが、「自然数の列を $2$ 個並べる」と $\omega$ より長くなる。
和と積は結合的であり、$\alpha<\beta$ ならば $\gamma+\alpha<\gamma+\beta$、$\gamma\geq1$ ならば $\gamma\cdot\alpha<\gamma\cdot\beta$ が成り立つ（左からの狭義単調性）が、右からは $\alpha<\beta$ でも $\alpha+\gamma\leq\beta+\gamma$ しか言えない（Jec03 Chapter 2）。ex-ordinal-order-types で用いた $(a,b)\mapsto\omega\cdot a+b$ が $\mathbb{N}\times\mathbb{N}$ の辞書式順序から $\omega\cdot\omega$ への順序同型であることは、積の順序型による特徴付けと $b\mapsto\omega\cdot a+b$・$a\mapsto\omega\cdot a$ の単調性から従う。
補足
順序数は「並び方」を、基数は「大きさ」を測る。$\omega$ と $\omega+1$ は異なる順序数だが、写像 $\omega+1\to\omega$、$\omega\mapsto0$、$n\mapsto n+1$ は全単射なので、二つの集合の大きさ（濃度）は等しい。すなわち順序数としては $\omega\neq\omega+1$、基数としては $|\omega|=|\omega+1|=\aleph_0$ である。順序数 $\alpha$ で、どの $\beta<\alpha$ とも全単射で結ばれないものを初期順序数といい、選択公理の下では基数は初期順序数として定義される。したがって基数は順序数の特別な場合であり、$\aleph_0=\omega$ である。基数の算術は順序数の算術と別のものであり、たとえば基数としては $\aleph_0+1=\aleph_0$ だが順序数としては $\omega+1\neq\omega$ である。詳細は 基数 が扱う。
順序数の概念は Cantor が整列集合の順序型として導入し、von Neumann が「自分より小さい順序数すべての集合」という集合としての標準的な定義を与えた（vN23、Jec03 Chapter 2）。Mat68 第3章のように、順序数を整列集合の順序同型類（順序型）として抽象的に扱う流儀では、thm-ordinal-representation が両者の橋渡しをする。def-ordinal の条件 2 は「$\in$ が $\alpha$ 上の整列順序である」ことを要求しているが、正則性公理を仮定すれば、任意の集合上で $\in$ は非反射的で無限降下列を持たないので、条件 2 を「$\in$ が $\alpha$ 上の狭義の全順序である」に弱めても同じ概念が得られる（Kun80 Chapter I §7）。本記事の証明は正則性公理を使っていない。
超限帰納法と超限再帰は、可算無限回では終わらない構成を可能にする。Zornの補題や整列可能定理の選択公理からの証明、Borel 集合族（Borel集合）の階層 $\Sigma^0_\alpha,\Pi^0_\alpha$（$\alpha<\omega_1$）、累積階層 $V_\alpha$ による集合全体の構成はその例である。順序数の算術に関しては、任意の順序数 $\alpha\neq0$ が $\alpha=\omega^{\beta_1}\cdot n_1+\cdots+\omega^{\beta_k}\cdot n_k$（$\beta_1>\cdots>\beta_k$、$n_i$ は正の自然数）と一意に表せるというCantor標準形（Jec03 Chapter 2）があり、$\omega^{\varepsilon}=\varepsilon$ を満たす順序数をイプシロン数という。最小の非可算順序数 $\omega_1$ とその共終数の理論は 基数・共終数 が扱う。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
