巨大数研究 Wiki
Advertisement
巨大数研究 Wiki

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

概要

順序数 (basis) のカントール標準形で表されているとはに対し

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

定理1.1 (カントール正規形定理)
とする.このとき,任意の順序数 について,ある自然数 と順序数 が存在してを満たし,

が成り立つ.

カントール標準形で一番重要なのは底がの場合で,各であるからは,有限回の和を用いてと表せることを用いれば以下の系を特殊なカントール標準形を得ることができる.

ここでとする.このような形でカントール標準形は述べられる場合もある.

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

定理1.2

とするとき以下は同値である.

ここで辞書式順序 (lexicographical order) である.すなわちまず,比較し等しかったらを比較して,順番に比していく.あるになった時点で比較を終え,全てのに対してなら,を比較することでが定まる.

順序数表記

のカントール標準形にてと表したとき,となるような最小の順序数であったことを思い返せばに対してとなる.よってもカントール標準形で表し,とし,をカントール標準形で表し,この操作を有限回繰り返すことでのみを用いて未満の順序数を表すことができる.なぜならで順序数の無限降下列は存在しないからである.

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

項とその割り当て

定義2.1.1 項 (term)

を記号とする. (term) は以下のように帰納的に定義される.

  1. は項である.
  2. が項ならも項である.
  3. が項ならも項である.

項の集合をとする.

このように項で順序数を表現できるので,項に対応する順序数も帰納的に定義する.

定義2.1.2 割り当て (assignment)

割り当て (assignment) を以下のように帰納的に定義する.

しかしとなるは一意に定まるとは限らない.よって一意に定まるようなの部分集合を定める.これを定めるためにカントール標準形を用いる.

定義2.1.3 順序数項 (ordinal term)

順序数項 (ordinal term) は以下のように帰納的に定義される.

  1. は順序数項である.
  2. が順序数項でならも順序数項である.

順序数項全体をとする.

また上の順序と定める.

計算可能性

前節で定めたの順序となる,正確に言えばとなるのは定義より明らかであるが,は未だに集合論的に定められていて計算可能性に対する情報を与えてくれない.そのためにはをコード化する必要があり,また実際に比較するためのアルゴリズムを与える必要がある.

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

定義2.2.1 列のコード

以下を素数の数え上げとして

と定める.またとし,

とする.直感的にはは列のコードを表していて,がコードする列の番目の要素,がコードする列の長さを表す.そしてがコードする列の結合のコードを表している.さてこれらは全て原始再帰的関数になる[2]

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

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

を帰納的に定義する.

の値域をとし,順序数コード (ordinal code) という.

さてが計算可能集合であることを示したいわけであるが,そのためには順序数項を定義するときにで比較していたためそれに対応する上の計算可能な二項関係構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \lhd} を同時再帰的に定義する必要がある.ここで定理1.1.よりカントール標準形でと表されたものを比較するためにはを辞書式順序で比較すれば良いことを思い出せば以下のように定義し直せるであろう.ここで重要な役割を果たしているのはとなっていることで再帰が回るのはここに所以する.

定義2.2.3
  1. 構文解析に失敗 (不明な関数「\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)]}
  2. 構文解析に失敗 (構文エラー): {\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*}}
  3. 構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle a\unlhd b:\Leftrightarrow a\lhd b\or a=b}

この定義はの定義に基づいていて,で比較していたものを相互再帰ですでに定義されている,構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle \unlhd} で置き換えたものになる.その構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle \unlhd}の要素であるかを確認し構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \lhd} の辞書式順序で比較するということを意図している.

このようにすれば計算可能(原始再帰)な順序数表記構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle} を得ることができる. ここで構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle\cong\langle\varepsilon_0,<\rangle} (これはカントール標準形による順序数表記なら簡単に示せるがより強い順序数表記,例えば順序数崩壊関数に伴う順序数表記の場合明らかではない)であることから以下の系が導かれる.

系2.2.4

である.ただしチャーチ・クリーネ順序数である.

証明.チャーチ・クリーネ順序数の定義と構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle\cong\langle\varepsilon_0,<\rangle}が計算可能であり構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \lhd} が計算可能であることから明らかである.□

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

カントール標準形を用いることでに対して標準的な基本列を定めることができる.

定義3.1

に対しを以下のように超限再帰で定義する.

  1. ,ただしは極限順序数.
  2. カントール標準形でとするとき

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

この基本列の定義では場合分けを用いていることから,その場合分けを構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle} に於いて計算可能にできるか否かが問題になる.すなわち以下のような関係が計算可能となる必要がある.

  1. .ただしは極限順序数とする.
  2. カントール標準形で

ここではコードから対応する順序数項を割り当てる写像の合成である.

4.は1,2,3.いずれでもないと表すことができるので1,2,3.についてのみ考える. 1.はであることからと同値であるため計算可能である. 2.はという形をしていることからであり,であるからと表せて計算可能である. 3.は後続順序数でないことからであるかと表すことができて計算可能である.

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

定義3.1

構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle \langle\langle 0\rangle\rangle\unlhd a} に対しを以下のように超限再帰で定義する.

  1. であるときに関して再帰的に
  2. であるときがコードする列の最後の要素を削った列のコードとし,に関して帰納的に
  3. を極限順序数としであるとき,
  4. カントール標準形でとするとき,のコードする最後の行を削った列のコードをとし,とする.

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

定理3.2

に対して上の標準形による急増加関数は計算可能である.

参考文献

  1. Cantor, Georg. "Beiträge zur Begründung der transfiniten Mengenlehre." Mathematische Annalen 46.4 (1895): 481-512.
  2. 新井敏康.数学基礎論.岩波書店.2011.
Advertisement