§E1.16順序数

最終更新

自然数は、個数を数える目盛りであると同時に、対象を並べる順序の目盛りでもある。有限個の対象に番号を付ける操作は、まだ番号を付けていない対象の中から次のものを選ぶことを繰り返して終わる。しかし無限個の対象を並べる場合、自然数を使い切った先を指す番号は自然数の中に存在せず、すべての自然数の後に続く段を自然数だけで書き表すことができない。「順序集合」で定めた整列順序は、どの空でない部分集合にも最小元があるという条件であり、次を選ぶ操作を途中で止まらせない。この操作の目盛りそのものを集合として取り出したものが順序数であり、順序数は集合の元へ超限に番号を与える構成と、濃度を比較する議論の土台になる。本記事は、整列集合と始切片を定義し、属する関係によって整列された推移的集合として順序数を定義して、その基本的な性質と算術を扱う。

1 整列集合と始切片

「順序集合」は、集合の上の狭義全順序と整列順序を定めている。整列順序は§E1.8 命題 5.7により全順序であり、§E1.8 定義 1.6が与える付随する狭義順序は狭義全順序である。本記事は、この狭義順序の側を用いて、整列順序を備えた集合と、その部分のうち順序について前半をなすものに名前を与えるところから始める。

定義 1.1. 集合WW上の狭義全順序<<について、WWの空でないどの部分集合SSも<<に関する最小元をもつとき、<<はWWを整列するといい、対(W,<)(W,<)を整列集合 (well-ordered set) という。ここでttがSSの<<に関する最小元であるとは、t∈St\in Sであって、ttと異なるどのs∈Ss\in Sについてもt<st<sが成り立つことをいう。

(W,<)(W,<)を整列集合とする。WWの部分集合IIが、x∈Ix\in Iとy<xy<xからつねにy∈Iy\in Iを導くとき、IIを(W,<)(W,<)の始切片 (initial segment) という。WW自身と異なる始切片を真の始切片という。a∈Wa\in Wに対して

W<a={x∈W∣x<a}W_{<a}=\{x\in W\mid x<a\}

と書く。

集合WWについて、WW上の整列順序（§E1.8 定義 5.6）に付随する狭義順序（§E1.8 定義 1.6）はWWを整列し、逆にWWを整列する狭義全順序<<について「x<yx<yまたはx=yx=y」で定まる関係はWW上の整列順序である。整列集合は、「順序集合」の整列順序を狭義の形で述べたものにほかならない。

x∈W<ax\in W_{<a}とy<xy<xからy<ay<aが従うのでW<aW_{<a}は始切片である。狭義全順序は非反射的であるからa∉W<aa\notin W_{<a}であり、W<aW_{<a}は真の始切片である。

例 1.2. 自然数全体N≥0\mathbb{N}_{\geq 0}は通常の大小について整列集合であり、a∈N≥0a\in\mathbb{N}_{\geq 0}が定める始切片N<a\mathbb{N}_{<a}はaaより小さい自然数の全体である。N≥0\mathbb{N}_{\geq 0}に属さない元ppを一つ取り、W=N≥0∪{p}W=\mathbb{N}_{\geq 0}\cup\{p\}に、N≥0\mathbb{N}_{\geq 0}の上では通常の大小を用い、どのn∈N≥0n\in\mathbb{N}_{\geq 0}についてもn<pn<pと定めた関係を入れる。WWの空でない部分集合SSについて、S∩N≥0S\cap\mathbb{N}_{\geq 0}が空でなければその最小元がSSの最小元であり、空ならばS={p}S=\{p\}で最小元はppである。よってWWは整列集合であり、ppが定める始切片はN≥0\mathbb{N}_{\geq 0}である。このWWは、自然数をすべて並べ終えた後にもう一段を置いた並べ方を表す。

補題 1.3. 整列集合(W,<)(W,<)の真の始切片IIに対して、I=W<aI=W_{<a}を満たすa∈Wa\in Wがただ一つ存在する。

証明.W∖IW\setminus IはWWの空でない部分集合であるから、最小元aaをもつ。x<ax<aとすると、aaの最小性によりx∉W∖Ix\notin W\setminus Iであるからx∈Ix\in Iである。逆にx∈Ix\in Iとする。x=ax=aならばa∈Ia\in Iとなってa∈W∖Ia\in W\setminus Iに反する。a<xa<xならば、IIが始切片であることからa∈Ia\in Iとなり、同じく矛盾する。よってx<ax<aである。以上よりI=W<aI=W_{<a}である。

W<a=W<bW_{<a}=W_{<b}かつa≠ba\neq bとすると、a<ba<bまたはb<ab<aである。a<ba<bの場合、a∈W<b=W<aa\in W_{<b}=W_{<a}からa<aa<aとなって非反射性に反する。b<ab<aの場合も同様である。よってaaはただ一つである。▨

補題 1.4.(W,<)(W,<)と(W′,<′)(W',<')を整列集合とする。次が成り立つ。

  1. 写像f:W→Wf:W\to Wがx<yx<yからつねにf(x)<f(y)f(x)<f(y)を導くならば、すべてのx∈Wx\in Wについてx≤f(x)x\le f(x)である。
  2. WWは自身のどの真の始切片とも順序同型でない。
  3. WWからW′W'への順序同型は、存在すればただ一つである。

証明. 写像f:W→Wf:W\to Wがx<yx<yからつねにf(x)<f(y)f(x)<f(y)を導くとし、S={x∈W∣f(x)<x}S=\{x\in W\mid f(x)<x\}とおく。S≠∅S\neq\emptysetと仮定すると、SSは最小元x0x_0をもつ。f(x0)<x0f(x_0)<x_0であるから、ffの仮定によりf(f(x0))<f(x0)f(f(x_0))<f(x_0)であり、f(x0)∈Sf(x_0)\in Sである。しかしf(x0)<x0f(x_0)<x_0はx0x_0がSSの最小元であることに反する。よってS=∅S=\emptysetであり、<<が全順序であることから、すべてのxxについてx≤f(x)x\le f(x)である。これで(1)が示された。

IIをWWの真の始切片、g:W→Ig:W\to Iを順序同型とする。補題 1.3によりI=W<aI=W_{<a}を満たすa∈Wa\in Wがある。ggをWWからWWへの写像とみなすとx<yx<yからg(x)<g(y)g(x)<g(y)が従うので、(1)によりa≤g(a)a\le g(a)である。一方g(a)∈W<ag(a)\in W_{<a}であるからg(a)<ag(a)<aであり、矛盾する。これで(2)が示された。

f,g:W→W′f,g:W\to W'を順序同型とする。h=g−1∘fh=g^{-1}\circ fはWWからWWへの順序同型であり、hhとh−1h^{-1}はいずれも順序を保つ。(1)により、すべてのx∈Wx\in Wについてx≤h(x)x\le h(x)かつx≤h−1(x)x\le h^{-1}(x)である。後者のxxをh(x)h(x)で置き換えるとh(x)≤h−1(h(x))=xh(x)\le h^{-1}(h(x))=xとなるので、h(x)=xh(x)=xである。よってhhは恒等写像であり、f=gf=gである。▨

例 1.5.補題 1.4の三つの主張は、整列性を落とすといずれも成り立たない。整数全体Z\mathbb{Z}は通常の大小について狭義全順序集合であるが、Z\mathbb{Z}自身が最小元をもたないので整列集合ではない。W={n∈Z∣n≤0}W=\{n\in\mathbb{Z}\mid n\le0\}とすると、WWも最小元をもたない狭義全順序集合である。写像f:W→Wf:W\to Wをf(n)=n−1f(n)=n-1で定めると、ffはm<nm<nからf(m)<f(n)f(m)<f(n)を導くが、すべてのnnについてf(n)<nf(n)<nであり、補題 1.4 (1)の結論は成り立たない。さらにffはWWから真の始切片W<0={n∈Z∣n≤−1}W_{<0}=\{n\in\mathbb{Z}\mid n\le-1\}への全単射であり、ffとその逆写像n↦n+1n\mapsto n+1はともに順序を保つので、WWは自身の真の始切片と順序同型である。またZ\mathbb{Z}については、恒等写像とn↦n+1n\mapsto n+1がともにZ\mathbb{Z}からZ\mathbb{Z}への順序同型であり、相異なる順序同型が二つ存在する。

補題 1.6.(W,<)(W,<)と(W′,<′)(W',<')を整列集合、g:W→W′g:W\to W'を順序同型とする。各a∈Wa\in Wについて、ggによるW<aW_{<a}の像は{y∈W′∣y<′g(a)}\{y\in W'\mid y<'g(a)\}であり、ggのW<aW_{<a}への制限はこの集合への順序同型である。

証明.x<ax<aとするとg(x)<′g(a)g(x)<'g(a)であるから、W<aW_{<a}の像は{y∈W′∣y<′g(a)}\{y\in W'\mid y<'g(a)\}に含まれる。逆にy<′g(a)y<'g(a)とする。ggは全射であるからy=g(x)y=g(x)を満たすx∈Wx\in Wがある。a≤xa\le xとするとg(a)≤′g(x)=yg(a)\le'g(x)=yとなってy<′g(a)y<'g(a)に反するので、x<ax<aである。よって像はこの集合に一致する。制限は単射であって順序を保ち、その逆写像もg−1g^{-1}の制限として順序を保つ。▨

2 順序数

定義 2.1. 集合xxが推移的集合 (transitive set) であるとは、xxのどの元yyについてもy⊆xy\subseteq xが成り立つことをいう。

推移的集合α\alphaが次の四条件を満たすとき、すなわちα\alphaの二元β\beta、γ\gammaをβ∈γ\beta\in\gammaによって比べる関係がα\alphaを整列するとき、α\alphaを順序数 (ordinal) という。

  1. α\alphaのどの元β\betaについてもβ∈β\beta\in\betaは成り立たない。
  2. α\alphaの元β\beta、γ\gamma、δ\deltaについて、β∈γ\beta\in\gammaとγ∈δ\gamma\in\deltaからβ∈δ\beta\in\deltaが従う。
  3. α\alphaの相異なる二元β\beta、γ\gammaについて、β∈γ\beta\in\gammaとγ∈β\gamma\in\betaのちょうど一方が成り立つ。
  4. α\alphaの空でないどの部分集合SSも∈\inに関する最小元をもつ。ここでttがSSの∈\inに関する最小元であるとは、t∈St\in Sであって、ttと異なるどのs∈Ss\in Sについてもt∈st\in sが成り立つことをいう。

順序数α\alpha、β\betaについて、α<β\alpha<\betaをα∈β\alpha\in\betaの意味で用い、α≤β\alpha\le\betaを「α<β\alpha<\betaまたはα=β\alpha=\beta」の意味で用いる。

空集合を00と書き、以下

0=∅,1={0},2={0,1},3={0,1,2}0=\varnothing,\qquad 1=\{0\},\qquad 2=\{0,1\},\qquad 3=\{0,1,2\}

と、それより小さいものをすべて集めた集合として自然数を表す。この表し方による自然数を von Neumann 自然数という。

例 2.2.0=∅0=\varnothingは元をもたないので推移的であり、空でない部分集合をもたないので、∈\inによる比較は00を整列する。よって00は順序数である。1={0}1=\{0\}の元は00だけであり0=∅⊆10=\varnothing\subseteq1であるから11は推移的である。11は相異なる二元をもたず、空でない部分集合は{0}\{0\}だけでその最小元は00であるから、11は順序数である。2={0,1}2=\{0,1\}については0⊆20\subseteq2と1={0}⊆21=\{0\}\subseteq2から推移性が従い、0∈10\in1により0<10<1であって、空でない部分集合{0}\{0\}、{1}\{1\}、{0,1}\{0,1\}の最小元はそれぞれ00、11、00である。よって22は順序数である。3={0,1,2}3=\{0,1,2\}についても、0⊆30\subseteq3、1⊆31\subseteq3、2⊆32\subseteq3から推移性が従い、0<1<20<1<2と各部分集合の最小元を同じように確かめることができる。

命題 2.3.α\alphaを順序数とする。次が成り立つ。

  1. α\alphaのどの元も順序数である。
  2. α∉α\alpha\notin\alphaである。
  3. β∈α\beta\in\alphaのときβ={γ∈α∣γ<β}\beta=\{\gamma\in\alpha\mid\gamma<\beta\}である。すなわちα\alphaの元はα\alphaの真の始切片にほかならず、α\alphaはα\alphaより小さい順序数の全体からなる集合である。

証明.β∈α\beta\in\alphaとする。α\alphaは推移的であるからβ⊆α\beta\subseteq\alphaであり、α\alphaを整列する関係を部分集合へ制限したものはその部分集合を整列する。実際、定義 2.1 条件 (a)、定義 2.1 条件 (b)および定義 2.1 条件 (c)は部分集合の元についても成り立ち、部分集合の空でない部分集合はα\alphaの空でない部分集合であるから定義 2.1 条件 (d)により最小元をもつ。β\betaが推移的であることを示す。γ∈β\gamma\in\betaかつδ∈γ\delta\in\gammaとすると、β⊆α\beta\subseteq\alphaによりγ∈α\gamma\in\alphaであり、α\alphaの推移性によりγ⊆α\gamma\subseteq\alphaであるからδ∈α\delta\in\alphaである。δ\delta、γ\gamma、β\betaはいずれもα\alphaの元でありδ∈γ\delta\in\gammaかつγ∈β\gamma\in\betaであるから、定義 2.1 条件 (b)によりδ∈β\delta\in\betaである。よってγ⊆β\gamma\subseteq\betaであり、β\betaは推移的集合である。ゆえにβ\betaは順序数であり、(1)が示された。

α∈α\alpha\in\alphaと仮定する。するとα\alphaはα\alphaの元であり、定義 2.1 条件 (a)によりα∈α\alpha\in\alphaは成り立たない。これは仮定に反する。よって(2)が成り立つ。

β∈α\beta\in\alphaとする。α\alphaの推移性によりβ⊆α\beta\subseteq\alphaであるから

{γ∈α∣γ<β}={γ∈α∣γ∈β}=β∩α=β\{\gamma\in\alpha\mid\gamma<\beta\}=\{\gamma\in\alpha\mid\gamma\in\beta\}=\beta\cap\alpha=\beta

である。(1)によりα\alphaの元はすべて順序数であり、γ∈α\gamma\in\alphaとγ<α\gamma<\alphaは同じ意味であるから、α\alphaはα\alphaより小さい順序数の全体からなる集合である。▨

補題 2.4. 順序数α\alpha、β\betaがα⊆β\alpha\subseteq\betaかつα≠β\alpha\neq\betaを満たすならば、α∈β\alpha\in\betaである。

証明.β∖α\beta\setminus\alphaはβ\betaの空でない部分集合であるから、定義 2.1 条件 (d)により∈\inに関する最小元γ\gammaをもつ。γ⊆α\gamma\subseteq\alphaを示す。δ∈γ\delta\in\gammaとすると、γ∈β\gamma\in\betaとβ\betaの推移性によりδ∈β\delta\in\betaであり、γ\gammaの最小性によりδ∉β∖α\delta\notin\beta\setminus\alphaであるからδ∈α\delta\in\alphaである。次にα⊆γ\alpha\subseteq\gammaを示す。δ∈α\delta\in\alphaとするとδ∈β\delta\in\betaであり、δ\deltaとγ\gammaはともにβ\betaの元であるから、定義 2.1 条件 (c)によりδ∈γ\delta\in\gamma、δ=γ\delta=\gamma、γ∈δ\gamma\in\deltaのいずれかが成り立つ。δ=γ\delta=\gammaならばγ∈α\gamma\in\alphaとなってγ∈β∖α\gamma\in\beta\setminus\alphaに反する。γ∈δ\gamma\in\deltaならばδ∈α\delta\in\alphaとα\alphaの推移性によりγ∈α\gamma\in\alphaとなり、同じく矛盾する。よってδ∈γ\delta\in\gammaである。以上よりα=γ∈β\alpha=\gamma\in\betaである。▨

命題 2.5. 次が成り立つ。

  1. 順序数α\alpha、β\betaについて、α⊆β\alpha\subseteq\betaとα≤β\alpha\le\betaは同値である。
  2. 順序数α\alpha、β\betaについて、α<β\alpha<\beta、α=β\alpha=\beta、β<α\beta<\alphaのちょうど一つが成り立つ。
  3. 順序数からなる集合は、∈\inによる比較について整列される。

証明.α≤β\alpha\le\betaとする。α=β\alpha=\betaならばα⊆β\alpha\subseteq\betaであり、α∈β\alpha\in\betaならばβ\betaの推移性によりα⊆β\alpha\subseteq\betaである。逆にα⊆β\alpha\subseteq\betaとすると、α=β\alpha=\betaであるか、補題 2.4によりα∈β\alpha\in\betaであるから、α≤β\alpha\le\betaである。これで(1)が示された。

γ=α∩β\gamma=\alpha\cap\betaとおく。δ∈γ\delta\in\gammaとするとδ∈α\delta\in\alphaかつδ∈β\delta\in\betaであり、α\alphaとβ\betaの推移性によりδ⊆α\delta\subseteq\alphaかつδ⊆β\delta\subseteq\betaであるからδ⊆γ\delta\subseteq\gammaである。よってγ\gammaは推移的集合であり、α\alphaの部分集合として∈\inで整列されるから順序数である。γ≠α\gamma\neq\alphaかつγ≠β\gamma\neq\betaと仮定すると、γ⊆α\gamma\subseteq\alphaとγ⊆β\gamma\subseteq\betaに補題 2.4を適用してγ∈α\gamma\in\alphaかつγ∈β\gamma\in\betaを得るので、γ∈α∩β=γ\gamma\in\alpha\cap\beta=\gammaとなり命題 2.3 (2)に反する。よってγ=α\gamma=\alphaまたはγ=β\gamma=\betaであり、α⊆β\alpha\subseteq\betaまたはβ⊆α\beta\subseteq\alphaが成り立つから、(1)によりα≤β\alpha\le\betaまたはβ≤α\beta\le\alphaである。二つ以上が同時に成り立たないことを見る。α<β\alpha<\betaかつα=β\alpha=\betaならばα∈α\alpha\in\alphaとなって命題 2.3 (2)に反する。α<β\alpha<\betaかつβ<α\beta<\alphaならば、α∈β\alpha\in\betaとβ\betaの推移性からα⊆β\alpha\subseteq\betaが、β∈α\beta\in\alphaとα\alphaの推移性からβ⊆α\beta\subseteq\alphaが従うのでα=β\alpha=\betaであり、ふたたびα∈α\alpha\in\alphaとなって矛盾する。これで(2)が示された。

AAを順序数からなる集合とする。命題 2.3 (2)により∈\inはAA上で非反射的であり、順序数の推移性によりβ∈γ\beta\in\gammaとγ∈δ\gamma\in\deltaからβ∈δ\beta\in\deltaが従い、(2)により相異なる二元は比較可能である。SSをAAの空でない部分集合とし、α∈S\alpha\in Sを取る。α∩S=∅\alpha\cap S=\emptysetならば、β∈S\beta\in Sについてβ∈α\beta\in\alphaは成り立たないので(2)によりα≤β\alpha\le\betaであり、α\alphaがSSの最小元である。α∩S≠∅\alpha\cap S\neq\emptysetならば、α∩S\alpha\cap Sは順序数α\alphaの空でない部分集合であるから、定義 2.1 条件 (d)により最小元γ\gammaをもつ。β∈S\beta\in Sについてβ∈γ\beta\in\gammaと仮定すると、γ∈α\gamma\in\alphaとα\alphaの推移性によりβ∈α\beta\in\alphaであるからβ∈α∩S\beta\in\alpha\cap Sとなり、γ\gammaの最小性に反する。よってγ≤β\gamma\le\betaであり、γ\gammaがSSの最小元である。これで(3)が示された。▨

命題 2.6. 順序数の全体からなる集合は存在しない。

証明. そのような集合Ω\Omegaが存在すると仮定する。命題 2.3 (1)によりΩ\Omegaの元の元はふたたび順序数であるからΩ\Omegaは推移的集合であり、命題 2.5 (3)により∈\inはΩ\Omegaを整列する。よってΩ\Omegaは順序数であり、Ω∈Ω\Omega\in\Omegaとなって命題 2.3 (2)に反する。▨

注意 2.7.命題 2.6は Burali-Forti のパラドックスとして知られる。本記事は、順序数の全体のように集合でない集まりを扱う形式的な語を導入せず、主張をつねに集合の言語の内側で述べる。集合でない集まりを対象として扱う枠組みは「公理的集合論」が与える。

3 順序型

定理 3.1. どの整列集合(W,<)(W,<)に対しても、WWと順序同型な順序数がただ一つ存在する。

証明. 一意性を示す。α\alphaとβ\betaをWWと順序同型な順序数とし、α≠β\alpha\neq\betaと仮定する。命題 2.5 (2)により、α<β\alpha<\betaまたはβ<α\beta<\alphaであり、番号を付け替えてα<β\alpha<\betaとしてよい。命題 2.3 (3)によりα\alphaはβ\betaの真の始切片であり、β\betaはWWと、WWはα\alphaと順序同型であるから、β\betaは自身の真の始切片α\alphaと順序同型である。これは補題 1.4 (2)に反する。よってα=β\alpha=\betaである。

存在を示す。WWの部分集合

D={a∈W∣W<a と順序同型な順序数が存在する}D=\{a\in W\mid W_{<a}\ \text{と順序同型な順序数が存在する}\}

を§E1.13 定義 2.1により取る。a∈Da\in Dについて、W<aW_{<a}と順序同型な順序数は一意性の部分によりただ一つであるから、これをαa\alpha_aと書く。

a∈Da\in Dとし、g:W<a→αag:W_{<a}\to\alpha_aを順序同型とする。c<ac<aとすると、W<aW_{<a}においてccが定める始切片はW<cW_{<c}であるから、補題 1.6によりggの制限はW<cW_{<c}から(αa)<g(c)(\alpha_a)_{<g(c)}への順序同型であり、命題 2.3 (3)により(αa)<g(c)=g(c)(\alpha_a)_{<g(c)}=g(c)である。g(c)g(c)は命題 2.3 (1)により順序数であるからc∈Dc\in Dであり、αc=g(c)\alpha_c=g(c)である。とくにDDはWWの始切片であり、c<ac<aのときαc∈αa\alpha_c\in\alpha_aである。

対応a↦αaa\mapsto\alpha_aはDDの各元に対して順序数をちょうど一つ定めるから、§E1.13 定義 5.1によりその像

A={αa∣a∈D}A=\{\alpha_a\mid a\in D\}

は集合である。AAが推移的であることを見る。γ∈αa\gamma\in\alpha_aとすると、g:W<a→αag:W_{<a}\to\alpha_aを順序同型としてγ=g(c)\gamma=g(c)を満たすc∈W<ac\in W_{<a}があり、前段によりγ=αc\gamma=\alpha_cかつc∈Dc\in Dであるからγ∈A\gamma\in Aである。AAは順序数からなる集合であるから命題 2.5 (3)により∈\inで整列され、よってAAは順序数である。

写像f:D→Af:D\to Aをf(a)=αaf(a)=\alpha_aで定める。ffは定義により全射である。c<ac<aならば前段によりf(c)<f(a)f(c)<f(a)であり、c≠ac\neq aならばc<ac<aかa<ca<cであるからf(c)≠f(a)f(c)\neq f(a)であって、ffは単射である。またf(c)<f(a)f(c)<f(a)のとき、c<ac<aでないとすればa≤ca\le cでありf(a)≤f(c)f(a)\le f(c)となって命題 2.5 (2)に反するからc<ac<aである。よってffは順序同型である。

D≠WD\neq Wと仮定する。DDはWWの真の始切片であるから、補題 1.3によりD=W<bD=W_{<b}を満たすb∈Wb\in Wがある。するとW<bW_{<b}は順序数AAと順序同型であるからb∈D=W<bb\in D=W_{<b}となり、b<bb<bとなって矛盾する。よってD=WD=Wであり、WWは順序数AAと順序同型である。▨

定義 3.2.定理 3.1により、整列集合(W,<)(W,<)と順序同型な順序数はただ一つである。これを(W,<)(W,<)の順序型 (order type) といい、ot⁡(W,<)\operatorname{ot}(W,<)と書く。順序<<が文脈から定まるときはot⁡(W)\operatorname{ot}(W)とも書く。

系 3.3.(W,<)(W,<)を整列集合、g:W→ot⁡(W)g:W\to\operatorname{ot}(W)を順序同型とする。各a∈Wa\in Wについてg(a)=ot⁡(W<a)g(a)=\operatorname{ot}(W_{<a})であり、

ot⁡(W)={ot⁡(W<a)∣a∈W}\operatorname{ot}(W)=\{\operatorname{ot}(W_{<a})\mid a\in W\}

が成り立つ。

証明.α=ot⁡(W)\alpha=\operatorname{ot}(W)とおく。補題 1.6によりggの制限はW<aW_{<a}からα<g(a)\alpha_{<g(a)}への順序同型であり、命題 2.3 (3)によりα<g(a)=g(a)\alpha_{<g(a)}=g(a)である。g(a)g(a)は命題 2.3 (1)により順序数であるから、定理 3.1の一意性によりg(a)=ot⁡(W<a)g(a)=\operatorname{ot}(W_{<a})である。ggはWWからα\alphaへの全単射であるから、α\alphaの元の全体はg(a)g(a)の全体、すなわちot⁡(W<a)\operatorname{ot}(W_{<a})の全体である。▨

注意 3.4.定理 3.1の証明が置換公理スキーマ（§E1.13 定義 5.1）を用いるのは、DDの各元aaに対して定まる順序数αa\alpha_aを一つの集合AAに集める箇所だけである。対応a↦αaa\mapsto\alpha_aはこの段階では集合として与えられておらず、その像が集合であることを与える原理が置換公理スキーマである。

例 3.5. 整列集合であるという仮定を狭義全順序集合に弱めると、定理 3.1は成り立たない。Z\mathbb{Z}は通常の大小について狭義全順序集合である。順序数はいずれも整列集合であり、順序同型は空でない部分集合の最小元を最小元へ移すので、順序数と順序同型な狭義全順序集合は整列集合である。Z\mathbb{Z}は最小元をもたないので整列集合ではなく、したがってどの順序数とも順序同型でない。有理数全体Q\mathbb{Q}についても同様である。

例 3.6.x={1}={{∅}}x=\{1\}=\{\{\varnothing\}\}とする。xxの元は11だけであるから、∈\inによる比較はxxを整列し、xxは順序数11と順序同型な整列集合である。しかし0∈10\in1かつ0∉x0\notin xであるから1⊆x1\subseteq xは成り立たず、xxは推移的集合ではないので順序数ではない。順序数の定義から推移性を落とすと、xxと11のように順序同型で相異なる集合がともに順序数となり、定理 3.1の一意性が失われる。推移性は、順序型を集合として一つに選び出すための条件である。

4 後続順序数と極限順序数

定義 4.1. 順序数α\alphaに対して

α+1=α∪{α}\alpha+1=\alpha\cup\{\alpha\}

と定め、これをα\alphaの後続 (successor) という。順序数β\betaが、ある順序数α\alphaについてβ=α+1\beta=\alpha+1と表されるとき、β\betaを後続順序数 (successor ordinal) という。00でも後続順序数でもない順序数を極限順序数 (limit ordinal) という。

命題 4.2.α\alphaを順序数とする。次が成り立つ。

  1. α+1\alpha+1は順序数である。
  2. α<α+1\alpha<\alpha+1であり、順序数β\betaがα<β\alpha<\betaを満たすならばα+1≤β\alpha+1\le\betaである。すなわちα+1\alpha+1はα\alphaより真に大きい順序数のうち最小である。
  3. 順序数β\betaについて、β<α+1\beta<\alpha+1とβ≤α\beta\le\alphaは同値である。したがってα<β<α+1\alpha<\beta<\alpha+1を満たす順序数β\betaは存在しない。
  4. α\alphaは、00、後続順序数、極限順序数のうちちょうど一つに属する。

証明.x∈α+1x\in\alpha+1とするとx∈αx\in\alphaまたはx=αx=\alphaである。前者ではα\alphaの推移性によりx⊆α⊆α+1x\subseteq\alpha\subseteq\alpha+1であり、後者ではx=α⊆α+1x=\alpha\subseteq\alpha+1である。よってα+1\alpha+1は推移的集合である。α+1\alpha+1の元はα\alphaの元とα\alpha自身であり、命題 2.3 (1)によりいずれも順序数であるから、命題 2.5 (3)により∈\inはα+1\alpha+1を整列する。ゆえにα+1\alpha+1は順序数であり、(1)が示された。

α∈α∪{α}\alpha\in\alpha\cup\{\alpha\}であるからα<α+1\alpha<\alpha+1である。順序数β\betaがα<β\alpha<\betaを満たすとすると、α∈β\alpha\in\betaでありβ\betaの推移性によりα⊆β\alpha\subseteq\betaであるからα∪{α}⊆β\alpha\cup\{\alpha\}\subseteq\betaである。命題 2.5 (1)によりα+1≤β\alpha+1\le\betaである。これで(2)が示された。

β≤α\beta\le\alphaとする。命題 2.5 (1)によりβ⊆α⊆α+1\beta\subseteq\alpha\subseteq\alpha+1である。β=α+1\beta=\alpha+1とするとα∈α+1=β⊆α\alpha\in\alpha+1=\beta\subseteq\alphaとなって命題 2.3 (2)に反するのでβ≠α+1\beta\neq\alpha+1であり、ふたたび命題 2.5 (1)によりβ<α+1\beta<\alpha+1である。逆にβ<α+1\beta<\alpha+1とするとβ∈α∪{α}\beta\in\alpha\cup\{\alpha\}であるからβ∈α\beta\in\alphaまたはβ=α\beta=\alphaであり、β≤α\beta\le\alphaである。α<β<α+1\alpha<\beta<\alpha+1を満たすβ\betaがあるとすると、いま示したことによりβ≤α\beta\le\alphaとなり命題 2.5 (2)に反する。これで(3)が示された。

α\alphaが00でも後続順序数でもなければ、極限順序数の定義によりα\alphaは極限順序数である。よって三つの場合の少なくとも一つが成り立つ。極限順序数は00でも後続順序数でもないから、α\alphaが極限順序数であることは他の二つのいずれとも同時には成り立たない。α=0\alpha=0であって、順序数β\betaについてα=β+1\alpha=\beta+1と表されると仮定すると、β∈β∪{β}=α=∅\beta\in\beta\cup\{\beta\}=\alpha=\varnothingとなって矛盾する。よってα\alphaが00であることと後続順序数であることも同時には成り立たない。これで(4)が示された。▨

系 4.3.λ\lambdaを極限順序数とする。順序数β\betaがβ<λ\beta<\lambdaを満たすならば、β+1<λ\beta+1<\lambdaである。

証明.β<λ\beta<\lambdaとすると命題 4.2 (2)によりβ+1≤λ\beta+1\le\lambdaである。λ\lambdaは極限順序数であるから後続順序数ではなく、λ≠β+1\lambda\neq\beta+1である。よってβ+1<λ\beta+1<\lambdaである。▨

補題 4.4.AAを順序数からなる集合とする。和集合⋃A\bigcup Aについて次が成り立つ。

  1. 各α∈A\alpha\in Aについてα≤⋃A\alpha\le\bigcup Aである。
  2. 順序数δ\deltaが各α∈A\alpha\in Aについてα≤δ\alpha\le\deltaを満たすならば、⋃A≤δ\bigcup A\le\deltaである。
  3. 順序数η\etaがη<⋃A\eta<\bigcup Aを満たすならば、η<α\eta<\alphaを満たすα∈A\alpha\in Aが存在する。
  4. ⋃A\bigcup Aは順序数である。

証明.⋃A\bigcup Aは§E1.13 定義 3.1により集合である。x∈⋃Ax\in\bigcup Aとするとx∈αx\in\alphaを満たすα∈A\alpha\in Aがあり、xxは命題 2.3 (1)により順序数であって、α\alphaの推移性によりx⊆α⊆⋃Ax\subseteq\alpha\subseteq\bigcup Aである。よって⋃A\bigcup Aは順序数からなる推移的集合であり、命題 2.5 (3)により∈\inで整列されるから順序数である。これで(4)が示された。

α∈A\alpha\in Aについてα⊆⋃A\alpha\subseteq\bigcup Aであるから、命題 2.5 (1)によりα≤⋃A\alpha\le\bigcup Aであり、(1)が成り立つ。

順序数δ\deltaが各α∈A\alpha\in Aについてα≤δ\alpha\le\deltaを満たすとする。命題 2.5 (1)によりα⊆δ\alpha\subseteq\deltaであるから⋃A⊆δ\bigcup A\subseteq\deltaであり、ふたたび命題 2.5 (1)により⋃A≤δ\bigcup A\le\deltaである。これで(2)が示された。

η<⋃A\eta<\bigcup Aとするとη∈⋃A\eta\in\bigcup Aであるから、η∈α\eta\in\alphaを満たすα∈A\alpha\in Aが存在し、η<α\eta<\alphaである。これで(3)が示された。▨

順序数からなる集合AAについて、(1)と(2)により、⋃A\bigcup AはAAの上界のうち最小のものである。この最小上界をsup⁡A\sup Aと書く。したがって

sup⁡A=⋃A\sup A=\bigcup A

である。

命題 4.5. 順序数α\alphaについて次が成り立つ。

  1. α=β+1\alpha=\beta+1と表されるならば⋃α=β\bigcup\alpha=\betaである。
  2. α\alphaが00または極限順序数ならば⋃α=α\bigcup\alpha=\alpha、すなわちα=sup⁡{β∣β<α}\alpha=\sup\{\beta\mid\beta<\alpha\}である。

証明.α=β+1=β∪{β}\alpha=\beta+1=\beta\cup\{\beta\}とすると

⋃α=(⋃β)∪β=β\bigcup\alpha=\Bigl(\bigcup\beta\Bigr)\cup\beta=\beta

である。最後の等号は、β\betaの推移性により⋃β⊆β\bigcup\beta\subseteq\betaであることによる。これで(1)が示された。

α\alphaは推移的であるから⋃α⊆α\bigcup\alpha\subseteq\alphaである。α=0\alpha=0のときは両辺が空集合であり、等号が成り立つ。α\alphaを極限順序数とし、β∈α\beta\in\alphaとする。系 4.3によりβ+1<α\beta+1<\alphaであり、β∈β+1\beta\in\beta+1であるからβ∈⋃α\beta\in\bigcup\alphaである。よってα⊆⋃α\alpha\subseteq\bigcup\alphaであり、⋃α=α\bigcup\alpha=\alphaである。sup⁡\supの定め方により⋃α=sup⁡α\bigcup\alpha=\sup\alphaであり、命題 2.3 (3)によりα\alphaはα\alphaより小さい順序数の全体であるから、α=sup⁡{β∣β<α}\alpha=\sup\{\beta\mid\beta<\alpha\}である。これで(2)が示された。▨

定義 4.6. 順序数nnについて、nnとnnのどの元も00であるか後続順序数であるとき、nnを有限順序数 (finite ordinal) という。

補題 4.7. 次が成り立つ。

  1. 有限順序数の元はふたたび有限順序数である。
  2. 有限順序数nnについて、n+1n+1はふたたび有限順序数である。
  3. 集合XXが00を元にもち、XXのどの元xxについてもx∪{x}x\cup\{x\}を元にもつならば、XXは有限順序数をすべて元にもつ。

証明.nnを有限順序数、mmをnnの元とする。mmは命題 2.3 (1)により順序数であり、mmの元はnnの推移性によりnnの元であるから00であるか後続順序数であり、mm自身もnnの元であるから00であるか後続順序数である。よってmmは有限順序数であり、(1)が示された。

nnを有限順序数とする。命題 4.2 (1)によりn+1n+1は順序数である。n+1n+1の元はnnとnnの元であり、どれも00であるか後続順序数である。n+1n+1自身は後続順序数であるから、n+1n+1は有限順序数である。これで(2)が示された。

XXを00を元にもち、どの元xxについてもx∪{x}x\cup\{x\}を元にもつ集合とする。有限順序数nnでn∉Xn\notin Xを満たすものがあると仮定し、T={m∈n+1∣m∉X}T=\{m\in n+1\mid m\notin X\}とおく。n∈n+1n\in n+1であるからTTは順序数n+1n+1（命題 4.2 (1)）の空でない部分集合であり、定義 2.1 条件 (d)により最小元mmをもつ。m∈n+1m\in n+1であるから命題 4.2 (3)によりm≤nm\le nであり、m=nm=nならば仮定により、m<nm<nならば(1)により、いずれにせよmmは有限順序数である。m=0=∅m=0=\varnothingならばm∈Xm\in Xとなってm∈Tm\in Tに反するのでm≠0m\neq0であり、有限順序数の定義によりmmは後続順序数であってm=k+1m=k+1と表される。k∈mk\in mかつm≤nm\le nであるからk∈n+1k\in n+1であり、k<mk<mとmmの最小性によりk∉Tk\notin T、すなわちk∈Xk\in Xである。XXの仮定によりm=k∪{k}∈Xm=k\cup\{k\}\in Xとなり、m∈Tm\in Tに反する。よって有限順序数はすべてXXに属し、(3)が示された。▨

命題 4.8. 有限順序数の全体は集合である。これをω\omegaと書くと、次が成り立つ。

  1. ω\omegaは極限順序数である。
  2. どの極限順序数λ\lambdaについてもω≤λ\omega\le\lambdaである。
  3. 順序数β\betaについて、β<ω\beta<\omegaと「β\betaは有限順序数である」は同値である。

証明. 「集合の存在原理」の無限公理により、∅\varnothingを元にもち、xxを元にもてばx∪{x}x\cup\{x\}も元にもつ集合IIが存在する。補題 4.7 (3)により有限順序数はすべてIIに属する。ゆえに

ω={n∈I∣n は有限順序数である}\omega=\{n\in I\mid n\ \text{は有限順序数である}\}

は§E1.13 定義 2.1により集合であり、有限順序数の全体である。

補題 4.7 (1)によりω\omegaの元の元はふたたび有限順序数であるからω\omegaは推移的集合であり、順序数からなる集合として命題 2.5 (3)により∈\inで整列されるので、ω\omegaは順序数である。00は有限順序数であるから0∈ω0\in\omegaであり、ω≠0\omega\neq0である。ω=β+1\omega=\beta+1と表されると仮定するとβ∈ω\beta\in\omegaであるからβ\betaは有限順序数であり、補題 4.7 (2)によりβ+1\beta+1も有限順序数である。するとω=β+1∈ω\omega=\beta+1\in\omegaとなり命題 2.3 (2)に反する。よってω\omegaは00でも後続順序数でもなく、(1)が成り立つ。

λ\lambdaを極限順序数とする。0⊆λ0\subseteq\lambdaであるから命題 2.5 (1)により0≤λ0\le\lambdaであり、λ≠0\lambda\neq0であるから0<λ0<\lambda、すなわち0∈λ0\in\lambdaである。β∈λ\beta\in\lambdaとすると、β\betaは命題 2.3 (1)により順序数であり、系 4.3によりβ+1=β∪{β}∈λ\beta+1=\beta\cup\{\beta\}\in\lambdaである。よって補題 4.7 (3)により有限順序数はすべてλ\lambdaに属し、ω⊆λ\omega\subseteq\lambdaである。命題 2.5 (1)により(2)が成り立つ。

ω\omegaは有限順序数の全体であり、β<ω\beta<\omegaとβ∈ω\beta\in\omegaは同じ意味であるから、(3)が成り立つ。▨

命題 4.9.§E1.14 命題 1.2が与える最小の帰納的集合N≥0\mathbb N_{\geq 0}は、命題 4.8が有限順序数全体として与えるω\omegaに等しい。この同一視のもとで、各n∈ωn\in\omegaについて

S(n)=n+1=n∪{n}S(n)=n+1=n\cup\{n\}

が成り立つ。

証明.N≥0\mathbb N_{\geq 0}は00を元にもち、各n∈N≥0n\in\mathbb N_{\geq 0}についてS(n)=n∪{n}S(n)=n\cup\{n\}を元にもつ。したがって補題 4.7 (3)により、有限順序数はすべてN≥0\mathbb N_{\geq 0}に属する。よってω⊆N≥0\omega\subseteq\mathbb N_{\geq 0}である。

X={n∈N≥0∣n は有限順序数である}X=\{n\in\mathbb N_{\geq 0}\mid n\text{ は有限順序数である}\}とおく。0∈X0\in Xである。n∈Xn\in Xとすると、補題 4.7 (2)によりn+1=n∪{n}n+1=n\cup\{n\}は有限順序数であり、N≥0\mathbb N_{\geq 0}の帰納性によりS(n)=n∪{n}∈N≥0S(n)=n\cup\{n\}\in\mathbb N_{\geq 0}である。したがってS(n)=n+1∈XS(n)=n+1\in Xであり、XXは帰納的集合である。§E1.14 命題 1.2の最小性によりN≥0⊆X\mathbb N_{\geq 0}\subseteq Xであり、X⊆ωX\subseteq\omegaであるからN≥0⊆ω\mathbb N_{\geq 0}\subseteq\omegaである。

二つの包含によりN≥0=ω\mathbb N_{\geq 0}=\omegaである。各n∈ωn\in\omegaについて、自然数の後続と順序数の後続はともにn∪{n}n\cup\{n\}であるから、S(n)=n+1=n∪{n}S(n)=n+1=n\cup\{n\}が成り立つ。▨

注意 4.10.ω\omegaの元は0=∅0=\varnothing、1={0}1=\{0\}、2={0,1}2=\{0,1\}、… という von Neumann 自然数であり、命題 4.8 (3)により、ω\omega未満の順序数は有限順序数にほかならない。以後、ω\omega未満の順序数を自然数と呼ぶ。例 1.2で通常の大小について整列集合とした自然数全体N≥0\mathbb{N}_{\geq 0}は、命題 4.9によりω\omegaに等しい。ω\omegaは、自然数をすべて並べ終えた段を表す最小の順序数である。命題 4.2 (1)によりω+1=ω∪{ω}\omega+1=\omega\cup\{\omega\}もふたたび順序数であり、後続を取る操作をここから先へ続けることができる。

5 順序数の和と積

命題 5.1.α\alpha、β\betaを順序数とする。集合

S(α,β)=({0}×α)∪({1}×β)S(\alpha,\beta)=(\{0\}\times\alpha)\cup(\{1\}\times\beta)

の上の関係≺\precを、(i,ξ)≺(j,η)(i,\xi)\prec(j,\eta)を「i<ji<j、またはi=ji=jかつξ<η\xi<\eta」によって定め、直積β×α\beta\times\alpha上の辞書式順序<lex<_{\mathrm{lex}}（§E1.8 定義 5.3）を、(η,ξ)<lex(η′,ξ′)(\eta,\xi)<_{\mathrm{lex}}(\eta',\xi')を「η<η′\eta<\eta'、またはη=η′\eta=\eta'かつξ<ξ′\xi<\xi'」によって定める。次が成り立つ。

  1. ≺\precはS(α,β)S(\alpha,\beta)を整列する。
  2. <lex<_{\mathrm{lex}}はβ×α\beta\times\alphaを整列する。

証明.≺\precの非反射性と推移性は、0<10<1と、α\alphaおよびβ\betaの上の<<の非反射性と推移性から従う。相異なる二元(i,ξ)(i,\xi)と(j,η)(j,\eta)については、i≠ji\neq jならばi<ji<jとj<ij<iのちょうど一方が、i=ji=jならばξ<η\xi<\etaとη<ξ\eta<\xiのちょうど一方が成り立つ。TTをS(α,β)S(\alpha,\beta)の空でない部分集合とする。T0={ξ∈α∣(0,ξ)∈T}T_0=\{\xi\in\alpha\mid(0,\xi)\in T\}が空でなければ、T0T_0はα\alphaの空でない部分集合であるから最小元ξ0\xi_0をもち、(0,ξ0)(0,\xi_0)がTTの最小元である。T0T_0が空ならばT⊆{1}×βT\subseteq\{1\}\times\betaであり、T1={η∈β∣(1,η)∈T}T_1=\{\eta\in\beta\mid(1,\eta)\in T\}の最小元η0\eta_0について(1,η0)(1,\eta_0)がTTの最小元である。これで(1)が示された。

∈\inはβ\betaとα\alphaをそれぞれ整列するから、これらに付随する≤\leはいずれも整列順序である。よって§E1.8 定理 5.10 (1)によりβ×α\beta\times\alpha上の≤lex\leq_{\mathrm{lex}}は整列順序であり、§E1.8 命題 5.4によりそれに付随する狭義順序は<lex<_{\mathrm{lex}}である。ゆえに<lex<_{\mathrm{lex}}はβ×α\beta\times\alphaを整列し、(2)が示された。▨

定義 5.2. 順序数α\alpha、β\betaに対して、命題 5.1の二つの整列集合の順序型として

α+β=ot⁡(S(α,β),≺),α⋅β=ot⁡(β×α,<lex)\alpha+\beta=\operatorname{ot}(S(\alpha,\beta),\prec), \qquad \alpha\cdot\beta=\operatorname{ot}(\beta\times\alpha,<_{\mathrm{lex}})

と定め、それぞれα\alphaとβ\betaの順序数の和 (sum of ordinals)、順序数の積 (product of ordinals) という。S(α,β)S(\alpha,\beta)はα\alphaの後にβ\betaを並べた並べ方であり、β×α\beta\times\alphaの上の辞書式順序はα\alphaをβ\beta個並べた並べ方である。

命題 5.3.α\alpha、β\beta、γ\gammaを順序数とする。次が成り立つ。

  1. α+0=α\alpha+0=\alphaかつ0+α=α0+\alpha=\alphaである。
  2. α+1=α∪{α}\alpha+1=\alpha\cup\{\alpha\}である。すなわち和としてのα+1\alpha+1はα\alphaの後続に一致する。
  3. α⋅0=0\alpha\cdot0=0、0⋅α=00\cdot\alpha=0、α⋅1=α\alpha\cdot1=\alphaかつ1⋅α=α1\cdot\alpha=\alphaである。
  4. β<γ\beta<\gammaならばα+β<α+γ\alpha+\beta<\alpha+\gammaである。

証明.S(α,0)={0}×αS(\alpha,0)=\{0\}\times\alphaであり、ξ↦(0,ξ)\xi\mapsto(0,\xi)はα\alphaからS(α,0)S(\alpha,0)への全単射であって、ξ<ξ′\xi<\xi'と(0,ξ)≺(0,ξ′)(0,\xi)\prec(0,\xi')は同値である。α\alphaは順序数であるから、定理 3.1の一意性によりα+0=α\alpha+0=\alphaである。S(0,α)={1}×αS(0,\alpha)=\{1\}\times\alphaについてもξ↦(1,ξ)\xi\mapsto(1,\xi)が同じ性質をもつので0+α=α0+\alpha=\alphaである。これで(1)が示された。

1={0}1=\{0\}であるからS(α,1)=({0}×α)∪{(1,0)}S(\alpha,1)=(\{0\}\times\alpha)\cup\{(1,0)\}である。写像h:S(α,1)→α∪{α}h:S(\alpha,1)\to\alpha\cup\{\alpha\}をh(0,ξ)=ξh(0,\xi)=\xiおよびh(1,0)=αh(1,0)=\alphaで定めると、hhは全単射である。(0,ξ)≺(0,ξ′)(0,\xi)\prec(0,\xi')とξ<ξ′\xi<\xi'は同値であり、(0,ξ)≺(1,0)(0,\xi)\prec(1,0)かつξ∈α\xi\in\alphaであるから、hhは順序を保ち反映する。α∪{α}\alpha\cup\{\alpha\}は命題 4.2 (1)により順序数であるから、一意性によりα+1=α∪{α}\alpha+1=\alpha\cup\{\alpha\}である。これで(2)が示された。

0×α=∅0\times\alpha=\varnothingであるからα⋅0=ot⁡(∅)=0\alpha\cdot0=\operatorname{ot}(\varnothing)=0であり、α×0=∅\alpha\times0=\varnothingであるから0⋅α=ot⁡(∅)=00\cdot\alpha=\operatorname{ot}(\varnothing)=0である。1×α={0}×α1\times\alpha=\{0\}\times\alphaであり、(0,ξ)↦ξ(0,\xi)\mapsto\xiは順序を保つ全単射であるからα⋅1=α\alpha\cdot1=\alphaである。α×1=α×{0}\alpha\times1=\alpha\times\{0\}であり、(η,0)↦η(\eta,0)\mapsto\etaは順序を保つ全単射であるから1⋅α=α1\cdot\alpha=\alphaである。これで(3)が示された。

β<γ\beta<\gammaとし、g:S(α,γ)→α+γg:S(\alpha,\gamma)\to\alpha+\gammaを順序同型とする。β∈γ\beta\in\gammaであるから(1,β)∈S(α,γ)(1,\beta)\in S(\alpha,\gamma)であり、(1,β)(1,\beta)が定める始切片は

{(i,ξ)∈S(α,γ)∣(i,ξ)≺(1,β)}=({0}×α)∪({1}×β)=S(α,β)\{(i,\xi)\in S(\alpha,\gamma)\mid(i,\xi)\prec(1,\beta)\}=(\{0\}\times\alpha)\cup(\{1\}\times\beta)=S(\alpha,\beta)

である。系 3.3によりg(1,β)=ot⁡(S(α,β))=α+βg(1,\beta)=\operatorname{ot}(S(\alpha,\beta))=\alpha+\betaであり、g(1,β)∈α+γg(1,\beta)\in\alpha+\gammaであるからα+β<α+γ\alpha+\beta<\alpha+\gammaである。これで(4)が示された。▨

例 5.4.1+ω=ω1+\omega=\omegaである。実際、S(1,ω)={(0,0)}∪({1}×ω)S(1,\omega)=\{(0,0)\}\cup(\{1\}\times\omega)であり、写像h:S(1,ω)→ωh:S(1,\omega)\to\omegaをh(0,0)=0h(0,0)=0およびh(1,n)=n+1h(1,n)=n+1で定める。n<ωn<\omegaならば、命題 4.8 (1)と系 4.3によりn+1<ωn+1<\omegaであるから、hhの値はω\omegaに属する。m∈ωm\in\omegaかつm≠0m\neq0とすると、mmは命題 4.8 (3)により有限順序数であり、00でないから後続順序数であって、m=n+1m=n+1と表される。このときn∈mn\in mとω\omegaの推移性によりn<ωn<\omegaであるから、hhは全射である。n+1=n′+1n+1=n'+1ならば命題 4.5 (1)によりn=n′n=n'である。またn∈n+1n\in n+1であるからn+1≠∅=0n+1\neq\varnothing=0であり、h(0,0)=0≠n+1=h(1,n)h(0,0)=0\neq n+1=h(1,n)である。よってhhは単射である。n<n′n<n'ならば命題 4.2 (2)によりn+1≤n′<n′+1n+1\le n'<n'+1であり、逆にn+1<n′+1n+1<n'+1ならば命題 4.2 (3)によりn+1≤n′n+1\le n'であってn<n′n<n'であるから、hhは{1}×ω\{1\}\times\omegaの上で順序を保ち反映する。また(0,0)≺(1,n)(0,0)\prec(1,n)であり0<n+10<n+1である。よってhhは順序同型であり、ω\omegaが順序数であることと定理 3.1の一意性により1+ω=ω1+\omega=\omegaである。

一方命題 5.3 (2)によりω+1=ω∪{ω}\omega+1=\omega\cup\{\omega\}であり、ω∈ω+1\omega\in\omega+1かつ命題 2.3 (2)によりω∉ω\omega\notin\omegaであるからω+1≠ω\omega+1\neq\omegaである。したがって1+ω≠ω+11+\omega\neq\omega+1であり、順序数の和は可換ではない。また命題 5.3 (1)により0+ω=ω0+\omega=\omegaであるから、0<10<1であるのに0+ω=1+ω0+\omega=1+\omegaである。すなわち命題 5.3 (4)の狭義単調性は、左の引数については成り立たない。

例 5.5.ω⋅2=ω+ω\omega\cdot2=\omega+\omegaである。実際、2={0,1}2=\{0,1\}であるから2×ω=({0}×ω)∪({1}×ω)=S(ω,ω)2\times\omega=(\{0\}\times\omega)\cup(\{1\}\times\omega)=S(\omega,\omega)であり、2×ω2\times\omegaの上の辞書式順序はS(ω,ω)S(\omega,\omega)の上の≺\precと同じ関係である。よって両者の順序型は等しい。

2⋅ω≠ω⋅22\cdot\omega\neq\omega\cdot2である。2⋅ω2\cdot\omegaはω×2\omega\times2の順序型である。ω×2\omega\times2の元(n,i)(n,i)が(0,0)(0,0)と異なるとき、i=1i=1ならば(n,0)(n,0)が、i=0i=0かつn≠0n\neq0ならば、nnは命題 4.8 (3)により有限順序数で00でないから後続順序数m+1m+1と表され(m,1)(m,1)が、それぞれ(n,i)(n,i)未満の元の全体の最大元である。すなわちω×2\omega\times2では、最小元以外のどの元についても、それ未満の元の全体が最大元をもつ。一方S(ω,ω)S(\omega,\omega)の元(1,0)(1,0)は最小元ではなく、それ未満の元の全体{0}×ω\{0\}\times\omegaは最大元をもたない。補題 1.6により順序同型は始切片を始切片へ全単射で移すので、始切片が最大元をもつかどうかは順序同型で保たれる。よってω×2\omega\times2とS(ω,ω)S(\omega,\omega)は順序同型ではなく、定理 3.1の一意性により2⋅ω≠ω⋅22\cdot\omega\neq\omega\cdot2である。したがって順序数の積も可換ではない。

6 置換公理スキーマとω+ω\omega+\omega

命題 6.1.A={ω+n∣n<ω}A=\{\omega+n\mid n<\omega\}は集合であり、

ω+ω=sup⁡A=⋃A\omega+\omega=\sup A=\bigcup A

が成り立つ。

証明. 対応n↦ω+nn\mapsto\omega+nはω\omegaの各元に対して順序数をちょうど一つ定めるから、§E1.13 定義 5.1によりAAは集合である。

g:S(ω,ω)→ω+ωg:S(\omega,\omega)\to\omega+\omegaを順序同型とする。n<ωn<\omegaについて、(1,n)(1,n)が定める始切片はS(ω,n)S(\omega,n)であるから、系 3.3によりg(1,n)=ω+ng(1,n)=\omega+nである。またk<ωk<\omegaについて、(0,k)(0,k)が定める始切片は{0}×k\{0\}\times kであり、ξ↦(0,ξ)\xi\mapsto(0,\xi)はこれとkkとの順序同型であるからg(0,k)=kg(0,k)=kである。ggは全射であるから

ω+ω={k∣k<ω}∪A\omega+\omega=\{k\mid k<\omega\}\cup A

である。

各n<ωn<\omegaについて命題 5.3 (4)によりω+n<ω+ω\omega+n<\omega+\omegaであるから、ω+ω\omega+\omegaはAAの上界であり、補題 4.4 (2)によりsup⁡A≤ω+ω\sup A\le\omega+\omegaである。sup⁡A<ω+ω\sup A<\omega+\omegaと仮定すると、前段によりsup⁡A\sup Aはω\omega未満の順序数kkであるか、あるn<ωn<\omegaについてω+n\omega+nである。前者では、命題 5.3 (1)によりω+0=ω\omega+0=\omegaでありk<ωk<\omegaであるからsup⁡A<ω+0\sup A<\omega+0となって、ω+0∈A\omega+0\in Aと補題 4.4 (1)に反する。後者では、命題 4.8 (1)と系 4.3によりn+1<ωn+1<\omegaであり、命題 5.3 (4)によりω+n<ω+(n+1)\omega+n<\omega+(n+1)であるから、ω+(n+1)∈A\omega+(n+1)\in Aと補題 4.4 (1)にふたたび反する。よってsup⁡A=ω+ω\sup A=\omega+\omegaであり、sup⁡\supの定め方によりsup⁡A=⋃A\sup A=\bigcup Aである。▨

注意 6.2.命題 6.1の証明が置換公理スキーマを用いるのは、各n<ωn<\omegaに対して定まる順序数ω+n\omega+nを一つの集合AAに集める箇所である。個々のnnについては、ω\omegaから後続を取る操作をnn段たどってω+n\omega+nを得ることができ、置換公理スキーマを必要としない。しかし、それらを集めたAAが集合であることは、対の公理、和集合の公理、冪集合の公理および分出公理スキーマからは一般には従わない。

このことを、置換公理スキーマを除くとω+ω\omega+\omegaが存在しない、と述べてはならない。正確には次のとおりである。置換公理スキーマを欠く体系には、内部に各ω+n\omega+nが存在してもω+ω\omega+\omegaを順序数としてもたないモデルがある。すなわち、各n<ωn<\omegaに対するω+n\omega+nの存在だけを根拠としてω+ω\omega+\omegaの存在を一般に証明することはできない。これは体系についての主張ではなくモデルについての相対化した主張であり、そのようなモデルの構成は「公理的集合論」が扱う。

7 演習

問題 7.1.AAを順序数からなる空でない集合とする。⋂A\bigcap AがAAの最小元であることを証明せよ。

解答.

α0∈A\alpha_0\in Aを一つ取ると⋂A⊆α0\bigcap A\subseteq\alpha_0であるから、⋂A\bigcap Aは§E1.13 定義 2.1により集合である。x∈⋂Ax\in\bigcap Aとすると、各α∈A\alpha\in Aについてx∈αx\in\alphaであり、命題 2.3 (1)によりxxは順序数であって、α\alphaの推移性によりx⊆αx\subseteq\alphaである。よってx⊆⋂Ax\subseteq\bigcap Aであり、⋂A\bigcap Aは推移的集合である。⋂A\bigcap Aは順序数α0\alpha_0の部分集合であるから命題 2.5 (3)により∈\inで整列され、順序数である。

各α∈A\alpha\in Aについて⋂A⊆α\bigcap A\subseteq\alphaであるから、命題 2.5 (1)により⋂A≤α\bigcap A\le\alphaである。⋂A∉A\bigcap A\notin Aと仮定すると、各α∈A\alpha\in Aについて⋂A≠α\bigcap A\neq\alphaであるから⋂A<α\bigcap A<\alpha、すなわち⋂A∈α\bigcap A\in\alphaである。よって⋂A∈⋂A\bigcap A\in\bigcap Aとなり、命題 2.3 (2)に反する。ゆえに⋂A∈A\bigcap A\in Aであり、⋂A\bigcap AはAAの最小元である。▨

問題 7.2. 順序数α\alpha、β\beta、γ\gammaについて(α+β)+γ=α+(β+γ)(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)が成り立つことを証明せよ。

解答.

集合

T=({0}×α)∪({1}×β)∪({2}×γ)T=(\{0\}\times\alpha)\cup(\{1\}\times\beta)\cup(\{2\}\times\gamma)

の上の関係≺T\prec_Tを、(i,ξ)≺T(j,η)(i,\xi)\prec_T(j,\eta)を「i<ji<j、またはi=ji=jかつξ<η\xi<\eta」によって定める。≺T\prec_TがTTを整列することと、ot⁡(T)\operatorname{ot}(T)が両辺に等しいこととを示す。

f:S(α,β)→α+βf:S(\alpha,\beta)\to\alpha+\betaを順序同型とし、Φ:T→S(α+β,γ)\Phi:T\to S(\alpha+\beta,\gamma)を

Φ(0,ξ)=(0,f(0,ξ)),Φ(1,η)=(0,f(1,η)),Φ(2,ζ)=(1,ζ)\Phi(0,\xi)=(0,f(0,\xi)), \qquad \Phi(1,\eta)=(0,f(1,\eta)), \qquad \Phi(2,\zeta)=(1,\zeta)

で定める。ffは全単射であるからΦ\Phiも全単射である。i≤1i\le1かつj≤1j\le1のとき、(i,ξ)≺T(j,η)(i,\xi)\prec_T(j,\eta)とS(α,β)S(\alpha,\beta)における(i,ξ)≺(j,η)(i,\xi)\prec(j,\eta)は同じ条件であり、ffは順序同型であるから、Φ\Phiはこれらの元の間で順序を保ち反映する。i≤1i\le1かつj=2j=2のときは(i,ξ)≺T(2,ζ)(i,\xi)\prec_T(2,\zeta)とΦ(i,ξ)≺Φ(2,ζ)\Phi(i,\xi)\prec\Phi(2,\zeta)がともに成り立ち、i=j=2i=j=2のときは第二成分の大小が両辺で一致する。よってΦ\Phiは全単射であって≺T\prec_Tと≺\precを互いに移す。命題 5.1 (1)により≺\precはS(α+β,γ)S(\alpha+\beta,\gamma)を整列するから、≺T\prec_Tの非反射性、推移性および比較可能性はΦ\Phiを通じて≺\precのそれらから従い、TTの空でない部分集合UUについては、Φ\Phiによる像の最小元のΦ\Phiによる逆像がUUの最小元である。ゆえに≺T\prec_TはTTを整列し、Φ\Phiは順序同型であるからot⁡(T)=(α+β)+γ\operatorname{ot}(T)=(\alpha+\beta)+\gammaである。

同様にg:S(β,γ)→β+γg:S(\beta,\gamma)\to\beta+\gammaを順序同型とし、Ψ:T→S(α,β+γ)\Psi:T\to S(\alpha,\beta+\gamma)を

Ψ(0,ξ)=(0,ξ),Ψ(1,η)=(1,g(0,η)),Ψ(2,ζ)=(1,g(1,ζ))\Psi(0,\xi)=(0,\xi), \qquad \Psi(1,\eta)=(1,g(0,\eta)), \qquad \Psi(2,\zeta)=(1,g(1,\zeta))

で定めると、同じ確認によりΨ\Psiは順序同型であり、ot⁡(T)=α+(β+γ)\operatorname{ot}(T)=\alpha+(\beta+\gamma)である。よって(α+β)+γ=α+(β+γ)(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)である。▨

問題 7.3.2⋅ω=ω2\cdot\omega=\omegaが成り立つことを証明せよ。

解答.

はじめに、整列集合(V,<)(V,<)とVVに属さない元ppについて、V∪{p}V\cup\{p\}にVVの順序を延長してppを最大元とする順序を入れると、その順序型がot⁡(V)+1\operatorname{ot}(V)+1であることを見る。e:V→ot⁡(V)e:V\to\operatorname{ot}(V)を順序同型とし、e(p)=ot⁡(V)e(p)=\operatorname{ot}(V)と延長すると、これはV∪{p}V\cup\{p\}からot⁡(V)∪{ot⁡(V)}\operatorname{ot}(V)\cup\{\operatorname{ot}(V)\}への順序を保つ全単射であり、命題 5.3 (2)により後者はot⁡(V)+1\operatorname{ot}(V)+1である。

λ=2⋅ω=ot⁡(ω×2,<lex)\lambda=2\cdot\omega=\operatorname{ot}(\omega\times2,<_{\mathrm{lex}})とおく。系 3.3により、λ\lambdaの元はω×2\omega\times2の元(n,i)(n,i)が定める始切片I(n,i)I_{(n,i)}の順序型である。ot⁡(I(n,i))\operatorname{ot}(I_{(n,i)})が有限順序数でないような(n,i)(n,i)の全体をTTとし、T≠∅T\neq\emptysetと仮定して<lex<_{\mathrm{lex}}に関する最小元(n,i)(n,i)を取る。I(0,0)=∅I_{(0,0)}=\emptysetの順序型は00であるから(n,i)≠(0,0)(n,i)\neq(0,0)である。例 5.5で見たとおり、i=1i=1のときは(n,0)(n,0)が、i=0i=0かつn≠0n\neq0のときはn=m+1n=m+1と表して(m,1)(m,1)が、I(n,i)I_{(n,i)}の最大元である。その最大元をqqと書くとI(n,i)=Iq∪{q}I_{(n,i)}=I_q\cup\{q\}であり、q<lex(n,i)q<_{\mathrm{lex}}(n,i)と(n,i)(n,i)の最小性によりot⁡(Iq)\operatorname{ot}(I_q)は有限順序数であるから、はじめに見たことによりot⁡(I(n,i))=ot⁡(Iq)+1\operatorname{ot}(I_{(n,i)})=\operatorname{ot}(I_q)+1であり、補題 4.7 (2)によりこれも有限順序数である。これは(n,i)∈T(n,i)\in Tに反する。よってT=∅T=\emptysetであり、λ\lambdaの元はすべて有限順序数であるから、命題 4.8 (3)によりλ⊆ω\lambda\subseteq\omegaであり、命題 2.5 (1)によりλ≤ω\lambda\le\omegaである。

ω×2\omega\times2は空でないからλ≠0\lambda\neq0である。λ=μ+1\lambda=\mu+1と表されると仮定すると、命題 4.2 (3)によりμ\muはλ\lambdaの最大元であるから、順序同型によりω×2\omega\times2も最大元をもつ。しかし(n,i)∈ω×2(n,i)\in\omega\times2に対して、命題 4.8 (1)と系 4.3によりn+1<ωn+1<\omegaであり(n,i)<lex(n+1,0)(n,i)<_{\mathrm{lex}}(n+1,0)であるから、ω×2\omega\times2は最大元をもたない。よってλ\lambdaは極限順序数であり、命題 4.8 (2)によりω≤λ\omega\le\lambdaである。以上と命題 2.5 (2)によりλ=ω\lambda=\omegaである。▨

順序数の全体にわたる帰納法と、順序数を添字とする族の再帰的な定義は「超限帰納法と超限再帰」が扱い、その極限段では補題 4.4の上限がそのまま用いられる。集合の濃度を順序数によって表す基数は「基数とアレフ」が扱い、可算な順序数の全体の上限として最小の非可算基数を得るところで、注意 3.4と同じ役割の置換公理スキーマがふたたび働く。

参考文献

  1. Thomas Jech, Set Theory, 3rd millennium ed., Springer Monographs in Mathematics, Springer, Berlin, 2003.順序数の定義、順序型、および順序数の算術を参考にした。
  2. Herbert B. Enderton, Elements of Set Theory, Academic Press, 1977.整列集合、始切片、順序型、および置換公理の役割を参考にした。
  3. Karel Hrbacek and Thomas Jech, Introduction to Set Theory, 3rd ed., Marcel Dekker, New York, 1999.順序数と順序数の算術の例と演習を参考にした。

前提記事