カントール標準形

カントール標準形 (Cantor normal form) とはカントールによって定義され，また証明された順序数の標準形である．これは$n$進法，及び遺伝的記法の順序数への一般化と考えることができる．

概要

順序数$\alpha>0$が底 (basis) $\beta >1$のカントール標準形で表されているとは$\alpha _{1}>\cdots >\alpha _{n}$と$0<\gamma _{i}<\beta (i=1,\ldots ,n)$に対し

$\alpha =\beta ^{\alpha _{1}}\gamma _{1}+\cdots +\beta ^{\alpha _{n}}\gamma _{n}$

となっていることである．また$\alpha=0$の場合は底によらす$\alpha=0$でカントール標準形で表されているとする．カントール標準形定理 (Cantor normal form theorem) は順序数$\alpha$に対しカントール標準形は一意に定まることを主張する．

定理1.1 (カントール正規形定理)
$\beta >1$とする．このとき，任意の順序数 $\alpha$について，ある自然数 $(0\leq )n<\omega$と順序数 $\alpha _{1},\cdots ,\alpha _{n},\gamma _{1},\cdots ,\gamma _{n}$が存在して$\gamma _{1},\cdots ,\gamma _{n}<\beta$，$\alpha \geq \alpha _{1}>\cdots >\alpha _{n}$を満たし， $\alpha =\beta ^{\alpha _{1}}\cdot \gamma _{1}+\cdots +\beta ^{\alpha _{n}}\cdot \gamma _{n}$ が成り立つ．

カントール標準形で一番重要なのは底が$\omega$の場合で，各$\gamma _{i}<\omega$であるから$\omega ^{\alpha _{i}}\gamma _{i}$は，有限回の和を用いて$\underbrace {\omega ^{\alpha _{i}}+\cdots +\omega ^{\alpha _{i}}} _{\gamma _{i}{\text{times}}}$と表せることを用いれば以下の系を特殊なカントール標準形を得ることができる．

$\alpha =\omega ^{\alpha _{1}}+\cdots +\omega ^{\alpha _{n}}$

ここで$\alpha _{1}\geq \cdots \geq \alpha _{n}$とする．このような形でカントール標準形は述べられる場合もある．

カントール標準形について重要となるのは以下の定理である．

定理1.2

$\alpha =\omega ^{\alpha _{1}}+\cdots +\omega ^{\alpha _{n}}$，$\beta =\omega ^{\beta _{1}}+\cdots +\omega ^{\beta _{m}}$とするとき以下は同値である． $\alpha < \beta$． $(\alpha _{1},\ldots ,\alpha _{n})<_{\mathrm {lex} }(\beta _{1},\ldots ,\beta _{m})$ ここで$<_{\mathrm {lex} }$は辞書式順序 (lexicographical order) である．すなわちまず，$\alpha _{1},\beta _{1}$比較し等しかったら$\alpha _{2},\beta _{2}$を比較して，順番に比していく．ある$i$で$\alpha _{i}<\beta _{i}$になった時点で比較を終え，全ての$i\leq \min\{n,m\}$に対して$\alpha _{i}=\beta _{i}$なら，$m,n$を比較することで$<_{\mathrm {lex} }$が定まる．

順序数表記

底$\omega$のカントール標準形にて$\alpha =\omega ^{\alpha _{0}}+\cdots +\omega ^{\alpha _{n}}$と表したとき，$\varepsilon_0$が$\xi = \omega^\xi$となるような最小の順序数であったことを思い返せば$\alpha<\varepsilon_0$に対して$\alpha _{i}<\alpha$となる．よって$\alpha_{i}$もカントール標準形で表し，$\alpha _{i}=\omega ^{\alpha _{i,0}}+\cdots +\omega ^{\alpha _{i,m}}$とし，$\alpha _{i,j}$をカントール標準形で表し，この操作を有限回繰り返すことで$0$と$+,\xi \mapsto \omega ^{\xi }$のみを用いて$\varepsilon_0$未満の順序数を表すことができる．なぜなら$\cdots <\alpha _{i,j}<\alpha _{i}<\alpha <\varepsilon _{0}$で順序数の無限降下列は存在しないからである．

この事実を用いて順序数表記を構成することができる。ただし上記の「順序数表示方法」自体は順序数表記そのものではないことに注意する。以下で、まず$\mathbb{N}$の部分集合として整列順序集合$({\mathsf {OT}},\prec )$を定義し、その後$({\mathsf {OT}},\prec )$が順序数表記であること（つまり$\mathsf{OT}$と$\prec$が計算可能であること）を示す。

項とその割り当て

定義2.1.1 項 (term)
$\overline{0}$，${\overline {\omega }}^{\cdot }$，${\overline {+}}$を記号とする． 項 (term) は以下のように帰納的に定義される． $\overline{0}$は項である． $a$が項なら${\overline {\omega }}^{a}$も項である． $a_{i}(i=0,\ldots ,n)$が項なら$a_{0}{\overline {+}}\cdots {\overline {+}}a_{n}$も項である． 項の集合を${\mathsf {T}}$とする．

このように項で順序数を表現できるので，項$a$に対応する順序数$|a|_{\mathcal {O}}$も帰納的に定義する．

定義2.1.2 割り当て (assignment)
割り当て (assignment) $|\cdot |_{\mathcal {O}}\colon {\mathsf {T}}\to \varepsilon _{0}$を以下のように帰納的に定義する． $|{\overline {0}}|_{\mathcal {O}}:=0$． $|{\overline {\omega }}^{a}|_{\mathcal {O}}:=\omega ^{|a|_{\mathcal {O}}}$． $|a_{0}{\overline {+}}\cdots {\overline {+}}a_{n}|_{\mathcal {O}}:=|a_{0}|_{\mathcal {O}}+\cdots +|a_{n}|_{\mathcal {O}}$．

しかし$\alpha =|a|_{\mathcal {O}}$となる$a\in {\mathsf {T}}$は一意に定まるとは限らない．よって一意に定まるような${\mathsf {T}}$の部分集合$\mathsf{OT}$を定める．これを定めるためにカントール標準形を用いる．

定義2.1.3 順序数項 (ordinal term)
順序数項 (ordinal term) は以下のように帰納的に定義される． $\overline{0}$は順序数項である． $a_{i}(i=0,\ldots ,n)$が順序数項で$|a_{0}|_{\mathcal {O}}\geq \cdots \geq |a_{n}|_{\mathcal {O}}$なら${\overline {\omega }}^{a_{0}}{\overline {+}}\cdots {\overline {+}}{\overline {\omega }}^{a_{n}}$も順序数項である． 順序数項全体を$\mathsf{OT}$とする． また$\mathsf{OT}$上の順序$\prec$を$a\prec b:\Leftrightarrow |a|_{\mathcal {O}}<|b|_{\mathcal {O}}$と定める．

計算可能性

前節で定めた$\prec$が$\varepsilon_0$の順序となる，正確に言えば$\langle {\mathsf {OT}},\prec \rangle \cong \langle \varepsilon _{0},<\rangle$となるのは定義より明らかであるが，$\prec$は未だに集合論的に定められていて計算可能性に対する情報を与えてくれない．そのためには$\mathsf{OT}$をコード化する必要があり，また実際に比較するためのアルゴリズムを与える必要がある．

さて前述の順序数表記をコード化する前に列に関するコード化について触れなければならない．

定義2.2.1 列のコード

以下$p_{i}(i\in \mathbb {N} )$を素数の数え上げとして $\langle x_{0},\ldots ,x_{n-1}\rangle :=\prod _{i<n}p_{i}^{1+x_{i}}$ と定める．また$\exp(x,i):=\max\{y\leq x\mid p_{i}^{y}|x\}$とし， $(x)_{i}:=\exp(x,i)-1$． $\mathrm {lh} (x)=\min\{i\leq x\mid \exp(x,i)=0\}$． $x^{\frown }y:=x\prod _{i<\mathrm {lh} (y)}p_{\mathrm {lh} (x)+i}^{1+(y)_{i}}$． とする．直感的には$\langle x_{0},\ldots ,x_{n-1}\rangle$は列のコードを表していて，$(x)_{i}$は$x$がコードする列の$i$番目の要素，$\mathrm {lh} (x)$は$x$がコードする列の長さを表す．そして$x^{\frown }y$は$x, y$がコードする列の結合のコードを表している．さてこれらは全て原始再帰的関数になる

この列のコード化を用いることで順序数項のコードも定義することができる．

定義2.2.2 順序数コード (ordinal code)

$\ulcorner \cdot \urcorner \colon {\mathsf {OT}}\to \mathbb {N}$を帰納的に定義する． $\ulcorner {\overline {0}}\urcorner :=0$． $\ulcorner {\overline {\omega }}^{a_{0}}{\overline {+}}\cdots {\overline {+}}{\overline {\omega }}^{a_{n}}\urcorner :=\langle \ulcorner a_{0}\urcorner ,\ldots \ulcorner a_{n},\urcorner \rangle$ $\ulcorner \cdot \urcorner$の値域を$\ulcorner {\mathsf {OT}}\urcorner \subseteq \mathbb {N}$とし，$\ulcorner {\mathsf {OT}}\urcorner$を順序数コード (ordinal code) という．

さて$\ulcorner {\mathsf {OT}}\urcorner$が計算可能集合であることを示したいわけであるが，そのためには順序数項を定義するときに$\prec$で比較していたためそれに対応する$\ulcorner {\mathsf {OT}}\urcorner$上の計算可能な二項関係$\prec$を同時再帰的に定義する必要がある．ここで定理1.1.よりカントール標準形で$\alpha =\omega ^{\alpha _{0}}+\cdots +\omega ^{\alpha _{n}}$，$\beta =\omega ^{\beta _{0}}+\cdots +\omega ^{\beta _{m}}$と表されたものを比較するためには$(\alpha _{0},\ldots ,\alpha _{n}),(\beta _{0},\ldots ,\beta _{m})$を辞書式順序で比較すれば良いことを思い出せば以下のように定義し直せるであろう．ここで重要な役割を果たしているのは$\alpha _{i}<\alpha ,\beta _{i}<\beta$となっていることで再帰が回るのはここに所以する．

定義2.2.3

$x\in \ulcorner {\mathsf {OT}}\urcorner :\Leftrightarrow x=0\lor (\forall i<\mathrm {lh} (x))[(x)_{i}\in \ulcorner {\mathsf {OT}}\urcorner \land (i+1<\mathrm {lh} (x)\to (x)_{i+1}{\underline {\triangleleft }}(x)_{i})]$． ${\begin{aligned}a\triangleleft b:\Leftrightarrow &a\in \ulcorner {\mathsf {OT}}\urcorner \land b\in \ulcorner {\mathsf {OT}}\urcorner \land [(a=0\land b\neq 0)\lor \\&(\exists i<\mathrm {lh} (a))(\forall j<i)[(a)_{j}=(b)_{j}\land (a)_{i}\triangleleft (b)_{i}]\lor \\&(\mathrm {lh} (a)<\mathrm {lh} (b)\land (\forall i<\mathrm {lh} (a))[(a)_{i}=(b)_{i}])\end{aligned}}$ $a{\underline {\triangleleft }}b:\Leftrightarrow a\triangleleft b\lor a=b$

この定義は$\mathsf{OT}$の定義に基づいていて，$|\cdot |_{\mathcal {O}}$で比較していたものを相互再帰ですでに定義されている，${\underline {\triangleleft }}$で置き換えたものになる．その${\underline {\triangleleft }}$は$\ulcorner {\mathsf {OT}}\urcorner$の要素であるかを確認し$\triangleleft$の辞書式順序で比較するということを意図している．

このようにすれば計算可能(原始再帰)な順序数表記$\langle \ulcorner {\mathsf {OT}}\urcorner ,\triangleleft \rangle$を得ることができる． ここで$\langle \ulcorner {\mathsf {OT}}\urcorner ,\triangleleft \rangle \cong \langle \varepsilon _{0},<\rangle$(これはカントール標準形による順序数表記なら簡単に示せるがより強い順序数表記，例えば順序数崩壊関数に伴う順序数表記の場合明らかではない)であることから以下の系が導かれる．

系2.2.4
$\varepsilon _{0}<\omega _{1}^{\mathrm {CK} }$である．ただし$\omega_1^{\mathrm{CK}}$はチャーチ・クリーネ順序数である． 証明．チャーチ・クリーネ順序数の定義と$\langle \ulcorner {\mathsf {OT}}\urcorner ,\triangleleft \rangle \cong \langle \varepsilon _{0},<\rangle$と$\ulcorner {\mathsf {OT}}\urcorner$が計算可能であり$\triangleleft$が計算可能であることから明らかである．□

カントール標準形に伴う基本列

カントール標準形を用いることで$\omega \leq \alpha <\varepsilon _{0}$に対して標準的な基本列$\alpha[n]$を定めることができる．

定義3.1
$\omega \leq \alpha <\varepsilon _{0}$に対し$\alpha[n]$を以下のように超限再帰で定義する． $\omega [n]:=n$． $\omega ^{\alpha +1}[n]:=\omega ^{\alpha }n$ $\omega ^{\lambda }[n]:=\omega ^{\lambda [n]}$，ただし$\lambda$は極限順序数． カントール標準形で$\alpha =\omega ^{\alpha _{1}}+\cdots \omega ^{\alpha _{m}}$とするとき$\alpha [n]:=\omega ^{\alpha _{1}}+\cdots \omega ^{\alpha _{m}}[n]$．

ただし，この定義では基本列が計算可能であるということを導かない．よってこの基本列で定義される急増加関数も計算可能であるということも導かれない．よって2節で定義した計算可能な順序数表記に対して基本列を定義しなければならないことに注意しよう．

この基本列の定義では場合分けを用いていることから，その場合分けを$\langle \ulcorner {\mathsf {OT}}\urcorner ,\triangleleft \rangle$に於いて計算可能にできるか否かが問題になる．すなわち以下のような関係が計算可能となる必要がある．

1. $\|a\|_{\mathcal {O}}=\omega$．
2. $\|a\|_{\mathcal {O}}=\omega ^{\alpha +1}$．
3. $\|a\|_{\mathcal {O}}=\omega ^{\lambda }$．ただし$\lambda$は極限順序数とする．
4. カントール標準形で$\|a\|_{\mathcal {O}}=\omega ^{\alpha _{1}}+\cdots \omega ^{\alpha _{m}}$．

ここで$\|\cdot \|_{\mathcal {O}}$はコードから対応する順序数項を割り当てる写像$|\cdot |\colon \ulcorner {\mathsf {OT}}\urcorner \to {\mathsf {OT}}$と$|\cdot |_{\mathcal {O}}$の合成である．

4.は1,2,3.いずれでもないと表すことができるので1,2,3.についてのみ考える． 1.は$\omega =\omega ^{\omega ^{0}}$であることから$a=\langle \langle 0\rangle \rangle$と同値であるため計算可能である． 2.は$\omega ^{\alpha +1}$という形をしていることから$\mathrm {lh} (a)=1$であり，$\|(a)_{0}\|_{\mathcal {O}}=\alpha +1=\alpha +\omega ^{0}$であるから$\mathrm {lh} (a)=1\land ((a)_{0})_{\mathrm {lh} ((a)_{0})-1}=\langle 0\rangle$と表せて計算可能である． 3.は後続順序数でないことから$\mathrm {lh} ((a)_{0})=1\land (a)_{0}\neq 0$であるか$\mathrm {lh} ((a)_{0})>1\land ((a)_{0})_{\mathrm {lh} ((a)_{0})-1}\neq \langle 0\rangle$と表すことができて計算可能である．

よって以下のように計算可能な基本列が定められる．

定義3.1

$\langle \langle 0\rangle \rangle {\underline {\triangleleft }}a$に対し$a[n]$を以下のように超限再帰で定義する． $\|a\|_{\mathcal {O}}=\omega$であるとき$n$に関して再帰的に$\omega [0]:=0,\omega [n+1]:=\omega [n]^{\frown }\langle \langle 0\rangle \rangle$． $\|a\|_{\mathcal {O}}=\omega ^{\alpha +1}$であるとき$(a)_{0}^{-}$を$(a)_{0}$がコードする列の最後の要素を削った列のコードとし，$n$に関して帰納的に$a[0]:=0,a[n+1]:=a[n]^{\frown }\langle (a)_{0}^{-}\rangle$． $\lambda$を極限順序数とし$\|a\|_{\mathcal {O}}=\omega ^{\lambda }$であるとき，$a[n]:=\langle (a)_{0}[n]\rangle$． カントール標準形で$\|a\|_{\mathcal {O}}=\omega ^{\alpha _{1}}+\cdots \omega ^{\alpha _{m}}$とするとき，$a$のコードする最後の行を削った列のコードを$a^{-}$とし，$a[n]:={a^{-}}^{\frown }\langle (a)_{\mathrm {lh} (a)-1}[n]\rangle$とする．

よって計算可能な基本列を得ることができる．この定義の系として以下が分かる．

定理3.2
$\alpha<\varepsilon_0$に対して上の標準形による急増加関数$f_\alpha$は計算可能である．