カントール標準形

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

概要

順序数$\alpha$が底 (basis) $\beta>0$のカントール標準形で表されているとは$\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}$

となっていることである．カントール標準形定理 (Cantor normal form theorem) は順序数$\alpha$に対しカントール標準形は一意に定まることを主張する．

カントール標準形で一番重要なのは底が$\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}$とする．このような形でカントール標準形は述べられる場合もある．

順序数表記

底$\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}$で順序数の無限降下列は存在しないからである．

この事実を用いて順序数表記を構成することができる。ただし上記の「順序数表示方法」自体は集合論において意味を持つものであり、算術で意味を持つ順序数表記そのものではないことに注意する。

定義2.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.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.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.4 順序数コード (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$ ここで$\langle \cdot \rangle$は適当な対関数とする．また$\ulcorner \cdot \urcorner$の値域を$\ulcorner {\mathsf {OT}}\urcorner \subseteq \mathbb {N}$とし，$\ulcorner {\mathsf {OT}}\urcorner$を順序数コード (ordinal code) という．