私は巨大数界隈で間違った情報が広まっていたり、正しい情報であったとしてもその出典が分からないという状況に不満を感じています。そんな状況を解決するために、確かな論文を利用しましょう。
この記事では "Ordinal Notations Based on a Weakly Mahlo Cardinal" (Michael Rathjen) という論文を読み、その中から出典として使える部分を抜き出してリストアップします。そのリストは記事を書きたいときに簡単に引用できるように整えてあります。私が利用するためのものですが、他の人にも使ってもらいたいと思っています。
表示されない数式[]
\[ \newcommand{\ordinarycolon}{:} \newcommand{\vcentcolon}{\mathrel{\mathop\ordinarycolon}} \newcommand{\coloneqq}{\vcentcolon\mathrel{\mkern-1.2mu}=} \]
形式[]
見出しはハーバード方式による出典の記法です。それぞれの節は一文に対応します。本文は訳であり、その後にもしあれば解説が続きます。
Rathjen 1990, p. 1[]
この部分は Introduction です。ここに限っては一次資料ではなく二次資料として使うこともできるでしょう。
順序数解析の最先端[]
今までに限るならば、 \( \Delta ^ 1 _ 2 \)-内包とバー帰納法により構成される二階算術のサブシステムが、その証明論的順序を私たちが算出できる最も強い理論だ。
原文[]
Up to now, the subsystem of second order arithmetic with \( \Delta _ 2 ^ 1 \)-comprehension and Bar-induction is the strongest for which we have a computation of its proof-theoretic ordinal.
解説[]
「今まで」は、この論文が書かれるまでとなる。つまり1990年までと思っていいだろう。
\( \Delta _ 2 ^ 1 \)-内包とバー帰納法により構成される二階算術のサブシステム (the subsystem of second order arithmetic with \( \Delta _ 2 ^ 1 \)-comprehension and Bar-induction) を略記するならば \( \Delta _ 2 ^ 1 \operatorname{-CA} + \mathrm{BI} \) となるであろう。この体系が何であるか理解するためには Googology Wiki の second-order arithmetic を参照すればいいであろう。なぜか Wikipedia や nLab より詳しい。巨大数研究wikiに訳もあるが、進んでいないため大して変わらない。
\( \Delta _ 2 ^ 1 \)-内包 (\( \Delta _ 2 ^ 1 \operatorname{-CA} \), \( \Delta _ 2 ^ 1 \)-comprehension) とは \( \Delta _ 2 ^ 1 \) 文に対する内包公理である。詳細に書くならば \( \forall \phi \in \Delta _ 2 ^ 1 \ldotp [ \exists X \ldotp \forall x \ldotp x \in X \leftrightarrow \phi ( x ) ] \) となるであろう。ここで角括弧は公理図式であることを表す。
\( \Sigma _ n ^ 1 \) と \( \Pi _ n ^ 1 \) と \( \Delta _ n ^ 1 \) とは、解析的階層 (analytical hierarchy) のことであり、算術的階層 (arithmetical hierarchy, 算術的階層) を二階算術の論理式に対して拡張したものである。そもそも旧来の算術的階層はペアノ算術の論理式を \( \Sigma _ n ^ 0 \) と \( \Pi _ n ^ 0 \) と分類するものである。そのペアノ算術の式における定義は以下のようなものであった。
- ある式 \( \phi \) が \( \Sigma _ n ^ 0 \) に属する条件：
- \( n = 0 \) のとき、 \( \phi \) の量化が全て有界であれば \( \Sigma _ n ^ 0 \) に属する。
- \( n > 0 \) のとき、 \( \Pi _ { n - 1 } ^ 0 \) に属する文 \( \psi \) が存在し、さらにある自然数 \( k \) が存在して、 \( \psi \) へと \( k \) 個の変数に対する存在量化を加えた \( \exists n _ 0 \ldotp \exists n _ 1 \ldotp \cdots \exists n _ k \ldotp \psi \)が \( \phi \) と論理的に等価になるとき、 \( \phi \) は \( \Sigma _ n ^ 0 \) に属する。
- ある式 \( \phi \) が \( \Pi _ n ^ 0 \) に属する条件：
- \( n = 0 \) のとき、 \( \phi \) の量化が全て有界であれば \( \Pi _ n ^ 0 \) に属する。
- \( n > 0 \) のとき、 \( \Sigma _ { n - 1 } ^ 0 \) に属する文 \( \psi \) が存在し、さらにある自然数 \( k \) が存在して、 \( \psi \) へと \( k \) 個の変数に対する全称量化を加えた \( \forall n _ 0 \ldotp \forall n _ 1 \ldotp \cdots \forall n _ k \ldotp \psi \)が \( \phi \) と論理的に等価になるとき、 \( \phi \) は \( \Pi _ n ^ 0 \) に属する。
解析的階層 (analytical hierarchy) の定義は上記の定義を少し変えて、以下のようになる。二階算術の式を分類するものになっている。 なお、算術的階層も自然に二階算術の式に対して定義できることに注意してほしい。
- ある式 \( \phi \) が \( \Sigma _ n ^ 1 \) に属する条件：
- \( n = 0 \) のとき、 \( \phi \) の量化が全て自然数に対するものであれば \( \Sigma _ n ^ 1 \) に属する。
- \( n > 0 \) のとき、 \( \Pi _ { n - 1 } ^ 1 \) に属する文 \( \psi \) が存在し、さらにある自然数 \( k \) が存在して、 \( \psi \) へと \( k \) 個の集合の変数に対する存在量化を加えた \( \exists X _ 0 \ldotp \exists X _ 1 \ldotp \cdots \exists X _ k \ldotp \psi \)が \( \phi \) と論理的に等価になるとき、 \( \phi \) は \( \Sigma _ n ^ 1 \) に属する。
- ある式 \( \phi \) が \( \Pi _ n ^ 1 \) に属する条件：
- \( n = 0 \) のとき、 \( \phi \) の量化が全て自然数に対するものであれば \( \Pi _ n ^ 1 \) に属する。
- \( n > 0 \) のとき、 \( \Sigma _ { n - 1 } ^ 1 \) に属する文 \( \psi \) が存在し、さらにある自然数 \( k \) が存在して、 \( \psi \) へと \( k \) 個の集合変数に対する全称量化を加えた \( \forall X _ 0 \ldotp \forall X _ 1 \ldotp \cdots \forall X _ k \ldotp \psi \)が \( \phi \) と論理的に等価になるとき、 \( \phi \) は \( \Pi _ n ^ 1 \) に属する。
バー帰納法 (\( \mathrm{BI} \), bar induction) とは、二階算術の式で表せる整礎半順序 \( \_ \prec \_ \) 全てに対して \( \forall X \ldotp ( \forall j \ldotp ( \forall i \prec j \ldotp i \in X ) \rightarrow j \in X ) \rightarrow \forall n \ldotp n \in X \) が成り立つという公理図式である。ここで \( \_ \in X \) は \( \phi ( \_ ) \) に取り換えることができる。なお wikipedia においては relations to other fields にある reverse mathematics における bar induction として記載されているものに該当すると思われる。ここで Wikipedia および Googology Wiki の書き方では整礎半順序であるという性質がメタなものなのかはっきりしないので Well-Ordering Principles and Bar Induction (Rathjen and Vizcaíno 2015) の p. 5 にある Definition 1.8 を参考にして定義を書こう。
二項関係 \( \_ \prec \_ \) と、二階算術においての任意の項 \( F ( \_ ) \) を渡る。一つ目の述語は progressiveness についてである。
\[ \mathrm{Prog} ( \_ \prec \_, F ) \coloneqq \forall x \ldotp ( \forall y \ldotp y \prec x \rightarrow F ( y ) ) \rightarrow F ( x ) \]
二つ目の述語は transfinite induction についてである。
\[ \mathbf{TI} ( \_ \prec \_, F ) \coloneqq \mathrm{Prog} ( \_ \prec \_, F ) \rightarrow \forall x \ldotp F ( x ) \]
三つ目の述語は well-foundedness についてである。アンダースコアを使っている部分は不思議かもしれないが部分は \( F ( x ) \coloneqq x \in X \) というように展開される。
\[ \mathrm{WF} ( \_ \prec \_ ) \coloneqq \forall X \ldotp \mathbf{TI} ( \_ \prec \_, \_ \in X ) \]
これらによりバー帰納法という公理図式が以下のように定義される。ここで \( \_ \prec \_ \) と \( F \) の引数は両方とも自然数であるか両方とも集合であるかのどちらかである。どちらでもいいような書き方になっていることに注意してほしい。
\[ \forall \_ \prec \_ \ldotp \forall F \ldotp [ \mathrm{WF} ( \_ \prec \_ ) \rightarrow \mathbf{TI} ( \_ \prec \_, F ) ] \]
ここで \( \_ \prec \_ \) は整礎半順序ではなく整礎関係であることだけが要請されているが、これはバリエーションと考えていいだろう。あるいは Googology Wiki の second-order arithmetic の方が間違っているのかもしれない。
Googology Wiki (second-order arithmetic) では整礎半順序であることが条件とされ、 Wikipedia (bar induction) では整列順序であることが条件とされている。
それを成した人[]
それは [9] において Jäger と Pohlers により成された。
原文[]
This was done in [9] by Jäger and Pohlers.
解説[]
ここでの [9] は Eine beweistheoretische Untersuchung von \( ( \Delta _ 2 ^ 1 \operatorname{-CA} ) + ( \mathrm{BI} ) \) und verwandter Systeme (Jäger and Pohlers 1982) のことである。タイトルを Google 翻訳で英訳すると A theoretical proof of \( ( \Delta _ 2 ^ 1 \operatorname{-CA} ) + ( \mathrm{BI} ) \) and related systems となった。私はドイツ語に詳しくないので間違っているかもしれないが、たいだいこんな意味なのだろう。
Δ_2^1-CA + BI と KPi の関連[]
上記のシステムは Kripke-Pratek 集合論の拡張の一つと正々つながっていて、それは \( \mathrm{KPi} \) と呼ばれている。
原文[]
The above mentioned system is neatly connected to an extension of Kripke-Platek set theory, called \( \mathrm{KPi} \).
解説[]
上記のシステムを具体的に示すと \( \Delta _ 2 ^ 1 \operatorname{-CA} + \mathrm{BI} \) が \( \mathrm{KPi} \) と正々つながっている、とになる。この部分は意味が捉えきれなかったが、きちんとしたつながりがある、正確な対応関係がある、ぐらいの意味なのだろう。
まず Kripke-Pratek 集合論 (KP集合論, \( \mathrm{KP} \), Kripke-Platek set theory, Kripke–Platek set theory, Kripke-Pratek set theory, KP集合論) は挙げたリンク先を参照すれば意義は別の話として理解できるだろう。KP集合論は許容順序数の定義に使われるということが重要なことであろう。
許容集合 (admissible set) とは、それがKP集合論の推移モデルになるような集合である。具体的に言うならば \( A \models \mathrm{KP} \) の時 \( A \) は許容集合である。
許容順序数 (admissible ordinal) とは、 \( L _ \alpha \) が許容集合であるような順序数 \( \alpha \) のことである。チャーチ＝クリーネ順序数 \( \omega _ 1 ^ \mathrm{CK} \) は最小の非再帰順序数であると定義されるが、最小の許容順序数でもある。二つの間につながりはないように見えるのに不思議である。
ここで \( \mathrm{KP} \) のモデルになることが分かっているので、許容集合は具体的な性質の集まりにより定義されることを注意してほしい。これにより \( \mathrm{KP} \) の言語の上で許容集合という概念を定義できることになる。
\( \mathrm{KPi} \) とはKP集合論に一つの公理を付け加えた拡張である。それは、任意の集合 \( a \) に対して、それを含む許容集合 \( b \) が存在するというものである。
KPi の標準モデル[]
\( \mathrm{KPi} \) の標準モデルは、最初の再帰的到達不能順序数により形成された構成可能階層の始切片である。
原文[]
The standard model of \( \mathrm{KPi} \) is the initial segment of the constructible hierarchy formed by the first recursively inaccessible ordinal.
解説[]
標準モデルは、曖昧な言葉に感じるが、最も自然なモデルという意味合いでいいだろう。例えば、ペアノ算術の標準モデルは自然数の集合 \( \mathbb{N} \) であり、二階算術の標準モデルは \( ( \mathbb{N}, \mathfrak{P} ( \mathbb{N} ) ) \) である。ちなみに、ここで二階算術の標準モデルが二つ組で表されるのは、扱う対象に自然数と集合（要素は自然数）の二種類あるからである。
再帰的到達不能順序数は、許容順序数かつ許容順序数の極限で表される順序数である。これには、正則基数かつ正則基数の極限で表される基数である到達不能基数との類似を見だすことが出来る。
構成可能階層は、構成可能集合の階層である。ウィキペディアでは構成可能集合を参照。最初は空集合から初めて、次々と超限再帰によって冪集合を取る操作を繰り返す階層が累積的階層であり、フォン・ノイマン宇宙と関連している。構成可能階層も、それと同じような定義だが、一つだけ違うところがある。冪集合を取る際に部分集合を集めるが、その時に構成可能な部分集合に限るのである。ここで「構成可能な」は一階述語論理の論理式によって部分集合が定義可能であることを指す。たとえば、全体の集合 \( \{ 1, 2 \} \in U \) に対して、部分集合 \( \{ 1 \} \) は \( \{ x \in U \mid x = 1 \} \) と定義可能である。この際、定義に使われる一階述語論理の論理式では、全ての量化は元々の集合の上を渡り、定数は全て元々の集合の要素である。
\( \alpha \) 番目の累積的階層は \( V _ \alpha \) であり \( \alpha \) 番目の構成可能階層は \( L _ \alpha \) と表される。
始切片は、順序集合に関する用語であり、ある順序集合 \( ( A, \_ < \_ ) \) があったとき、その \( a \) での始切片は \( \{ x \in A \mid x < a \} \) である。ここで \( L _ \alpha \) も \( \_ \subset \_ \) に関して始切片になっていることに注意。
ここまでくると、原文の意味を理解できる。すなわち、「 \( \mathrm{KPi} \) の標準モデルは \( L _ \alpha \) である。ただし \( \alpha \) は最小の再帰的到達不能順序数である」となる。
次のステップ[]
そして、 \( \Pi _ 2 ^ 1 \)-内包により構成される二階算術のサブシステムの順序数解析に向けた次のステップは、 \( \mathrm{L} ( \mu _ 0 ) \) の本質的な特徴を公理化している集合論によって提供される——ここで \( \mu _ 0 \) は最初の再帰的マーロ順序数を表している。
原文[]
So a next step towards an ordinal analysis of the subsystem of second order arithmetic based on \( \Pi _ 2 ^ 1 \)-comprehension is offered by a set theory which axiomatizes essential features of \( \mathrm{L} ( \mu _ 0 ) \), where \( \mu _ 0 \) denotes the first recursively Mahlo ordinal.
解説[]
...
KPM[]
このような理論を \( \mathrm{KPM} \) と呼ぼう。
原文[]
Let us call such a theory \( \mathrm{KPM} \).
解説[]
...
再帰的マーロ順序数の性質[]
ここでは、 \( \mu _ 0 \) は、一見したところでは再帰的巨大順序数の領域に依拠しない、高次再帰理論からの概念による記述を許す： \( \mu _ 0 \) はスーパージャンプにおいて再帰的ではない最初の順序数であり（ [7] を見よ）、特別な種類の非単調 \( \Pi _ 2 ^ 0 \)-定義の閉順序数の上限である（ [13] を見よ）。
原文[]
Now, \( \mu _ 0 \) allows descriptions by concepts from higher recursion theory which do not prima facie rely on the realm of recursively large ordinals: \( \mu _ 0 \) is the first ordinal which is not recursive in the superjump (see [7]), and \( \mu _ 0 \) is the supremum of the closure ordinals of non monotonic \( \Pi _ 2 ^ 0 \)-definitions of a special kind (see [13]).
解説[]
...
期待[]
...
原文[]
So it is much to be hoped for that a proof theory of KPM would be a starting point for a proof theory of the superjump as well as a proof theory of non monotonic inductive definitions.
解説[]
....