細 (→カントール標準形に伴う基本列) |
細編集の要約なし |
||
(4人の利用者による、間の14版が非表示) | |||
1行目: | 1行目: | ||
− | '''カントール標準形''' (Cantor normal form) とはカントール<ref name="Cantor1895">Cantor, Georg. "Beiträge zur Begründung der transfiniten Mengenlehre." Mathematische Annalen 46.4 (1895): 481-512.</ref>によって定義され,また証明された順序数の標準形である.これは<math>n</math>進法,及び遺伝的記法の順序数への一般化と考えることができる. |
+ | '''カントール標準形''' (Cantor normal form) とはカントール<ref name="Cantor1895">Cantor, Georg. "Beiträge zur Begründung der transfiniten Mengenlehre." Mathematische Annalen 46.4 (1895): 481-512.</ref>によって定義され,また証明された[[順序数]]の標準形である.これは<math>n</math>進法,及び遺伝的記法の順序数への一般化と考えることができる. |
== 概要 == |
== 概要 == |
||
9行目: | 9行目: | ||
となっていることである.また<math>\alpha=0</math>の場合は底によらす<math>\alpha=0</math>でカントール標準形で表されているとする.'''カントール標準形定理''' (Cantor normal form theorem) は順序数<math>\alpha</math>に対しカントール標準形は一意に定まることを主張する. |
となっていることである.また<math>\alpha=0</math>の場合は底によらす<math>\alpha=0</math>でカントール標準形で表されているとする.'''カントール標準形定理''' (Cantor normal form theorem) は順序数<math>\alpha</math>に対しカントール標準形は一意に定まることを主張する. |
||
+ | {| class="wikitable" |
||
⚫ | |||
+ | ! 定理1.1 (カントール正規形定理) |
||
+ | |- |
||
+ | | <math>\beta > 1</math>とする.このとき,任意の順序数 <math>\alpha</math>について,ある自然数 <math>(0\leq)n<\omega</math>と順序数 <math>\alpha_1,\cdots,\alpha_n,\gamma_1,\cdots,\gamma_n</math>が存在して<math>\gamma_1,\cdots,\gamma_n<\beta</math>,<math>\alpha\geq\alpha_1>\cdots>\alpha_n</math>を満たし,<br /> |
||
+ | :<math>\alpha=\beta^{\alpha_1}\cdot\gamma_1+\cdots+\beta^{\alpha_n}\cdot\gamma_n</math> |
||
+ | が成り立つ. |
||
+ | |} |
||
+ | |||
⚫ | |||
<math>\alpha=\omega^{\alpha_1}+\cdots+\omega^{\alpha_n}</math> |
<math>\alpha=\omega^{\alpha_1}+\cdots+\omega^{\alpha_n}</math> |
||
17行目: | 25行目: | ||
カントール標準形について重要となるのは以下の定理である. |
カントール標準形について重要となるのは以下の定理である. |
||
{| class=wikitable |
{| class=wikitable |
||
− | ! '''定理1. |
+ | ! '''定理1.2''' |
|- |
|- |
||
| |
| |
||
29行目: | 37行目: | ||
底<math>\omega</math>のカントール標準形にて<math>\alpha=\omega^{\alpha_0}+\cdots+\omega^{\alpha_n}</math>と表したとき,[[Ε₀|<math>\varepsilon_0</math>]]が<math>\xi=\omega^\xi</math>となるような最小の順序数であったことを思い返せば<math>\alpha<\varepsilon_0</math>に対して<math>\alpha_i<\alpha</math>となる.よって<math>\alpha_i</math>もカントール標準形で表し,<math>\alpha_i=\omega^{\alpha_{i,0}}+\cdots+\omega^{\alpha_{i,m}}</math>とし,<math>\alpha_{i,j}</math>をカントール標準形で表し,この操作を有限回繰り返すことで<math>0</math>と<math>+,\xi\mapsto\omega^\xi</math>のみを用いて<math>\varepsilon_0</math>未満の順序数を表すことができる.なぜなら<math>\cdots<\alpha_{i,j}<\alpha_i<\alpha<\varepsilon_0</math>で順序数の無限降下列は存在しないからである. |
底<math>\omega</math>のカントール標準形にて<math>\alpha=\omega^{\alpha_0}+\cdots+\omega^{\alpha_n}</math>と表したとき,[[Ε₀|<math>\varepsilon_0</math>]]が<math>\xi=\omega^\xi</math>となるような最小の順序数であったことを思い返せば<math>\alpha<\varepsilon_0</math>に対して<math>\alpha_i<\alpha</math>となる.よって<math>\alpha_i</math>もカントール標準形で表し,<math>\alpha_i=\omega^{\alpha_{i,0}}+\cdots+\omega^{\alpha_{i,m}}</math>とし,<math>\alpha_{i,j}</math>をカントール標準形で表し,この操作を有限回繰り返すことで<math>0</math>と<math>+,\xi\mapsto\omega^\xi</math>のみを用いて<math>\varepsilon_0</math>未満の順序数を表すことができる.なぜなら<math>\cdots<\alpha_{i,j}<\alpha_i<\alpha<\varepsilon_0</math>で順序数の無限降下列は存在しないからである. |
||
− | この事実を用いて順序数表記を構成することができる。ただし上記の「順序数表示方法」自体は順序数表記そのものではないことに注意する。以下で、まず<math>\mathbb{N}</math>の部分集合として整列順序集合<math>(\mathsf{OT},\prec)</math>を定義し、その後<math>(\mathsf{OT},\prec)</math>が順序数表記であること(つまり<math>\mathsf{OT}</math>と<math>\prec</math>が計算可能であること)を示す。 |
+ | この事実を用いて[[順序数表記]]を構成することができる。ただし上記の「順序数表示方法」自体は順序数表記そのものではないことに注意する。以下で、まず<math>\mathbb{N}</math>の部分集合として整列順序集合<math>(\mathsf{OT},\prec)</math>を定義し、その後<math>(\mathsf{OT},\prec)</math>が順序数表記であること(つまり<math>\mathsf{OT}</math>と<math>\prec</math>が計算可能であること)を示す。 |
=== 項とその割り当て === |
=== 項とその割り当て === |
||
37行目: | 45行目: | ||
|- |
|- |
||
| |
| |
||
− | <math>\overline{0}</math> |
+ | <math>\overline{0}</math>,<math>\overline{\omega}^{\cdot}</math>,<math>\overline{+}</math>を記号とする. |
'''項''' (term) は以下のように帰納的に定義される. |
'''項''' (term) は以下のように帰納的に定義される. |
||
# <math>\overline{0}</math>は項である. |
# <math>\overline{0}</math>は項である. |
||
79行目: | 87行目: | ||
<math>\langle x_0,\ldots,x_{n-1}\rangle:=\prod_{i<n}p_i^{1+x_i}</math> |
<math>\langle x_0,\ldots,x_{n-1}\rangle:=\prod_{i<n}p_i^{1+x_i}</math> |
||
− | と定める.また<math>\exp(x,i):=\max\{y\leq x\mid p_i^y |
+ | と定める.また<math>\exp(x,i):=\max\{y\leq x\mid p_i^y|x\}</math>とし, |
# <math>(x)_i:=\exp(x,i)-1</math>. |
# <math>(x)_i:=\exp(x,i)-1</math>. |
||
# <math>\mathrm{lh}(x)=\min\{i\leq x\mid \exp(x,i)=0\}</math>. |
# <math>\mathrm{lh}(x)=\min\{i\leq x\mid \exp(x,i)=0\}</math>. |
||
+ | # <math>x^\frown y:=x\prod_{i<\mathrm{lh}(y)}p^{1+(y)_i}_{\mathrm{lh}(x)+i}</math>. |
||
− | とする.直感的には<math>\langle x_0,\ldots,x_{n-1}\rangle</math>は列のコードを表していて,<math>(x)_i</math>は<math>x</math>がコードする列の<math>i</math>番目の要素,<math>\mathrm{lh}(x)</math>は<math>x</math>がコードする列の長さを表す.さてこれらは全て原始再帰的関数になる<ref>新井敏康.数学基礎論.岩波書店.2011.</ref> |
+ | とする.直感的には<math>\langle x_0,\ldots,x_{n-1}\rangle</math>は列のコードを表していて,<math>(x)_i</math>は<math>x</math>がコードする列の<math>i</math>番目の要素,<math>\mathrm{lh}(x)</math>は<math>x</math>がコードする列の長さを表す.そして<math>x^\frown y</math>は<math>x,y</math>がコードする列の結合のコードを表している.さてこれらは全て原始再帰的関数になる<ref>新井敏康.数学基礎論.岩波書店.2011.</ref> |
|} |
|} |
||
この列のコード化を用いることで順序数項のコードも定義することができる. |
この列のコード化を用いることで順序数項のコードも定義することができる. |
||
145行目: | 154行目: | ||
2.は<math>\omega^{\alpha+1}</math>という形をしていることから<math>\mathrm{lh}(a)=1</math>であり,<math>\|(a)_0\|_\mathcal{O}=\alpha+1=\alpha+\omega^0</math>であるから<math>\mathrm{lh}(a)=1\land((a)_0)_{\mathrm{lh}((a)_0)-1}=\langle 0\rangle</math>と表せて計算可能である. |
2.は<math>\omega^{\alpha+1}</math>という形をしていることから<math>\mathrm{lh}(a)=1</math>であり,<math>\|(a)_0\|_\mathcal{O}=\alpha+1=\alpha+\omega^0</math>であるから<math>\mathrm{lh}(a)=1\land((a)_0)_{\mathrm{lh}((a)_0)-1}=\langle 0\rangle</math>と表せて計算可能である. |
||
3.は後続順序数でないことから<math>\mathrm{lh}((a)_0)=1\land(a)_0\neq 0</math>であるか<math>\mathrm{lh}((a)_0)>1\land((a)_0)_{\mathrm{lh}((a)_0)-1}\neq\langle 0\rangle</math>と表すことができて計算可能である. |
3.は後続順序数でないことから<math>\mathrm{lh}((a)_0)=1\land(a)_0\neq 0</math>であるか<math>\mathrm{lh}((a)_0)>1\land((a)_0)_{\mathrm{lh}((a)_0)-1}\neq\langle 0\rangle</math>と表すことができて計算可能である. |
||
+ | |||
+ | よって以下のように計算可能な基本列が定められる. |
||
+ | {| class=wikitable |
||
+ | ! '''定義3.1''' |
||
+ | |- |
||
+ | | |
||
+ | <math>\langle\langle 0\rangle\rangle\unlhd a</math>に対し<math>a[n]</math>を以下のように超限再帰で定義する. |
||
+ | # <math>\|a\|_\mathcal{O}=\omega</math>であるとき<math>n</math>に関して再帰的に<math>\omega[0]:=0,\omega[n+1]:=\omega[n]^\frown\langle\langle 0\rangle\rangle</math>. |
||
+ | # <math>\|a\|_\mathcal{O}=\omega^{\alpha+1}</math>であるとき<math>(a)_0^-</math>を<math>(a)_0</math>がコードする列の最後の要素を削った列のコードとし,<math>n</math>に関して帰納的に<math>a[0]:=0,a[n+1]:=a[n]^\frown\langle(a)_0^-\rangle</math>. |
||
+ | # <math>\lambda</math>を極限順序数とし<math>\|a\|_\mathcal{O}=\omega^\lambda</math>であるとき,<math>a[n]:=\langle(a)_0[n]\rangle</math>. |
||
+ | # カントール標準形で<math>\|a\|_\mathcal{O}=\omega^{\alpha_1}+\cdots\omega^{\alpha_m}</math>とするとき,<math>a</math>のコードする最後の行を削った列のコードを<math>a^-</math>とし,<math>a[n]:={a^-}^\frown\langle(a)_{\mathrm{lh}(a)-1}[n]\rangle</math>とする. |
||
+ | |} |
||
+ | よって計算可能な基本列を得ることができる.この定義の系として以下が分かる. |
||
+ | {| class=wikitable |
||
+ | ! '''定理3.2''' |
||
+ | |- |
||
+ | | |
||
+ | <math>\alpha<\varepsilon_0</math>に対して上の標準形による急増加関数<math>f_\alpha</math>は計算可能である. |
||
+ | |} |
||
== 参考文献 == |
== 参考文献 == |
||
<references/> |
<references/> |
||
+ | |||
− | {{stub}} |
||
+ | [[en:Cantor normal form]] |
||
− | [[en:Ordinal_notation#Ordinal_notation_associated_to_iterated_Cantor_normal_form]] |
||
+ | |||
+ | {{DEFAULTSORT:かんとおるひようしゆんけい}} |
||
[[カテゴリ:順序数]] |
[[カテゴリ:順序数]] |
||
[[カテゴリ:数理論理学]] |
[[カテゴリ:数理論理学]] |
||
+ | [[カテゴリ:順序数表記]] |
||
+ | [[カテゴリ:集合論]] |
2021年3月6日 (土) 02:03時点における版
カントール標準形 (Cantor normal form) とはカントール[1]によって定義され,また証明された順序数の標準形である.これは進法,及び遺伝的記法の順序数への一般化と考えることができる.
概要
順序数が底 (basis) のカントール標準形で表されているとはとに対し
となっていることである.またの場合は底によらすでカントール標準形で表されているとする.カントール標準形定理 (Cantor normal form theorem) は順序数に対しカントール標準形は一意に定まることを主張する.
定理1.1 (カントール正規形定理) |
---|
とする.このとき,任意の順序数 について,ある自然数 と順序数 が存在して,を満たし, が成り立つ. |
カントール標準形で一番重要なのは底がの場合で,各であるからは,有限回の和を用いてと表せることを用いれば以下の系を特殊なカントール標準形を得ることができる.
ここでとする.このような形でカントール標準形は述べられる場合もある.
カントール標準形について重要となるのは以下の定理である.
定理1.2 |
---|
,とするとき以下は同値である.
ここでは辞書式順序 (lexicographical order) である.すなわちまず,比較し等しかったらを比較して,順番に比していく.あるでになった時点で比較を終え,全てのに対してなら,を比較することでが定まる. |
順序数表記
底のカントール標準形にてと表したとき,がとなるような最小の順序数であったことを思い返せばに対してとなる.よってもカントール標準形で表し,とし,をカントール標準形で表し,この操作を有限回繰り返すことでとのみを用いて未満の順序数を表すことができる.なぜならで順序数の無限降下列は存在しないからである.
この事実を用いて順序数表記を構成することができる。ただし上記の「順序数表示方法」自体は順序数表記そのものではないことに注意する。以下で、まずの部分集合として整列順序集合を定義し、その後が順序数表記であること(つまりとが計算可能であること)を示す。
項とその割り当て
定義2.1.1 項 (term) |
---|
,,を記号とする. 項 (term) は以下のように帰納的に定義される.
項の集合をとする. |
このように項で順序数を表現できるので,項に対応する順序数も帰納的に定義する.
定義2.1.2 割り当て (assignment) |
---|
割り当て (assignment) を以下のように帰納的に定義する.
|
しかしとなるは一意に定まるとは限らない.よって一意に定まるようなの部分集合を定める.これを定めるためにカントール標準形を用いる.
定義2.1.3 順序数項 (ordinal term) |
---|
順序数項 (ordinal term) は以下のように帰納的に定義される.
順序数項全体をとする. また上の順序をと定める. |
計算可能性
前節で定めたがの順序となる,正確に言えばとなるのは定義より明らかであるが,は未だに集合論的に定められていて計算可能性に対する情報を与えてくれない.そのためにはをコード化する必要があり,また実際に比較するためのアルゴリズムを与える必要がある.
さて前述の順序数表記をコード化する前に列に関するコード化について触れなければならない.
定義2.2.1 列のコード |
---|
以下を素数の数え上げとして
と定める.またとし,
とする.直感的にはは列のコードを表していて,はがコードする列の番目の要素,はがコードする列の長さを表す.そしてはがコードする列の結合のコードを表している.さてこれらは全て原始再帰的関数になる[2] |
この列のコード化を用いることで順序数項のコードも定義することができる.
定義2.2.2 順序数コード (ordinal code) |
---|
を帰納的に定義する.
の値域をとし,を順序数コード (ordinal code) という. |
さてが計算可能集合であることを示したいわけであるが,そのためには順序数項を定義するときにで比較していたためそれに対応する上の計算可能な二項関係構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \lhd} を同時再帰的に定義する必要がある.ここで定理1.1.よりカントール標準形で,と表されたものを比較するためにはを辞書式順序で比較すれば良いことを思い出せば以下のように定義し直せるであろう.ここで重要な役割を果たしているのはとなっていることで再帰が回るのはここに所以する.
定義2.2.3 |
---|
|
この定義はの定義に基づいていて,で比較していたものを相互再帰ですでに定義されている,構文解析に失敗 (不明な関数「\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 |
---|
に対しを以下のように超限再帰で定義する.
|
ただし,この定義では基本列が計算可能であるということを導かない.よってこの基本列で定義される急増加関数も計算可能であるということも導かれない.よって2節で定義した計算可能な順序数表記に対して基本列を定義しなければならないことに注意しよう.
この基本列の定義では場合分けを用いていることから,その場合分けを構文解析に失敗 (不明な関数「\lhd」): {\displaystyle \langle\ulcorner\mathsf{OT}\urcorner,\lhd\rangle} に於いて計算可能にできるか否かが問題になる.すなわち以下のような関係が計算可能となる必要がある.
- .
- .
- .ただしは極限順序数とする.
- カントール標準形で.
ここではコードから対応する順序数項を割り当てる写像との合成である.
4.は1,2,3.いずれでもないと表すことができるので1,2,3.についてのみ考える. 1.はであることからと同値であるため計算可能である. 2.はという形をしていることからであり,であるからと表せて計算可能である. 3.は後続順序数でないことからであるかと表すことができて計算可能である.
よって以下のように計算可能な基本列が定められる.
定義3.1 |
---|
構文解析に失敗 (不明な関数「\unlhd」): {\displaystyle \langle\langle 0\rangle\rangle\unlhd a} に対しを以下のように超限再帰で定義する.
|
よって計算可能な基本列を得ることができる.この定義の系として以下が分かる.
定理3.2 |
---|
に対して上の標準形による急増加関数は計算可能である. |