非再帰順序数は、分かりやすく言えば、それに届く順序数表記を決して作ることが出来ないほど大きい順序数です[note 1]。
チャーチ゠クリーネ順序数[]
チャーチ゠クリーネ順序数は、まさしく非再帰順序数の入り口となるべき順序数でしょう。チャーチ゠クリーネ順序数は最小の非再帰順序数なのです。
すなわち、次のような定義が成立します。
定義 1.1 |
---|
チャーチ゠クリーネ順序数は、フォン・ノイマン順序数として扱うならば、全ての再帰順序数の集合そのものである。 |
この定義により、チャーチ゠クリーネ順序数が能く定義されているかどうかも考えなければなりません。
定理 1.1 |
---|
全ての再帰順序数のクラスは集合である。全ての再帰順序数の集合は存在する。最小の非再帰順序数は存在する。チャーチ゠クリーネ順序数は存在する。 証明: 最小の非可算順序数は非再帰順序数である。ゆえに、最小の非可算順序数から「 \( \alpha \) は再帰順序数である」で分出すれば、チャーチ゠クリーネ順序数が構成できる。 |
最小の非可算順序数と最小の非再帰順序数は似ています。どちらも、加法や乗法や冪乗[note 2]などに対して閉じています。最小の非可算順序数は \( \omega _ 1 \) として表記されますが、それに倣ってかチャーチ゠クリーネ順序数も \( \omega _ 1 ^ \mathrm{CK} \) と表記されます。
コラム 1.1 |
---|
ひと昔は、 Googology Wiki において、チャーチ゠クリーネ順序数は、急増加関数に与えると、ビジービーバー関数を近似できるものとされていました。しかし、正確な証明がなく、何の基本列を使うのかも明示されていなかったので、今では記述が削除されています。 |
許容順序数[]
許容順序数は、チャーチ゠クリーネ順序数の先への道を示します。チャーチ゠クリーネ順序数の定義においては、 \( \omega _ 2 ^ \mathrm{CK} \) などを定義していませんでした。これは許容順序数という概念を使って定義されます。
定義 2.1 |
---|
許容順序数は、 \( \mathrm{L} _ \alpha \) が \( \mathsf{KP} \) の推移的モデルとなる順序数のことである。 |
最小の許容順序数は \( \omega \) です。その次の許容順序数は \( \omega _ 1 ^ \mathrm{CK} \) です。というわけで、 \( \omega _ 0 ^ \mathrm{CK} = \omega \) と定めてしまいましょう。さらに、 \( \omega _ 1 ^ \mathrm{CK} \) よりも大きい最初の許容順序数を \( \omega _ 2 ^ \mathrm{CK} \) と書くことにしましょう。さらに同じように、一般の自然数 \( n \) に対して \( \omega _ n ^ \mathrm{CK} \) を定めましょう。
定義 2.2 |
---|
一般の自然数 \( n \) に対して \( \omega _ n ^ \mathrm{CK} \) を次のように定める。
|
さて、こんな回りくどいことをしなくても許容順序数そのものを数え上げることで \( \omega _ n ^ \mathrm{CK} \) を定義できます。そして、そうすれば一般の順序数 \( \alpha \) に対しても \( \omega _ \alpha ^ \mathrm{CK} \) を定義できます。しかし、ここで困ったことが起きます。 \( \omega _ 0 ^ \mathrm{CK}, \omega _ 1 ^ \mathrm{CK}, \omega _ 2 ^ \mathrm{CK}, \omega _ 3 ^ \mathrm{CK}, \ldots \) の極限の順序数は許容順序数になりません。
定義 2.3 |
---|
\( \omega _ \alpha ^ \mathrm{CK} \) は \( \mathrm{Enum} ( \mathrm{closure} ( \{ \alpha : \textrm{\( \alpha \) is admissible.} \} ) ) ( \alpha ) \) である。 |
この定義では \( \sup \{ \omega _ 0 ^ \mathrm{CK}, \omega _ 1 ^ \mathrm{CK}, \omega _ 2 ^ \mathrm{CK}, \omega _ 3 ^ \mathrm{CK}, \ldots \} \) は \( \omega _ \omega ^ \mathrm{CK} \) になります。そして、 \( \omega \) 番目の許容順序数は \( \omega _ {\omega + 1} ^ \mathrm{CK} \) です。
\( \omega _ 0 ^ \mathrm{CK} \) は許容順序数です。 \( \omega _ 1 ^ \mathrm{CK} \) は許容順序数です。 \( \omega _ 2 ^ \mathrm{CK} \) は許容順序数です。 \( \omega _ \omega ^ \mathrm{CK} \) は許容順序数ではありません。 \( \omega _ {\omega + 1} ^ \mathrm{CK} \) は許容順序数です。 \( \omega _ {\omega + 2} ^ \mathrm{CK} \) は許容順序数です。 \( \omega _ {\omega + \omega} ^ \mathrm{CK} \) は許容順序数ではありません。何かに似ていませんでしょうか。そう、許容順序数は正則基数に似ているのです。
もちろん、許容順序数が正則基数と同じという訳ではありません。一般に、正則基数の方がずっと大きいです。たとえば、正則基数は必ず許容順序数です。あくまでも似ているというだけです。
許容順序数の極限[]
\( \omega _ \omega ^ \mathrm{CK} \) のような順序数は、許容順序数ではありません。しかし、 \( \omega + 1 \) や \( \varepsilon _ 0 \) や \( \omega _ 1 ^ \mathrm{CK} + 1 \) のような順序数とは何かが明らかに違います。それを明確に言語化する概念として、許容順序数の極限というものがあります。
定義 2.4 |
---|
ある順序数 \( \alpha \) が、許容順序数のみからなる \( \omega \) 以上の長さの狭義単調増加列の極限として表されるとき、その順序数を許容順序数の極限であるという。 |
許容順序数は正則基数に似ています。許容順序数の極限は極限基数に似ています。ある \( \omega _ \alpha ^ \mathrm{CK} \) が許容順序数ではなく許容順序数の極限でもないということはあり得ません。
再帰的到達不可能順序数[]
許容順序数は正則基数に似ている、許容順序数の極限は極限基数に似ている、両者は交わらないように見える、となると、許容順序数でもあり許容順序数の極限でもある順序数は、もし存在すれば到達不能基数に似ているのではないかと考えるのも自然なことでしょう。
定義 3.1 |
---|
ある順序数 \( \alpha \) が再帰的到達不可能順序数であるとは、それが許容順序数かつ許容順序数の極限であることである。 |
再帰的到達不可能順序数は到達不能基数に似ています。到達不能基数を崩壊させる順序数崩壊関数を、再帰的到達不可能順序数を崩壊させる順序数崩壊関数へと書き換えることが出来ます。
しかし、再帰的到達不可能順序数と到達不能基数の間には重大な違いがあります。到達不能基数は \( \mathsf{ZFC} \) で存在性を証明することが出来ませんが、再帰的到達不可能順序数は \( \mathsf{ZFC} \) やそれよりも弱い集合論でも存在性を証明することが出来ます。
定理 3.1 |
---|
再帰的到達不可能順序数は存在する。 証明: \( \omega _ 1 \) は許容順序数かつ許容順序数の極限である。ゆえに、 \( \omega _ 1 \) は再帰的到達不可能順序数の一例となる。 |
Notes[]
References[]
- とりマセ Σ^0_2: ビジービーバーQ&A: 計算不可能の鳥瞰図 - 数々の訳語については、これに倣っています。