カントール標準形

カントール標準形 (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$に対しカントール標準形は一意に定まることを主張する．

カントール標準形で一番重要なのは底が$\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.1

$\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 項 (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.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}\mid x\}$とし， $(x)_{i}:=\exp(x,i)-1$． $\mathrm {lh} (x)=\min\{i\leq x\mid \exp(x,i)=0\}$． とする．直感的には$\langle x_{0},\ldots ,x_{n-1}\rangle$は列のコードを表していて，$(x)_{i}$は$x$がコードする列の$i$番目の要素，$\mathrm {lh} (x)$は$x$がコードする列の長さを表す．

定義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$ ここで$\langle \cdot \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$上の計算可能な二項関係構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \lhd} を同時再帰的に定義する必要がある．ここで定理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

構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle 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}\unlhd(x)_i)]} ． 構文解析に失敗 (構文エラー): {\displaystyle \begin{align*}a\lhd b:\Leftrightarrow & a\in\ulcorner\mathsf{OT}\urcorner\land b\in\ulcorner\mathsf{OT}\urcorner\land[(a=0\land b\neq 0)\lor\\ & (\exist i<\mathrm{lh}(a))(\forall j< i)[(a)_j=(b)_j\land(a)_i\lhd(b)_i]\lor\\ & (\mathrm{lh}(a)<\mathrm{lh}(b)\land(\forall i<\mathrm{lh}(a))[(a)_i=(b)_i])\end{align*}} 構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle a\unlhd b:\Leftrightarrow a\lhd b\or a=b}

このようにすれば計算可能(原始再帰)な順序数表記構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle} を得ることができる．