ラヨ関数
計算不可能関数
急増加関数 \(f_{\mathrm{???}}(n)\)

ラヨ数 (Rayo's number) は、Agustín Rayo と Adam Elga の巨大数決闘で Agustín Rayo が名付けた巨大数である。ラヨ数は、ラヨ自身の言葉によれば、「一階の集合論(一階述語論理)の言葉でグーゴル個以内の記号で表現できるいかなる有限の正の整数よりも大きな最小の正の整数」である。[1][2][3][4]

「グーゴル」を任意の正の整数とすれば、非常に増加速度の大きいラヨ関数 \( \mathrm{Rayo} ( n ) \) を得ることができる。ラヨ関数は計算不可能であり、チューリングマシンによって(そして、チャーチ・チューリングのテーゼによれば、いかなる現代のコンピュータを使っても)、 \( \mathrm{Rayo} ( n ) \)あるいは \( \mathrm{Rayo} ( { 10 } ^ { 100 } ) \) の値を、無限の時間とメモリを使わずに計算することはできない。さらに、神託機械あるいはオーダー n のビージービーバー関数を使っても計算出来ない。

ラヨ関数の強さは、「現代数学の基礎そのもの」に対して対角化をしている、というところから来ている。 \( \mathrm{Rayo} ( n ) \) よりも有意に強い簡単なシステムを構築することはとても難しい。

定義

\([\phi]\) と \([\psi]\) を ゲーデル数化された式 として、\(s\) と \(t\) を変数設定とする。 \(\text{Sat}([\phi], s)\) を次のように定義する。

∀R {
  {
    ∀[ψ], t: R([ψ],t) ↔ ([ψ] = "xi ∈ xj" ∧ t(xi) ∈ t(xj))
                      ∨ ([ψ] = "xi = xj" ∧ t(xi) = t(xj))
                      ∨ ([ψ] = "(¬θ)"    ∧ ¬R([θ], t))
                      ∨ ([ψ] = "(θ∧ξ)" ∧ R([θ], t) ∧ R([ξ], t))
                      ∨ ([ψ] = "∃xi(θ)"  ∧ ∃t′: R([θ], t′))
                      (ここでt′はtのxiを変化させたもの)
  } ⇒ R([ϕ],s)
}

\(n\)個以下の記号を持ち、自由変数がただ1つ\(x_1\)であり、そして次のすべての性質を満たすような式 \(\phi(x_1)\) が存在する時に、自然数 \(m\) を「\(n\)個の記号でラヨ命名可能である」とする。

  1. \(Sat([ϕ(x_1)],s)\) であるように \(x_1:=m\) とする変数設定\(s\) が存在する。
  2. 任意の変数設定\(t\) に対して、 \(Sat([ϕ(x_1)],t)\) なら\(t\) は \(x_1=m\) を含む。

そして\(\text{Rayo}(n)\)は\(n\)個の記号でラヨ命名可能なすべての数より大きい最小の数である。

説明1

変数設定は、 \((3, 2, 6, 1/2, \{4, \pi\}, \text{カナダ}, \omega, 65, \ldots)\) のようなオブジェクトの無限の連続である。は、変数設定に関する文章である。たとえば、「3つ目の変数は2つ目の変数に対して素である」「2番目の変数は3.2以外のすべての実数の集合である」というような文章である。

ラヨは、式を記述するためのマイクロ言語を、このように厳密に定義した。

  1. "ab" a番目のオブジェクトはb番目のオブジェクトの要素である
  2. "a=b" a番目のオブジェクトはb番目のオブジェクトと等しい
  3. "(¬e)" 式eの否定
  4. "(ef)" 式eと式fの論理積(and)
  5. "∃a(e)" 式eが真となるようにa番目のオブジェクトを変えることができる

たとえば、"1∈2"という式を考える。これは「1番目のオブジェクトは2番目のオブジェクトの要素である」ということであるから、(リンゴ, すべての果物の集合, \(\ldots)\) という変数設定をすれば、式の評価は「真」となる。なぜならば、リンゴは果物の1種であるからである。もし、 (チーズ, すべての果物の集合, \(\ldots)\) という変数設定をすれば、チーズは果物ではないため、式の評価は「偽」となる。

さらに複雑な例を示す。 "(¬∃1(1∈2))" これは、「1番目のオブジェクトが2番目のオブジェクトの要素である、という条件を満たすように、1番目のオブジェクトを変えることはできない」ということである。このような条件は、2番目のオブジェクトが空集合の時に成り立つ。たとえば、 \((3, \{\}, \ldots)\) というような変数設定である。この時、1番目のオブジェクトである \(3\) の値をいかように変えても、空集合の要素とすることはできない。

ある変数設定がされたときにある式が真であれば、その変数設定がその式に対して「適合する」と言うこととする。

ここでようやく、主要概念である「ラヨ命名可能」を次のように書くことができる。ただし、式に含まれる記号の数に関する制限は無視する。

ある式\(\phi\)が存在し、以下の条件を全て満たす時、\(m\)は「ラヨ命名可能」である。
  1. 式\(\phi\)の自由変数は1番目の引数だけである。
  2. 式\(\phi\)に適合するようなあらゆる変数設定に対して、1番目の引数が \(m\) である。
  3. そのような変数設定が少なくとも1つは存在する。

まずは、0がラヨ命名可能であることを示す。順序数の体系では、\(0 = \{\}\) と定義される(順序数の定義参照)。1つ目の要素が必ず空集合 \(\{\}\) となるような式 \(\phi\) を考える必要がある。その1つが "(¬∃2(2∈1))" = "変数2が変数1の要素となるような変数2を選ぶことができない" = "変数1の要素を選ぶことができない" = "変数1の要素はない" である。

さて、次は \(1 = \{\{\}\}\) をラヨ命名する方法を見つける必要がある。まずは、上記と同じ方法で "(¬∃3(3∈2))" として変数2を空集合とする。そして、変数1は \(\{\{\}\}\) であり、変数2の \(\{\}\) を要素に持つ集合であるから、 "2∈1" が必要である。変数1が他に要素を持たないことは、 "(¬∃3((3∈1∧(¬3=2))))" = "変数3が変数1の要素であるが、変数2と等しくない、という条件を満たすように変数3を選ぶことができない" = "変数3が変数1の要素であれば、必ず変数2と等しい" = "変数1に要素が存在する場合には、変数2は変数1の唯一の要素である" と表現できる。これら3つの文を "and" で結んで、 "∃2((((¬∃3(3∈2))∧2∈1)∧(¬∃3((3∈1∧(¬3=2))))))" という式を得る。これが、1をラヨ命名する式である。

このパターンを続けることで、自然数を1つずつ定義することができる。数字が大きくなれば、再帰的操作を定義することができるようになり、より大きな数字を少ない文字数でラヨ命名できるようになる。十分に大きな数字に対しては、指数を計算するために使われる記号の数は我々が自然に思いつく方法よりも少ない文字数で可能となるであろう。

なぜラヨ関数が計算不可能なのであろうか?集合論は算術と異なり、無限集合を直接取り扱う。たとえば、 "∃1(∃2(2∈1)∧¬∃2(2∈1∧¬∃3(2∈3∧3∈1)))" という式は通常の集合論で証明可能であり、この式を満たす1は要素2を持ち、2を要素に持つ3を要素に持ち、3を要素に持つ要素を持ち、と無限個の要素を持つことが分かる。手で完全に書き下すことは困難ではあるが、急増加関数や他の階層における順序数を∈のみを用いて定義して、変数に代入することも可能である。このように、集合論で定義される関数は自在に無限集合を操作することができる。一方で計算可能関数はその定義から、有限的な入力を有限回書き換えるような操作しかできず、無限集合を直接操作することは出来ない。ラヨ関数は定義の中に無限集合を直接操作しているため、計算可能ではなさそうであることが想像つくだろう。一方でこの議論では計算不可能性は厳密には従わない。ラヨ関数と同じ出力をする関数が、実際に有限的な手続きだけで定義できないことを示して初めて計算不可能性が証明可能である。そのためにはラヨ関数がいかなる計算可能な関数より早く増大することを証明すれば十分であり、それはラヨ関数がビジービーバー関数より早く増大することから従う。

説明2

ベリーのパラドックスから説明を始める。

xを英単語12個以内で定義できない最小の自然数であるとする。すると、xは "the smallest natural number not definable using at most twelve English words" と、英単語12個で定義できる。このように、xを12文字以内の英単語で定義できたので、xは英単語12個以内で定義できない最小の自然数ではない。これは、矛盾である。

このパラドックスが生じる原因は、「定義可能である」という言葉の曖昧さにあり、もっと根本的には、英語という言語そのものの曖昧さにある。ラヨ関数は、「英語」のかわりに「一階の集合理論」(FOST)と言われる形式体系を使うことによって、このような数学的な欠点を回避している。FOSTはフォン・ノイマン宇宙を領域(domain)とする一階述語論理の体系である。具体的には、FOSTは集合の要素を決定すること、領域上で量化すること、そして論理演算子を適用することができる。実際にどのように動くかという詳細は、上に記されている。

ベリーのパラドックスが生じないように、次のように定義する。

FOSTの表現でn個以内の記号で一意に特定できない最小の自然数

これは、次の Rayo(n) の表現を少し書き換えたものである。

FOSTの表現でn個以内の記号で一意に特定できるいかなる自然数よりも大きな最小の自然数

定義可能性の記述が形式体系に置き換えられているため、パラドックスがなくなっている。FOSTは、他の形式体系と同じように、Tarski's undefinability theoremが成り立ち、真偽判定や、ましてや定義可能性の判定を記述することができないため、英語の中に英語を含めるように、FOSTの中にFOSTを含めることができない。

公理

集合論によって自然数を定義するためには、どの公理系によってその自然数を定義するかを固定する必要がある。ラヨ数数の定義の問題は、ラヨが公理系を明記しなかったことである。数学では伝統的に \(\textrm{ZFC}\) 集合論を使っている場合には公理系の宣言を省略している。そのことから、ラヨ数が \(\textrm{ZFC}\) 集合論によって定義されている、あるいは公理系には関係がないと考える者もいるが、それは誤りである。

少なくとも、\(\textrm{ZFC}\) 集合論はフォンノイマン宇宙の真理述語を形式化できないため、ラヨ数の定義を証明可能性によって解釈しない限りは、\(\textrm{ZFC}\)集合論の中でラヨ数の定義は成立しない。 Even if we interpret the definition in that way, the resulting large number will not be significantly larger than, for example, \(\Sigma(10^{100})\) (where \(\Sigma\) is the busy beaver function) because the provability in a recursively enumerable theory with a restriction of the length is decidable by a Turing machine. To get significantly beyond the Busy Beaver function, we must abandon provability, and talk about truth in a particular model, whose existence is not provable under \(\textrm{ZFC}\) set theory as long as \(\textrm{ZFC}\) set theory is consistent.

On the other hand, FOST is just a formal language, which is irrelevant to axioms by the definition, but it does not mean Rayo's number is irrelevant to axioms. The irrelevance of FOST and axioms or the relation between the Busy Beaver function and the proof-based interpretation of the definition of Rayo's number might be the main reasons of the misunderstanding that Rayo's number is irrelevant to axioms.

As Rayo wrote that he uses second-order set theory in order to formalize the primitive semantics vocabulary in the original description, Rayo's number is defined under certain axioms of second-order set theory, which are not clarified. It is important to clarify axioms in uncomputable googology, because uncomputable large numbers can be compared with each other only when they share axioms used in their definitions. Fortunately, there are many choices of axioms of second-order set theory which enable us to define Rayo's number. As a conclusion, Rayo's number is well-defined for googologists who do not care about clarification of axioms and is ill-defined for googologists who care about clarification of axioms. That is why this article belongs to en:Category:Incomplete.

2020年に、ラヨはラヨ数について以下のような新しい記述を加えた。

: 哲学者はときどき集合論の現実主義的解釈を仮定する。この解釈では、集合論の表現はその言語のそれぞれの文に対して真理値を決定する「標準的な」意味を持ち、それは原理的にその真理値を知り得るかどうかには関わらない。(たとえば、Vann McGee によるこの論文を参照。)巨大数決闘では、アダムと私は(2階)集合論の言語はこの標準的解釈によるものであるということを当然の前提としていたため、最終エントリーであるラヨ数が1つの数に対応することが保証されている。もしそうではなく、その言語が公理系によって解釈されていれば、ラヨ数は無効である。なぜならば、ある言語のすべての(無矛盾な)公理系は、同型ではないモデルを持ち、ラヨ数が異なるモデルに対して同じ数に対応するという保証がないためである。

つまり、ラヨは集合論の式に対する現実世界の「真理」に対応する哲学的な「解釈」を考えていて、それは数学的には形式化できないものであり、特定の公理系を選択することを意図していなかった。これは巨大数論の数学外への展開の1つの方向ではある。一方、最後の文は彼らが形式化できない「真理」を当然の前提としていた理由を主張しているように見えるが、ある数の値がモデルに依存することは「無効」であるかどうかには依存しないため、理由にはなっていない。数学では、値がモデルに依存して変化する well-defined な表記はたくさんある。たとえば、\((\text{CH} \to n=0) \land (\neg \text{CH} \to n=1)\) を満たす自然数 \(n\) などである。巨大数論では、モデルに依存する巨大数はたくさんあり、たとえばビジービーバー関数において \(S\) をmaximum Shift functionとしたときの \(S(1919)\) がそうである。巨大数決闘では、モデルに依存する数を禁止するルールがなく、実際に公理系を固定しないことを認めていた。

歴史

ラヨとエルガの巨大数競争は、Scott Aaronson の記事に基づいている。

2013年の1月に、 Adam Goucher は \(\text{Rayo}(n)\) の増加速度は急増加関数で \(f_{\omega^\text{CK}_\omega}(n)\) に相当すると報告をした[5]。ここで、 \(\omega^\text{CK}_\omega\) は 許容順序数 の数列 \(\omega^\text{CK}_1\), \(\omega^\text{CK}_2\), \(\omega^\text{CK}_3\), ... の極限で、 \(\omega^\text{CK}_1\) は チャーチ・クリーネ順序数 である。そして、彼はクサイ関数を考案し、その増加速度は急増加関数で \(\alpha \mapsto \omega_\alpha^\text{CK}\) が成り立つ最初の順序数であると信じている。

しかしながら、この主張は誤りであることが分かった。誤りの原因は、 Goucher がラヨ数の定義を「n文字の一階算術(ペアノの公理)で一意に表現できる最大の整数」であると勘違いをしていたことであった。一階算術よりも二階算術(Second-order arithmetic)はもっと強く、一階集合理論はさらに強い。一階算術の議論領域は自然数で、一階集合理論の議論領域はフォン・ノイマン宇宙の集合全体であると定義されている。したがって、ラヨ関数はほぼ間違いなくクサイ関数よりも強く、 \(\text{Rayo}(n)\) の急増加関数による増加速度の見積りは、第一定義不能順序数に関係しているのではないのかという推測もあったが、基本列を固定せずに急増加関数と比較することは数学的に意味を持たず、その意味で推測そのものが誤りに基づいている。

計算

巨大数研究 Wiki ユーザーP進大好きbot は、任意の非負整数 n に対して 2↑↑n を FOST の表現で 362+20n 文字で命名可能であり、したがって Rayo(362+20n)>2↑↑n となることを示した[6]

巨大数研究 Wiki ユーザーEmkは、連続体仮説の独立性を用いて 1924 以上のいかなる非負整数 n に対しても Rayo(n) が決定不能、つまり \(\mathsf{ZFC}\) で具体的な値に関して証明することができない、すなわち適当な原始再帰関数などが十分に扱えるようなメタ理論、例えば \(\mathrm{PA}\) などに於いてある標準自然数 \( m\) が存在して \(\mathsf{ZFC}\nvdash\mathrm{Rayo}(n)=m\) かつ \(\mathsf{ZFC}\nvdash\mathrm{Rayo}(n)\neq m\) であることを示し[7]、また Rayo(7901) が BB(10100) より大きいことを示した[8]。ここで BB はビジービーバー関数 を表す。

またGoogology WikiのユーザーであるPlain'N'Simpleは \(n<10\) に対して \(\mathrm{Rayo}(n)=0\) であることを示して[9]、Emkは\(\mathrm{Rayo}(10)=1\) であることを示した[10]

関連項目

出典

特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。