細 (→概要) |
細 (→計算可能性) |
||
65行目: | 65行目: | ||
<math>\ulcorner\cdot\urcorner\colon\mathsf{OT}\to\mathbb{N}</math>を帰納的に定義する. |
<math>\ulcorner\cdot\urcorner\colon\mathsf{OT}\to\mathbb{N}</math>を帰納的に定義する. |
||
# <math>\ulcorner\overline{0}\urcorner:=0</math>. |
# <math>\ulcorner\overline{0}\urcorner:=0</math>. |
||
− | # <math>\ulcorner\overline{\omega}^{a_0}\overline{+}\cdots\overline{+}\overline{\omega}^{a_n}\urcorner:=\langle\ulcorner a_0\urcorner,\ldots\ulcorner a_n\urcorner\rangle</math> |
+ | # <math>\ulcorner\overline{\omega}^{a_0}\overline{+}\cdots\overline{+}\overline{\omega}^{a_n}\urcorner:=\langle\ulcorner a_0\urcorner,\ldots\ulcorner a_n,\urcorner\rangle</math> |
ここで<math>\langle\cdot\rangle</math>は適当な(計算可能)[[対関数]]とする.また<math>\ulcorner\cdot\urcorner</math>の値域を<math>\ulcorner\mathsf{OT}\urcorner\subseteq\mathbb{N}</math>とし,<math>\ulcorner\mathsf{OT}\urcorner</math>を'''順序数コード''' (ordinal code) という. |
ここで<math>\langle\cdot\rangle</math>は適当な(計算可能)[[対関数]]とする.また<math>\ulcorner\cdot\urcorner</math>の値域を<math>\ulcorner\mathsf{OT}\urcorner\subseteq\mathbb{N}</math>とし,<math>\ulcorner\mathsf{OT}\urcorner</math>を'''順序数コード''' (ordinal code) という. |
||
|} |
|} |
2020年7月7日 (火) 08:18時点における版
カントール標準形 (Cantor normal form) とはカントール[1]によって定義され,また証明された順序数の標準形である.これは進法,及び遺伝的記法の順序数への一般化と考えることができる.
概要
順序数が底 (basis) のカントール標準形で表されているとはとに対し
となっていることである.またの場合は底によらすでカントール標準形で表されているとする.カントール標準形定理 (Cantor normal form theorem) は順序数に対しカントール標準形は一意に定まることを主張する.
カントール標準形で一番重要なのは底がに場合で,各であるからは,有限回の和を用いてと表せることを用いれば以下の系を特殊なカントール標準形を得ることができる.
ここでとする.このような形でカントール標準形は述べられる場合もある.
順序数表記
底のカントール標準形にてと表したとき,がとなるような最小の順序数であったことを思い返せばに対してとなる.よってもカントール標準形で表し,とし,をカントール標準形で表し,この操作を有限回繰り返すことでとのみを用いて未満の順序数を表すことができる.なぜならで順序数の無限降下列は存在しないからである.
この事実を用いて順序数表記を構成することができる。ただし上記の「順序数表示方法」自体は集合論において意味を持つものであり、算術で意味を持つ順序数表記そのものではないことに注意する。以下で、まず集合論内での部分集合として整列順序集合を定義し、その後が順序数表記であること(集合論を用いずに算術内で再帰的にが定義可能であること)を示す。
項とその割り当て
定義2.1 項 (term) |
---|
を定数記号,を一変数関数記号,を多変数関数記号とする. 項 (term) は以下のように帰納的に定義される.
項の集合をとする. |
このように項で順序数を表現できるので,項に対応する順序数も帰納的に定義する.
定義2.2 割り当て (assignment) |
---|
割り当て (assignment) を以下のように帰納的に定義する.
|
しかしとなるは一意に定まるとは限らない.よって一意に定まるようなの部分集合を定める.これを定めるためにカントール標準形を用いる.
定義2.3 順序数項 (ordinal term) |
---|
順序数項 (ordinal term) は以下のように帰納的に定義される.
順序数項全体をとする. また上の順序をと定める. |
計算可能性
前節で定めたがの順序となる,正確に言えばとなるのは定義より明らかであるが,は未だに集合論的に定められていて計算可能性に対する情報を与えてくれない.そのためにはをコード化する必要があり,また実際に比較するためのアルゴリズムを与える必要がある.
定義2.4 順序数コード (ordinal code) |
---|
を帰納的に定義する.
ここでは適当な(計算可能)対関数とする.またの値域をとし,を順序数コード (ordinal code) という. |
さてが計算可能集合であることを示したいわけであるが,そのためには順序数項を定義するときにで比較していたためそれに対応する上の計算可能な二項関係構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \lhd} を同時再帰的に定義する必要がある.カントール標準形で,と表されたものを比較するためにはを辞書式順序で比較すれば良いことを思い出せば以下のように定義し直せるであろう.
定義2.5 |
---|
|
このようにすれば計算可能(原始再帰)な順序数表記構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle} を得ることができる.
参考文献
- ↑ Cantor, Georg. "Beiträge zur Begründung der transfiniten Mengenlehre." Mathematische Annalen 46.4 (1895): 481-512.