TREE数列
組合せ数学
急増加関数 ≥\(f_{\vartheta(\Omega^{\omega}\omega)}(n)\)

TREE数列とは、グラフ理論に起因するとても成長の早い関数である。数理論理学者の Harvey Friedman によって考案された。[1][2]

定義

次の特徴を持つ根付きk-ラベル付き木 の列 T1, T2 ... があるとする。

  1. それぞれのグラフTiは最大でiの頂点を持つ。
  2. 列の中には、列の前にあるグラフがそれよりも後ろの方にあるグラフに inf保存かつラベル保存埋め込み可能 であるようなペアは1つもない。

WQO理論とクラスカルの木の定理によると、そのような列は無限列にはなりえない[3]。Harvey Friedman はこの問いを拡張した、 与えられたkに対して、列の最大長はなんだろう?

この最大長は、kの関数として TREE[k] とあらわされる。 最初の二つの値は TREE[1]=1、そしてTREE[2]=3である。次の数TREE[3]は有名で、とても大きい。TREE[3] > nX(5) はすべての「十分な量の」Xで証明されている。[4]

TREE[n]は急増加関数で\(f_{\vartheta(\Omega^\omega)}(n)\)よりも早く成長する。これは、巨大数研究者にとっても非常に大きな数で、 \(\vartheta(\Omega^\omega)\) はBEAFでは「線形配列次元の配列」の強さとなる。この数列はヒドラゲームグッドスタイン数列よりも強いが、サブキュービックグラフ数ブーフホルツのヒドラよりも弱い。

Chris Birdバードの配列表記を使って\(\text{TREE}[3] > \lbrace3, 6, 3 [1 [1 \neg 1,2] 2] 2\rbrace\)、とした。[5]

弱いtree関数

tree(n)弱いtree関数 を次のような1-labelled trees の列の最大長と定義する。

  1. 全てのグラフはすべての場所kでk+n以下の頂点を持つ。
  2. 列の中には列の前にあるグラフがそれよりも後ろの方にあるグラフに位相同型的埋め込み可能であるペアは1つもない。

Adam P. Goucher はこの関数についての情報を発見したとGoogology Wikiにかかれていたが、実際にはそれに関する証明は一切なかった。

  1. tree(n)は急増加関数で \(\vartheta(\Omega^\omega)\) の成長レベルを持つ。
  2. TREE[3] > treetreetreetreetree8(7)(7)(7)(7)(7)。

より大きい下限も見つかっているとされている。 \(\text{tree}_2(n)=\text{tree}^n(n)\) かつ \(\text{tree}_3(n)=\text{tree}_2^n(n)\) としたときに、 \(\text{TREE}[3] > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\) が成立する。これは、 \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\) としたときの、treetreetree...tree(n)...(n)(n)(n) (n段重ね)とも表せる。[6]

Googology Wikiに記載されていたTREEやtreeの評価はほぼ全て証明がないため、信憑性については疑問である。

\(\text{tree}(n)\) の値

\(\text{tree}(1) = 2, \text{tree}(2) = 5\) そして \(\text{tree}(3) \geq 2^{18}-4\) となる。 \(\text{tree}(1)\) は次の列が解である:

(())
()

\(\text{tree}(2)\) 少し大きいが, 二つの最長列が存在する。

((()))
(()()())
(()())
(())
()

もしくは:

(()())
(((())))
((()))
(())
()

\(\text{tree}(3)\) の値を決定するのは難しいが、その解の長さを持ったたくさんの最長列が存在する。

\(\mathrm{tree}(n)\)の値は数理論理学者の木原貴行によって以下のように評価された[7]. \begin{eqnarray*} \mathrm{tree}(1.00001n+2)>f_{\textrm{SVO}}(n) \end{eqnarray*} ここで\(\textrm{SVO}\)は小ヴェブレン順序数である。

説明

以下の説明はソースがないため要検証である。

グラフをそのまま書かずに可視化するのは難しいため、もっとコンパクトにグラフを表現する必要がある。(), [], {} と多くの種類のかっこで書かれた言語を考える。かっこたちはペアになっていて、互いにネストを形成できる。例えば、次のようなものがこの言語では「正しい」と言える。

[]
([])
{[()]()}
[(){[[]]}(){(())[]}]

文字列Aがあるとする。対応するかっこのペアをノードと呼ぶことにする。を、元のノードに1階層奥にネストされたノードであると定義する。例えば、Aを {[()()][][()]} であるとすると、{}の子は[]であり、()ではない。

ノードの持つ子が2つ未満ならば、それを削除可能と呼ぶ。例えば、Aを {[()()][][()]} であるとすると、全ての()、 最後の2つの[]は削除可能であるが、最初の[]と{}はそうでない。

もし文字列 A から文字列Bに、削除可能なノードを削除することで変換することが出来るならば、AはBへ縮約可能であるという。BであらわされるグラフがAであらわされるグラフと位相同型的埋め込み可能であることと文字列Aが文字列Bへ縮約可能であることは同値である。

これらすべてを考え、TREE[k]と同じであることが期待されるものを定義できる。次のような文字列列があるとする、

  1. k種類以下のブラケットを使っている
  2. 第1の文字列は最大1個の括弧のペア、2つ目は2個のペア…となっている。
  3. どの文字列も、その文字列から前の文字列に縮約可能でない。

TREE[K]はこのような列の最大長である。

k=1, 文字列列は1つのみ、(). k=2なら、 文字列列は、 (),[[]],[] となる。

弱いtree関数

上記と同様に定義すると:

  1. () 以外に括弧を使ってはならない。
  2. 始めの文字列は最大1 + k個の括弧のペア、2番目は 2 + k 個の括弧のペア…となっている。
  3. どの文字列も後の文字列から carvable ではない。

tree(K)はこのような列の最大長である。

動画

出典

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